Consistent Hashing
What it is
A service with several servers needs a rule for which server owns each key, for example which cache server holds a given item. The easy rule, hash(key) % serverCount, breaks badly the moment a server joins or leaves: changing the count changes almost every key's owner at once, and every server has to hand most of its keys to a different one, all at the same time. This sudden, needless reshuffle is sometimes called a stampede. Consistent hashing is the fix. It is used in distributed caches, databases, and load balancers, anywhere a group of servers needs to split up a large set of keys and still cope calmly when a server joins or leaves.
The core idea
Place servers and keys on the same circle of numbers. A key belongs to the server whose point is the first one you reach walking clockwise from the key's own point, wrapping around to the lowest point if the key's point is past every server's point. Give each server several points around the circle, not just one, so its share is made of many small pieces spread around instead of one big piece in one place. These extra points are sometimes called virtual nodes, a name you will see in other material on this topic. Adding a server takes a small number of keys from the points nearest its new ones. Removing a server gives its keys to the points right after them, going clockwise. Nothing else on the circle has to move.
Example: a tiny circle
Picture a circle numbered 0 to 99, wrapping from 99 back to 0. Server A has a point at 15, server B at 50, and server C at 85.
| key's number | walking clockwise lands on |
|---|---|
| 40 | 50, server B |
| 60 | 85, server C |
| 90 | wraps past 99 back to 15, server A |
Now add server D with a point at 70. Only keys between 51 and 70 move, from C to D. Nothing that was already going to A or B changes. Remove server B instead, and only its keys (40 to 50) move, to C. This is the whole point: a change to one server only disturbs the small piece of the circle right around it.
The hash rule
This challenge pins the exact hash every language must use: FNV-1a 64, then one more mixing step sometimes called a finalizer (the kind used in splitmix64). FNV-1a alone spreads similar short strings poorly, so two servers with almost the same name could land close together on the circle. The extra mixing step fixes that. Follow the exact numbers on the challenge page, they let you check your own hash function before you build anything else. Break a tie between two points at the exact same number by the lower server name.
Where you meet this
- Amazon's Dynamo paper: "Dynamo's partitioning scheme relies on consistent hashing", with virtual nodes so each machine owns many small parts of the ring. (Amazon's Dynamo)
- Cassandra maps every node to one or more tokens on a ring. With several tokens per node, a new node takes about the same amount of data from each of the others. (Cassandra Dynamo architecture)
- Envoy offers a "ring hash" load balancer. Adding or removing one host from N hosts affects only about 1 in N requests. (Envoy load balancers)
When to choose it: each key must stick to one owner (cached data, a user's session, stored rows), and owners come and go.
When not to: the set of servers almost never changes, or nothing is lost when a key moves. Then hash(key) % N is simpler and spreads keys evenly. Envoy also offers Maglev, which uses a fixed lookup table, but its docs say it moves about twice as many keys as a ring when hosts are removed.
Common bugs
- Using the server count as a modulus, which remaps almost everything when that count changes.
- Giving each server only one point, so shares end up lumpy instead of even.
- Picking a point by looking through an unordered collection, so the same key can resolve differently between runs.
- Letting the order servers were added in change which point a key resolves to.
- Forgetting to wrap around past the last point back to the first one.
- Moving keys between two servers that were not the one that joined or left. Only the changed server's own points should ever change hands.
Check it yourself
Draw a small circle and place a few server points on it, using small made-up numbers like the example above instead of real hash values. Follow a few keys clockwise, including one that has to wrap past the last point. Add a server and check that only the keys near its new points move. Remove a server and check that only its own keys move, and that they go to the next point clockwise. Build the same circle with the servers added in a different order. Every key should land on the same server either way.
Keep it fast
Keep every point sorted by its number. Finding a key's owner is then a fast search through the sorted points rather than a check of every point one at a time, and it stays fast even with many servers and many points per server.
Learn more
The Dynamo paper describes this design inside a real distributed store. Rendezvous hashing solves the same problem, choosing an owner for each key without putting anything on a circle at all.