Consistent Hashing for Load Balancing and Caches
On this page
Learning Objective
Explain why modulo hashing collapses when the backend count changes, describe how a consistent hash ring with virtual nodes bounds the disruption to roughly one over N of the keyspace, and identify when cache-friendly routing is worth the load imbalance it introduces.
Concept Explanation
Sometimes even distribution is not what you want. If each backend maintains a local cache, or holds a user session in memory, or is the designated owner of a shard, then routing the same key to the same backend every time is worth far more than perfect balance, because it turns cache misses into cache hits and avoids the need for shared state. The naive way to achieve that is modulo hashing: compute hash(key) mod N where N is the number of backends. It is deterministic, it is cheap, and it is catastrophically fragile.
The fragility is arithmetic. When N changes from 10 to 11, nearly every key changes its assignment, because hash(key) mod 10 and hash(key) mod 11 agree only by coincidence. Roughly ninety percent of all keys move. For a cache tier, that means a single machine being added or removed invalidates almost the entire cache at once, and every one of those keys must be recomputed from the origin simultaneously. The consequence is not a gradual warm-up but an instant, near-total cache miss rate against a database sized for a ten percent miss rate, which is one of the most reliable ways to take a system down during what was supposed to be a routine capacity increase.
Consistent hashing, introduced by Karger and colleagues in 1997 specifically for distributed web caching, fixes this by changing what gets hashed. Instead of mapping keys onto backend indices, both keys and backends are hashed into the same circular keyspace, conventionally visualized as a ring from 0 to 2^32 minus 1. A key is served by the first backend encountered walking clockwise from the key position. Now when a backend is removed, only the keys that fell in the arc it owned need to move, and they move to the single next backend clockwise. Everything else is untouched. Adding a backend is symmetric: it claims one arc from one neighbor. The expected fraction of keys disrupted is roughly one over N rather than roughly all of them.
Plain consistent hashing has a distribution problem, though: with only N points on the ring, the arcs between them are very unevenly sized, so a fleet of ten backends can easily see one backend owning three times the keyspace of another. Virtual nodes solve this. Each physical backend is hashed onto the ring many times, commonly 100 to 200 replicas, under names like backend-a#0, backend-a#1, and so on. With 10 backends and 150 virtual nodes each, the ring has 1500 points, the arcs are far more uniform by the law of large numbers, and each physical backend owns many small scattered arcs instead of one large one. Virtual nodes also give you weighting for free: a machine with twice the capacity simply gets twice the virtual nodes. And when a backend is removed, its many small arcs are absorbed by many different neighbors rather than dumping its entire load onto one unlucky successor.
The cost of any affinity scheme is that you have deliberately given up even distribution. If one key is far hotter than the others, consistent hashing will faithfully send all of that heat to exactly one backend, which is the hot key problem covered in the final phase of this course. The mitigations are worth knowing now: bounded-load consistent hashing adds a capacity cap so that when a backend exceeds a multiple of the average load, keys overflow to the next backend on the ring, trading a little affinity for a guaranteed load bound. Google Maglev takes a different approach, building a lookup table that is close to perfectly even while still keeping the vast majority of entries stable across backend changes, which fits its use case of L4 connection pinning where evenness matters more than absolute stability. And for the session affinity case specifically, the best mitigation is usually architectural rather than algorithmic: externalize the session into a shared store and let the routing layer stop caring where a request lands at all.
| Scheme | Keys Moved When N Changes | Distribution Quality | Best Fit |
|---|---|---|---|
| Modulo hashing | Nearly all of them | Perfectly even while N is stable | Fixed-size pools that genuinely never change |
| Consistent hashing, no virtual nodes | About 1/N | Poor; arc sizes vary widely | Rarely the right choice on its own |
| Consistent hashing with virtual nodes | About 1/N | Good; improves with more replicas per node | Distributed caches, shard ownership, sticky routing |
| Bounded-load consistent hashing | About 1/N plus overflow churn | Bounded by construction against a chosen factor | Affinity routing where one key can go hot |
| Maglev hashing | Small fraction of table entries | Near-perfect evenness | L4 connection pinning at very high packet rates |
Worked Example: Ring Placement and the Cost of Adding a Node
Working the arithmetic once makes the difference concrete. The example below uses a deliberately tiny ring so the positions are readable, then states the general result that holds at realistic ring sizes.
# A 1000-point ring for readability (real rings use the full 32-bit space).
# Three backends, 4 virtual nodes each, positions = hash(name#i) % 1000.
A#0=120 A#1=390 A#2=640 A#3=905
B#0=055 B#1=310 B#2=560 B#3=830
C#0=205 C#1=470 C#2=715 C#3=980
# Sorted ring:
# 55(B) 120(A) 205(C) 310(B) 390(A) 470(C) 560(B) 640(A) 715(C) 830(B) 905(A) 980(C)
# Lookup = first virtual node clockwise from hash(key).
hash("user:8821") % 1000 = 333 -> next clockwise is 390(A) -> backend A
hash("user:1204") % 1000 = 690 -> next clockwise is 715(C) -> backend C
hash("cart:5567") % 1000 = 042 -> next clockwise is 55(B) -> backend B
# --- Now add backend D with virtual nodes at 160, 420, 600, 870 ---
# Only keys landing in these four arcs move, and each moves to D:
# (120,160] was A#1's arc -> now D
# (390,420] was C#1's arc -> now D
# (560,600] was A#2's arc -> now D
# (830,870] was A#3's arc -> now D
# Total keyspace disturbed: (160-120)+(420-390)+(600-560)+(870-830) = 150/1000
# = 15%, which is close to the expected 1/4 share D should end up owning
# once the ring is large enough for the law of large numbers to apply.
# Compare modulo hashing over the same change:
# hash(key) % 3 -> hash(key) % 4
# A key keeps its backend only when the two remainders coincide,
# which happens for roughly 1 key in 4. About 75% of keys move,
# and at N=10 -> 11 it is about 90%.
# Bounded-load variant: cap each backend at (1 + eps) * average_load.
# target = ceil((1 + 0.25) * total_keys / num_backends)
# walk clockwise until a backend below its cap is found, then assign.
# Guarantees no backend exceeds 125% of average, at the cost of some
# keys not landing on their natural owner.Real-World Examples
- Amazon Dynamo, described in the 2007 SOSP paper that influenced Cassandra, Riak, and Voldemort, uses consistent hashing with virtual nodes for exactly the reasons above: the paper explicitly notes that the basic algorithm produced non-uniform data and load distribution and that assigning multiple positions on the ring per physical node both evened out the distribution and spread a departed node load across many surviving nodes rather than dumping it on one successor.
- Google published the Maglev paper at NSDI 2016 describing a purpose-built consistent hashing scheme that trades a small amount of stability for near-perfect evenness, because in its L4 load balancing role an uneven split of connections across backends was more costly than occasionally breaking an existing connection mapping. Vimeo subsequently implemented Maglev hashing in HAProxy and reported it publicly, and the algorithm is now available as a hashing policy in Envoy, making it a rare case of a published research design being adopted directly into mainstream proxies.
Review Questions & Answers
Going from N equals 10 to N equals 12 changes the assignment for the large majority of keys, since a key keeps its node only when hash(key) mod 10 and hash(key) mod 12 happen to point at the same machine. The cache itself does not fail, it simply misses: every remapped key is now requested from a node that has never seen it. That converts what was perhaps a five percent miss rate into something close to a total miss rate instantaneously, and every one of those misses becomes a query to the origin database. A database provisioned to absorb five percent of read traffic now receives essentially all of it, all at once, during a peak, so it saturates and starts timing out. The application then sees database timeouts, retries them, and amplifies the load further. The cache tier is healthy throughout; the damage is entirely downstream.
With only one ring position per backend, the arcs between positions are highly variable because a small number of random points on a circle produce very unequal gaps, so one backend can own several times the keyspace of another. Many virtual nodes per backend means many more points, and the law of large numbers pulls each backend total share toward its fair fraction. The failure benefit follows from the same structure: a departing backend owned many small scattered arcs rather than one large contiguous one, so its load is absorbed by many different successors instead of doubling the load on one unlucky neighbor. The cost is memory and lookup time. The ring must store N times R entries, and every lookup is a binary search over that sorted structure, so very high replica counts inflate the routing table and make ring rebuilds, which happen on every membership change, more expensive. Values in the low hundreds are the usual practical balance.
Bounded-load consistent hashing adds a capacity constraint: each backend may hold at most some factor, commonly 1.25 or 1.5, times the average load. A key is assigned by walking clockwise from its hash position as usual, but any backend already at its cap is skipped and the walk continues to the next one. This guarantees a hard upper bound on imbalance no matter how skewed the key popularity distribution is, which plain consistent hashing cannot offer at all. What it gives up is determinism and locality: a key overflowing to a different backend means the lookup now depends on current load rather than on the hash alone, so the mapping can change as traffic shifts, and the overflow keys will miss the cache on the new backend. It converts an unbounded worst case into a bounded one at the cost of some cache efficiency, which is usually the right trade for a routing tier and the wrong one for durable shard ownership.
When affinity exists only because the backend is holding mutable state that could live somewhere else, typically an in-memory user session, it is solving a self-inflicted problem. Sticky routing for sessions means a backend failure logs out every user pinned to it, deployments become disruptive, scaling events shuffle sessions, and load can never be truly balanced because the routing layer is constrained by history rather than by current capacity. Externalizing the session into a shared store such as a distributed cache or a signed token carried by the client removes the constraint entirely: any backend can serve any request, the load balancer is free to use a purely load-aware algorithm, and instance replacement becomes invisible. Affinity is genuinely justified when it exists to preserve an expensive-to-rebuild local cache or to enforce single-owner semantics for a shard, not merely to avoid moving session state out of process memory.