Consistent hashing

The problem it solves

You have a keyspace and a set of nodes, and you need a rule that maps one to the other. The obvious rule is hash(key) % n. It is fast, it is one line, and it is uniform. It also has a property that makes it unusable for anything stateful: change n and the mapping changes for nearly every key.

That is not a rounding error. Go from four nodes to five and roughly 80% of keys move — for a cache, that means an 80% miss rate the instant you add capacity, and the origin behind it takes a flood at exactly the moment you were trying to relieve pressure. For a sharded database it means moving four fifths of your data. The failure is worst precisely when you most need to act: during a scale-up, or when a node has died and the ring is reconfiguring itself under load.

Consistent hashing is the fix, and its promise is a single number: adding one node to a ring of n moves about 1/n of the keys, and no others.

The mechanism

Take the output space of your hash function and treat it as a circle. Hash each node — not each key — to a point on that circle. Now hash a key, land somewhere on the circle, and walk clockwise until you hit a node. That node owns the key.

Everything follows from that one construction. Add a node and it lands at one point on the circle; it steals the keys between its own position and the previous node clockwise of it, and nothing else moves, because every other key still walks to the same node it walked to before. Remove a node and its arc merges into its clockwise successor; again, nothing else moves. The keys that move are exactly the keys in one arc, and an arc is about 1/n of the circle.

The construction has a weakness you can see immediately if you think about it geometrically. Four random points on a circle do not divide it into four equal arcs — they divide it into four arcs of random size, and the largest is typically several times the smallest. So the ring is stable but not balanced, and one node ends up owning far more than its share.

The fix is virtual nodes: hash each physical node to many points instead of one. With forty tokens per node, the arcs each node owns are forty independent random slices, and by the law of large numbers their sum is close to fair. Virtual nodes also give you weighting for free — a machine with twice the capacity gets twice the tokens — and they make removal smooth, because a departing node’s keys spread over many successors rather than dumping onto one.

What the simulation shows

The ring and modulo hashing are computed over the same keyspace at the same time, so the comparison is not an argument. Let the run reach the moment a node is added and read the churn panel: the ring moves about a fifth of the keys, modulo moves nearly all of them. Same keys, same hash function, different mapping rule.

The second thing to try is one token per node. The ring is still stable — adding a node still moves one arc — but look at the keys-per-node panel. The bars are ragged. One node owns a third of the keyspace and another owns a tenth, and no amount of adding nodes fixes it, because the problem is not the count, it is the randomness of the arcs. Turn the tokens back up and watch the bars level out. That is the entire argument for virtual nodes, and it is not the argument most people give when asked.

The numbers worth carrying

Adding the (n+1)-th node to a ring of n moves 1/(n+1) of the keys. Four to five: a fifth. Ten to eleven: a bit under a tenth. Under modulo, the fraction that moves is 1 - 1/n — approaching all of them as your cluster grows, which is the wrong direction for a rule to get worse in.

For virtual nodes, the standard deviation of a node’s share falls like 1/sqrt(tokens). That is why the numbers you see in real systems cluster in the 100–256 range: a hundred-odd tokens gets the imbalance down to a few percent, and going further buys diminishing accuracy for linearly growing ring-lookup cost and memory.

Where it breaks down

A ring balances keys, not load. If one key is hot, the ring sends it to one node, and the ring has no opinion about that. Consistent hashing is a solution to rebalancing, not to skew — see the hot-key scenario on the load balancing page, and the same failure from the storage side on sharding.

The ring also cannot help you with the contents of the arcs it moves. Moving a fifth of the keys is cheap for a cache, which can simply miss and refill. For a database it means physically copying a fifth of your data across the network, and the ring’s mathematical elegance does nothing about the bytes. That is why real data stores add a layer of indirection: keys hash to a fixed, large number of partitions, and partitions are assigned to nodes by a directory. Rebalancing then moves whole partitions and the map is explicit rather than derived.

Finally, the ring does not tell you about replication. A key needs to live on more than one node, and the standard construction — walk clockwise and take the next R distinct physical nodes — has a subtlety: without the “distinct physical” clause, virtual nodes will happily place all your replicas on the same machine.

What people get wrong

“Virtual nodes make it consistent.” They do not; the ring is consistent with one token per node. Virtual nodes make it balanced. Being able to separate the two properties is the difference between having read about consistent hashing and having implemented it.

“It guarantees even distribution.” It guarantees even distribution of hash values, in the limit, with enough tokens. Distribution of traffic depends on key popularity, which the ring never sees.

“Rebalancing is free.” The mapping change is free. Moving the data is not.

“Any hash function will do.” It needs decent avalanche behaviour. This simulation originally used plain FNV-1a and the ring was measurably lumpy for keys sharing a prefix — a realistic key pattern — because FNV’s low bits do not diffuse well. A finalisation step fixed it. Use murmur3, xxhash, or something else with published avalanche properties, not the first thing that returned a number.

In production

Amazon’s Dynamo paper popularised the ring, and DynamoDB, Cassandra and Riak all descend from it — Cassandra calls virtual nodes num_tokens and defaults to 16 in recent versions with a smarter allocation algorithm that beats naive random placement. Memcached clients (ketama) use a ring with around 160 points per server. Envoy’s RING_HASH exposes minimum_ring_size for the same reason.

The main alternative worth knowing is Maglev hashing, from Google’s load balancer paper: it builds a lookup table rather than a ring, giving near-perfect balance and O(1) lookup, at the cost of moving slightly more than the theoretical minimum on a topology change. It is a better fit for stateless balancing; the ring is a better fit when you own data and every moved key costs a copy.

The follow-up questions

“Why does modulo move nearly everything?” — Because the modulus is in the mapping. Changing n changes the arithmetic for every key, not just for the keys near a boundary. There are no boundaries.

“How many virtual nodes and why?” — Enough that 1/sqrt(tokens) is an imbalance you can tolerate; in practice 100 to 256, and be ready to say the trade is memory and lookup cost.

“A node dies. Walk me through what happens.” — Its arcs merge into clockwise successors, which is 1/n of the keyspace redistributed across many nodes rather than dumped on one — but only because of virtual nodes. Then say what happens to the cache hit ratio during that window, and how the origin copes.

“Can you get consistent hashing with weights?” — Yes: tokens proportional to capacity. Say it, because heterogeneous fleets are the normal case and the uniform-ring answer quietly assumes they are not.