Consistent hashing, jump hash, Maglev and rendezvous
What it is
A family of algorithms mapping keys to nodes such that adding or removing a node moves as few keys as possible.
The naive alternative shows why they exist:
node = hash(key) % N
N = 4 -> N = 5:
hash(key) % 4 vs hash(key) % 5 agree for roughly 1 key in 5.
*** ~80% of keys move. ***
For a cache, that is a near-total cache miss and an origin
stampede. For a sharded store, it is a full data reshuffle.
Consistent hashing bounds the movement to roughly $K/N$: adding the fifth node to a four-node ring moves about a fifth of the keys, and only from the existing nodes to the new one.
Commonly confused with load balancing generally. Consistent hashing is about stable assignment, not about balance: a plain ring is stable and badly balanced, and virtual nodes are the fix for the balance problem rather than part of the core idea.
Also commonly confused with sharding. Sharding is the decision to partition; consistent hashing is one mechanism for assigning partitions to nodes, and a range-partitioned system with an explicit shard map is a legitimate alternative that many production systems use instead.
The problem it solves
Three distinct requirements, and each algorithm below optimises a different subset:
MINIMAL DISRUPTION Adding or removing a node moves ~K/N keys,
not ~K.
BALANCE Each node gets roughly K/N keys, and the
variance matters as much as the mean.
LOOKUP COST The mapping is computed per request, so it
must be fast and ideally allocation-free.
Plus two that are often forgotten and decide the choice in practice:
DISRUPTION ON FAILURE When a node fails, where do its keys go?
If they all go to one neighbour, that
neighbour receives double load and often
fails too. This is the cascading-failure
mode.
CONSISTENT VIEW Do all clients agree on the mapping? If
client A and client B disagree during a
membership change, they route the same key
to different nodes, which for a cache means
duplicate entries and for a store means
split state.
Mechanics
Ring consistent hashing, with virtual nodes
Hash nodes and keys onto the same circular space (0 to 2^32-1).
A key belongs to the first node clockwise from it.
0
|
n3 --+-- n1 key k hashes here ──┐
| │
n2 ▼ walks clockwise to n1
The plain ring has terrible balance. With $N$ randomly placed nodes, the largest arc is $O(\log N / N)$ rather than $1/N$, so the busiest node can receive several times the mean. Virtual nodes fix it: each physical node is hashed to $V$ positions.
import bisect, hashlib
class HashRing:
def __init__(self, nodes, vnodes=160):
# 100-200 virtual nodes per physical node brings the load
# standard deviation to roughly 5-10% of the mean. Fewer
# than ~50 and the imbalance is visible; more than ~500
# and the ring is large with no further benefit.
self.vnodes = vnodes
self.ring = {}
for node in nodes:
self._add(node)
self.sorted_keys = sorted(self.ring)
def _add(self, node):
for i in range(self.vnodes):
h = self._hash(f"{node}#{i}")
self.ring[h] = node
def get(self, key):
h = self._hash(key)
# Binary search for the first vnode clockwise. O(log(N*V)).
idx = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)
return self.ring[self.sorted_keys[idx]]
@staticmethod
def _hash(s):
return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=4).digest(), "big")
Virtual nodes solve a second, more important problem than balance: failure spreading.
WITHOUT vnodes: node n2 fails -> ALL of its keys go to n3.
n3 now serves double load and frequently
falls over too. Cascading failure.
WITH vnodes: node n2's 160 virtual positions are scattered
around the ring, so its keys are distributed
across ALL remaining nodes, each taking
roughly 1/(N-1) extra.
That is the argument for virtual nodes that matters operationally, and it is more important than the balance argument, because the balance problem is a steady-state inefficiency while the failure problem is an outage.
The costs: memory ($N \times V$ entries, so 100 nodes at 160 vnodes is 16,000 entries) and $O(\log(NV))$ lookup.
Jump consistent hash
// Lamping and Veach, 2014. No storage, no allocation, ~O(log n),
// and the entire algorithm is this function.
int32_t jump_hash(uint64_t key, int32_t num_buckets) {
int64_t b = -1, j = 0;
while (j < num_buckets) {
b = j;
key = key * 2862933555777941757ULL + 1;
j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1));
}
return b;
}
Perfect balance, no memory, and much faster than a ring lookup. The trade is severe and must be stated:
Buckets must be numbered 0 to n-1, and you can only add or
remove buckets at the END of that range.
You cannot remove bucket 3 from a 10-bucket configuration.
You can only go from 10 buckets to 9, which removes bucket 9.
That makes jump hash unusable when nodes fail arbitrarily, which is most distributed systems, and ideal for a fixed set of shards where the identity of a shard is stable and you only scale the count. The distinction to state: jump hash is for sharding a keyspace, not for assigning keys to servers that can die.
Rendezvous hashing (highest random weight)
def rendezvous(key, nodes):
# Hash (key, node) for every node and take the maximum.
# No ring, no virtual nodes, and it generalises to "give me
# the top k nodes" for free by taking the k largest, which is
# exactly what replica placement needs.
return max(nodes, key=lambda n: hash_pair(key, n))
Properties worth knowing:
+ Minimal disruption, provably: removing a node only moves the
keys for which it was the maximum, which is exactly K/N.
+ Excellent balance without virtual nodes, because every node
competes for every key independently.
+ Top-k replica selection falls out for free.
+ Trivially simple to implement and to reason about.
- O(N) per lookup rather than O(log N). At 20 nodes that is
nothing; at 5,000 it is the bottleneck.
Rendezvous is under-used and is often the right answer at small node counts, which is most systems. The O(N) cost is a real objection only above a few hundred nodes, and the simplicity plus the free top-k replica selection is worth a lot below that.
Maglev hashing
Google's, designed for load balancers where connection consistency during backend changes is the requirement.
Build a lookup TABLE of size M (a prime, typically 65,537 or
655,373), populated by having each backend claim entries in a
permutation order derived from its name.
Lookup: table[hash(key) % M]. O(1), one array index.
Disruption on a backend change: slightly more than the K/N
minimum, but bounded and small.
The trade Maglev makes deliberately: it accepts marginally worse-than-minimal disruption in exchange for O(1) lookup and near-perfect balance. For a load balancer processing millions of packets per second, the constant-time lookup is worth more than the last fraction of a percent of key stability, and that reasoning is the interesting part.
The table build is O(M log M)-ish and happens on membership change, not per request, which is the right place for the cost in a load balancer.
Choosing
Are nodes a stable numbered range you only grow or shrink at
the end (shard counts, partitions)?
-> JUMP HASH. Zero memory, perfect balance, fastest.
Do you need per-request O(1) and near-perfect balance, with
frequent backend membership changes (an L4 load balancer)?
-> MAGLEV.
Fewer than ~200 nodes, and do you want replica selection too?
-> RENDEZVOUS. Simplest, provably minimal, top-k for free.
Many nodes, arbitrary failures, and you want the well-trodden
path with mature implementations?
-> RING WITH VIRTUAL NODES (100-200 vnodes).
The problem none of them solve: hot keys
Consistent hashing distributes keys evenly. It does not distribute load evenly, and that distinction is the most common production failure in this area.
A celebrity user's key hashes to node 7.
That key receives 40% of all traffic.
Node 7 is saturated; every other node is idle.
No amount of virtual nodes helps: it is ONE key, and one key
lives on one node by construction.
The fixes, none of which are consistent hashing:
KEY SPLITTING key -> key#0 .. key#9, spread across nodes,
reads fan out to all ten. Works for read-heavy
hot keys; complicates writes.
REPLICATION replicate hot keys to every node and read
locally. Requires knowing which keys are hot.
CLIENT-SIDE CACHE a small local cache in front of the hash,
which absorbs the hot key entirely and is
usually the cheapest fix.
POWER OF TWO
CHOICES for stateless work: hash to two candidates
and pick the less loaded. Dramatically better
tail than a single choice.
Naming that consistent hashing does not solve hot keys is a strong signal, because the question is often asked as though it does.
The consistent-view problem
All clients must agree on the membership, or they route the same key to different nodes.
Client A believes nodes = {n1, n2, n3, n4}
Client B believes nodes = {n1, n2, n3} (has not seen n4 yet)
They route key k to different nodes.
For a cache: duplicate entries, halved effective hit rate, and
a stale entry that nothing invalidates.
For a store: split state, and a read may not find its write.
The mechanisms:
GOSSIP Cassandra, Riak. Eventually consistent
membership; brief disagreement is expected and
the data model tolerates it.
COORDINATION SVC etcd or ZooKeeper holds the authoritative
membership; clients watch it. Stronger, and
it adds a dependency.
CENTRAL CONFIG A control plane pushes the map. Simplest to
reason about, and the push must be atomic
enough that clients do not straddle versions.
For a cache, brief disagreement is a hit-rate problem. For a store, it is a correctness problem, and that difference determines how much machinery the membership needs.
A worked example: resharding a cache fleet
Current: 20 nodes, 400 GB of cached data, 200k requests/sec,
hit rate 94%, origin can serve 25k requests/sec.
Plan: grow to 30 nodes.
WITH modulo hashing:
Keys moved: ~1 - 20/30 (agreement) ≈ 97% of keys.
Hit rate collapses to ~3% instantly.
Origin load: 200k x 0.97 = 194k requests/sec against a
25k capacity.
*** Origin dies. This is a self-inflicted outage. ***
WITH consistent hashing:
Keys moved: 10/30 = 33%.
Hit rate drops from 94% to ~63%.
Origin load: 200k x 0.37 = 74k requests/sec.
*** Still 3x over capacity. ***
The important observation: consistent hashing alone is not sufficient here. It reduced the disruption by a factor of three and the origin still cannot absorb it. The rest of the answer is operational:
1. ADD NODES GRADUALLY. Two at a time rather than ten:
each step moves 2/22 ≈ 9% of keys, so the miss rate rises
from 6% to ~15% and the origin sees 30k rather than 74k.
Five steps, twenty minutes apart.
2. WARM THE NEW NODES before they take traffic. Copy the keys
they will own from the nodes that currently hold them, then
add them to the ring. Disruption approaches zero.
3. REQUEST COALESCING at the cache layer, so a thousand
concurrent misses on the same key produce one origin
request rather than a thousand.
4. stale-while-revalidate, so a miss on an expired-but-present
entry serves the stale value while refreshing behind it.
The lesson to state: consistent hashing bounds the disruption, and bounding it is not the same as surviving it. A rollout plan is part of the design, and this is exactly the cache stampede interaction.
Production evidence
Karger et al., "Consistent Hashing and Random Trees" (STOC 1997) is the original, from the work that became Akamai, and the motivating problem was exactly this: distributing web cache load across a changing set of servers.
Amazon's Dynamo paper (SOSP 2007) documents the ring with virtual nodes in production and is explicit that virtual nodes were introduced to address both load imbalance and the failure-redistribution problem.
Lamping and Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm" (2014) is jump hash, including the proof of perfect balance and the explicit statement of the sequential-buckets limitation.
Thaler and Ravishankar, "Using name-based mappings to increase hit rates" (1998) is rendezvous hashing, predating its rediscovery, and the top-k property is in the original.
Eisenbud et al., "Maglev: A Fast and Reliable Software Network Load Balancer" (NSDI 2016) documents the lookup-table design, the deliberate acceptance of slightly-above-minimal disruption in exchange for O(1) lookup, and the connection-tracking that complements it.
Mitzenmacher, "The Power of Two Choices in Randomized Load Balancing" (2001) is the result behind the hot-key mitigation: picking the less loaded of two random candidates reduces maximum load from $O(\log n / \log\log n)$ to $O(\log\log n)$, which is the dramatic tail improvement.
Cassandra's and Riak's documented use of vnodes, with Cassandra defaulting to 256 tokens per node historically and later moving to a lower default with a smarter allocation algorithm, is evidence that the vnode count is a real tuning parameter rather than a formality.
The debate
The case for ring plus virtual nodes: it is the well-trodden path, implementations are mature, it handles arbitrary node failures, and virtual nodes solve both the balance and the failure-redistribution problems.
The case for rendezvous: provably minimal disruption, better balance without any tuning parameter, top-k replica selection for free, and an implementation that fits in three lines and is obviously correct. The O(N) lookup is the only objection and it is irrelevant below a few hundred nodes.
The case for jump hash: zero memory, perfect balance, fastest lookup. It only applies when buckets are a numbered range you grow and shrink at the end, which is a real but narrow case.
The case for an explicit shard map: skip the algorithm entirely and keep a table of which shard lives where, published by a control plane. Full control over placement, trivial to reason about, and rebalancing is an explicit operation rather than an emergent one. Many production systems do this and it is under-considered.
My position: rendezvous below roughly 200 nodes, ring with 150 virtual nodes above that, jump hash only for fixed numbered shard counts, and an explicit shard map whenever placement needs to satisfy constraints.
Rendezvous is my default at typical node counts because it is provably minimal, needs no tuning parameter, and gives replica selection for free by taking the top k. The O(N) lookup is genuinely a non-issue at 20 or 50 nodes and the simplicity is worth real money in debugging.
The reason I would insist on virtual nodes in any ring implementation is the failure mode rather than the balance: without them, a failed node's entire keyspace lands on one neighbour, which then serves double load and frequently fails too. That cascading failure is the actual risk, and the balance improvement is secondary.
The explicit shard map deserves more consideration than it gets. If placement has constraints, such as data residency, rack diversity or keeping a tenant's shards together, no hashing algorithm can express them, and fighting the algorithm is worse than keeping a table.
And the point I would make unprompted: consistent hashing does not solve hot keys. It distributes keys evenly and says nothing about load, and one key that receives 40 percent of traffic lives on one node no matter how many virtual nodes there are. That needs key splitting, replication of hot keys, or a client-side cache, and it is a different problem that the question frequently conflates with this one.
Follow-up Q&A
"Why not just hash modulo N?" Because changing N moves almost everything. Going from four
to five nodes, hash(key) % 4 and hash(key) % 5 agree for about one key in five, so
roughly 80 percent move. For a cache that is a near-total miss and an origin stampede; for a
store it is a full reshuffle. Consistent hashing bounds it to about K/N, so adding the fifth
node moves a fifth of the keys and only onto the new node.
"What do virtual nodes actually fix?" Two things, and the second matters more. Balance: with randomly placed nodes the largest arc is $O(\log N / N)$ rather than $1/N$, so the busiest node can get several times the mean, and 100 to 200 virtual nodes brings the standard deviation to around 5 to 10 percent. And failure redistribution: without them, a failed node's entire keyspace goes to its single clockwise neighbour, which then serves double load and frequently fails too. With them, the failed node's keys spread across all survivors. The cascading failure is the real argument.
"When would you use jump hash?" When buckets are a numbered range you only grow or shrink at the end, which means sharding a keyspace rather than assigning keys to servers. It has zero memory, perfect balance and the fastest lookup, and it cannot express "remove bucket 3 from ten", only "go from ten buckets to nine". So it is unusable when nodes fail arbitrarily and ideal for a fixed shard count you occasionally rescale.
"What is rendezvous hashing and why is it under-used?" Hash the pair of key and node for every node and take the maximum. It is provably minimal in disruption, because removing a node only moves the keys where it was the maximum, it balances well with no tuning parameter, and taking the top k gives you replica placement for free. The objection is O(N) per lookup rather than O(log N), which is genuinely irrelevant below a few hundred nodes. At typical node counts it is my default, and the simplicity is worth real money.
"What is Maglev optimising for?" O(1) lookup and near-perfect balance, at the cost of slightly worse than minimal disruption. It builds a lookup table of prime size on membership change and a lookup is one array index. For a load balancer handling millions of packets a second, constant-time lookup is worth more than the last fraction of a percent of key stability, and that deliberate trade is the interesting part of the design.
"Does consistent hashing solve hot keys?" No, and this is the thing the question usually conflates. It distributes keys evenly and says nothing about load. One celebrity key taking 40 percent of traffic lives on one node by construction, and no number of virtual nodes changes that because it is a single key. The fixes are elsewhere: split the key into ten suffixed variants and fan out reads, replicate hot keys to every node, put a small client-side cache in front, or for stateless work use power-of-two-choices, which takes the maximum load from $O(\log n/\log\log n)$ to $O(\log\log n)$.
"What happens if clients disagree about the membership?" They route the same key to different nodes. For a cache that means duplicate entries and a halved effective hit rate, plus stale entries nothing invalidates. For a store it is a correctness problem: a read may not find its write. So the membership mechanism matters, and it matters more for a store than a cache: gossip is fine for Cassandra because the data model tolerates brief disagreement, whereas a store needing a consistent view wants etcd or a control plane pushing an atomic map.
"You're growing a cache fleet from 20 to 30 nodes. Walk through it." Consistent hashing moves 10/30, about a third of the keys, so the hit rate goes from 94 to roughly 63 percent and the origin sees 74,000 requests per second against 25,000 of capacity. So consistent hashing bounded the disruption and did not make it survivable, which is the lesson. The rest is operational: add two nodes at a time rather than ten, so each step moves about 9 percent; pre-warm the new nodes by copying the keys they will own before adding them to the ring; and have request coalescing and stale-while-revalidate at the cache layer so the misses that do happen do not multiply.
"When would you skip all of this and keep a shard map?" When placement has constraints that no hash function can express: data residency requiring EU tenants on EU nodes, rack diversity for replicas, or keeping one tenant's shards together for locality. A hashing algorithm decides placement and you cannot argue with it; a table lets you place things deliberately and makes rebalancing an explicit operation rather than an emergent one. Plenty of production systems do this and it is under-considered.
Common misconceptions
"Consistent hashing balances load." It balances keys. One hot key defeats it entirely and no vnode count helps.
"Virtual nodes are for balance." They also, and more importantly, prevent a failed node's entire keyspace landing on one neighbour and cascading.
"Jump hash is a drop-in replacement." It only supports adding and removing buckets at the end of a numbered range, so it cannot handle arbitrary node failure.
"Rendezvous is too slow." O(N) at 20 or 50 nodes is nothing, and it is provably minimal with free top-k replica selection.
"Consistent hashing makes resharding safe." It bounds the disruption. Whether the origin survives the remaining third is a separate calculation and usually needs a gradual rollout.
Interview delivery note
Motivate it with the modulo arithmetic, because it makes the problem concrete in one line:
"With hash(key) % N, going from four nodes to five moves about eighty percent of keys,
because % 4 and % 5 agree for one key in five. For a cache that's a near-total miss and
an origin stampede. Consistent hashing bounds it to K over N."
Give virtual nodes their real justification: "Virtual nodes are usually explained as a balance fix, and the more important reason is failure redistribution. Without them, a failed node's entire keyspace goes to its one clockwise neighbour, which then serves double load and often falls over too. With a hundred and sixty virtual positions scattered around the ring, the failed node's keys spread across every survivor."
Show you know the alternatives and when each applies: "Below a couple of hundred nodes I'd actually reach for rendezvous: hash the key-node pair for every node and take the max. Provably minimal, no tuning parameter, and top-k for free so replica placement falls out. The O(N) lookup is a non-issue at that scale."
Volunteer the limitation, because the question often assumes otherwise: "And I'd say unprompted that none of this solves hot keys. Consistent hashing distributes keys, not load. One celebrity key taking forty percent of traffic lives on one node by construction. That needs key splitting, hot-key replication or a client-side cache, and it's a different problem."
Close with the operational point, which is where the experience shows: "and bounding the disruption isn't the same as surviving it. Growing twenty nodes to thirty moves a third of the keys, which took the origin from twelve thousand requests a second to seventy-four against twenty-five of capacity. The answer is adding two nodes at a time and pre-warming them, not a better hash function."
Further reading
- Karger et al., "Consistent Hashing and Random Trees" (STOC 1997).
- DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007), for virtual nodes in production.
- Lamping and Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm" (2014).
- Eisenbud et al., "Maglev: A Fast and Reliable Software Network Load Balancer" (NSDI 2016).
- Mitzenmacher, "The Power of Two Choices in Randomized Load Balancing" (2001), for the hot key and tail-latency result.