Consistent hashing is a technique for distributing data across a changing set of servers while keeping redistribution minimal. It’s a staple in distributed caches, sharded databases, and peer‑to‑peer storage systems. Below is a practical way to explain it in an interview, from the one‑sentence definition to a concrete example and the typical follow‑up questions you might face.
One‑Sentence Definition
Consistent hashing is a method of assigning keys to a logical ring so that when you add or remove a node, only the keys that fall into the departing or arriving node’s segment need to be moved.
How the Mechanism Works
- Hash the key space – Choose a hash function (e.g., SHA‑256) and map every possible key to a 0‑to‑2³² range.
- Create a ring – Visualize the hash range as a circle; the highest value wraps around to the lowest.
- Place nodes on the ring – Each physical server is hashed multiple times (virtual nodes) and placed at those points on the circle.
- Assign keys – To locate a key, hash the key, then walk clockwise on the ring until you hit the first node. That node owns the key.
- Handle changes – Adding a node inserts new virtual points; only keys that now map to those points move. Removing a node causes its keys to shift to the next clockwise node.
Virtual Nodes (VNodes)
Virtual nodes are replicas of a physical server placed at different positions on the ring. They smooth out load because a single server’s hash may land in a sparse region, leaving some nodes overloaded. By spreading a server’s VNodes evenly, the probability that any one node becomes a hotspot drops dramatically.
Trade‑offs
| Aspect | Benefit | Cost |
|---|---|---|
| Minimal redistribution | Only O(1/N) keys move when a node joins or leaves. | Requires a lookup step (hash → ring → node). |
| Load balancing | VNodes improve uniformity without needing a central coordinator. | More memory for the vnode table; extra hash computations. |
| Simplicity of client logic | Clients can compute the location locally; no need for a master. | |
| Complexity of ring maintenance | Adding/removing nodes requires updating the vnode map on all clients (or a discovery service). | |
| Cold‑start latency | New nodes need to warm up caches for the keys they inherit. | |
| Deterministic placement | Same hash function yields same placement across runs, aiding debugging. | |
| Potential unevenness | If the hash function isn’t well‑distributed or VNode count is low, some nodes may still get more keys. |
Concrete Example: A Distributed Cache
Imagine a web service that uses a memcached cluster to store session data. The cluster has three physical servers: cache‑a, cache‑b, and cache‑c. Each server creates 100 virtual nodes, giving a total of 300 points on the ring.
- Hash a session ID – Suppose the session ID
user‑12345hashes to0x7A3F. The client walks clockwise and lands on the virtual node belonging tocache‑b. The session is stored there. - Add a new server – A fourth server,
cache‑d, joins. Its 100 virtual nodes are inserted into the ring. Only the keys that now map to those new points (roughly 1/4 of the total) migrate from their previous owners tocache‑d. - Node failure – If
cache‑ccrashes, its virtual nodes disappear. The keys that were on those points automatically fall to the next clockwise node, which might becache‑aorcache‑b. No central coordinator is needed; clients recompute the location on the fly.
This pattern lets the service scale out smoothly and survive node churn without a massive data reshuffle.
Typical Interview Questions
| Question | What the interviewer is probing |
|---|---|
| “Can you describe the basic steps of consistent hashing?” | Understanding of the ring concept and key lookup. |
| “Why do we use virtual nodes?” | Awareness of load‑balancing issues and how VNodes mitigate them. |
| “What happens when a node leaves the ring?” | Knowledge of redistribution impact and fault tolerance. |
| “How would you handle hot keys that concentrate on a single node?” | Insight into mitigation strategies (e.g., increase VNode count, use secondary hashing, or apply a load‑aware router). |
| “Compare consistent hashing to modulo‑based sharding.” | Ability to articulate trade‑offs: redistribution cost vs. simplicity. |
| “What are the drawbacks of using consistent hashing in a latency‑critical system?” | Recognizing extra indirection, possible cache misses during rebalancing, and the need for a discovery service. |
When answering, keep the focus on the why as much as the how; interviewers care about design decisions.
60‑Second Spoken Answer (45‑90 seconds)
“Consistent hashing is a way to spread keys across a set of servers while keeping the amount of data that moves when you add or remove a server very small. You hash every key into a numeric space and arrange that space as a circle. Each server is placed on the circle multiple times as virtual nodes. To find a key you hash it, then walk clockwise until you hit the first node – that node owns the key. Because the ring is circular, adding a new server only affects the keys that fall between the new node’s points and the next node clockwise, which is typically a fraction of the total. Virtual nodes smooth out load, so no single server becomes a hotspot. The trade‑offs are a bit more bookkeeping and an extra lookup step, but you gain elasticity and fault tolerance without a central coordinator.”
Tip: Practice this aloud with Call Assistant so the pacing feels natural and you can answer follow‑up questions without losing focus.
How to Practice This
- Write the answer on paper – Sketch the ring, label a few virtual nodes, and walk through a key lookup step by step.
- Record yourself – Use a phone or a voice recorder to deliver the 60‑second version. Listen for filler words and timing; aim for 45‑90 seconds.
- Simulate follow‑ups – Have a friend ask the typical interview questions listed above, or let Call Assistant generate them and keep the conversation on topic while you respond.
FAQ
- What is the main advantage of consistent hashing over simple modulo sharding? Consistent hashing limits the amount of data that needs to be moved when the cluster size changes, whereas modulo sharding can require reshuffling almost all keys.
- Do virtual nodes increase memory usage? Yes, each virtual node adds an entry to the routing table, but the overhead is modest compared to the benefit of smoother load distribution.
- Can consistent hashing handle weighted servers? By assigning more virtual nodes to higher‑capacity servers, you can approximate weighted distribution without changing the core algorithm.
- Is consistent hashing still useful with modern service meshes? Service meshes often provide built‑in load balancing, but consistent hashing remains valuable for data placement decisions that need to be deterministic across independent clients.
Frequently asked questions
What is the main advantage of consistent hashing over simple modulo sharding?
Consistent hashing limits the amount of data that needs to be moved when the cluster size changes, whereas modulo sharding can require reshuffling almost all keys.
Do virtual nodes increase memory usage?
Yes, each virtual node adds an entry to the routing table, but the overhead is modest compared to the benefit of smoother load distribution.
Can consistent hashing handle weighted servers?
By assigning more virtual nodes to higher‑capacity servers, you can approximate weighted distribution without changing the core algorithm.
Is consistent hashing still useful with modern service meshes?
Service meshes often provide built‑in load balancing, but consistent hashing remains valuable for data placement decisions that need to be deterministic across independent clients.
#concept#consistent hashing#distributed systems#interview#scalability