Consistent Hashing

SYSTEM DESIGN SERIES  ·  TOPIC 15 OF 23+  ·  part of the 14 → 15 → 16 chain
1. Adding One Node - Two Very Different Outcomes
Same cluster, same new node - watch how many keys actually have to move (looping)
mod N: every key's home depends on N itself - changing N changes almost every answer
mod N: adding one server to relieve load means moving almost all the data first
mod N: that's exactly backwards from what you wanted
Ring: keys and nodes share one hash space - a key belongs to the next node clockwise
Ring: a new node only claims the small arc between it and its neighbor
Ring: everything else on the ring doesn't even notice
2. Why Naive Hashing Breaks on Resize
The formula itself is the problem
  • hash(key) mod N - the answer depends on N, not just the key
  • Change N by one, and nearly every key's remainder changes too
  • You added a server to help - and now you're copying almost everything onto it
  • The formula was never designed to survive N changing
🗂️ It's like renumbering every locker in the building because you added one more locker - instead of just labeling the new one.
3. Mod-N vs the Ring, Side by Side
hash(key) mod N
  • Dead simple to implement
  • Perfectly even, as long as N never changes
  • Resizing moves ~all keys
VS
Consistent Hashing (Ring)
  • A bit more bookkeeping to implement
  • Even-ish out of the box, even better with vnodes
  • Resizing moves ~1/N of the keys
⚖️ You're trading a little upfront complexity for a resize that costs a slice of the data instead of nearly all of it.
4. Virtual Nodes - Fixing Uneven Arcs
One point per node is unlucky more often than you'd think
  • Give each physical node many points scattered around the ring, not just one
  • Arcs even out - no node gets a lucky-huge or unlucky-tiny slice
  • Bonus: when a node fails, its load spreads across many neighbors, not just one
5. What Consistent Hashing Doesn't Fix
It's a resize fix, not a magic wand
  • Adding or removing a node still moves some data - just not almost all of it
  • A single wildly popular key can still overload whichever node owns it (topic 14's hot shard, unsolved)
  • Without virtual nodes, distribution can still be lumpy by chance
  • This fixes resizing pain - it doesn't fix skewed traffic
6. Where This Shows Up in the Wild
Not just a whiteboard trick
DynamoDB / Cassandra
Memcached Client Sharding
(topic 07)
CDN Edge Routing
(topic 08)
Load Balancer Affinity
(topic 06)
One idea reused everywhere something needs to grow without a full reshuffle
Any time you hear "minimal disruption when scaling," there's a good chance a hash ring is doing the work underneath.
7. When It's Worth It
Reach for it when:
✔ The cluster will grow or shrink over its lifetime
✔ Minimizing data movement on resize actually matters
✔ You're building a distributed cache or shard layer
A Little Complexity Now, So Resizing Never Costs Everything Later
Skip it when:
✔ The cluster size is fixed and small
✔ Plain mod-N is simpler and nobody's resizing it
✔ The complexity would outweigh the benefit
💡 So far, every topic has been about storing data reliably. Next: how systems talk without waiting on each other directly - that's Queues, topic 16.