You run 4 cache servers and route each key with hash(key) % 4. You add a fifth server. What just happened to your database?
hash(key) % N is coordinator-free and even, but changing N remaps ~80% of keys — a cache stampede on a routine resize. Consistent hashing places servers and keys on a ring so a join or leave moves only ~1/N of keys and leaves the rest warm.
The landmine: hash % N
Modulo routing is tempting: no coordinator, keys spread evenly. But watch what one added server does. Going from N=4 to N=5, hash(key) % 4 and hash(key) % 5 agree only occasionally — for a good hash, roughly 80% of all keys now map to a different server, not the 25% you’d hope.
Those 80% are looked up on servers that don’t have them → 80% instant miss rate → every miss falls through to the database → a cache stampede. A cache meant to shield the database becomes the thing that knocks it over — triggered by a single routine event: a node dying, or an autoscaler adding capacity. hash % N is a landmine wired to N.
The fix: a hash ring
Stop thinking of a flat list you take modulo over. Picture a ring of hash values, 0 to 2³², wrapping back to 0. Hash the servers onto points on the ring (by name/IP). To place a key, hash it to a point on the same ring and walk clockwise to the first server you meet — that server owns the key. Same formula for everyone, no coordinator: every client computes the same owner from the ring alone.
Why this survives a resize
A server owns exactly the arc of the ring immediately before it (counter-clockwise to the previous server). So:
- A server dies → its point vanishes; only the keys in its arc move, walking clockwise to the next server. Every other arc is untouched — the other ~(N−1)/N of keys stay warm.
- A server joins → it drops onto one point and steals only the arc between itself and its previous neighbor. Nobody else is affected.
Either way, ~1/N of keys move, not ~all of them — a small, survivable trickle of misses instead of a database-killing stampede. Note it stays coordinator-free: the owner is a formula over the ring, not a decision by a leader (unlike Raft) — because here you want determinism, not an authority.
Recall checkpoint
1. Why does going 4→5 with `hash % N` move ~80% of keys, not 25%? `hash%4` and `hash%5` rarely agree, so most keys land on a different server — the remap is ~(N−1)/N, not 1/N.
2. What two problems do virtual nodes fix? Uneven arcs (one server overloaded) and a death dumping its whole arc onto a single neighbor.
TL;DR
hash(key) % Nis coordinator-free and even, but changing N remaps ~(N−1)/N of keys → mass misses → cache stampede on a routine node add/remove.- Consistent hashing: hash servers and keys onto a ring; a key is owned by the first server clockwise.
- A join/leave moves only the keys in one arc (~1/N); the rest stay warm. Still a coordinator-free formula.
- Virtual nodes (~100–200 points/server) even out load and spread a failure across many neighbors.
- Used by Cassandra, DynamoDB, Riak, memcached clients.