Consistent hashing
You have eight cache servers and you pick one with hash(key) % 8. It works. It is fast,
it needs no coordination, and every client agrees on the answer without talking to
anything.
Then you add a ninth server, and roughly 89% of your keys now point at a different machine than they did a second ago. Not because they moved. Because the divisor changed and every remainder changed with it. Your cache hit rate goes to almost zero, every miss falls through to the database at once, and the database is the thing that actually goes down.
Before you scroll: with 8 servers and modulo hashing, you add a ninth. What fraction of keys keep the same server, and why is it that number?
Why modulo is so bad at this
A key stays put only if hash % 8 and hash % 9 happen to give the same answer. That is
about one time in nine. Everything else moves.
The failure is not that keys move. Some keys have to move, because the new server needs work to do. The failure is the ratio. Adding one server to eight should move about one ninth of the keys, which is 11%. Modulo moves 89%. It is off by a factor of eight, and it gets worse as the cluster gets bigger.
The same arithmetic decides which shard a row lives on, which node owns a partition, and which worker handles a queue. Anywhere a set of machines splits a keyspace between them, a resize with modulo hashing means moving nearly everything.
The ring
Stop mapping keys to servers. Map both of them to the same space instead.
Take the output of the hash function and treat it as a circle, from zero round to 2^32 and back to zero. Hash each server name and place it on the circle. Hash each key and place it on the circle too. A key belongs to the first server you meet walking clockwise from where the key landed.
Now add a server. It lands somewhere on the circle and takes over only the keys sitting between it and the previous server going anticlockwise. Every other key in the system is untouched, because nothing about their walk changed.
Add a node below and watch the counter. Then drag the virtual nodes slider and watch what it does to the spread.
Two things are worth doing in that widget before you read on. Add a node and note how few keys move. Then drop back to four servers with one virtual node each and look at how lopsided the ownership is.
Why virtual nodes are not optional
A hash function scatters points evenly on average, and “on average” needs a lot of points. With four servers you have four points on a circle, and four random points do not divide a circle into four equal arcs. One server routinely ends up owning 40% of the ring while another owns 10%.
So stop putting each server on the ring once. Put it on 100 or 200 times, as
server1#0, server1#1, and so on, each hashed separately. Now you have 400 points
instead of 4, the arcs even out, and each physical server owns a scattered collection of
small slices rather than one big one.
Virtual nodes buy a second thing that matters more during an outage. When a server with one ring position dies, its entire share lands on exactly one neighbour, which is the machine now most likely to die next. When a server with 200 positions dies, its share is spread across every other server in the cluster, a couple of percent each.
Notice what is missing from Figure 1. There is no directory service, no metadata lookup, no coordinator in the request path. The client computes the answer locally. The only shared state is the list of live members, and that changes rarely enough to gossip around.
What it does not fix
Consistent hashing solves the resize problem. It does not solve the hot key problem, and people conflate the two constantly.
If one key gets 40% of your traffic, consistent hashing sends 40% of your traffic to one node, exactly like modulo did. The ring balances the keyspace, not the load. Balancing load on a skewed workload needs a different tool: replicate the hot key to several nodes, or put a small cache in front of the client so the hot key never reaches the ring.
It also does not give you replication on its own. What it gives you is an ordering, and replication is built on top: store the key on the first N distinct physical servers you meet walking clockwise. Dynamo, Cassandra and Riak all do exactly this, which is why their replication factor is a number you set rather than a topology you draw.
Trade-offs
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Modulo hashing | One line of code, perfectly even distribution, no memory overhead at all. | Resizing moves almost every key, which in a cache means a cold start and in a database means a migration. | The set of nodes is genuinely fixed, or the data is cheap to lose and rebuild. |
| Consistent hashing with virtual nodes | Adding or removing a node moves roughly 1/N of the keys, and the load from a dead node spreads across everyone. | A ring of a few hundred entries per node in memory, and distribution that is even only within about 10%. | The node set changes: caches, sharded stores, anything that autoscales. |
| Rendezvous hashing | Same movement guarantees, better spread, and no ring to build or tune. | Scoring every node per lookup, so it costs O(N) instead of a binary search over the ring. | Node counts in the tens rather than the thousands, which covers most real clusters. |
| A lookup table someone maintains | Total control. You can move one hot shard on purpose, which no hash function will do for you. | A directory service in the request path, and it has to be correct everywhere at once. | Large sharded databases where placement is an operational decision, not an automatic one. |
Interview replay
Checkpoint
1. Moving from 8 servers to 9 with modulo hashing, roughly what fraction of keys keep the same server?
2. Why put each physical server on the ring a few hundred times?
3. Your ring is perfectly balanced but one node is at 100% CPU. What is the most likely cause?
Consistent hashing maps servers and keys into the same hash space, drawn as a ring, and a key belongs to the first server clockwise from it. The reason to use it over hash modulo N is what happens on a resize: modulo moves nearly every key, which cold starts the entire cache and dumps that load on the database, while the ring moves only about one Nth of them. I would give each physical server a couple of hundred virtual nodes, both so the ownership is even and so a dead node's share spreads across the whole cluster instead of doubling one neighbour. It does not solve hot keys, because it balances the keyspace and not the request load, and that needs client side caching or replicating the hot key.
