The whole course ▾
System Design · Lesson 13 of 39 · Week 3
Consistent hashing
QuickBite adds a fifth cache machine, and suddenly almost every lookup misses. Today: consistent hashing, and why it moves so little.
Got a doubt? Ask in the comments under the video.Subscribe
QuickBite's cache cluster grows from 4 to 5 nodes.
QuickBite is the food delivery app we grow through the course, from one server to millions of orders.
Four caches become five
Since lesson eight, QuickBite's menus have lived in a cache cluster: one big cache, spread over several machines. Today it needs one more machine, and that should be easy.
Each menu lives on one of four cache nodes. To find it, the app servers hash the menu's key, divide by four, and keep the remainder: hash mod four. Remainder zero means node zero; remainder two, node two. Every app server works out the same answer without asking anyone, and the keys spread evenly across the four. Simple, fast, and it works perfectly. Until Friday.
On Friday, traffic grows, and we add a new node. Now it's hash mod five, and for most keys the answer changes. A menu that lived on node two is now looked for on a node that has never seen it. Just like yesterday's shards, about eighty percent of the keys move. Every one of those lookups misses, and all the misses land on the database at once, at lunchtime. Adding capacity just caused an outage.
The hash ring
The fix is to stop dividing by the number of machines. Instead, put the keys and the machines on the same circle.
Picture every possible hash value laid around a circle, from zero all the way round to the largest, joined at the top like a clock. Hash each cache node's name, and place the node at that point on the circle. Now hash a key, say menu forty-two, and place it on the same circle. To find its home, walk clockwise from the key until you meet the first node. That node owns it.
So the rule has three steps. Hash the nodes onto the ring. Hash the keys onto the same ring. And each key belongs to the first node clockwise from it. Every app server knows the same ring, so every app server finds the same node, without asking anyone. And notice what's missing: we never divide by the number of nodes. In code, the ring is just a sorted list of positions, and finding a key's node is a quick binary search: a few microseconds.
Adding a node
Now replay Friday, on the ring, and watch how little moves.
Add a fifth node. Its name hashes to a spot between node B and node C. Which keys move? Only the ones between node B and the new node. They used to walk on to node C; now they stop earlier. Node C gives up one slice, and every other key stays exactly where it was. So instead of eighty percent of the keys moving, only about a fifth do, and they all come from one neighbour.
Removing a node works the same way: its keys move to the next node clockwise, and nothing else changes. With N nodes, a change moves about one Nth of the keys. That's the whole idea of consistent hashing, and it's why caches and databases can grow without a stampede of misses. With a hundred cache nodes, adding one moves about one percent of the keys. Friday's outage becomes a blip.
Uneven slices
There's a catch. Nodes land wherever their hashes put them, and with only a few of them, the slices come out very uneven.
Four random points on a circle almost never split it into four equal parts. One node can easily own double its fair share, and run hot while another idles. And when a node dies, its whole slice lands on a single neighbour, which may now have three times the load, exactly when things are already going wrong.
The fix is called virtual nodes. Instead of one point per machine, each machine gets many points on the ring, say a hundred, by hashing its name with a number attached. Now each machine owns a hundred small slices, scattered around the circle, and the totals even out. When a machine dies, its slices spread across all the others, a little to each. And bigger machines simply get more points. The price is tiny: the ring holds a few thousand points instead of five, a few kilobytes in every app server.
Where you'll see it
Consistent hashing is everywhere that keys are spread over machines that come and go.
Memcached clients use it to decide which server holds each key. Amazon's Dynamo design and Cassandra use it, with virtual nodes, to decide which machines store each row. And load balancers use it for sticky routing, so the same user or key keeps reaching the same server, even as servers are added and removed.
And one close cousin worth knowing, because QuickBite runs Redis. Redis Cluster splits keys into sixteen thousand three hundred and eighty-four fixed hash slots. Each node owns a set of slots, and adding a node means moving some slots to it. Same goal, a different shape: only the moved slots' keys change home.
In the interview
Consistent hashing comes up whenever you say the words cache cluster, or partition.
Say it with the consequence attached: we spread keys with consistent hashing and virtual nodes, so adding a node moves only about one Nth of the keys, and a node's death spreads its load evenly. The consequence is what shows you understand it. For a database rather than a cache, add that each key is also copied to the next two nodes clockwise. That's how Dynamo-style stores keep their copies, and Sunday's mock interview uses exactly that.
Then expect these. Why not just hash mod N? Because changing N moves almost every key. How do you keep the load even? Virtual nodes. And a node dies: what happens? Its keys move to the next nodes clockwise, which for a cache means a burst of misses, so keep the cache warm or keep a copy of each key on the next node too.
The common mistake is saying consistent hashing as a magic phrase and moving on. Interviewers will ask what moves when a node joins. Answer with the slice, and the number.
Quick check
Ten cache nodes using hash mod N. You add an eleventh. Roughly how many keys move?
Show the answer
About 90%: only 1 key in 11 stays on its node.
Same ten nodes, on a consistent hashing ring. You add an eleventh. Now?
Show the answer
About 1/11 of the keys, roughly 9%, from its neighbours.
Remember: with hash mod N, adding a node moves almost everything. On the ring, it moves one slice, about one Nth. And virtual nodes even out the slices, so no node runs hot and a dead node's keys spread wide. Tomorrow, a harder question: when copies of the same data disagree.
Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.