1Understand
The idea
Consistent hashing places keys and servers on a hash ring so when membership changes, only keys in the affected arc move, roughly 1/N of all keys when you add one node to N, unlike hash(key) % N which remaps almost everything. Interviews reach for it for elastic cache clusters, distributed KV, and L7 partition routing, not for SQL range analytics dominated by time scans.
Virtual nodes spread load when you have few physical machines. Replication walks clockwise to distinct hosts for fault tolerance. The skill is pairing the ring model with migration tooling and admitting hot keys are not fixed by hashing alone.
Contrast with directory-based sharding (lookup table) and range partitions (time buckets), consistent hash optimizes key→node stability on resize, not BETWEEN reporting queries.
Intuition
Modulo pain. shard = hash(key) % 10. Resize to 11 → most keys change destination → thundering herd of cache misses or terabytes to move. Interview one-liner: “modulo reshuffles O(keys); ring moves O(keys/N).”
Ring mechanics. Hash keys and nodes to 0…2³²−1 on circle. Owner = first node clockwise from hash(key). Add node → only keys between predecessor and new node migrate.
Virtual nodes (vnodes). Each physical host owns many points (e.g. 100-200) so arc widths stay even with 3-5 machines; without vnodes one server can own 60% of arc.
Join/leave. Add node: copy keys in arcs from neighbors. Remove node: reassign arcs clockwise; use handoff (get from new owner, delete old) to avoid stale reads during lazy migration.
Replication on ring. Primary at owner; replica R1 at next distinct physical node clockwise; R2 next after that, survive one host loss if reads allowed from replica.
Hot keys. Superstar product id still lands on one vnode arc, need local cache, read replicas, or key splitting (product:123:part-{0..7}).
LB consistent hash. Hash client IP or session id at load balancer for cache partition affinity, related but different layer from data ring.
Operational migration. Tools limit bytes/sec moved during node add; track progress per vnode; cancel resize if origin error budget burns. Interview bonus: mention bounded load papers conceptually without deriving math.
Manual override. Emergency cache flush still happens, consistent hash reduces how often you need cluster-wide invalidate, not never.
Client library note. Many caches implement ring logic in the driver, ops still plans vnode count and migration runbooks.
What you will be able to do
- Contrast modulo hashing with consistent hashing on cluster change
- Explain the ring and virtual nodes
- Know when it helps caches vs relational sharding
When this comes up
- Cache cluster resize
- Distributed hash table
- Minimal remapping
- Virtual nodes
2See it
Architecture sketch
Hash ring
Keys and nodes share a ring. Add a node, move only nearby keys (~1/N), not everything.
Walkthrough
Add a node
Why % N remaps the world
1 / 4
Three nodes on the ring. hash(key) maps clockwise to the next node.
Read the walkthrough as text
Worked example, Memcached cluster grows 6 → 8 nodes during holiday traffic.
Workload: product:{id} cache; no multi-key transactions; ~500M keys.
- Baseline: 6 physical nodes, 150 vnodes each; monitor per-node hit rate and arc width.
- Modulo alternative rejected:
% 6 → % 8would remap ~80%+ keys → origin DB meltdown, state why ring chosen. - Add 2 nodes: only keys in new arcs migrate; background transfer with rate limit; clients dual-read during handoff optional.
- Hot key:
product:viral→ single arc hot; mitigate app-side local cache + singleflight to origin. - Node loss: vnode arcs to successor; brief duplication if lazy delete, “read repair” pattern.
- Not for: “Reports by week” SQL, use date-range shards instead.
- Handoff window: clients may read stale vnode during migration, dual-read or brief TTL lowering acceptable.
- Monitoring: per-node hit rate, bytes migrated/sec, pending key count in migration queue.
- Interview close: cite Dynamo/Cassandra use rings; Redis Cluster hash slots, same family of ideas.
What interviewers listen for: ring + clockwise rule; vnode balance; ~1/N migration; hot key caveat; wrong-fit for range analytics.
Napkin math
place nodes + keys on hash ring
key → first node clockwise
add 1 node → remap ≈ 1/N keys (not all)
virtual nodes (e.g. 100-200/vnode) smooth load
replicas: next R distinct nodes on ring
mod N remaps everything. A ring remaps a slice.
3Answer it
How to answer in an interview
When cache cluster resize, DHT, “how do you route keys to servers”:
- Modulo failure on N±1.
- Ring model, hash, walk clockwise.
- Vnodes for balance.
- Join/leave fraction moved + handoff.
- Replication on ring if durability needed.
- Fit, KV/cache vs SQL range scans.
- Hot keys, explicit mitigation.
Phrases: “only ~1/N keys move,” “virtual nodes even the arcs,” “consistent hash is not range partitioning.”
- Numeric anchor: 10 nodes → ~10% keys move on add-one-node resize vs modulo reshuffling nearly all keys.
Answer checklist
Tradeoffs & numbers
- vs modulo: stability on resize; more operational complexity (vnode tuning, migration jobs).
- vs directory shard map: ring is decentralized; directory flexible but SPOF/scale on metadata service.
- Many vnodes: better balance; more metadata per node.
- Weak hash function: cluster imbalance, use stable hashes (Murmur, xxHash slice).
- Range queries: poor unless keys share locality by design.
- When NOT: relational warehouse time partitions; tiny static cache where modulo is acceptable.
- Interview tip: quote ~1/N migration when adding a node to N, converts ring theory to a number.
- Ring math anchor: add 1 node to 10-node ring → ~10% keys move; modulo would move ~100%.
- Elasticity goal: add/remove cache nodes weekly without nightly full cache flush, that is the business justification.
- Interview anchor: ~10% key churn on ring resize vs ~100% under modulo.
Kinds of questions (4)
Same pattern, different interview surfaces. Recognise which variant you are in before you answer.
Cache cluster membership change
Example. Elasticache cluster autoscaling adds two nodes during Prime Day without flushing entire catalog cache. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.
How. Ring join moves only affected key arcs; background key migration with rate cap; contrast modulo reshuffle storm. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.
Virtual nodes for balance
Example. Only four beefy cache servers must each hold ~25% of keys despite unequal physical capacity labels. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.
How. Assign 200 vnodes per host; monitor arc QPS; rebalance vnode count if one host runs hot after hardware change. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.
Replication along the ring
Example. Session cache must survive loss of any single Memcached rack without mass logout. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.
How. Primary vnode owner + R1 on next physical node clockwise; read-your-session from replica on primary timeout. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.
Modulo vs consistent hash
Example. Interviewer asks why Redis cluster docs mention hash slots not `key % N`. Contrast with `hash % N` remapping, mention virtual nodes, and admit hot keys still need app-level mitigation beyond the ring.
How. Explain slot migration moves bounded key ranges; modulo resize invalidates nearly all mappings at once. Ring add/remove moves ~1/N keys; replication walks successors; pair with migration and monitoring of key distribution.
Common mistakes
Failure modes the AI coach watches for when you practise open questions.
Resize cost
Avoid. hash(key) % N. Add one cache host, almost every key misses.
Prefer. Consistent hash ring (often with vnodes). Resize moves ~1/N of keys.
Weak sketch
Bad
Stronger sketch
Good
Modulo on resize
Why it happens. Modulo remaps nearly all keys when N changes, triggering cache stampede and massive data movement operators cannot complete in a maintenance window.
How it fails. “We’ll scale Redis from 8 to 10 and update clients to `hash % 10` overnight.”.
Fix. Consistent hashing ring with controlled vnode migration; expect ~1/N keys moved per added node.
No virtual nodes
Why it happens. Few ring points on small clusters create uneven arc ownership and one server absorbing most traffic.
How it fails. Three cache nodes, three hash points total; monitoring shows node-A at 70% hit QPS.
Fix. Hundreds of virtual nodes per physical host; monitor and rebalance arc distribution.
Wrong tool
Why it happens. Time-range analytics need locality of consecutive keys, not uniform key scatter around a ring.
How it fails. Clickhouse-style weekly reports sharded only via consistent hash on `user_id` with full table scans anyway.
Fix. Range/time partitioning for scans; use consistent hash for cache/KV membership elasticity.
4Practise
Concept check
A short quiz on this lesson before open questions. Optional, and it does not gate practice.
Open questions
- about 8 min
Cluster resize
A distributed cache uses 8 nodes. You need 10. Explain why `hash(key) % 8` → `% 10` is painful. How does consistent hashing on a ring limit how many keys move? Give an order-of-magnitude fraction.
- about 7 min
Virtual nodes
Three physical cache servers sit on a consistent-hash ring but load is skewed: one machine serves 70% of keys with only three ring positions. What are virtual nodes, how many might you assign per host, and what do you watch in metrics?
- about 8 min
Replicas on the ring
Cache entries must survive loss of any single node. On a consistent-hash ring with N physical servers, where do you place the primary copy and one replica for key K?
- about 8 min
Modulo vs ring
An engineer proposes `shard_id = murmur3(user_id) % num_shards` for a Redis cluster that frequently adds shards. In 6-8 sentences, critique modulo for elastic clusters and say when consistent hashing is the better fit vs when range sharding by time is better.
Ready to practise?
Write an answer, get AI coaching, then revise. You are not building a real system.