Consistent Hashing
1. The problem
Data is split across many servers. Which server has key X?
A lookup table works but becomes a bottleneck and a single point of failure. Better: let every machine calculate the answer from the key itself. No table, no network call.
2. Why hash(key) % N fails
4 servers 5 servers
───────────────────────── ─────────────────────────
user_a hash 17 % 4 = 1 user_a hash 17 % 5 = 2 ← moved
user_b hash 22 % 4 = 2 user_b hash 22 % 5 = 2
user_c hash 35 % 4 = 3 user_c hash 35 % 5 = 0 ← moved
user_d hash 40 % 4 = 0 user_d hash 40 % 5 = 0- 4 → 5 servers: ~80% of keys move
- 9 → 10 servers: ~90% of keys move
Why: N is baked into the formula. Change N, change nearly every answer.
Consequence: cache hit rate drops to zero, all reads hit the DB at once. You added capacity and caused an outage.
What we want instead:
- Only ~1/N of keys move
- They come evenly from all servers
- They move only onto the new server — never between two old ones
3. The ring
Hash keys and server names onto the same circle. Start at the key, walk clockwise, first server you meet owns it.
Unrolled into a line, it's easier to see what each server owns — the arc behind it:
0 ──────A────────B──────────C───────D──────── MAX ⟲
└────┘└───────┘└─────────┘└──────┘└──────┘
A's B's C's D's A's
arc arc arc arc (wraps)Add a server E — it splits one arc. Nothing else moves:
Remove a server — its arc merges into the next one clockwise. Again, nothing else moves.
N is no longer in the formula → only keys near the change are affected.
4. Virtual nodes (vnodes)
Why: random placement gives uneven arcs, and a dead server crushes its single neighbour.
Fix: place each server at many positions (serverA#1, serverA#2, …). One machine, many scattered slices. Typically 100–200 per machine.
Buys you: better balance, failure spread across many survivors, new servers take a small bite from many.
Costs (say this — it's the senior bit):
- More memory, slower lookup
- Slower repair / streaming
- More vnodes = worse availability — each machine shares data with more peers, so a random pair of failures is likelier to wipe out a full set of copies
Cassandra's default went 256 → 16 for exactly this reason.
5. Replication & failure
Why? A node failing does not change the ring. If I rehash on every failed heartbeat I get a migration storm during a degraded state, thrashing on flapping nodes, and split ownership under a network partition.
Picking the copies
Same walk — just don't stop at one. Take the next N servers clockwise.
Two gotchas:
- Distinct physical machines — vnodes mean consecutive positions can be the same box. "3 copies" on 1 machine = no redundancy.
- Different racks / AZs — 3 machines on one power strip is still one failure.
The mistake everyone makes
Mental model: the ring is a seating chart, not an attendance sheet. Ownership is a deliberate decision. Being briefly unreachable is not a reason to reassign anyone's seat.
| Mechanism | Plain meaning |
|---|---|
| Quorum | With 3 copies, only need 2 to answer |
| Hinted handoff | Neighbour holds the write with a sticky note, replays it when the node returns |
| Read repair | On a read, notice one copy is stale and quietly fix it |
| Anti-entropy | Background sweep comparing copies via a tree of checksums, so you only ship what differs |
When does data actually move?
Only on planned operations: adding capacity, or permanently replacing a dead machine. Copy first, flip ownership last, throttled.
For a cache: skip all of this
No copies, no streaming. A dead node = misses that repopulate from the DB. Only guard the stampede — collapse duplicate in-flight requests for the same key.
6. Membership agreement
The hidden assumption: the lookup is coordination-free only if everyone has the same server list. You didn't remove shared state — you shrank it. But now everyone's correctness depends on it.
client X (knows 5 servers) ── writes key_123 ──► server C
client Y (knows 6 servers) ── reads key_123 ──► server F ✗ empty
no error, no alert — just quietly wrongJob 1 — spread the list
| Method | Pro | Con |
|---|---|---|
| Gossip | No central component, scales | Eventually consistent, failure detection is a guess |
| Coordination service (ZooKeeper/etcd) | One clear truth, ordered changes | Hard dependency, scaling limit |
| Config push | Simplest | Slow to react |
Job 2 — make disagreement safe
You can never make views agree instantly. So make disagreement harmless: version the ring, stamp requests with the version, and have a server refuse and redirect rather than serve a key it doesn't own.
This is exactly Redis Cluster's MOVED / ASK.
During a handover
Who computes the ring?
token-aware client: client ──────────────► owner 1 hop
(but the list must reach every client)
coordinator/proxy: client ──► any server ──► owner 2 hops
(but the ring only lives on your servers — simpler)7. Interview script
1. the need find the owner of a key, no central lookup table
2. naive attempt hash(key) % N — simple, fast, tempting
3. break it 9→10 servers moves ~90% of keys → outage from adding capacity
4. state the goal only 1/N moves, and only onto the new server
5. the ring hash both onto a circle, walk clockwise, own the arc behind you
6. name the flaw uneven arcs + a dead server crushes one neighbour ← unprompted
7. vnodes balance + spread the failure; costs incl. WORSE availability
8. replication next N distinct PHYSICAL machines, across racks
9. failure ≠ rehash migration storm / flapping / split brain → quorum + hints instead
10. membership same list for everyone, gossip vs coordination, epoch + redirectSteps 6, 9 and 10 are what separate a pass from a strong pass.
8. The four lines that earn the most
- "9 → 10 servers remaps ~90% of keys — that's an outage caused by adding capacity."
- "More vnodes improves balance but reduces availability, which is why Cassandra's default dropped from 256 to 16."
- "A node failing must not change the ring — that gives you migration storms, thrashing, and split ownership. Copies handle failure."
- "The lookup is only coordination-free if everyone shares the same membership list, so I version the ring and redirect stale requests instead of serving them."
9. Numbers to remember
| Thing | Value |
|---|---|
| mod-N key movement | ~(1 − 1/N) — nearly everything |
| Ring key movement | ~1/N |
| 100 vnodes/server | ~10% load std dev |
| 1000 vnodes/server | ~3% load std dev |
Cassandra num_tokens | 256 → 16 |
| Typical replication | 3 copies, quorum 2 |
| Redis Cluster | 16,384 fixed slots (alternative to the ring) |
10. When NOT to go deep
Managed stores do this for you. In a product design interview ("design Instagram"), one sentence is correct:
"Cassandra/DynamoDB partition by hash of the key, so adding capacity doesn't reshuffle the dataset."
Go deep only for infrastructure questions: distributed cache, sharded KV store, message broker partitioning, stateful worker pools.