The problem consistent hashing solves fits in one sentence from the paper that later replaced it. Lamping and Veach's jump hash paper opens with the arithmetic: split key-value data across 10 shards with h(key) mod 10, grow to 12 shards, and h(key) mod 12 disagrees with the old assignment for almost every key — "the data would need to be completely rearranged among the shards." Yet only 1/6 of the data actually needs to move to end up balanced across 12 shards. Everything else is waste: cache misses, network transfer, rebalancing load on machines that gained and lost nothing.
Consistent hashing is the family of algorithms that move only what must move. What's less well known is that the famous hash ring is the expensive member of that family — and that its own authors quantified how expensive.
The ring, and the property that actually matters
Karger et al. introduced consistent hashing in 1997 for web caching — their motivating problem was hot spots on the early web (they cite the JPL site after the Shoemaker-Levy 9 comet impact, and IBM's site during Deep Blue vs. Kasparov), in a setting where no client could be assumed to know the full set of cache servers.
The construction: a random function maps each bucket (server) to a point on the unit interval, another maps each item there, and an item belongs to the closest bucket point. Dynamo's description of the practical version is the one everyone knows — hash the key onto a fixed circular space, walk clockwise, first node you meet owns the key.
The paper defines four properties — balance, monotonicity, spread, and load — but for storage systems the load-bearing one is monotonicity: when buckets are added, an item may move from an old bucket to a new bucket, but never from one old bucket to another. That single constraint is what caps data movement at the theoretical minimum. Spread and load only matter when different clients see different subsets of the servers — the 1997 web-caching setting. If all your clients agree on the member list (true of virtually every modern storage deployment), those two properties are irrelevant, and that gap is exactly what jump hash later exploited.
One point per server is a load-balancing disaster
The subtlety Karger et al. were upfront about: with one random point per bucket, arc lengths on the ring are wildly uneven. Their fix is replication — each bucket gets κ·log(C) points on the ring, and Theorem 4.1's balance guarantee depends on it.
Lamping and Veach measured how bad the imbalance actually is, as a function of points per bucket:
| Points per bucket | Std. error of bucket size | 99% CI (vs. average bucket) |
|---|---|---|
| 1 | 0.998 | (0.005, 5.25) |
| 10 | 0.315 | (0.37, 1.98) |
| 100 | 0.0997 | (0.76, 1.28) |
| 1000 | 0.0316 | (0.92, 1.09) |
With one point per server, roughly 1% of servers end up more than 5x the average size. Even at 1000 points per bucket — the figure Karger et al. used in their own experiments to reach a 3.2% standard deviation — about 1% of buckets are still at least 8% off average.
Those 1000 points each cost memory in every client. Lamping and Veach implemented the ring two ways: an STL map (48 bytes per point, supports dynamic updates) and a sorted vector of 32-bit truncated hashes (8 bytes per point, must be rebuilt on any membership change). At 1000 points per bucket, 1,000 buckets cost 46 MB or 7.6 MB respectively; 100,000 buckets cost 4.5 GB or 0.75 GB — per client that routes requests.
What virtual nodes look like in production
Dynamo (SOSP 2007) is the canonical production deployment of the ring, and its Section 6 is a quiet admission that random placement never fully worked. Amazon measured per-node request load over 24 hours in 30-minute windows, calling a node out-of-balance when it deviated more than 15% from average: the imbalance ratio hit ~20% during low load and ~10% during high load. (High traffic helps because many popular keys are in play at once and the law of large numbers smooths things out.)
Dynamo's partitioning evolved through three strategies:
- T random tokens per node, partition by token value — the classic vnode ring, initial production deployment.
- T random tokens, hash space pre-divided into Q equal partitions — tokens now only decide placement, not partition boundaries.
- Q/S tokens per node, equal partitions — with S nodes, each takes an equal share of fixed-size partitions; joining nodes "steal" tokens, leaving nodes scatter theirs.
The direction of travel is telling: away from "hash randomness will balance things" and toward fixed, equal-sized partitions with explicit placement — the ring reduced to a membership-change protocol rather than a load balancer.
Jump hash: five lines, no ring
Lamping and Veach's 2014 algorithm deletes the data structure entirely:
int32_t JumpConsistentHash(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;
}The reasoning behind it is a beautiful inversion: instead of asking "which bucket does this key hash near," ask "as the bucket count grew from 1 to n, when did this key's assignment jump?" For the function to stay balanced, going from n to n+1 buckets must move exactly 1/(n+1) of keys — so P(ch(k, n) = ch(k, m)) = m/n for n ≥ m. Seed a pseudo-random generator with the key, and the destination of the next jump after landing at bucket b has closed form j = floor((b+1)/r) for uniform r in (0,1). The loop skips straight from jump to jump; expected iterations are under ln(n) + 1. The magic constant is a 64-bit linear congruential multiplier, re-mixed every iteration, which is also why the input key doesn't need pre-hashing if it's already an integer.
The measured results, on an Intel Xeon E5-1650:
- Balance: standard error of 0.00000000764 — a 99% CI of (0.99999998, 1.00000002) versus the ring's (0.92, 1.09) at 1000 points per bucket.
- Speed: 65 ns at 1,024 buckets and 165 ns at a billion buckets, versus 658 ns for the map-based ring at 1,024 buckets with k=1000 — 3-4x faster up to 1,000 buckets, 5-8x up to 100,000, before accounting for the ring's cache misses under real workloads.
- Rebalancing: adding bucket 1,001 pulls almost exactly 0.1% of the key space from every existing bucket. On a ring with 10 points per new bucket, at most 10 existing buckets participate — useless if you added the node to relieve a hot spot that isn't one of the 10.
- Memory: a few registers.
The catch, and how to choose
Jump hash's price is printed in its signature: num_buckets, not a member list. Buckets are the integers [0, n) — you can add bucket n or remove bucket n−1, but you cannot remove bucket 3 while 4 through n−1 live on. Arbitrary node death is unhandled by design.
Lamping and Veach argue this is the right trade for storage: a shard is the only home of its data, so a dead node must be replaced (from replicas), not hashed around — membership changes are capacity changes, which happen at the end of the sequence. For a stateless cache tier, where a dead server genuinely should vanish from the function, the constraint is disqualifying, and you're back to the ring — or to rendezvous hashing (Thaler and Ravishankar), which scores every bucket per key with h(key, bucket) and takes the max: no state, arbitrary IDs and removals, but O(n) per lookup unless you accept the balance costs of the tree variant.
So the decision procedure is short. Sequentially numbered shards that only grow and shrink at the end: jump hash, and stop paying for a ring you don't need. Arbitrary membership with few nodes: rendezvous. Arbitrary membership at scale: the ring — with the Dynamo lesson attached, which is that you'll eventually stop trusting random tokens and carve the space into fixed equal partitions anyway.