Consistent Hashing
The Question
What is consistent hashing and why is it used?
What a Strong Answer Covers
- Hash ring
- minimal redistribution
- virtual nodes.
Senior-Level Answer
Consistent hashing is a distributed hashing technique designed to minimize the number of keys that must be remapped when the number of nodes changes. It is foundational to distributed caches (Memcached, Redis Cluster), distributed databases (Cassandra, DynamoDB), and load balancers.
**The problem with naive hashing:**
With N servers, naive modular assignment is `server = hash(key) % N`. Adding or removing a server changes N, which changes the computed slot for almost every key — in expectation, nearly all K keys move. For a distributed cache this means a near-total cache miss storm; for a database it means massive data migration.
**The consistent hashing solution:**
Map both nodes and keys onto a **hash ring** — a logical circle from 0 to 2^32 (or 2^64). Hash each node to a position on the ring. To look up the server for a key, hash the key to a ring position and walk clockwise until you find the first node — that node owns the key.
When a node is added: only the keys between the new node and its predecessor need to move — approximately K/N keys on average. When a node is removed: only the keys it owned move to its successor — again approximately K/N. All other keys are unaffected.
**Virtual nodes (vnodes):**
A single physical node hashed to one ring position creates uneven distribution — different arc lengths mean different load. The standard fix is **virtual nodes**: each physical node is hashed to multiple positions on the ring (e.g., 150 vnodes per physical node). This statistical sampling evens out the load distribution. It also makes rebalancing more granular — adding a physical node gradually takes over vnodes from many others rather than one large arc.
**Consistent hashing in practice:**
- **Cassandra:** Uses vnodes. The ring is divided into token ranges. Each node is responsible for its token range. A new node joins by splitting existing ranges. - **Redis Cluster:** Uses 16,384 hash slots (not a ring, but a similar concept). Slots are redistributed on topology changes. - **Memcached client libraries:** Implement consistent hashing client-side to route requests to the correct server. - **Load balancers:** Route requests from the same source IP to the same backend server (session affinity) by hashing source IP on the ring.
**Limitations:** Consistent hashing assumes uniform key distribution in the hash space. Hot keys (a small set of keys receiving disproportionate traffic) still cause hot spots on specific nodes — vnodes mitigate but don't eliminate this. Additional strategies: key splitting, client-side sharding bypass, or read replicas for hot keys.
The time complexity for lookup is O(log N) using a sorted data structure (binary search on the sorted list of node positions) — not O(N) linear scan.
What Separates a 2/3 from a 3/3
2/3 — Passing but Incomplete
Correctly explains the hash ring concept, the K/N remapping improvement over naive hashing, and why virtual nodes improve load distribution.
3/3 — Strong Answer
Covers the ring mechanism, K/N math, virtual nodes and their purpose, real-world examples (Cassandra/Redis), O(log N) lookup, and knows the hot key limitation.
Common Mistakes
- Explaining consistent hashing without first establishing what problem naive modular hashing has
- Not explaining virtual nodes — single-position nodes create uneven distribution, which defeats the purpose
- Confusing consistent hashing with rendezvous hashing (highest random weight) — different algorithms with similar goals
- Not knowing the lookup time complexity — linear scan is common in naive implementations but O(log N) is correct with a sorted node list
Follow-Up Questions
- How many keys move on average when you add one node to a consistent hash ring with N nodes and K keys? — K/N keys — only the keys in the new node's arc. This is the core advantage over naive hashing where ~K keys move.
- Why do we use virtual nodes and how many are typical? — One position per physical node creates uneven arc lengths = uneven load. 150-200 vnodes per physical node is typical (Cassandra default was 256).
- How does Cassandra's token ring differ from a textbook consistent hash ring? — Cassandra uses vnodes by default. The ring is divided into a configurable number of tokens. New nodes in recent versions use automatic vnode assignment.
- What is rendezvous hashing and how does it compare to consistent hashing? — Rendezvous (HRW) hashing: for each key, compute hash(key, node) for all nodes, pick the highest score. No ring needed. O(N) lookup but simpler and more uniform without vnodes.
Related Questions
Can You Explain This Cold?
Reading the answer is step one. Explaining it unprompted — under interview pressure — is what actually matters. Get AI-graded feedback on your answer with follow-up probes on your weak points.
Get Graded — Free Assessment