Consistent Hashing

Back in Distributed Caching, you built the ring. You bent the whole range of hash values into a circle, dropped each node onto it, and gave every key one rule: walk clockwise, and the first node you meet is home. It solved the hash % N disaster in one move — add a node and it claims only its own arc, roughly a fair 1/N of the keys, while every other key's walk is untouched. No more fleet-wide cache-miss storm every time you scale.

But that lesson ended on a deliberate cliffhanger, and it's worth quoting: one point per node makes uneven slices — bad luck can hand one node a triple share, and a hot slice makes a hot node. You drew each node once on the circle, and the arc lengths came out however the hash happened to scatter them. Some nodes got a wide swath of the ring and the traffic that comes with it; others got a sliver. Your load balancer isn't balancing — it's rolling dice.

That's where this lesson lives. Consistent hashing, as invented by David Karger and colleagues at MIT in 1997 — in a paper literally titled "Consistent Hashing… for Relieving Hot Spots", the math that later ran Akamai — is not just the ring. It's the ring plus the machinery that makes it actually balanced, and that machinery is what turns a clever idea into something Amazon's Dynamo, Cassandra, and DynamoDB run in production. This is that machinery.

In this lesson: why one point per node is lumpy and by how much (measured), the almost embarrassingly simple fix, the law that says exactly how much of it you need, the second thing it buys you that nobody mentions, how the real ring is tuned in production, and the one problem it still can't touch.

Scope: the ring intuition and the hash % N disaster are Distributed Caching's — we build on them, not repeat them. Choosing a Shard Key picked what to hash on; this lesson is how to map that key to a node. And what to do when a single key is red-hot — the one thing a balanced ring can't fix — is Resharding & Hot Shards.

Put a number on the cliffhanger. Take a real ring — ten nodes, one point each, a hundred thousand keys hashed with MD5 — and measure who owns what. The result isn't close to even: the busiest node carried 3.68× its fair share, while another owned barely a twentieth of it. The standard deviation of load across nodes was 104% of the mean — the spread is as large as the average itself.

Why so bad? Because with one point per node, each node's arc is just the random gap between its hash position and the next node's. Drop ten points at random on a circle and the gaps between them are wildly uneven — that's not a bug in the hash, it's what randomness looks like. The theory says the same thing: with one point per node, the most-loaded node is expected to carry O(log N) times the average. On a real cluster that's not an abstraction — it's the one box that pages you at 3am because it's doing three times the work of its neighbours, and there's nothing wrong with it except where its dot landed.

So the ring solved remapping (adding a node barely disturbs anything) but left balance to luck. You need a way to make each node's territory average out instead of depending on a single roll.

Here's the whole idea: instead of hashing each node onto the ring once, hash it many times — hash(node#0), hash(node#1), hash(node#2), and so on — so one physical node occupies dozens or hundreds of positions scattered all around the circle. Each of those positions is a virtual node (also called a token or a replica). They're not extra servers — zero new hardware — just extra dots for the same machine.

Watch what it does to the luck. A node no longer owns one random arc; it owns many small random arcs from all over the ring. And the sum of many small random pieces is far steadier than any one of them — the same reason a hundred coin flips lands near 50/50 while four flips can easily go 3-1. The territory averages out.

How much do you need? There's a clean law for it. To hold the peak-to-average load ratio within a small ε of perfect, you need about V = ln(N) / ε² virtual nodes per physical node. Turn that around and the imbalance shrinks like 1/√V — quadruple the virtual nodes and you roughly halve the spread. In the same measured run, the standard deviation of load fell from 104% at one virtual node to 28% at four, 11% at sixty-four, and 5% at a hundred and twenty-eight — and then it stopped improving. Past a couple hundred vnodes you're paying for nothing.

This is the single most useful thing the ring interactive teaches, so go feel it: drag the virtual-node count from one upward and watch the load bars — wildly uneven at first, one tall and one nearly empty — physically flatten toward the same height. That collapsing spread is the 1/√V law, and it's the difference between a ring that balances and a ring that gambles.

Virtual nodes fix balance. They also fix something people rarely connect to them: what happens when a node dies.

With one point per node, a death is brutal in a specific way. The dead node owned one contiguous arc, and every key in it walks clockwise to the very next node — a single survivor. That one neighbour inherits the dead node's entire load on top of its own, so it's now carrying roughly double, which makes it more likely to fall over, which dumps its keys on the next node… the cascade that turns one failure into an outage. We measured it: kill a node on the one-point ring and 100% of its keys landed on a single clockwise neighbour.

Now kill a node on a ring with 64 virtual nodes each. The dead node's territory was 64 little arcs scattered all over the circle, and each one's clockwise neighbour is a different survivor. So its load doesn't fall on one machine — it scatters across many. Measured: the same death spread over nine survivors, the busiest inheriting only 18% of the orphaned keys. No one node is crushed; the fleet absorbs the loss and keeps its balance. The exact same trick that flattens the load also flattens the blast radius of a failure — which is why every production ring uses it.

This is a real consistent-hash ring — real hashing, real key placement, computed live. Start where C1 left you: one virtual node each, and a ring sliced into lumpy wedges with one node visibly hot. Now drag the virtual-node slider up and watch the arcs shatter into a fine, even confetti of colour while the load bars level out — that's the 1/√V law happening in your hands. Add a node and read how few keys move (a whisper, versus the 90% storm hash % N would cause). Then the real test: kill a node with one virtual node each and watch a single neighbour inherit everything; raise the vnodes and kill again, and watch the load scatter gracefully across the survivors.

The widget uses a fast browser hash; here's the real thing in ~20 lines of Python with MD5, so you can reproduce the exact numbers the figures cite. No dependencies.

import hashlib, bisect
RING = 1 << 32
h = lambda s: int(hashlib.md5(s.encode()).hexdigest(), 16) % RING

def build(nodes, V):
    r = sorted((h(f'{n}#{i}'), n) for n in nodes for i in range(V))
    return r
def owner(ring, kh):
    pts = [p for p, _ in ring]
    return ring[bisect.bisect(pts, kh) % len(ring)][1]

nodes = [f'node-{i}' for i in range(10)]
keys  = [h(f'key-{i}') for i in range(100_000)]
mean  = len(keys) / len(nodes)

for V in (1, 4, 16, 64, 128):
    ring = build(nodes, V)
    load = {n: 0 for n in nodes}
    for kh in keys: load[owner(ring, kh)] += 1
    peak = max(load.values()) / mean
    print(f'V={V:>3}:  peak {peak:.2f}x')

Predict before you run it: the busiest node at V=1 — closer to 1.5× or closer to 4×? Then the output:

V=  1:  peak 3.68x
V=  4:  peak 1.43x
V= 64:  peak 1.12x
V=128:  peak 1.08x

There's the law you dragged in the widget, in your own terminal: one point per node hands the busiest box 3.68× its share; at 128 it's 1.08×, and the improvement has flattened. To watch a node die gracefully, kill node-0 and see who inherits its keys — one survivor at V=1, many at V=64:

def inheritors(V):
    before, after = build(nodes, V), build([n for n in nodes if n != 'node-0'], V)
    who = {}
    for kh in keys:
        if owner(before, kh) == 'node-0':
            who[owner(after, kh)] = who.get(owner(after, kh), 0) + 1
    return len(who), max(who.values()) / sum(who.values())
# V=1  -> (1, 1.00)   one neighbour takes 100%
# V=64 -> (9, 0.18)   scattered across 9, busiest 18%

The production ring is exactly what you just drove, with the vnode count picked deliberately. Some reference points worth carrying:

• Cassandra (whose architecture doc is literally named Dynamo, after the Amazon paper that productionized this) defaults to 16 virtual nodes per node — num_tokens: 16. The number is interesting: it used to be 256, and they turned it down. A smarter token-allocation algorithm meant 16 was the smallest count that still balanced well, and fewer tokens means less ring metadata and far less data streaming to move when a node joins or leaves. The lesson of the 1/√V curve, in a config default: past the knee, more vnodes is cost without benefit.
• ketama — memcached's classic client-side ring, built at Last.fm in 2007 and still the name in configs — uses about 160 points per node. Caches can afford more vnodes than databases because there's no heavy data to restream, just keys to re-route.
• The memory is cheap: a ring for 60,000 servers at 100 vnodes each is only tens of megabytes. The real cost of vnodes isn't RAM — it's the operational weight of moving more token ranges on every change.

And a deliberate counterexample worth knowing: Redis Cluster does not use a ring at all. It pre-chops the keyspace into exactly 16,384 fixed slots (slot = CRC16(key) mod 16384) and hands each node a range of slots. Fixed slots are easier to reason about and to reassign by hand than fluid ring arcs — a real system that chose operability over the ring's automatic rebalancing. Consistent hashing is the default answer, not the only one.

The classic vnode ring is a great default, and it earns its keep — but it isn't free, and it isn't always the right tool.

Its costs are the ones you just met: a sorted table of N×V points to store and keep consistent across every client, an O(log(NV)) binary search on every lookup, and real streaming work whenever the ring changes. For most systems that's a fine price. When it isn't, a few well-known alternatives trade it away:

• Jump hash (Google, 2014) needs no ring at all — it computes a node from a key and the node count in a few CPU registers, with near-perfect distribution and zero memory. The catch is sharp: nodes must be numbered 0…N−1 and you can only add or remove the last one — you cannot drop an arbitrary node in the middle. Perfect for a storage cluster you grow and shrink at the tail; useless for a cache fleet where any machine can die.
• Rendezvous (HRW) hashing also skips the ring: for a key, it scores every node with hash(key, node) and picks the highest. Beautifully balanced and simple, but O(N) per lookup — fine for tens of nodes, not thousands.
• Bounded-load and multi-probe variants chase the ring's low variance without storing a fat vnode table.

The point isn't to memorize the menu. It's that a ring with virtual nodes is the sensible default because it supports arbitrary add and remove with good balance and modest cost — and when one of those three (memory, lookup speed, or arbitrary removal) is the thing that hurts, there's a sharper tool.

Sit with what "balanced" actually means here, because it hides a limit. A ring with enough virtual nodes spreads the keyspace evenly — every node owns about the same slice of the space of possible keys. That is not the same as spreading the load.

Remember the celebrity from Choosing a Shard Key. If one single key — Taylor Swift's row, the one viral post — gets a thousand times the traffic of any other, the ring does its job perfectly: it hashes that key to exactly one position and faithfully sends all thousand times the traffic to the one node that owns it. Perfect keyspace balance, one molten node. Consistent hashing balances which keys live where; it has no opinion about a key that is hot all by itself.

That's not a flaw to fix here — it's the exact residual the last lesson left open, and it has its own answer: split or replicate the hot key so it stops being a single point. That's Resharding & Hot Shards, next. The ring gets your keys evenly distributed and cheaply rebalanced; taming a key that's a hotspot on its own is a different problem, and knowing the boundary between them is half of using either one well.

• "Consistent hashing spreads load evenly." Only with enough virtual nodes. One point per node is lumpy — the busiest node runs O(log N)× the average, measured 3.68× on a real ring — on nothing but where its dot landed.
• "More virtual nodes is always better." Diminishing returns past ~100-200: the imbalance flattens (5% std at 128), and more just adds ring metadata, lookup cost, and streaming. Cassandra tuned its default down from 256 to 16.
• "Virtual nodes are extra real servers." No — they're extra points on the ring for the same physical node. Zero new hardware; one machine simply stands in many places, made by hashing node-id#0, node-id#1, and so on.
• "Consistent hashing fixes hot keys." It balances the keyspace, not per-key load. One hot key still sends all its traffic to the single node that owns it — that's Resharding & Hot Shards, not this.
• "It's the only way to shard." It's the default, not the law. Jump hash (no memory, but only remove the last node), rendezvous/HRW (no ring, O(N) lookup), and fixed slots (Redis Cluster's 16,384) are all real choices with different trade-offs.
• "Adding a node is basically free because only ~1/N of keys move." The fraction is small (measured ~9% adding to a 10-node ring, versus mod-N's 91%), but each moved key is a real transfer or cache miss. Small and online — not zero.

• The ring solved remapping but left balance to luck: one point per node is lumpy — the busiest node carries O(log N)× the average (measured 3.68×, std 104%) on nothing but where its dot fell.
• Virtual nodes are the fix: hash each physical node onto the ring many times so its many small arcs average out. Imbalance shrinks like 1/√V (V = ln N/ε²) — measured std 104% → 5% from 1 to 128 vnodes — then flattens, which is why Cassandra ships 16 tokens, not 256 (ketama uses ~160).
• Vnodes also make death graceful: one point per node dumps 100% of a dead node's keys on a single neighbour (cascade risk); 64 vnodes scatter them across 9 survivors, max 18% each. One mechanism, two gifts.
• The ring is the default, not the only tool: jump hash (zero memory, last-node-only removal), rendezvous/HRW (no ring, O(N) lookup), and Redis Cluster's 16,384 fixed slots are real alternatives when memory, lookup speed, or arbitrary removal bite.
• The boundary that matters: consistent hashing balances the keyspace, cheaply and rebalanceably — it does nothing for a single hot key, which still melts its one owner. That's the handoff. Next — Resharding & Hot Shards: what to do when one shard is on fire anyway.