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.
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.
Here are a hundred keys, placed both ways, going from 8 servers to 9. Each cell is one key and the number inside is the server it lives on. A lit cell had to move. Add and remove a few servers and compare the two grids.
The left grid is nearly all lit on every change. The right grid lights up roughly one server's worth of keys and leaves the rest alone. The rest of this page is how the right grid works.
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.
A worked example you can do in your head#
Real rings run from 0 to about 4 billion. Shrink it to 0 to 99 so the arithmetic is easy. Think of a clock face with 100 marks instead of 12.
Three cache servers hash to these marks: A at 10, B at 40, C at 75. Five keys hash to the marks below. For each key, start at its mark and walk clockwise until you hit a server.
| Key | Lands on mark | Walk clockwise to | Owner |
|---|---|---|---|
user:42 | 7 | 10 | A |
cart:7 | 33 | 40 | B |
order:19 | 52 | 75 | C |
sess:3 | 64 | 75 | C |
post:88 | 81 | past 99, wrap round to 10 | A |
The last row is the reason it is a ring and not a line. A key past the last server wraps round to the first one.
Now change the cluster. Work out each answer before you reveal it.
That is the whole algorithm. Everything after this is about making it behave well with real numbers.
The same thing, live#
Here is a real ring with four servers and eight keys. Add a node and watch the counter. Click any key to see its walk drawn on the ring.
Two things are worth doing in that widget before you read on. Add a node and note how few
keys move. Then press reset and look at the bars marked "share of the ring". With one
point each, s3 owns 42% of the circle and s2 owns 10%. Same hardware, four times the
work. Now drag the virtual nodes slider to the right and watch the bars level out.
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.
You saw the numbers in the widget. At 1 point per server the shares were 24%, 24%, 10% and 42%. At 200 points per server they are 26%, 22%, 24% and 27%. Not perfect, but every server is within about a tenth of its fair 25%, and that is as good as this method gets.
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.
Replication is the same walk, continued#
One copy of each key is not enough for a database. Lose the server and you lose the data. The ring gives you replication almost for free: do not stop at the first server. Keep walking and store a copy on the next ones too.
The ring below keeps three copies. Click a few keys. The dotted arc is the walk, and the circled points are the servers holding a copy.
Look closely at a walk and you will see it skip some points. If the next point belongs to a server that already has a copy, it is passed over. Otherwise all three "copies" could land on virtual nodes of one physical machine, and one dead machine would lose all three. The rule is the first three different servers clockwise. Dynamo calls this the key's preference list.
This also changes what a failure looks like. When a server dies, every key it held still has two other copies, and the next server along the walk becomes the new third copy. No key is ever unreachable.
What a resize costs, in gigabytes#
Percentages hide the pain. Put sizes on it.
With modulo, only 1 key in 11 stays where it was. For a cache that means your hit rate drops to about 9% the instant the new node joins, and everything else falls through to the database.
Notice that the gap grows with the cluster. At 10 nodes the ring is 10 times better. At 50 nodes it is 50 times better. The bigger your system, the less you can afford modulo.
Where you have already met it#
Consistent hashing came out of MIT in 1997, in a paper by David Karger and others about spreading web cache load. It is now inside a lot of software you have used.
Amazon Dynamo. The 2007 Dynamo paper is where the ring, virtual nodes and preference lists were put together for a database. Most of this page is that paper in plain words.
Cassandra. Every node owns a set of tokens, which are its points on the ring. The
num_tokens setting is the virtual node count. It defaulted to 256 for years and was
lowered to 16 in version 4.0, with a smarter way of choosing where the tokens go.
Memcached clients. Memcached servers do not know about each other. The client library picks the server, and the popular way to do it is "ketama", a ring implementation Last.fm published in 2007 so that adding a cache server would stop wiping out the whole cache.
Load balancers. HAProxy and Nginx can both route by a consistent hash of the URL or the user, so the same request keeps landing on the same backend and finds its cache warm.
- CassandraA ring, with tokens as virtual nodes
- MeMemcachedThe client picks the server, often with ketama
- NGINXHash by URL or user to a backend
- HAHAProxyHash routing, with bounded loads since 2016
- Redis ClusterNot a ring: 16,384 fixed hash slots
It is a common interview slip. Redis Cluster splits the keyspace into 16,384 fixed
slots, and each key goes to slot CRC16(key) % 16384. A table says which node owns
which slots, and a resize means moving whole slots from one node to another. Same goal,
only the needed keys move, but done with a small lookup table instead of a ring. Say
"hash slots" for Redis and "ring" for Cassandra and Dynamo.
When the ring is balanced and a server is still overloaded#
Even with good virtual nodes, a server can end up 20% or 30% over the average for a while, because keys are not all equally busy. In 2016 Google published a small fix called consistent hashing with bounded loads, and Vimeo added it to HAProxy the same year.
The rule is one sentence. Give every server a cap, say 1.25 times the average load. If a key's owner is already at its cap, keep walking clockwise to the next server that has room.
Most requests still land on their usual server, so caches stay warm. No server can ever be more than 25% over the average. And when the busy server calms down, its keys walk back on their own.
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.
Break it#
The dial here is not traffic, it is the cluster changing shape underneath you. Watch which step is survivable and which one is an outage.
Read every step as text
- steady · Healthy. Eight nodes, 150 virtual nodes each, keys spread within a few percent of even. Every client computes placement locally, so there is no lookup service in the request path and nothing to keep alive.
- add a node · Healthy. A ninth node joins and takes roughly one ninth of the keyspace, spread across all eight existing nodes rather than taken from one. Those keys miss once and refill. Database load rises by about a ninth of your read traffic for a few minutes, which is a blip rather than an incident. With modulo it would have been 89% of keys and an outage.
- node dies · Degraded. One node vanishes and its share of keys moves to its clockwise neighbours. One eighth of your traffic now misses and falls to the database at once. Survivable, and the thing to check is whether your database can absorb an eighth of your read traffic arriving with no warning.
- no virtual nodes · Down. With one point per host instead of 150, the ring is lumpy: some nodes own three times what others do, and when a node dies its entire load lands on exactly one neighbour, which then dies too. This is the cascading failure that virtual nodes exist to prevent, and it is why they are not optional.
- hot key · Down. One key gets 40% of the traffic. Consistent hashing has nothing to say about this: the key hashes to one point, that point belongs to one node, and no amount of rebalancing splits a single key. Fix it above the ring, with a local cache or by replicating that one key, and say so rather than reaching for more nodes.
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?
- Adding a ninth server moves about 89% of keys with modulo, and about 11% with a ring.
- 100 to 200 virtual nodes per physical node. Fewer than that and the ring is lumpy and failures cascade.
- A node leaving moves its keys to its clockwise neighbours and nobody else.
- Replication is the first N different servers clockwise. That list is the key's preference list.
- It does nothing for a hot key. One key is one point on the ring, and no rebalancing splits it.
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.