The whole course ▾

System Design · Lesson 13 of 39 · Week 3

Consistent hashing

Updated 22 Oct 2026 · By Akshay, software engineer, India · 6 min read

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 in this lesson

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

Four caches become five
App servers
Cache node
0
Cache node
1
Cache node
2
Cache node
3
hash mod 4
1
New node
4
80% miss
menu 42 isn't here now

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 hash ring
Node
A
Node
B
Node
C
Node
D
Menu
42
clockwise
next node
The rule
1
Hash each node onto the ring
2
Hash each key onto the ring
3
Walk clockwise to the first node

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

Adding a node
IN ONE LINE
Addingorremovinganodemovesone
slice:about1/Nofthekeys,not
almostallofthem.
The hash ring
Node
A
Node
B
Node
C
Node
D
Menu
42
clockwise
next node
Node
E
new
gives up one slice
~ 1/5 of keys
The rule
1
Hash each node onto the ring
2
Hash each key onto the ring
3
Walk clockwise to the first 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

Uneven slices
The catch
4 random points: unequal slices
One node can own double its share
A dead node dumps it all on one neighbour
The fix: virtual nodes
Each machine gets many points
Small slices even out
A dead machine's keys spread wide
Bigger machines get more points

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

Where you'll see it
Used in
->
Memcached clients spreading keys
->
Dynamo and Cassandra placing data
->
Load balancers routing by key
A CLOSE COUSIN
RedisClusteruses16,384
fixedhashslots:nodes
ownslots,andslotsmove
betweennodes.

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

In the interview
SAY THIS IN THE INTERVIEW
Spreadkeyswithconsistent
hashingandvirtualnodes:
addinganodemovesonly
about1/Nofthekeys.
Follow-ups to expect
->
Why not just hash mod N?
->
How do you keep load even?
->
A node dies. What happens?
THE COMMON MISTAKE
Saying"consistent
hashing"andstopping:
saywhatmoveswhen
anodejoinsorleaves.

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

Quick check
?
Ten cache nodes using hash
mod N. You add an eleventh.
Roughly how many keys move?
About 90%: only 1 key in 11
stays on its node.
?
Same ten nodes, on a
consistent hashing ring. You
add an eleventh. Now?
About 1/11 of the keys, roughly
9%, from its neighbours.
Remember
mod N: a new node moves
almost everything
The ring: one slice moves
Virtual nodes even out the
load
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.

Quick check

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.

Practise with flashcardsYour progress stays on this device.
New System Design videos at 6 pm

Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.