The Ring That Shares the Load: Consistent Hashing and the Art of Moving Gracefully

The Hook: The Most Expensive Mistake in Distribution

Imagine you run a cache — a set of fast servers that keep frequently requested data in memory so the underlying database isn't queried on every click. You have ten of these servers, and you must decide which server is responsible for which record. The obvious, almost self-evident solution is the one every computer science student learns in their first semester: take a hash of the key, compute it modulo the number of servers, and there's your assignment. server = hash(key) % 10. Elegant, fast, evenly balanced.

And a catastrophe the moment the number of servers changes.

Suppose an eleventh server is added because load is rising. % 10 becomes % 11. What happens? Practically every key now lands on a different server. Not one tenth, not one eleventh — nearly all of them. The record that was just on server 3 is now on server 7, the next on server 0, and so on. For a cache this means that from one second to the next almost every entry is in the wrong place. Every request misses the cache, every request falls through to the database. This is called a cache stampede, and it can bring down a database designed for ten percent of the load under the sudden full load. The very attempt to add capacity triggers exactly the collapse you were trying to avoid.

This problem sits at the heart of one of the most important and simultaneously most underappreciated ideas in modern cloud infrastructure: consistent hashing. It answers a question that arises in the machine room of practically every distributed system — from Amazon's shopping cart through Discord's message routing to content delivery networks serving video to billions of users: how do I distribute data or load across a set of machines such that adding or removing a machine changes only a minimal, controlled fraction of the assignments?

This article takes you along the whole route: from a precise definition of what "consistent" means here, through the original ring devised by David Karger and colleagues in 1997, the crucial refinement of virtual nodes, all the way to the modern alternatives — rendezvous hashing, jump hashing, and Google's Maglev — each of which strikes its own set of trade-offs. What emerges at the end is not merely an algorithm but a design principle about stability under change.

Part 1: What "Consistent" Really Means

The Measure of All Things: Minimal Disruption

The term "consistent hashing" grew historically and is unfortunately a little misleading — it has nothing to do with "consistency" in the sense of database consistency or the CAP theorem. Something more precise is meant. In 1997, Karger and his co-authors defined a consistent hash function as one that changes minimally when the range of the function changes — that is, when buckets (servers, nodes, ranges) are added or removed.

Let's state the requirement cleanly. We have a set of keys (the records, requests, objects) and a set of buckets (the servers). A mapping function assigns each key to a bucket. From a good such function for distributed systems we demand four properties:

Balance: The keys should be distributed as evenly as possible across the buckets. No server should carry a disproportionate share of the load.

Monotonicity / minimal disruption: When a bucket is added or removed, only the keys that absolutely must be reassigned should move. Ideally, when one of n buckets fails, only a fraction of about 1/n of all keys migrates — namely exactly those that were on the vanished bucket. All others stay where they are.

Spread and load: In systems where different clients hold different, possibly stale views of the bucket set, a key should still not be scattered across too many different buckets, and no bucket should be responsible for too many keys.

Low cost: Computing the assignment and holding any necessary state should be cheap.

The modulo approach nails balance but fails catastrophically at monotonicity: a change in n reshuffles almost everything. This is precisely where consistent hashing steps in.

Why This Matters Especially in the Cloud

In a static system with a fixed number of servers, the modulo trick would be entirely sufficient. But the cloud is the opposite of static. Servers are spun up and torn down to breathe with load (autoscaling). Machines fail — with tens of thousands of servers, at any moment one is almost guaranteed to be broken somewhere. Deployments continuously replace instances. The set of available nodes is therefore constantly in motion. A distribution scheme that reshuffles almost all data on every such change is simply unusable in this environment. Consistent hashing is the answer to the fact that elasticity — the ability to adjust capacity dynamically — has become a foundational principle of the cloud. It is the silent precondition that lets a system grow and shrink without collapsing on every breath.

Part 2: The Ring — Karger's 1997 Idea

From the Straight Line to the Circle

The central invention was introduced in 1997 in a now-famous paper: Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web by David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy, then at MIT's Laboratory for Computer Science. The motivation was decidedly practical: the young World Wide Web suffered from "hot spots" — suddenly popular pages that overran individual servers. The goal was to spread load across a network of cache servers without each client needing a current, consistent view of all servers. (This same work later became the technical foundation of the content delivery network Akamai, co-founded by Daniel Lewin and Tom Leighton.)

The basic idea is disarmingly simple. Instead of laying the servers out on a straight number line and computing modulo, you bend the number line into a circle — a ring. Picture a value range, say all numbers from 0 to 2³²−1, and close it into a circle: after the largest number comes 0 again.

Now the decisive trick occurs: you place not only the keys on this ring, but the servers as well. Each server is assigned one or more positions on the ring by hashing its name (e.g. its IP address). Each key gets a position by the same hash function. Servers and data thus live in the same abstract space.

The Responsibility Rule: Clockwise to the Next Node

The assignment now follows a single, elegant rule: a key belongs to the server you reach by walking clockwise around the ring from the key's position until you hit the first server. Each server is therefore responsible for the arc of the ring immediately "before" it — for all keys between it and its predecessor on the ring.

Here comes the crux, the real magic. What happens when a server fails? Its arc of the ring is orphaned. But instead of throwing the whole system into disarray, something local happens: only the keys that lay on that one orphaned arc migrate to the next server clockwise. All other keys across the entire ring stay exactly where they were. Their position hasn't changed, their next server clockwise is still the same. So only about 1/n of all keys move — with ten servers, roughly one tenth instead of, as with the modulo approach, practically everything.

Mirror-image on adding a server: the newcomer takes a position on the ring and assumes exactly the part of the arc lying between it and its predecessor — keys that previously belonged to the next server clockwise. Only that one segment moves; the rest of the ring is untouched. This is the minimal disruption the definition demands, put into practice.

An Image to Hold On To

You can picture the ring like a round clock face, with servers sitting at various hours. Each record finds its own time of day and then walks clockwise until it reaches the next server — where it checks in. If the server at "three o'clock" fails, all its guests simply find the next server at "four o'clock." No one else on the dial has to move. This locality — that a disruption affects only its immediate neighborhood — is the conceptual achievement of consistent hashing.

Part 3: The Problem of the Naked Ring and the Rescue by Virtual Nodes

The Ring Is Naively, Dangerously Imbalanced

As beautiful as the basic ring is, in its naked form it has two serious weaknesses that make it unfit for production use.

Problem 1 — uneven distribution. If you throw only n servers randomly onto the ring, the arcs between them are not equally long. Statistically, large and small gaps inevitably arise. A server that happens to draw an especially long arc gets far more keys than its peers. With few servers, the standard deviation of the load distribution can be considerable — outliers carrying two or three times the average are not rare. Theory says: with only n positions, the imbalance can easily reach a factor of two.

Problem 2 — uneven redistribution on failure. When a server fails, its entire arc migrates to exactly one neighbor — the next one clockwise. That neighbor suddenly inherits the full load of the failed server on top of its own. Instead of spreading the failed server's load evenly across all remaining servers, it is dumped onto a single one — which may then in turn become overloaded and fail. Such a domino effect is every operator's nightmare.

The Elegant Solution: Many Ghosts per Server

The answer to both problems is as simple as it is effective, and in its well-known form it comes from Amazon's Dynamo system: virtual nodes (also called tokens or vnodes). Instead of placing each physical server on the ring only once, you place it many times — say 100 to 200 times — at different, hash-scattered positions. Each physical server thus appears as a cloud of many small "ghosts" spread across the whole ring.

This fixes both problems at once. For balance: if each server is represented by a hundred random points, the lengths of the many small arcs average out. The law of large numbers ensures that the total load per physical server sits very tightly around the average. The more virtual nodes, the more even the distribution — at the cost of a bit more memory for the ring data structure.

For redistribution on failure: when a physical server now fails, its hundred ghosts vanish from a hundred different spots on the ring. Each of these hundred small arcs migrates to its respective neighbor clockwise — and because the ghosts are scattered across the whole ring, those neighbors are, with high probability, a hundred different physical servers. The failed server's load is thus finely atomized and spread evenly across all remaining servers rather than crushing a single one. The domino effect is averted.

Another often-underestimated benefit: virtual nodes enable heterogeneity. A server twice as powerful simply gets twice as many virtual nodes and carries correspondingly twice the load. You can weight capacity in a fine-grained way without changing the algorithm.

Dynamo: Consistent Hashing at Industrial Scale

The canonical example of consistent hashing at scale is Amazon's Dynamo, described in 2007 by Giuseppe DeCandia and colleagues in an influential paper that shaped an entire generation of NoSQL databases (Cassandra, Riak, Voldemort, and others build directly on it). Dynamo distributes its key-value pairs across the ring with consistent hashing — very similar in its basic idea to Chord, the distributed hash table system. On joining, each node is assigned several positions (tokens) on the ring, and the number of these virtual nodes per machine can be tuned according to its capacity.

But Dynamo uses the ring not only for distribution but also for replication: each record is stored not only on the first node clockwise but additionally on the next N−1 nodes. The ring thereby directly yields the list of servers that should hold a copy — the so-called preference list. Thus a distribution scheme simultaneously becomes a foundation for fault tolerance. Whoever has internalized the mechanics of distribution also understands why such systems handle node failures so gracefully: the next node clockwise already holds a copy anyway.

Part 4: The Alternatives — An Ecosystem of Trade-offs

The ring with virtual nodes is the classic, most widespread solution. But it is not the only one, and for certain use cases there are better ones. The history of consistent hashing is a history of trade-offs: memory against evenness, simplicity against flexibility, computation time against predictability.

Rendezvous Hashing (Highest Random Weight)

Interestingly, one of the most elegant alternatives is even older than the ring. Rendezvous hashing, also called Highest Random Weight (HRW), was described in 1996/1998 by David Thaler and Chinya Ravishankar at the University of Michigan (technical report CSE-TR-316-96, formally published as Using Name-Based Mapping Schemes to Increase Hit Rates in IEEE/ACM Transactions on Networking, 1998). It too arose from the problem of distributed web caching and found early use in Microsoft's Cache Array Routing Protocol (CARP).

The idea dispenses with the ring entirely. To find out which server is responsible for a key, you proceed as follows: for each available server s, you compute a combined hash value hash(key, s) — a hash of the combination of key and server name. This yields for each server a kind of random number, a "weight." Then you simply pick the server with the highest of these values. Done.

The appeal: when a server fails, it affects only the keys for which precisely that server had the highest weight. For all other keys the winner stays unchanged — the second-highest was already someone else and now simply becomes the highest for the affected keys. You thereby achieve the same minimal disruption as the ring, but with perfect, natural balance and without virtual nodes and without having to hold a ring data structure in memory. The price: assigning a single key costs O(n) hash computations, because you must iterate over all servers. For small to medium server sets this is no problem and often the cleanest solution; for thousands of buckets it becomes expensive (though variants with logarithmic runtime via skip structures exist). Weighting for heterogeneous capacities is also possible — through a one-line change that folds the weight into the formula.

Jump Hashing: Five Lines, No Memory

In 2014, John Lamping and Eric Veach at Google published a remarkably short paper: A Fast, Minimal Memory, Consistent Hash Algorithm. The Jump Consistent Hash it describes can be expressed in about five lines of code, needs no memory for state at all, is faster than Karger's ring, and provably distributes keys more evenly across the buckets.

The algorithm computes directly which of n numbered buckets a key falls into, by running through a deterministic pseudo-random sequence and making "jumps" at points where the assignment would change. It needs O(1) memory and O(ln n) time and achieves near-perfect balance without virtual nodes.

The decisive limitation — and the reason jump hashing doesn't simply replace the ring everywhere — is that the buckets must be numbered sequentially: 0, 1, 2, …, n−1. You can only add or remove buckets at the end. There is no way to remove an arbitrary bucket in the middle (say, because that one specific server failed) without disturbing the numbering. This makes jump hashing excellent for data-storage systems with numbered shards where you scale up or down in an orderly fashion — but unsuitable for distributed web caching, where individual, named servers can fail at any time and in any order.

Maglev: The Consistent Lookup Table

Google's Maglev, presented at NSDI in 2016 by Daniel Eisenbud and colleagues, is a software-based network load balancer that distributes millions of packets per second across backend servers. For this purpose Google needed a scheme that looks up very fast (each packet must be assigned to a backend in constant time) while disturbing connections as little as possible when the set of backends changes.

To this end, Maglev's consistent-hashing algorithm precomputes a fixed-size lookup table in which each backend fills its entries via a well-designed permutation procedure. A packet is then assigned to a backend by a single table access — constant time, very cache-friendly. The scheme achieves near-perfect load distribution while keeping connection churn — the fraction of connections that migrate to a different backend when the backend set changes — low. Maglev achieves weighting by letting more heavily weighted backends fill table entries more frequently. The compromise: minimal disruption is not perfect as with the ring — a small fraction of additional connections may move on a change — but the lookup is extremely fast and the memory footprint is predictably constant.

A Map of the Trade-offs

The table makes the central pattern visible: there is no universally best scheme, only one that fits the given context. Whoever may lose named nodes in arbitrary order needs the ring or rendezvous. Whoever scales in order and won't waste memory takes jump. Whoever must route millions of packets per second in constant time takes Maglev.

Part 5: The Subtleties That Hurt in Practice

Hot Keys — When a Single Key Blows Up the System

Consistent hashing distributes keys evenly — but not necessarily load. If a single key is requested disproportionately often (a celebrity's tweet, a viral product listing, a superstar's profile), then the entire load of that one "hot key" lands on the one server responsible for it — no matter how finely the ring is balanced. No hashing scheme can solve this problem on its own, because it operates in principle at the level of keys, not at the level of access frequency. In practice, hot keys are addressed with additional layers: replicating especially hot keys across multiple nodes, a small cache layer in front, or artificially splitting a hot key into several sub-keys. It's important to know this boundary: consistent hashing solves the problem of structural redistribution, not the problem of skewed access patterns.

Bounded Loads — Balance with a Seatbelt

Even with virtual nodes, balance remains statistical, not guaranteed. In 2016, researchers (with participation from Google and Vimeo) presented an extension called Consistent Hashing with Bounded Loads. The idea: you set a hard upper bound on how much load a single server may carry — say 1.25 times the average. If a key, on its ring search, runs into an already "full" server, it simply continues clockwise to the next one that still has capacity. This combines the minimal disruption of the ring with a real guarantee against overload — a fine example of how the basic idea can be made progressively more robust, layer by layer.

The Choice of Hash Function

An often-overlooked detail: for the statistical even distribution to take hold at all, the underlying hash function must scatter values well across the value range. Cryptographic strength is usually unnecessary here and too slow; one uses fast but well-scattering non-cryptographic functions (such as MurmurHash, xxHash, or similar). A poor hash function with clumping can undermine the most beautiful ring construction, because servers and keys then don't actually lie randomly distributed.

Part 6: The Overarching Design Principle

Step back, and consistent hashing is far more than a trick for distributing cache entries. It is an answer to a very general question: how do you build a system whose behavior changes only as little as necessary under change? The modulo approach is fragile because a small change of the parameter (n) triggers a global upheaval — the entire system reacts to every local disturbance. The ring is robust because it enforces locality: a disturbance at one spot stays at that spot. This property — that the impact of a change stays proportional to the size of the change and doesn't spread to the whole — is a deep design principle that reaches far beyond hashing.

You find the same pattern everywhere in well-designed distributed systems: in the way How Machines Come to Agree - Distributed Consensus from FLP to Paxos to Raft relies on a leader change not rewriting the entire log; in the way Clocks That Know Their Own Uncertainty - Spanner TrueTime and Mastering Time in the Cloud bounds the uncertainty of time locally instead of letting it propagate through the system; in the way Das Logbuch der Wahrheit - Event Sourcing und CQRS verstehen treats state changes as immutable, local events that do not retroactively rewrite existing state. The message is everywhere the same: robust systems are those in which the radius of a disturbance stays small.

The Central Takeaway

The practical lesson for designing any distributed or elastic system reads: for every distribution or assignment scheme, ask not only whether it is even in the static case, but what happens when the set of targets changes. How many assignments break when a node is added or removed? If the answer is "almost all," you have built in a time bomb that goes off at the first autoscaling event or server failure. If the answer is "only the affected fraction," you have built a system that can breathe with change. Consistent hashing — whether as ring, rendezvous, jump, or Maglev — is the tool that makes this second answer possible. And you make the choice between the variants deliberately, guided by the questions: can my nodes disappear in arbitrary order? How much memory and computation may a lookup cost? How perfect must the balance be?

A Question to Ponder

Consistent hashing solves the problem of bounding disturbances spatially — a change at one node stays local. But there is a related question it does not answer: how do you bound the disturbance temporally when many clients simultaneously still hold a stale view of the node set and therefore briefly compute contradictory assignments? How much inconsistency during a transition is acceptable, and where in your own system would you rather assign quickly-but-wrongly than correctly-but-blockingly?

Cross-References in the Vault

• How Machines Come to Agree - Distributed Consensus from FLP to Paxos to Raft – how nodes agree on a shared state despite failures; the logical complement to the question of which node is responsible for what.
• Clocks That Know Their Own Uncertainty - Spanner TrueTime and Mastering Time in the Cloud – another example of making uncertainty locally manageable in distributed cloud systems.
• Das Logbuch der Wahrheit - Event Sourcing und CQRS verstehen – state as local, immutable events rather than globally rewritable values.

Sources

• Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., Panigrahy, R. (1997): Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proc. 29th ACM Symposium on Theory of Computing (STOC), pp. 654–663. DOI: 10.1145/258533.258660. https://dl.acm.org/doi/10.1145/258533.258660
• DeCandia, G. et al. (2007): Dynamo: Amazon's Highly Available Key-value Store. Proc. 21st ACM Symposium on Operating Systems Principles (SOSP). https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
• Thaler, D., Ravishankar, C. (1998): Using Name-Based Mapping Schemes to Increase Hit Rates. IEEE/ACM Transactions on Networking 6(1), pp. 1–14 (first as tech. report CSE-TR-316-96, 1996). https://en.wikipedia.org/wiki/Rendezvous_hashing
• Lamping, J., Veach, E. (2014): A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv:1406.2294. https://arxiv.org/abs/1406.2294
• Eisenbud, D. E. et al. (2016): Maglev: A Fast and Reliable Software Network Load Balancer. Proc. 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI). https://research.google/pubs/maglev-a-fast-and-reliable-software-network-load-balancer/
• Stanford CS168, Lecture 1: Introduction and Consistent Hashing. https://web.stanford.edu/class/cs168/l/l1.pdf

← All articles