Consistent Hashing: Add and Remove Nodes Without Reshuffling Everything
How consistent hashing maps keys and nodes onto a ring so adding a server moves only ~1/N of keys — plus virtual nodes, replication, and interview trade-offs.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You have 4 cache servers and a simple rule for picking one: server = hash(key) % 4. It works perfectly — until traffic doubles and you add a fifth server. Change the 4 to a 5 and nearly every key now hashes to a different box. Your cache hit rate collapses to almost zero, every miss slams the database, and the database falls over. You didn't lose data; you just moved it all at once.
That single failure mode — a small change to the cluster forces a huge change to the key mapping — is what consistent hashing exists to eliminate. It's the algorithm underneath Amazon DynamoDB, Cassandra, Memcached client libraries, and most large-scale sharded systems. The core promise: adding or removing one node out of N should move only about 1/N of the keys, not all of them.
Why plain modulo hashing breaks
hash(key) % N is fast, uniform, and stateless. Its fatal flaw is that N is baked into the formula. The moment N changes, the output changes for almost every input.
Concretely, with keys spread evenly and N going from 4 to 5, roughly (N-1)/N = 80% of keys land on a different server. For a Memcached tier that means an 80% cold-cache stampede. For a sharded database it means physically copying 80% of your rows between machines while the system is live.
| Cluster change | Keys remapped (modulo) | Keys remapped (consistent) |
|---|---|---|
| 4 → 5 nodes | ~80% | ~20% (1/5) |
| 10 → 11 nodes | ~91% | ~9% (1/11) |
| Node fails (5 → 4) | ~80% | ~20% |
The right column is the whole point. Consistent hashing decouples the key mapping from the exact count of nodes, so scaling up, scaling down, and recovering from a crash all touch a bounded, predictable slice of the keyspace.
How the ring works
Instead of a formula tied to N, picture a fixed circular keyspace — a ring of 2^32 slots (the output range of a 32-bit hash like MurmurHash). Both nodes and keys get hashed onto this same ring.
- Hash each server's identifier (say its IP) to get its position on the ring.
- Hash each key to get its position.
- To find a key's owner, start at the key's position and walk clockwise until you hit the first node. That node owns the key.
Because the ring is fixed at 2^32 slots and never depends on N, adding a node only steals the arc between it and its predecessor. Every other key keeps its owner.
Lookups don't literally walk the ring one slot at a time. You keep node positions in a sorted structure — a TreeMap, sorted array, or skiplist — and binary-search for the first node position greater than the key's hash, wrapping to the first node if you fall off the end. That's O(log N) per lookup.
class HashRing {
constructor() {
this.tokens = []; // sorted ring positions
this.tokenToNode = {}; // position -> node id
}
addNode(node) {
const pos = hash(node); // e.g. murmur(node) % 2**32
this.tokens.push(pos);
this.tokens.sort((a, b) => a - b);
this.tokenToNode[pos] = node;
}
getNode(key) {
const h = hash(key);
// first token clockwise from the key
for (const t of this.tokens) {
if (h <= t) return this.tokenToNode[t];
}
return this.tokenToNode[this.tokens[0]]; // wrap around
}
}The for loop is written for clarity; in production the clockwise search is a binary search over tokens for O(log N).
Walkthrough: 3 nodes on a small ring
Real rings use 2^32 slots, but the mechanics are identical on a tiny ring of 100 slots. Say hash() returns a value in [0, 99]. Three nodes land like this:
| Node | Ring position | Owns the arc (clockwise) |
|---|---|---|
| A | 10 | (75, 99] ∪ [0, 10] |
| B | 40 | (10, 40] |
| C | 75 | (40, 75] |
Each node owns everything from just after its predecessor up to and including its own position. Now route four keys by walking clockwise to the first node at or past the key's hash:
| Key | hash(key) | Walk clockwise → first node | Owner |
|---|---|---|---|
| user:42 | 12 | next token ≥ 12 is 40 | B |
| cart:9 | 8 | next token ≥ 8 is 10 | A |
| order:7 | 55 | next token ≥ 55 is 75 | C |
| photo:3 | 88 | past 75, wrap to 10 | A |
photo:3 at position 88 has no node above it, so it wraps around the top of the ring to node A at 10. That wrap is why A owns two arcs.
Now add node D at position 60. Only keys in the arc (40, 60] — previously owned by C — move to D. order:7 at 55 now belongs to D. Every other key above (user:42, cart:9, photo:3) keeps its owner untouched. One node joined, and exactly one arc changed hands. That's the guarantee modulo hashing can't make.
Virtual nodes: fixing the load-skew problem
The basic ring has a quiet problem. With one token per node, positions are random, so by luck some nodes own a huge arc and others a sliver. In practice this produces 2-3x load skew — one server holding triple the data of another. Worse, when a node dies, its entire arc dumps onto its single clockwise neighbor, instantly overloading it.
Virtual nodes (vnodes) fix both. Each physical node is hashed to many positions on the ring instead of one — Dynamo used ~100-200 tokens per node, Cassandra defaults to 256. More tokens means more, smaller arcs per node, and the arc sizes average out. Load variance shrinks roughly like 1/√V: at 256 vnodes the skew drops from ~2-3x to a few percent.
| Property | 1 token/node | 256 vnodes/node |
|---|---|---|
| Load skew | ~2–3x | ~few % |
| Failure rebalance | all to one neighbor | spread across many peers |
| Weighting hardware | impossible | give a 2x box 2x vnodes |
| Ring size / memory | tiny | N×256 tokens to store |
Two more wins fall out of vnodes. Heterogeneous hardware: give a machine with double the RAM double the vnodes and it owns double the keyspace. Graceful failure: when a node dies, its 256 arcs scatter to 256 different neighbors, so the rebalance load fans out instead of crushing one box.
Replication and hot keys
Consistent hashing also drives replication in Dynamo-style stores. After finding the primary owner by walking clockwise from hash(key), keep walking and pick the next N−1 distinct physical nodes. That ordered set is the key's preference list. To survive a rack or availability-zone outage, the walk skips candidates sharing a failure domain with an already-chosen replica. Reads and writes then use quorum — R + W > N — against that list, with hinted handoff parking writes on a stand-in when a preferred replica is down.
What consistent hashing cannot fix on its own is a hot key. A celebrity user ID hashes to exactly one position and therefore one owner, so evenly spreading keys doesn't help when a single key is the problem. Mitigations layer on top:
- Key splitting / salting — write to
key#0…key#K-1across K shards and fan out on read. - Extra replicas for hot keys — bump the replication factor and serve reads from any replica with read repair.
- Edge / client caching — a CDN or local LRU absorbs reads before they ever reach the ring.
- Bounded-load consistent hashing (Google, 2016) — cap each node at
(1+ε)·averageand overflow to the next node clockwise when it's full.
How this shows up in interviews
Consistent hashing is a near-guaranteed follow-up in any "design a distributed cache/database/key-value store" round. Interviewers rarely ask you to code the ring; they probe whether you understand why it beats modulo and where it stops helping.
The strongest signals you can send:
- Quantify the win. "Modulo remaps ~(N−1)/N of keys on any change; the ring moves ~K/N." Numbers beat hand-waving.
- Volunteer vnodes before being asked and name a real default (Cassandra's 256), plus the reason: load variance falls like 1/√V and failures fan out.
- Know the lookup cost — O(log N) via a sorted token map, not O(N).
- Separate hot shard from hot key. Recognizing that consistent hashing can't fix a single overloaded key — and reaching for salting or bounded-load — is a senior-level tell.
A common trap is claiming consistent hashing gives perfect load balance. It doesn't; it gives incremental rebalancing. If the interviewer wants perfect uniformity for a small, stable cluster, mention rendezvous (HRW) hashing: score every node with hash(key, node) and pick the max. It's O(N) per lookup but perfectly uniform with no vnodes — the better pick for a few dozen fixed caches, where consistent hashing's O(log N) and ring bookkeeping aren't worth it.
Further learning
- What is CONSISTENT HASHING and Where is it used? — Gaurav Sen's whiteboard walk through the ring and its motivation.
- Consistent Hashing: What It Is and How to Implement It — Arpit Bhayani's implementation-focused deep dive with code.
Once the ring clicks, it connects to the rest of the fundamentals: Scaling for how horizontal growth actually happens, SQL vs NoSQL for why Dynamo/Cassandra chose this partitioning, Database Indexing for the sorted structures that make O(log N) lookups possible, and API Gateway for where request routing sits above the data layer. You can also practice this topic on YeetCode with the interactive roadmap.
FAQ
What exactly does consistent hashing solve that modulo hashing doesn't?
Modulo hashing (hash(key) % N) bakes the node count into the formula, so any change to N remaps almost every key — about (N−1)/N of them. Going from 4 to 5 cache servers moves ~80% of keys, causing a cold-cache stampede that can topple the database behind it. Consistent hashing places keys and nodes on a fixed ring, so adding or removing a node only reassigns the keys in one arc — on average K/N of them. That makes scaling out, scaling in, and crash recovery cheap and predictable instead of catastrophic.
How is a key assigned to a node on the ring?
You hash the key with the same function used for nodes (MurmurHash, MD5, etc.) to get a position on the ring, then walk clockwise until you reach the first node position at or beyond the key — that node is the owner. If you pass the largest node position, you wrap around to the first node. In practice the walk is a binary search over a sorted list of token positions (a TreeMap or sorted array), giving O(log N) lookups rather than an O(N) scan.
Why do production systems use virtual nodes?
With a single token per physical node, ring positions are random, so arc sizes vary wildly and produce 2-3x load skew; worse, a node's death dumps its whole arc onto one neighbor. Giving each physical node many tokens — Cassandra defaults to 256 — splits its ownership into many small arcs whose sizes average out, shrinking load variance roughly like 1/√V. Vnodes also let you weight heterogeneous hardware (a bigger box gets more tokens) and spread a failed node's load across many peers instead of one.
Can consistent hashing fix a hot key?
No — and this distinction matters in interviews. A single hot key (a celebrity account) hashes to exactly one position and therefore one owner, so balancing keys across the ring does nothing for it. You need extra techniques: split or salt the key across several shards and fan out on read, add replicas for that key and read from any of them, cache it at the edge or client, or use bounded-load consistent hashing to cap per-node load and overflow to the next node. Consistent hashing solves hot shards, not hot keys.
When would I choose rendezvous hashing over consistent hashing?
Rendezvous (highest-random-weight) hashing scores every node with hash(key, node) and picks the highest, giving perfectly uniform load with no virtual nodes — but each lookup is O(N). Consistent hashing is O(log N) via a sorted ring, though it needs vnodes to balance load and more bookkeeping to maintain the token map. Choose rendezvous for small, stable clusters (a few dozen caches) where simplicity and uniformity win; choose consistent hashing for large or churny clusters (hundreds of storage nodes) where the logarithmic lookup and incremental ring updates scale better.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.