Lay your servers around a circle; a key belongs to the next server you meet walking clockwise. Add or remove a server and only the keys in that one arc move — not, as the naive scheme demands, nearly all of them.
Back in Chapter 1 we sharded a database with user_id % N and quietly admitted it: "resharding is brutal." This chapter is the fix. Consistent hashing is the trick that lets a distributed system add and remove machines while moving as few keys as physically possible.
The idea is almost embarrassingly simple once you see the picture. Instead of computing "which of my N boxes owns this key" — a calculation that depends on N, so it changes the instant N changes — you place both the keys and the servers onto a circle and let geometry decide ownership. A key belongs to the first server you hit walking clockwise from it. Move one server and only its immediate neighborhood is disturbed; everyone else keeps the keys they already had.
We'll start with the pain that motivates all of this, build the ring, prove why it moves only ~K/N keys, fix its lopsidedness with virtual nodes, then weight it for servers of different sizes — and finish where it actually lives: DynamoDB, Cassandra, memcached clients, and CDNs.
Say you run N cache servers and you want to spread keys evenly across them. The obvious move: hash the key to a big number, then take it modulo N. The result, 0…N-1, is the server that owns it.
It's a one-liner: server = hash(key) % N. It distributes keys beautifully and looks up in constant time. For a fixed fleet it is genuinely hard to beat.
The catastrophe is what happens when N changes. Add one server — go from 4 to 5 — and the formula becomes % 5 instead of % 4. Now almost every key hashes to a different slot, because the remainder of a number changes when you change the divisor. A key that lived on server 2 might now belong to server 0. You haven't moved one server's worth of data; you've reshuffled the entire dataset.
For a cache, that means a near-total cache stampede: every key is suddenly a miss, and the whole fleet hammers the database at once to repopulate. For a sharded store, it means mass data movement — gigabytes flying between machines while the system limps. The pain isn't the formula; it's that the formula entangles the answer with the exact count of machines.
hash % N isn't "which box" — it's "which box out of exactly N." Change N and you've changed the question for every key at once, not just for the keys near the new machine.Here's the reframe. Take the whole range of possible hash values — 0 up to 2^k − 1 — and bend that line into a circle so the largest value sits right next to 0. This circle is the hash ring.
Now hash two different things onto the same ring. Hash each server (by its name or IP) to a point on the circle. And hash each key to a point too. To find which server owns a key, start at the key's point and walk clockwise until you bump into a server. That server owns the key. (Walk past 2^k − 1 and you wrap around to 0 — it's a circle, there's no edge.)
Why is this so much better? Because ownership is now local. Each server is responsible for the arc of the circle that sits just counter-clockwise of it — the stretch between the previous server and itself. When you add a server, it drops onto the ring somewhere and claims only the slice of arc between it and the next server clockwise; every other arc is untouched. Remove a server and its arc simply merges into the next server clockwise. One arc moves. Everyone else keeps what they had.
Let's count. Suppose you have K keys spread across N servers. On average each server owns about K/N keys — its share of the circle.
When a new server joins, it lands on one arc and steals exactly the keys that fall in the slice it now covers. Those keys used to belong to the one server clockwise of it; now they belong to the newcomer. That's roughly K/N keys that move — and only those. The other N−1 arcs never notice.
When a server leaves, the mirror image happens: its arc folds into the next server clockwise, which inherits its ~K/N keys. Again, just one arc's worth.
Compare the two regimes directly. Modulo moves on the order of K keys (nearly all of them) on every membership change. The ring moves on the order of K/N. With 100 servers that's a hundredfold reduction in data churn — the difference between a routine, invisible scaling event and an outage.
The ring as described has a flaw, and it shows up with small fleets. Hashing throws your servers onto random points of the circle — and random points are not evenly spaced. With only three or four servers you'll routinely get one server sitting just behind a huge empty arc and another crammed into a tiny one. The big-arc server owns most of the keys; the small-arc one idles. So much for even distribution.
There's a nastier consequence on failure. When a server dies, its entire arc — all of its keys — dumps onto the single next server clockwise. That neighbor suddenly carries its own load plus all the dead server's load. If it was already busy, it now tips over too, and you get a cascading failure marching around the ring. The promise was "spread the load"; with naive placement, removing a node concentrates it.
Both problems share a root cause: with few points, the arcs are lopsided and each server has exactly one downstream heir. We want many small arcs per server, scattered all around the circle, so that any one server's keys are spread across many neighbors. That's the next idea.
The fix: stop giving each physical server one point on the ring. Give it many. Instead of hashing "serverA" once, hash "serverA#1", "serverA#2", … "serverA#V" and drop all V points on the circle. Each of those points is a virtual node (or "vnode") that maps back to the same physical machine.
Two things get fixed at once. First, distribution smooths out: with, say, 150 vnodes per server, the law of large numbers takes over and each physical server ends up owning very close to its fair 1/N share, even with a handful of servers. The lopsided-arc problem melts away. Second, a failure spreads: a dead server's vnodes are scattered all around the ring, so its arcs have many different successors. Its load is redistributed across many neighbors, a little to each, instead of crushing one. No cascade.
The tradeoff is bookkeeping. Each vnode is an entry in the ring's lookup structure, so V times more servers means V times more ring entries — more memory for the routing table and slightly slower membership updates. In practice a few hundred vnodes per server is a sweet spot: distribution is excellent and the metadata is still tiny.
Let's nail down exactly which keys move, because that precision is the entire payoff.
Each new vnode lands at some point p on the ring. It claims the arc immediately counter-clockwise of p — the keys between the previous ring point and p. Those keys are pulled from the one server that was clockwise of p (the old owner of that arc) and handed to the newcomer. Nothing else moves. With V vnodes the newcomer pulls a little arc from V different existing servers — and across all of them the total taken is ~K/N keys, the newcomer's fair share.
Each of its vnodes vanishes from the ring, and the arc it covered merges into the next vnode clockwise — which belongs to some other server. So the departing server's keys flow to its clockwise successors, spread across many machines (one per vnode). Again ~K/N total, and only those keys, ever cross the wire.
This is what "smooth scaling" means: a membership change touches a bounded, predictable, minimal set of keys, and the boundary is purely local — a server only ever exchanges data with its ring neighbors. No global reshuffle, no central coordinator deciding who gets what.
Real fleets aren't uniform. One server has 64 GB of RAM, the next has 256 GB; one is a current-generation box, another is three years old. You don't want them all carrying an identical share — you want the big machine to do more work and the small one less.
Virtual nodes make this trivial. Since a server's share of the ring is just the total length of arc its vnodes cover, and more vnodes means more arc, you simply give bigger servers more vnodes. A 256 GB box gets 400 vnodes; a 64 GB box gets 100. The big one now owns roughly four times the keys — automatically, with no special-casing in the lookup path. The same clockwise rule still decides every key; you've only changed how densely each server is sprinkled around the circle.
This is weighted consistent hashing, and it's how heterogeneous clusters stay balanced by capacity rather than by raw machine count. Add a beefier server later? Give it proportionally more vnodes and the ring rebalances toward it — still moving only the keys in the arcs it newly covers.
lookup is a pure function — key ↦ ceiling(hash(key)), wrapping to the first entry. Weight, vnodes, joins, and leaves are all just different contents of that map. The lookup never changes; only the data does.The whole scheme is one sorted structure keyed by ring position. Adding a node inserts V entries (one per vnode); removing a node deletes them. A lookup hashes the key and finds the first entry at or after that position — and if there isn't one, it wraps to the very first entry on the ring. That "wrap around the circle" step is the only thing that makes it a ring rather than a line.
Watch the two languages line up on exactly that step: Scala's ceilingEntry and Haskell's lookupGE both mean "smallest key ≥ this," and both fall back to the minimum entry when the search runs off the top of the circle.
ceilingEntry ⇄ lookupGE are the same idea: "the first node at or clockwise of this point." When the key hashes past the last node, both wrap to the first entry (firstEntry / findMin) — that fallback is the seam where the line becomes a circle. Add V virtual points per node and the very same lookup gives you smooth, weighted distribution for free.Consistent hashing isn't a textbook curiosity — it's load-bearing infrastructure across the industry:
1/N of the cache instead of all of it — no stampede.The common thread: any time membership changes and you'd rather not reshuffle the world, a hash ring with virtual nodes is the answer. Next we put it to work building an actual store.
hash % N for anything whose N changes — a membership change remaps nearly every key.ceiling, wrapping to first — the same pure function in any language.