Systems design · 4 of 121 / 3
Consistent hashing
The conceptWhy adding a fifth cache server can empty the other four
The obvious way to pick a server is hash(key) mod N, with N servers. Go from 4 to 5 servers and about 80% of keys get a new answer, so most cached items are suddenly looked up on the wrong server and miss.
Consistent hashing hashes servers and keys onto one circle of numbers, the ring (say 0 to 2³²−1, wrapping round to 0). A key belongs to the first server clockwise from its spot.
Adding a server only takes the keys on the arc just before it; every other key stays where it was.
What it’s forEstimates how many keys must move when one server joins a consistent-hashing ring.
keys moved ≈ K / (N + 1)
- K
- total number of keys stored, e.g. 1,000,000
- N
- number of servers before the new one joins, e.g. 4
- N + 1
- servers afterwards; the newcomer ends up with about one share of keys
What it givesOnly the newcomer's fair share of keys moves, instead of nearly all of them.
- K = 1,000,000 keys, N = 4 servers, add a 5th
- Consistent hashing: 1,000,000 / 5 = 200,000 keys move
- hash mod N going from 4 to 5: 4/5 of keys, 800,000, move