Consistent hashing
Assigning keys to machines so adding one machine moves only a few keys.
01The intuition
The problem it solves
A hostel assigns 1,000 students to 4 wardens by roll number: warden = roll number mod 4. Then a fifth warden joins. Under mod 5, student 7 moves from warden 3 to warden 2, student 8 from warden 0 to warden 3, and so on: about 800 of the 1,000 students change warden on the same day. Every file, every record about them has to move. Adding one warden caused a reshuffle of nearly everyone.
Servers holding cached keys or partitioned data are assigned the same way, and hash(key) mod n has the same flaw: change n and almost every key moves, which for a cache means a storm of misses and for a database means moving most of the data. Consistent hashing is an assignment rule where adding or removing one server moves only the keys that server should take or give up, about 1/n of them.
Build it one piece at a time
Step 1: a ring of numbers. Picture the hash space 0 to 232 − 1 bent into a circle. Hash each server's name onto the ring; each lands at a point.
Step 2: place keys and walk clockwise. Hash each key onto the same ring. A key belongs to the first server found walking clockwise from the key's point.
| Ring state | Positions (0–100 for the example) | Owner of key at 37 | Keys that move |
|---|---|---|---|
| servers A, B, C | A at 20, B at 55, C at 90 | B | — |
| add D at 40 | A 20, D 40, B 55, C 90 | D (first clockwise from 37) | only keys in (20, 40], formerly B's, about a quarter of B's keys |
| remove B | A 20, D 40, C 90 | D | only B's keys in (40, 55], which go to C |
Step 3: fix the uneven arcs. With few servers the arcs are uneven: one server may own half the ring. Give each server many virtual nodes (say 150 points on the ring under names like B#1 … B#150). Each server's share becomes the sum of many small arcs and evens out, and a server with twice the capacity simply gets twice the virtual nodes.
Step 4: replicate along the ring. To keep three copies of a key, store it on the owner and the next two distinct servers clockwise. When a server dies, its keys' next-clockwise servers already hold copies; nothing must be computed in a panic.
Step 5: share the ring. Every client must agree on the ring. Either a small coordination service publishes the membership and clients rebuild the ring locally, or servers gossip membership among themselves. The state now: a sorted list of (position, server) that any client can binary-search in microseconds.
Why it works, with the numbers
Each key's owner depends only on the servers near it on the ring, so adding one server affects only the arc it lands in:
keys moved when adding a server ≈ K ÷ (n + 1), versus about K × (1 − 1⁄n) under mod n; for K = 10 million and n = 10, about 900,000 versus 9 million
With v virtual nodes per server, the standard deviation of load falls roughly as 1⁄√v; 100 to 200 virtual nodes bring the imbalance under about 10 percent. Lookup is a binary search over n × v ring points, a few microseconds. The guarantee is minimal movement under membership change plus a deterministic owner for every key. The failure modes are hot keys (consistent hashing balances keys, not traffic; one viral key still lands on one server), clients with different views of the ring during a change (they send some keys to the old owner for a while, so the store must tolerate it), and forgetting virtual nodes and getting a server with three times the average load.
The trade-off you must say out loud
Consistent hashing gives smooth scaling at the cost of a ring every client must know and a small imbalance that virtual nodes reduce but do not remove. Say how clients learn the ring and what happens to requests in flight during a change. The interviewer often asks "what about a hot key?", and the right answer is that the ring does not help; caching the key client-side or splitting it does. Newer schemes (rendezvous hashing, jump hashing, bounded-load variants) solve particular cases, and naming one earns a nod.
Where it shows up in the 100 Google problems
- Design a distributed cache: the classic use; adding a cache node must not empty the cache.
- Design a distributed key-value store: the ring assigns owners and the next-clockwise replicas.
- Design a video distribution CDN: hash the content id to pick which edge server caches it, so each video is cached once per site.
- Design a distributed rate limiter: hash the client key so one limiter node sees all of a client's requests.
- Design a load balancer: sticky routing that survives servers coming and going.