Consistent Hashing

Symptom

You shard a cache across ten servers with the obvious rule:

server = servers[hash(key) % len(servers)]

It works. Then you add an eleventh server, and % 10 becomes % 11.

Every key now maps somewhere else. Not one tenth of them — essentially all of them. A key landing on the same server after the change is a coincidence with probability about $1/11$, so roughly 91% of your cache is instantly invalid. Every request misses, every miss hits the database, and the database, sized for a 95% cache hit rate, now receives twenty times its provisioned load and falls over.

You have just taken an outage by adding capacity. The remedy people reach for is to never resize, or to resize during a maintenance window with a slow warm-up script, both of which are working around a data structure rather than fixing it.

Statement

Map both keys and servers into the same space, a circle of hash values $[0, 2^{32})$. A key belongs to the first server encountered walking clockwise from the key’s position.

Consistent hashing. With $n$ servers, adding or removing one server remaps only $O(1/n)$ of the keys in expectation. All other keys keep their assignment.

The contrast is the whole result. Modular hashing moves $\Theta(1)$ fraction of keys on a resize; consistent hashing moves $\Theta(1/n)$, which is the information-theoretic minimum since the new server must receive some keys and those keys must come from somewhere.

Argument

Why the ring works. Each server hashes to a point on the circle and owns the arc ending at it, running counterclockwise back to the previous server. Adding a server splits exactly one arc into two: the new server takes the portion of one existing server’s range. No other arc is touched, because no other boundary moved.

Removing a server merges its arc into the next one clockwise. Again, one boundary changes.

That is the entire mechanism. The insight is to make the assignment depend on the positions of the servers rather than on their count, so that changing the count perturbs one neighbourhood instead of the global function.

The variance problem, and why the naive version fails. With $n$ servers placed at random on the circle, arc lengths are not equal. They follow the spacings of $n$ uniform points, and the expected maximum spacing is $\Theta(\log n / n)$ rather than $1/n$. This is exactly the balls-into-bins result (T009) reappearing: random assignment gives a max load logarithmically above the mean.

Simulating 20,000 random placements of 10 servers, the median largest arc is 2.78 times the average arc, and the median ratio of largest to smallest arc is 39. Half the time, one server owns nearly three times its share while another owns a fortieth of what its busiest peer does. Worse, removing a server hands its entire arc to one neighbour, so that neighbour’s load roughly doubles in a single step — precisely at the moment the system is already degraded.

Virtual nodes fix it, and the mechanism is averaging. Hash each physical server to $v$ points on the circle instead of one. A server owns $v$ small arcs scattered around the ring rather than one large one. The load is now the sum of $v$ independent samples, so the relative standard deviation falls as $1/\sqrt{v}$.

The numbers are decisive. Simulating 10 servers again, the median busiest server owns 3.64× its fair share at $v = 1$, 1.21× at $v = 100$, 1.14× at $v = 256$, and 1.07× at $v = 1000$. Dynamo used around 100 to 200 virtual nodes per physical server, Cassandra defaulted to 256, and Riak used a fixed ring of 64 or 256 partitions, and these numbers all come from the same $1/\sqrt{v}$ curve rather than from folklore: 256 vnodes is where the worst-case overload falls into the teens of percent, which is roughly the headroom a capacity plan already carries.

Virtual nodes buy a second thing that matters more operationally: when a server fails, its $v$ arcs are absorbed by $v$ different neighbours, so the failed node’s load is spread across the cluster instead of landing on one machine. The failure of one node adds roughly $1/(n-1)$ to everyone rather than 100% to someone.

Cost of the lookup. Store the $nv$ virtual node positions in a sorted array or balanced tree; a lookup is a binary search for the successor, $O(\log(nv))$. For $n = 100$ servers at $v = 256$ that is 25,600 entries and about 15 comparisons, on the order of a hundred nanoseconds. The ring is small enough to sit in every client’s memory, which is why consistent hashing is usually done client-side with no coordination at all.

Rendezvous hashing does the same job differently. For each key, compute $h(\text{key}, \text{server})$ for every server and pick the maximum. Adding a server changes the winner only for keys where the new server’s score is highest, which is $1/(n+1)$ of them, and the load is naturally balanced with no virtual nodes. The cost is $O(n)$ per lookup rather than $O(\log nv)$, which is why it is preferred for small $n$ and weighted cases, and the ring for large clusters.

Jump consistent hash (Lamping and Veach, 2014) achieves the same guarantee in $O(\log n)$ time and zero memory, using a clever recurrence over the sequence of resizes. Its limitation is that it maps to bucket numbers $0..n-1$ and cannot remove an arbitrary server, only the last one, which suits sharded storage with an ordered bucket list and not a cluster with arbitrary failures.

Forbids

Adding a node to a modular-hashed cluster without a mass invalidation. The $\bmod n$ scheme has no locality in $n$, and no amount of tuning changes that.

Perfect balance from a single hash point per server. The $\Theta(\log n/n)$ maximum arc is a theorem about uniform spacings, not a defect of your hash function.

Zero movement on a topology change. The new server must own some keys, and those keys must move. $O(1/n)$ is optimal, not merely good.

Uniform load with non-uniform key popularity. Consistent hashing balances the keyspace, not the traffic. One hot key sits on one server no matter how many virtual nodes you configure.

Does not forbid

It does not forbid weighted clusters. This is the misreading that stops teams using it in heterogeneous fleets. A server with twice the capacity simply gets twice as many virtual nodes. The ring handles mixed hardware naturally, and Cassandra’s num_tokens is set per node for exactly this.

It does not require the ring to be centrally managed. Every client can compute the ring from the membership list, so lookups need no coordination service. Dynamo, Cassandra, Riak, and memcached client libraries such as ketama all do this, and it is why a cache lookup costs no network round trip beyond the one to the data.

It does not mean data movement is free during rebalance. Only $1/n$ of keys move, and moving them still consumes disk and network. Cassandra’s bootstrap streaming is throttled for this reason, and adding a node to a large cluster is an hours-long background operation rather than an instant one.

It does not solve hot keys, and conflating the two wastes effort. The fix for a hot key is replication or a local cache in front, not more virtual nodes. Facebook’s memcache leases and client-side hot-key detection exist because consistent hashing is silent on the problem.

It does not conflict with replication. The standard extension walks the ring clockwise past the first server to the next $R-1$ distinct physical servers, giving a preference list. Combined with quorums (T065), that is essentially the whole Dynamo architecture.

Boundary

• Balances keyspace, not load. Uniform key access is assumed. Skewed access needs a different tool.
• Virtual node count is a real tradeoff. More vnodes means better balance and a larger ring to store, distribute, and gossip. Cassandra’s shift from 256 to 16 default tokens happened because gossip and repair costs scale with the token count.
• Membership must be agreed, eventually. Two clients with different views of the ring route the same key differently. This is tolerable for a cache and not for a database, which is why storage systems layer gossip or a consensus-backed membership service underneath.
• Assumes a good hash. A hash with poor distribution ruins arc uniformity, and adversarial keys can be crafted to collide onto one node unless the hash is keyed (T104).
• Ordered scans are lost. Hashing destroys key order, so range queries must hit every node. Systems needing ranges use ordered partitioning instead and accept the rebalancing complexity, which is the split between DynamoDB’s hash keys and HBase’s region splits.

The idea to carry: make the mapping depend on where the servers are, not how many there are, and a resize becomes a local edit instead of a global one.

Read next