Consistent hashing.
Seats around a circle, so a newcomer bumps one neighbour instead of reshuffling the room.
Spreading keys across servers with key-mod-N is the seating chart that re-seats the whole classroom when one new kid arrives. Change N from 3 to 4 and every remainder changes with it: thirty children pick up their bags and shuffle. For a cache, that shuffle is an avalanche of misses; for a database, a night of copying data that mostly did not need to move.
Consistent hashing throws away the division. Hash servers and keys onto the same circle, and give each key to the first server clockwise from where it lands. Membership stops being a global fact: a server arriving or leaving redraws one boundary on the circle, and every other key stays exactly where it was.
- 1
The divisor is the trap: every key’s home is computed from N, so changing N re-homes nearly all of them at once.
- 2
A server’s position comes from hashing its name — nothing about it depends on how many others exist.
- 3
Each key walks clockwise to the first server it meets; no arithmetic ever mentions the server count.
- 4
The newcomer inherits only the arc just behind it — keys on the rest of the circle never hear the news.
- 5
Departure is the mirror image: the orphaned arc slides to the next server along, and nobody else moves.
- 6
Entering each server many times under different names irons out the luck of where the hashes landed.
Roughly 1/N moves, instead of nearly all
Add a tenth server under modulo and about ninety percent of keys relocate; on the ring, about ten percent do — precisely the share the new node should own. That difference is the entire invention. A cache cluster can grow during a traffic spike without flushing itself in the process, and a storage cluster can lose a machine without kicking off a full reshuffle at the worst possible moment.
Hash luck, and the fix
One position per server is a lottery: the hashes can bunch three servers together and leave the fourth owning half the circle. Virtual nodes fix it by placing each server at a hundred-odd points, so each owns many small arcs that average out fair. There is a bonus: when a server dies, its hundred little arcs are inherited by many different neighbours, so the failure load is shared around rather than dumped on one unlucky machine. Dynamo, Cassandra, and most distributed caches are built on this.
Pairs well with Sharding
The real version Consistent hashing simulator →