Consistent Hashing
How to spread keys across a changing set of servers without reshuffling the entire world every time one joins or dies.
Core Concept
The naive way to shard data is server = hash(key) mod N. It works perfectly until N changes. Go from 4 servers to 5 and almost every key's answer changes — roughly (N-1)/N of your data, about 80%, must move. Your cache empties, your database stampedes, your night is ruined.
Consistent hashing removes N from the equation. Instead of hashing keys into buckets, you hash both keys and servers into the same circular address space — typically 0 to 232−1, wrapped so that the largest value sits next to zero. A key belongs to the first server found by walking clockwise from the key's position.
Now the geometry does the work. A node only ever owns the arc between itself and its counter-clockwise neighbour. Delete a node and only that one arc is inherited by its clockwise successor — every other arc is untouched, because no other key's clockwise walk was affected.
Key Components
The hash ring
A fixed circular key space (0 … 232−1) that never resizes. Because its size is constant, node membership changes don't change any key's position — only who is nearest.
Successor lookup
Node positions held in a sorted structure; routing is a binary search for the smallest position ≥ hash(key), wrapping to the first if none. O(log N), no coordinator required.
Virtual nodes
Each physical server is hashed onto the ring V times (100–256 typical). Averaging many small arcs instead of one large one crushes load variance and lets you weight bigger machines.
Replication walk
For redundancy, keep walking clockwise past the owner to the next R distinct physical nodes. This is how Dynamo/Cassandra derive a preference list from pure geometry.
How It Works
- Place the nodes. For every server, hash a stable identity string (
"srv-A#0"…"srv-A#255") and insert each resulting position into a sorted array or balanced tree. - Place the key. Hash the key with the same function into the same space. The key does not know or care how many servers exist.
- Walk clockwise. Binary search for the first node position ≥ the key's position; if you run off the end, wrap to index 0. That node is the owner.
- Replicate if needed. Continue clockwise, skipping virtual nodes belonging to a physical machine you already picked, until you have R distinct replicas.
- A node leaves. Remove its V positions. Each vanished arc merges into the arc of its clockwise neighbour. Only keys inside those arcs — about K/N — need to move or be re-fetched.
- A node joins. Insert its V positions. It steals a slice from each clockwise neighbour, again ≈ K/N total, spread thinly across many machines rather than dumped on one.
Naive Hash vs Consistent Hashing
| Property | hash mod N | Consistent hashing |
|---|---|---|
| Keys moved when N→N+1 | ≈ K·(N−1)/N | ≈ K/N |
| Lookup cost | O(1) | O(log N) binary search |
| State each client needs | N | N·V ring positions |
| Load balance | Near-perfect | Needs virtual nodes to be even |
| Heterogeneous machines | No mechanism | Weight by V per node |
| Behaviour under churn | Global reshuffle | Local, bounded disruption |
The trade is explicit: you accept a logarithmic lookup and a larger routing table in exchange for bounded disruption. In a system where machines fail weekly, that bound is worth far more than the O(1).
Real-World Applications
- Amazon Dynamo & Apache CassandraPartitioning plus the clockwise preference list for N replicas — consistent hashing is the core placement primitive of the whole family.
- Memcached / Redis client-side shardingThe original motivation (Karger et al., 1997, for web caching): a cache node dying should cost you one node's worth of misses, not a cold cache.
- CDN edge selectionMap content URLs to edge servers so the same object keeps landing on the same cache even as POPs are drained or added.
- Load balancers with sticky sessionsEnvoy's
ring_hashandmaglevpolicies route a session key to a stable backend so connections survive fleet changes. - Kafka-style partition assignment & sharded queuesDistributing partitions or work items over a consumer group that scales up and down without a full rebalance storm.
Where Beginners Get It Wrong
Three traps worth memorising
1. Skipping virtual nodes. With one position per server, random placement gives wildly unequal arcs — a "balanced" scheme where one node quietly takes triple the traffic. V=1 is the most common broken implementation.
2. Hashing the node's IP or index. If the node's ring identity changes when it restarts on a new IP, or shifts because a peer was removed from a list, you have re-introduced the reshuffle you were trying to avoid. Hash a stable ID.
3. Confusing it with a consistency model. "Consistent" here means stable under membership change — it says nothing about CAP-style consistency, replication lag, or quorums. That is the next card's problem.
Checkpoint — answer before you move on
- You have 8 servers and 1,000,000 keys. One server dies. Roughly how many keys must be remapped under
hash(key) mod N, and roughly how many under consistent hashing? Show the reasoning, not just the numbers. Hint: compare K·(N−1)/N against K/N, and say precisely why the ring avoids touching the other arcs. - What specific problem do virtual nodes solve, and what do you pay for using 256 of them per server? Hint: think about variance of arc sizes on one side, and routing-table size plus lookup cost on the other.
- A colleague hashes each node's current IP address onto the ring. The fleet runs on ephemeral instances that get new IPs on restart. Describe the failure mode and the one-line fix. Hint: what happens to a node's ring position — and therefore to its arc — after a routine reboot?