Consistent hashing, and the three things the ring diagram never tells you

The ring solves rebalancing. It does not solve hot shards, its load balance is weaker than the picture suggests, and the virtual node count nobody revisits is a real operational decision.

| 7 min read

Take the obvious design first, because it is the one everybody writes before they know the word consistent. You have eight cache nodes, so you send each key to hash(key) % 8. It is one line, it is fast, and the distribution is as even as your hash function.

Then you add a ninth node. Every key whose hash modulo 9 differs from its hash modulo 8 now lives on the wrong machine, and that is roughly eight keys in nine. Your cache hit rate goes to approximately 11 percent for as long as it takes to refill, and every one of those misses becomes a read against the database you bought the cache to protect. Adding capacity is what takes you down. That failure is not exotic, it is arithmetic, and it is the entire reason consistent hashing exists.

Karger and colleagues published the fix in 1997: hash nodes and keys into the same circular space, and let each key belong to the first node clockwise from it (Karger et al., STOC 1997). Add or remove a node and only the keys in that node's arc move. Everything else stays where it is.

That is the part every explanation covers, and it is correct. Below it sit three things the diagram does not say, and all three are operational.

I have not operated a large Dynamo style ring myself. My prior comes from the PhonePe merchant ecosystem, which takes tens to hundreds of millions of requests a day, and from what that volume teaches you about the gap between a uniform design and a uniform workload. Where a claim rests on judgement rather than a measurement, the sentence says so.

A B C A C B A C B A k1 k2 k3 k4 k5 k6 k7 k8 k9 3 physical nodes 10 virtual nodes dashed arcs move if B dies Node A: 4 vnodes Node B: 3 vnodes, owns the dashed arcs Node C: 3 vnodes keys, placed clockwise to the next vnode Assumption: uniform hash, no load feedback. Ownership is the arc ending at a vnode, walking clockwise.
A ring with 3 physical nodes and 10 virtual nodes. The dashed arcs are the keys that move when node B is lost, which is the only thing the ring guarantees. It says nothing about how much traffic those keys carry.

#One: it balances keys, not load

The guarantee is about key ranges. Every statement in the original result is about how many keys move, and how evenly the key space is divided. Nothing in it is about requests, bytes, or CPU.

Production workloads are not uniform over keys. One product, one video, one merchant, one campaign link takes a large multiple of everything else, and a perfectly uniform ring will route all of that traffic to exactly one node, because that is what it is designed to do. Consistent hashing solves the rebalancing problem. It does nothing whatsoever for the hot key problem, and reaching for it when the symptom is a hot shard is one of the more common misdiagnoses I see.

The distinction matters because the two problems have opposite fixes. Rebalancing wants stable ownership: the same key on the same node, so caches stay warm. Hot shards want the opposite: the same key spread across several nodes, so the load divides. You cannot get both from one mechanism, and a design that pretends otherwise has quietly chosen one.

The opposite case, stated plainly: if your node set almost never changes, do not use consistent hashing at all. Fixed capacity with a planned resharding window is better served by explicit range partitioning, because ranges give you scans, ordered iteration, and a partition map a human can read during an incident. The ring buys elasticity, and elasticity is worth real complexity only if membership actually churns.

#Two: the balance is worse than the picture, and the fix has a name

The standard ring picture shows arcs of comfortably similar size. Randomly placed points do not behave like that. Mirrokni, Thorup and Zadimoghaddam put the real bound plainly: the load balancing of consistent hashing is no better than a random assignment of clients to servers, so with n of each you expect many servers overloaded by a factor of order log n over log log n (Consistent Hashing with Bounded Loads, 2016). Their algorithm adds a capacity ceiling: pick a balancing parameter c greater than 1, allow no node above c times the mean, and overflow spills to the next node clockwise, at the cost of a constant expected number of extra moves per update.

Virtual nodes are the older answer to the same problem, and they are the parameter nobody revisits. Assigning each physical node many points on the ring smooths the distribution, which is why Dynamo used them and why the Dynamo paper lists the benefits in terms of failure dispersal and heterogeneous capacity (DeCandia et al., SOSP 2007).

What the paper also records, and what almost no explainer repeats, is that Amazon changed the scheme in production. Their strategy 1, random tokens per node with partitioning by token value, is the design in every tutorial. They moved to strategy 3, a fixed number of equal sized partitions with tokens assigned out of that fixed set, and report that it achieved better efficiency and reduced the membership information held at each node by three orders of magnitude.

That is the single most useful sentence in the paper for anyone building this today, and it is the default I would take: do not hash keys onto nodes. Hash keys onto a large fixed number of partitions, then assign partitions to nodes in a map you can read, log, diff, and move by hand at three in the morning. Partition count becomes a decision you make once, ownership becomes data rather than a function, and rebalancing becomes a scheduled move of whole partitions instead of an emergent property of a hash.

More virtual nodes give smoother load and larger membership state, more gossip, slower failure detection and slower bootstrap. Fewer give the opposite. Picking that number once during a prototype and never looking at it again is not a neutral choice, it is a choice made by whoever wrote the example you copied.

NoYes, overflowownership churn costs hitrateKeyhash(key)Walk clockwise to the nextvirtual nodeOwner: physical nodebehind that vnodeOwner above c times meanload?Serve from owner, cachestays warmNext vnode clockwise withcapacityServe from overflow node,cold for this keyDuplicate copies, extrainvalidationHealth and load feedback
Request path with a capacity ceiling. The overflow branch is the difference between the ring in the diagram and a ring that survives a skewed workload, and it is the part that turns a hash lookup into a stateful decision.

Two things on that diagram are decisions rather than drawing. The capacity test reads live load, which means ownership is no longer a pure function of the key and two clients can disagree about the owner during a load spike. And the dotted cost edge is the thing people forget to price: every overflow creates a second cached copy of the same key, so a ceiling that is set too tight trades a hot node for a fleet wide drop in hit rate.

#Three: removal is the easy case, and return is the expensive one

The diagram shows a node disappearing and its arc moving to the neighbour. Clean. What it does not show is the same node coming back.

A node that returns after twenty minutes holds data that was correct when it left. If ownership snaps back to it on rejoin, it starts serving stale values, so a real system must either invalidate on rejoin, which produces a thundering refill against the store, or hold ownership away until it has caught up, which means the membership view and the ownership view are different things and you now have two states to reason about. This is where an implementation stops being a hash function and becomes a distributed systems problem with a failure detector in it.

The second hidden cost is that "minimal keys move" is a statement about keys, not about bytes or about time. Moving one nth of the key space can mean moving terabytes across a network that is also serving traffic, and during that window your replication factor is degraded, which is precisely when a second failure would be expensive. Capacity events therefore need to be planned for the recovery window, not for the steady state, and my judgement is that the honest planning number is how long a full partition rebuild takes under production load, measured once, written down, and re-measured when the data grows.

Hence the fixed partition map again. Whole partition moves are schedulable, throttleable, observable and reversible. An emergent arc handoff is none of those.

#Where the ring is exactly right

The strongest version of the opposing case: when membership genuinely churns, the ring is unbeaten. Distributed caches where nodes come and go, storage systems that must grow without a maintenance window, load balancers hashing sessions onto backends behind an autoscaler. In all of those, the alternative is a coordination service that has to be consulted on every request, and a hash you can compute locally with no round trip is worth a lot of complexity elsewhere.

There is also a simpler variant worth knowing. If the buckets can be numbered sequentially, jump consistent hash gives better distribution than the ring with no storage at all, in about five lines of code (Lamping and Veach, 2014). The constraint that buckets must be numbered is why it suits data storage more than distributed caching, and that constraint is also exactly what a fixed partition map gives you for free.

So the judgement I would offer: reach for the ring when membership is unpredictable, reach for a fixed partition map when it is not, and in either case know that you have solved where keys live and have not touched how much traffic they bring. The ring diagram is a picture of ownership. Your incident will be about load.

#Sources