Consistent Hashing
Consistent hashing is a distributed hashing technique that minimizes data movement when nodes are added or removed. With naive modulo hashing (hash(key) % N), removing one node re-maps almost every key. With consistent hashing, only the keys on the removed node need to move. This is how Cassandra, DynamoDB, and Redis Cluster distribute data.
How it works
The problem:
Suppose you have 5 cache servers and distribute keys using hash(key) % 5. Server 0 gets keys where hash % 5 == 0, server 1 gets hash % 5 == 1, etc. This works fine.
Now server 3 crashes. You now have 4 servers, so you re-hash with hash(key) % 4. Almost every key now maps to a different server. If you had 1M keys cached, ~750,000 of them just moved. Your cache is effectively invalidated.
This is the modulo hashing problem. It makes adding or removing nodes catastrophically expensive.
How consistent hashing works:
- Ring: Imagine a ring with positions 0 to 2^32 - 1 (the hash space).
- Place servers: hash each server's name/ID onto the ring. Server A goes to position hash('A'), server B to hash('B'), etc.
- Place keys: hash each key. The key goes to the next server clockwise from its position on the ring.
- Remove a server: only the keys between the removed server and the previous server move (they go to the next server clockwise). All other keys stay.
- Add a server: only the keys between the new server and the next server clockwise move. All other keys stay.
The key insight: adding or removing a node only affects the keys in that node's arc of the ring. With N nodes, approximately 1/N of the keys move — not all of them.
If you place each server once on the ring, the distribution can be uneven (server A might get 40% of keys, server B only 10%). The fix: place each server multiple times at random positions — 'virtual nodes'. With 150 VNodes per server, the distribution is nearly uniform. This is what Cassandra and DynamoDB do.
Real-world usage:
- Cassandra: each node owns a range of the ring. Data is replicated to the next N-1 nodes clockwise. Adding a node only moves data in the new node's range.
- DynamoDB: uses consistent hashing internally to distribute partition data across nodes.
- Redis Cluster: 16384 hash slots (not a ring, but the same idea: adding/removing a node only moves its slots).
- Discord: uses consistent hashing to route voice channels to servers. When a server is added or removed, only the channels on that server move.
- CDNs: use consistent hashing to route requests to edge caches.
You have 10 cache servers using hash(key) % 10 to distribute keys. You add an 11th server. How many keys need to move?
Pick one answer.
In consistent hashing, why do we use virtual nodes (VNodes)?
Pick one answer.
In consistent hashing, when a server is removed, which keys need to move?
Pick one answer.
Engineering mental model
Mental model. Think of Consistent Hashing as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does Consistent Hashing mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”
Before choosing Consistent Hashing, name the workload, the critical user path, the dominant bottleneck, the failure you are trying to absorb, and the trade-off you are willing to accept. If you cannot name those five things, the design is probably premature.
// Pseudocode
request = receive()
result = consistent_hashing(request)
return result
// Production questions:
// 1. What happens on timeout?
// 2. Can this operation be retried safely?
// 3. What is the bottleneck?Back-of-the-envelope reasoning
Numerical lens: write down traffic, payload size, read/write ratio, peak multiplier and durability target before choosing a component. The numbers should justify the architecture.
Interactive thought experiment: Consistent Hashing
Change the variables below and predict what breaks first in Consistent Hashing. The production lab can later reuse these same inputs.
Change one variable at a time. Predict the failure mode first, then move the slider and see whether your mental model matches the simplified system response.
If you are stuck on Consistent Hashing, start by drawing the request path and marking every network hop, stateful component, queue, cache and failure boundary. Then estimate where the system will saturate.
You increase traffic by 10× in a system using Consistent Hashing. What should you inspect first?
Pick one answer.
Which statement is the safest engineering habit when using Consistent Hashing?
Pick one answer.
You have dashboards for traffic, latency, errors and saturation. You can change the architecture, but every change has operational cost.
Production scenario: your system uses Consistent Hashing, traffic suddenly spikes, and p99 latency doubles. What is your first move?
Interview drill
Answer this without notes: When would you choose Consistent Hashing, and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.
A useful engineering lens for Consistent Hashing: define the problem it solves, the simpler design that fails first, the constraint that forces you to introduce this concept, and the new failure modes the concept creates.
Numerical sanity check
Back-of-the-envelope reasoning beats fake precision. State your traffic, payload, concurrency and growth assumptions explicitly, then calculate enough to know whether the current architecture is orders of magnitude away from the target.
Do not optimize for a memorized definition. Reason from the workload and failure mode.
Imagine the simplest version of a system using Consistent Hashing. What breaks first as traffic grows by 10×, and what would you change before reaching 100×?
Pick one answer.
What you gain, what you pay
- +Minimal data movement on node add/remove (~1/N keys move, not ~all).
- +Scales horizontally — add/remove nodes without cache wipe.
- +Even distribution with virtual nodes.
- +No central coordinator needed (each node can compute the ring).
- −More complex than modulo hashing.
- −Ring maintenance — nodes need to know the ring topology.
- −VNodes add memory overhead for routing tables.
- −Doesn't handle hot keys (a popular key still goes to one server).
How this breaks in production
- Hot keys — even with consistent hashing, a viral key overloads its assigned server. Mitigate with replication + client-side caching.
- Uneven distribution (without VNodes) — one server gets disproportionate load.
- Ring topology changes during network partitions — split-brain.
Don't fall into these traps
- •Using modulo hashing for distributed caches. Use consistent hashing instead.
- •Not using virtual nodes — distribution is uneven without them.
- •Forgetting that consistent hashing doesn't solve hot keys — you still need replication.
Real systems using this
How real systems implement this
- Cassandra — Each node owns VNodes on the ring. Data is replicated to the next N-1 nodes clockwise. Adding a node only moves data in the new node's VNode ranges. Default 256 VNodes per node.
- Discord — Uses consistent hashing to route voice channels to servers. When a server is added or removed, only the channels on that server move — not all channels.
Practice saying it out loud
- Q1What is consistent hashing? Why is it needed?
- Q2How does consistent hashing differ from modulo hashing?
- Q3What are virtual nodes, and why are they important?
- Q4How does Cassandra use consistent hashing for data distribution?
Further reading & references
Core explanations are original NO CAP material. External references are provided for deeper study and standards.
What next?
Mark as understood once the mental model clicks.
Next recommended
Sharding