Consistent hashing.
Placing servers around a clock face so adding one only nudges a few neighbours, not everyone.
Suppose you spread data across servers by a simple rule: take the key, divide by the number of servers, use the remainder to pick one. It works — until you add or remove a server. Now the divisor changes, and almost every key maps somewhere new, so nearly all your data has to move at once.
Consistent hashing fixes that. Picture a clock face. You place both the servers and the keys around the ring by hashing them, and each key belongs to the next server clockwise. Add a server and it only steals the slice of keys between it and its neighbour — everyone else stays put.
- 1
With plain key-%-N, the server count is baked in — change it and almost everything moves.
- 2
Consistent hashing seats the servers around a ring, like chairs around a clock face.
- 3
Each key belongs to the next server clockwise from where it lands.
- 4
Add a server and it only steals one arc of keys — everyone else stays put.
- 5
Remove a server and its arc simply passes to the next one along.
- 6
Virtual nodes place each server at many points, so the load spreads evenly.
Why "only a slice moves" matters
In a distributed cache or database, moving data means copying it across the network and, for a cache, suffering misses until it warms up again. With plain modulo, one new node triggers that for nearly everything at once. On the ring, only the keys in the new node's arc — roughly one node's share — have to move. That makes scaling up and down cheap and gradual instead of catastrophic.
Virtual nodes even it out
A single point per server can land unevenly, leaving one node with a huge arc and another with a sliver. The fix is virtual nodes: each physical server is placed at many points around the ring. That smooths the load, and when a server dies its many small arcs are shared out among the others rather than dumped on one unlucky neighbour. This is the trick behind systems like Dynamo and many distributed caches.