// The Design Playbook
Consistent hashing
System Design track · 20 min
- Show with numbers why hash mod N moves almost every key when one server is added.
- Find a key's server on the ring, and work out how many keys move when a server joins or leaves.
- Explain what virtual nodes fix and how replicas are placed on the ring.
It is 3 a.m. and one of your ten cache servers dies. Annoying, but you still have nine.
Except that with the usual routing rule, losing that one server just sent almost every key in the cache to a new address. The hit rate collapses, and the database underneath takes the whole flood of reads while the caches fill up again. One machine failed and the whole fleet shook.
There is a way to route keys so that losing one server costs you that server's share and nothing more.
The obvious rule is: server = hash(key) mod N, where N is the number of servers. It is simple and perfectly balanced, until N changes.
Take two keys. One hashes to 7: 7 mod 10 = 7 and 7 mod 11 = 7, so it stays on server 7. The other hashes to 25: 25 mod 10 = 5 but 25 mod 11 = 3, so it moves. Go from 10 servers to 11 and only about 1 key in 11 lands in the same place; roughly 90% of all keys move.
Every moved key is a cache miss, or a row to copy in a sharded database. And you usually add servers when you are already under pressure, which is exactly when this reshuffle hurts most.
You met the ring briefly in the data-at-scale lesson. Here is why it works.
Picture a ring road around a city, with restaurant branches placed along it. Every home is served by the next branch you reach driving clockwise. When a new branch opens, only the homes between it and the previous branch switch to it. Everyone else keeps their usual branch.
That is consistent hashing. Mod N makes every change in the server list a global event: one server moves, every key reshuffles. The ring makes it a local event: only the stretch next to the changed server is affected.
- Take every number your hash function can output, say from 0 to 2³²−1, and bend that line into a circle.
- Hash each server, by its name or IP address, to get its spot on the circle. Hash each key with the same function to place it on the same circle.
- Each key belongs to the first server you meet walking clockwise from the key's spot.
- To find a key's server quickly: keep the server positions in a sorted list, hash the key, and binary-search for the next position. That takes O(log N) steps, a handful even for thousands of servers.
Add an eleventh server to a ring of ten. It lands at one spot and takes over only the stretch between itself and the server before it, counter-clockwise: about 1/11 of the keys on average. The other ten servers keep every key they had.
Remove a server and its stretch passes to the next server clockwise. Again only about 1/N of the keys move, and they all go to one neighbour.
Compare: about 9% of keys move with the ring, against about 90% with mod N.
A ring with only a few servers is uneven. Random spots can give one server a slice several times bigger than another's. And every server is treated as equally strong, even if one is twice as powerful.
The fix is virtual nodes: place each real server at 100 to 200 spots around the circle (server1#1, server1#2, and so on). With that many small slices, the sizes average out, and each server's share ends up within a few percent of fair.
A bonus: give a stronger machine more virtual nodes and it takes a bigger share of keys. Weighting by capacity comes for free.
Want three copies of every key? Start at the key's spot, walk clockwise, and take the next three different real servers, skipping virtual nodes that belong to a machine you already picked. Two copies on the same machine are not real copies; they die together.
This is how Dynamo-style databases place replicas. And there is a side benefit: when a server dies, its virtual nodes are scattered around the ring, so its load spreads in thin slices across many survivors instead of crushing one neighbour.
Start in mod N mode, add one server and note the share of keys that move. Then switch to ring mode and do the same. Remove a server in each mode too. The gap between the two numbers is the whole lesson.
A common slip is running the ring with no virtual nodes, or very few, because the default config looked fine. With five servers and one spot each, one server can easily own a third of the keys. The ring then moves few keys on change, but the load is badly unbalanced every day. Check the virtual node count, don't assume it.
You run 4 servers with 100 virtual nodes each. One server is removed. Roughly what share of keys must move, and where do they go?
Answer in your head first, then check.
Servers and keys sit on the same circle, and each key walks clockwise to its server. Adding or removing a server moves about 1/N of the keys, not nearly all of them. Virtual nodes add balance, capacity weighting and gentle failure. That is why this idea lives inside Memcached clients, Cassandra, DynamoDB, CDNs and modern load balancers.
Find where your stack already uses consistent hashing: your cache client, your sharded database, your load balancer's routing mode. Open the config and check whether virtual nodes are on and how many each server gets. If the number is tiny or zero, write down how many keys the next added server would move, and bring that number to your next architecture review.
- Show with numbers why hash mod N moves almost every key when one server is added.
- Find a key's server on the ring, and work out how many keys move when a server joins or leaves.
- Explain what virtual nodes fix and how replicas are placed on the ring.
The Design Playbook