Consistent hashing
- Lesson 14 of 40
- 10 min
- Intermediate
- 10 steps
With hash(key) % N, changing N shuffles almost everything. On a ring, each change touches a single arc and the rest of the data stays put.
- Live servers
- 4
- Keys that move
- —
- Largest share
- 30%
- request
- batch
- cache miss
Step 1 of 10
Problem
hash % N breaks when N changes
Last lesson spread keys with server = hash(key) % N. As long as N stays the same, every key has a fixed home and the load is even: 25 % per server with 4.
Going to 5 servers changes the answer for 4 keys out of 5. A key only stays where it was when h % 4 and h % 5 agree, and that happens for 4 values in every 20. 80 % of the data would have to travel.
Step 2 of 10
Technique
Close the hash space into a circle
A 32-bit hash returns numbers between 0 and 2^32 − 1. Glue the end to the start and that range becomes a ring: after the highest value comes 0 again.
Now run each server’s name through the same hash and put it at the point it lands on. They are not evenly spaced: each one sits wherever its hash says.
What changed
- Hash ring
- Each server at position hash(name)
Step 3 of 10
Technique
Every key moves clockwise
Keys go through the hash too and land on the ring. Their owner is the first server you meet going clockwise. k1 lands between D and A, so it belongs to A; k2 lands between B and C, so it belongs to C.
Each server keeps the arc that ends at it. In this example the arcs differ in length and C’s is the longest: 30 % of the ring.
What changed
- Keys k1 and k2 on the ring
- Each key belongs to the next server clockwise
Step 4 of 10
Solution
A new server takes a single arc
E joins the ring between B and C. From then on, keys in the arc from B to E no longer go on to C: they stop at E. That is what happens to k2.
Only those keys change owner, 18 % in this example, and all of them come from C. A, B and D never notice.
What changed
- Server E
- 18 % of the keys move from C to E
- Everything else stays
Step 5 of 10
Technique
When a server fails, one arc moves too
Back to the original four servers, and now C goes down. Its keys keep moving clockwise until they reach D. No other server changes.
With % N, going from 4 to 3 servers would move 3 keys out of 4. Here only C’s 30 % moves.
What changed
- Server C
- C’s keys, 30 %, move to D
Step 6 of 10
Problem
Random positions, uneven arcs
Since every server lands wherever its hash says, the arcs are not the same length. Without C, D inherits its arc and ends up with 54 % of the keys: more than twice what A or B hold.
With few servers, chance alone is enough for one of them to carry far more work than the rest.
What changed
- D holds 54 % of the keys
Step 7 of 10
Solution
Several positions per server
Instead of one position, every server gets several: hash «A#1», «A#2» and so on. Each one is a virtual node. Here every server has two and owns several short arcs instead of one long one.
The shares even out: the largest drops from 54 % to 35 % in this example. And when a server leaves, its arcs are split among several neighbours instead of landing on just one.
What changed
- Two positions per server
- Largest share: 54 % → 35 %
Step 8 of 10
Technique
Copies on the next servers
One copy per key is not enough: if its server goes down, the data is gone. So every key is stored on the first three distinct servers it meets going clockwise: its owner and the next two.
To keep the drawing readable we go back to one position per server. k1 is stored on A (copy 1), B (copy 2) and C (copy 3). If A fails, B and C still have it.
What changed
- Every key on 3 servers
- Survives up to two failures without losing the key
Step 9 of 10
Concept
Case: growing a group of caches
A group of cache servers answers reads before the database. If clients pick a server with hash(key) % N, going from 4 to 5 changes the target of ~80 % of the keys: nearly all of them miss at once and those reads land on the database.
With consistent hashing, the fifth cache only gets its arc: 18 % of the keys in this example. Those miss until E fills up; the rest keep hitting.
What changed
- Fifth cache, E
- Misses after the change: ~80 % → 18 %
Step 10 of 10
Summary
Consistent hashing in short
Servers and keys share one hash ring; each key belongs to the first server clockwise.
Adding or removing a server moves a single arc: about 1/N of the keys.
Virtual nodes even out the shares and spread the load when a server leaves.
Store every key on the next distinct servers along the ring to get replicas.
← → step · R replay · Space pause
You will learn
- See why hash % N moves almost every key (covered)
- Place servers and keys on a hash ring (covered)
- Know which keys move when a server joins or leaves (covered)
- Even out the load with virtual nodes (covered)
- Keep replicas on the next servers along the ring (covered)