Consistent Hashing — Staff Interview Quick Reference
The 60-Second Version
- Hash both keys and nodes onto the same circular space (0 to 2^32 - 1). A key belongs to the first node found clockwise from its hash position.
- Without virtual nodes, distribution is wildly uneven — some nodes absorb roughly 3x the keys of others due to random clustering on the ring.
- Virtual nodes fix this: each physical node maps to 100-200 points on the ring, smoothing the distribution to under 10% variance with 150+ vnodes.
- Adding a node: only ~1/N keys migrate (the new node absorbs a slice from its clockwise neighbor). Everything else stays put.
- Removing a node: its slice transfers to the next clockwise node. Again, ~1/N keys move — not the full reshuffle you get with modular hashing.
- This is the property that matters at scale: incremental membership changes cause incremental data movement.
- You should be able to articulate ring + vnodes + add/remove cleanly in under 60 seconds. Interviewers treat this as a fluency check.
What Staff Engineers Say (That Seniors Don't)
| Concept | Senior Response | Staff Response |
|---|---|---|
| Key distribution | "Hash keys to a ring and walk clockwise" | "Without vnodes, standard deviation across nodes is O(1/sqrt(N)) of total keys — unusable past 20 nodes" |
| Virtual nodes | "Each node gets multiple spots on the ring" | "150 vnodes per physical node keeps variance under 10%; tuning higher trades memory for balance" |
| Node addition | "Only some keys move" | "Exactly 1/N of keys migrate on average, but you need anti-entropy repair for the transition window" |
| When NOT to use it | (Reaches for consistent hashing by default) | "Under 10 nodes with tolerance for brief reshuffles? Modular hashing is simpler to operate and debug" |
| Alternatives | "Rendezvous hashing exists" | "Jump hash gives perfect balance for fixed node sets in O(ln N) time but can't handle arbitrary removal — use it for stable clusters only" |
The Numbers That Matter
- 50 vnodes per node: ~15-20% load variance across nodes
- 150 vnodes per node: <10% variance — the standard production target
- 200+ vnodes per node: diminishing returns; memory cost of the ring metadata grows linearly
- Keys moved on node add/remove: ~1/N of total keys (vs. ~(N-1)/N with modular hashing)
- Ring lookup cost: O(log V) with binary search, where V = total virtual nodes across all physical nodes
Common Interview Traps
- Forgetting virtual nodes entirely and presenting the naive ring — interviewers will push on "what about hot spots?" and you'll have nowhere to go.
- Claiming "no keys move" when a node is added. Keys do move; the win is that only 1/N of them move.
- Ignoring the operational cost: during rebalancing, you need replication and consistency mechanisms to avoid serving stale or missing data.
- Defaulting to consistent hashing for every distribution problem. Interviewers use "how would you distribute keys?" as a probe to see whether you reason about tradeoffs or just pattern-match.
Ring Mechanics
Rendering diagram...
When Node D joins at position 5000: Only keys between 3500-5000 move from Node C to Node D. Everything else stays put.
When Node B leaves: Keys between 1000-3500 transfer to Node C (the next clockwise node). Only ~1/3 of keys move.
Hashing Strategy Comparison
| Strategy | Key Movement on Resize | Balance | Lookup Cost | Best For |
|---|---|---|---|---|
Modular hash (key % N) | ~(N-1)/N keys move | Perfect | O(1) | Fixed-size clusters only |
| Consistent hash (naive) | ~1/N keys move | Poor (3x variance) | O(log V) | Rarely used in practice |
| Consistent hash + vnodes | ~1/N keys move | Good (<10% variance) | O(log V) | Production caches, distributed DBs |
| Jump hash | ~1/N keys move | Perfect (0% variance) | O(ln N) | Stable clusters with only additions |
| Rendezvous hash | ~1/N keys move | Perfect | O(N) per lookup | Small clusters, weighted nodes |
Practice Prompt
Staff-Caliber Answer ShapeExpand
- Quantify the data movement. Adding 4 nodes to 12 means ~4/16 = 25% of keys will migrate to the new nodes. The other 75% stay on their current nodes.
- The migration window is the danger zone. Keys that moved are now cache misses on the new nodes. Under high QPS, those misses stampede the database.
- Warm the new nodes before adding them to the ring. Copy the key ranges that will migrate to the new nodes while they're still being served by old nodes. Once the new nodes have warm caches, add them to the ring. Miss rate during transition: near zero.
- Stagger the addition. Don't add all 4 nodes simultaneously. Add one at a time with a 5-minute gap. Each addition moves ~1/13, ~1/14, ~1/15, ~1/16 of keys — manageable chunks.
- Singleflight during transition. Enable request coalescing on the new nodes so that concurrent cache misses for the same key result in only one database query.
The Staff move: Treat cache node additions as a deployment, not a config change. Warm → add → monitor → repeat.
Additional Traps
- Assuming consistent hashing is always the right answer. For a 3-node cluster that rarely changes, modular hashing is simpler and has perfect balance. Consistent hashing's benefit is proportional to the frequency of membership changes.
- Ignoring replication in the ring. Production systems replicate keys to K clockwise neighbors (typically K=3). Node removal means the replica already has the data — no cold start.
- Forgetting that vnodes have memory cost. 150 vnodes × 1,000 nodes = 150K entries in the ring. This is fine in memory but needs to be gossiped across the cluster for membership changes.