CS PAPERS DEEP-READ · PAPER 74
Karger, Lehman, Leighton, Levine, Lewin & Panigrahy · MIT · STOC 1997
In 1997 a group of theorists at MIT (Karger and colleagues) set out to cure a plague of the early web — a page suddenly goes viral and the server buckles. Their answer was consistent hashing: a rule for deciding which machine holds which thing, whose virtue is that adding or removing machines almost never reshuffles everything. A year later two of the authors founded Akamai on it. The videos you stream, your Amazon cart, databases like Cassandra — when they decide which machine a piece of data lives on, they still use this idea.
To split many things across a few machines, the natural move is to divide by the count and take the remainder: turn the name into a number, divide by how many machines you have, and whoever owns that remainder owns the item. With ten machines everyone gets a share, fairly evenly.
The trouble starts when the count changes. Add an eleventh machine and the divisor goes from 10 to 11, so nearly every item changes hands — the whole cluster shuffles data at each other, the network saturates, and nobody gets any real work done. All you wanted was one more machine.
Consistent hashing lays things out differently. Picture a clock face. Every machine computes a position from its own name and is pinned there; every piece of data computes a position from its own name too. One rule: a piece of data belongs to "the first machine you meet walking clockwise from its position."
The key is that positions are computed independently: where an item lands on the clock face depends only on its own name and not at all on how many machines exist. So adding a machine just means driving a new pin into the face: it takes over only the items in the short stretch immediately behind it, from the neighbour clockwise of it, and nothing anywhere else on the face changes by a single character. Losing a machine is the mirror image — its stretch passes to the next pin along. Every change is confined to one small arc.
There was another benefit that mattered even more at the time: different browsers knew about different sets of caches. Under "divide and take the remainder," a list that differs by one machine gives completely different answers; under the clock-face rule, lists can disagree slightly and almost all data still lands on the same machine — so nobody has to agree in advance to end up agreeing.
A single pin per machine has a side effect: the arcs the face gets cut into vary wildly, so an unlucky machine minds a huge stretch while a lucky one minds a sliver. Uneven work.
The fix is crude: give every machine dozens or hundreds of pins (many "alter egos" on the face). With that many slices, long and short cancel out and each machine's total comes out about the same. A bonus: when a machine goes offline, its dozens of stretches are picked up by many different machines rather than dumped whole onto one unlucky neighbour.
One honest caveat: what it evens out is the number of items, not how often they're wanted — a single record the whole internet is hammering still lives on exactly one machine, and can still flatten it.
Don't assign by "divide by the machine count and take the remainder." Pin both machines and data onto one clock face by name, and give each item to the first machine clockwise. Adding or removing a machine then disturbs only a small arc — migration drops from "nearly everything" to "about one machine's worth" — and scattering many pins per machine evens out the load.
Want the ring diagram, the four properties, and the guarantees? → switch to the deep read
The paper first formalizes what "a good assignment" even means — four properties (balance, monotonicity, spread, load) — and then gives a minimal construction that satisfies them: hash both machines and items onto the same ring, and give each item to the first machine clockwise. Adding or removing a machine then migrates only about 1/n of the data, and clients holding slightly different lists of machines still agree on where things go. The other half of the paper uses random trees to spread the traffic of a single hot page across many caches. Consistent hashing went on to become a shared component of Akamai, Chord, Dynamo, Cassandra and modern load balancers.
hash mod n): the most common assignment rule — hash the name to a number, divide by the machine count, and the remainder picks the machine.O(log n)): a coarse measure of growth that ignores constants; O(log n) means it grows very slowly with scale.The authors are David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin and Rina Panigrahy of MIT's theory group; the paper is "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web," STOC 1997. It follows a mid-1990s line of work on how to organize web caches, and answers the most concrete engineering disaster of the exploding web: hot spots. In 1998 Leighton and Lewin turned the theory into a company, Akamai (Lewin was killed aboard American Airlines Flight 11 on September 11, 2001). Downstream it covers most of the next two decades of distributed storage — see the impact section.
The mid-1990s web had a brutal failure mode: get a page linked from a portal's front page and request volume could climb by orders of magnitude within minutes, killing the origin server. The natural fix is to scatter caches through the network to absorb the load — which immediately raises the question: which cache is responsible for which page?
The obvious answer is modulo bucketing: cache = hash(URL) mod n, i.e. hash the URL to a number and take it modulo the cache count. It has two fatal flaws.
First, change the set and everything is reshuffled. Go from n = 10 to n = 11 and most URLs change owner — every cache is invalidated at once and all the requests go back to the origin, precisely at the moment you were scaling out.
Second, and more awkward at the time: nobody's list matches. Caches were run by different organizations and came and went; the list any given browser knew was inevitably different. If each client takes the modulo of its own n, the same page is computed to different caches by different clients — the same content is stored separately in many caches and each of them fetches it from the origin once. Space and bandwidth both wasted.
And a third thing modulo never touches: the page itself is hot. However evenly you assign, a viral page still has exactly one cache responsible for it, and it still gets flattened. That is what the paper's second half is for.
key mod 4 to key mod 5 reshuffles almost every assignment — one extra machine means a cluster-wide migration.Half the paper's real contribution is that it pins the problem down first. It introduces a ranged hash function: an ordinary hash has one fixed mapping, but this one gives a separate item-to-bucket assignment for every possible view V (the set of buckets some client knows about), and the family is required to satisfy four properties at once:
The last two exist precisely to handle inconsistent views: even when lists differ, the conclusions must largely agree. That is what the "consistent" in consistent hashing actually means — not data consistency, but agreement of the assignment across different views. This point is perennially misread and worth memorizing on its own.
The construction that satisfies all four is startlingly plain: hash the buckets onto the unit interval [0,1) with the ends joined into a ring, and hash the items onto the same ring. One rule: bucket(item) = the first bucket whose hash is ≥ hash(item), wrapping around at the end — nearest clockwise.
Monotonicity comes almost for free: an item's position depends only on its own name and not on how many buckets exist, so inserting a new bucket only takes over the items in the stretch counter-clockwise of it, from whoever was their successor; every other arc is untouched, and deletion is the mirror image. Hence the expected migration: adding the (n+1)-th bucket moves only about 1/(n+1) of the items, and all of them move into the new bucket.
That alone is not balanced enough: n random points cut the ring into n arcs of wildly differing length, and the longest can be several times the average. So the paper replicates each bucket into Θ(log C) points on the ring (C being the total number of buckets that may ever appear). One machine now has many alter egos, long and short arcs cancel out, and each machine's total arc length concentrates near the mean. Industry later named the trick virtual nodes (vnodes), and it pays two dividends: when a machine leaves, its many arcs are taken over by different machines (no single neighbour absorbs the hit), and machines of different capacity can be weighted by scattering more or fewer alter egos.
On that basis the paper proves (with high probability, i.e. the failure probability vanishes rapidly with scale): balance — each bucket receives an O(1/|V|) fraction of the items; monotonicity — unconditionally, since it is a property of the construction rather than of chance; and, assuming every client sees at least 1/t of all buckets, spread and load both stay on the order of O(t·log C). The weight of the result is this: a rule you can evaluate with a single hash, needing no coordination at all, gets all four at once.
Consistent hashing settles "who is responsible," not "what if one machine can't cope." The paper's second half gives every page a random tree: take a pool of caches as nodes and hash "page name + node index" into a d-ary tree — a different page yields a differently shaped tree with different members. A request does not go straight to "the responsible machine"; it picks a random leaf of that page's tree and asks there, and on a miss asks the parent, on up, reaching the origin server only if even the root misses.
Two things make it work. First, each node is only ever asked by its d children — fan-in is constant, so no machine faces the whole internet. Second, once a node fetches the page it caches it, so later requests hit immediately and the number of requests passed upward is capped. Pressure from a hot page therefore decays rapidly up the tree and the origin sees only a few fetches; and because each page's tree is generated randomly from its name, different hot pages have their roots on different machines and cannot gang up on one. The paper proves that under its request model, with high probability no machine bears more than a logarithmic factor above its fair share.
The two halves are two faces of one conviction: fix the division of labour with no central coordinator and no global state, purely by having everyone compute the same hash — the ring divides space, the tree divides pressure. That is why it could work on the 1997 internet, where nobody was in charge of anybody.
To be clear up front: this is a theory paper (STOC), and its results are theorems, not measurements — there is no system evaluation, so there are no throughput or latency numbers to quote. What it guarantees:
1/(n+1) of the items change hands (modulo bucketing reshuffles nearly all of them); monotonicity holds unconditionally.Θ(log C) copies per bucket, with high probability each bucket's share stays within a constant factor of the mean.O(t·log C) — one page is stored by only a handful of caches network-wide.The real "experiment" came later, in industry: Akamai built a global CDN on it, and Dynamo and Cassandra have used it as their default placement scheme ever since.
It took something everyone was doing crudely — sharding — and made it a primitive with a definition and guarantees, and so it became a shared part of a whole generation of systems: the ring under Chord and other DHTs, Dynamo's data placement, Cassandra's token ring, memcached's ketama clients, the backend-picking logic in layer-7 load balancers. The deeper contribution is "agreement without agreeing on the list" — the precondition for any system without a centre to function at all, and the starting point of twenty years of follow-up work on sharding that is more balanced and cheaper in memory.
① In one line: hash machines and data onto one ring and give each item to the first machine clockwise, so adding or removing a machine disturbs only one arc.
② The pain: hash(key) mod n reshuffles almost everything when n changes, and clients with mismatched machine lists compute conflicting owners.
③ The real contribution is defining "assigned well" first: balance, monotonicity, spread, load — the last two aimed squarely at inconsistent views, which is what "consistent" here actually means (not data consistency).
④ The construction is minimal: buckets and items hash onto a [0,1) ring, nearest clockwise wins; monotonicity is built in, and adding the (n+1)-th bucket moves only about 1/(n+1) of the data, all of it into the new bucket.
⑤ Virtual nodes: only with Θ(log C) alter egos per machine is balance achievable; the by-products are multi-machine takeover on departure and capacity weighting.
⑥ Random trees: a per-page cache tree generated from its name, constant fan-in, stopping at the first hit — thinning a single hot spot layer by layer. This half was largely forgotten.
⑦ Impact: the shared bedrock of Akamai (founded by two of the authors), Chord, Dynamo, Cassandra, ketama and layer-7 load balancing.
⑧ Limits: balances keys not heat; virtual-node metadata cost; no notion of rack or zone; rendezvous, jump and Maglev hashing each trade differently.