Consistent Hashing Rings and Virtual Node Counts

Modulo hashing fails at exactly the moment a cluster becomes interesting. Adding the tenth machine to a nine-machine cluster reassigns ninety per cent of the keys, because the partition of a key depends on the modulus and any change to the modulus re-rolls nearly every assignment. Consistent hashing, introduced for web caches and later adopted by key-value stores, changes the placement rule so that a membership change touches a fraction of the keys proportional to the size of the change rather than to the size of the data set. The idea is small. The engineering around it, particularly the number of virtual nodes, is where the useful detail lives.

Placing keys and nodes on one circle

Both keys and nodes are hashed into the same space, conventionally the integers modulo 2^32 or 2^64, and that space is treated as a circle by wrapping at the top. Each node is assigned one or more positions on the circle. A key belongs to the first node position encountered when walking clockwise from the key’s own position.

import bisect, hashlib

def h(x: str, bits: int = 32) -> int:
    return int.from_bytes(hashlib.sha1(x.encode()).digest()[: bits // 8], 'big')

class Ring:
    def __init__(self, nodes, vnodes: int = 256):
        self.pos = sorted((h(f'{n}#{i}'), n) for n in nodes for i in range(vnodes))
        self.keys = [p for p, _ in self.pos]

    def owner(self, key: str) -> str:
        i = bisect.bisect(self.keys, h(key)) % len(self.keys)
        return self.pos[i][1]

The owner lookup is a binary search over the node positions, so it costs O(log(N·V)) with N nodes and V virtual nodes each, and the position list is the entire routing table. A node learns the ring by gossip or by reading a coordinator, and any node can compute any key’s owner from that same list, which is why the scheme suits a peer-to-peer topology where no component holds authoritative state.

The property that motivates the design is what happens on membership change. Removing a node deletes only its positions. The keys that pointed at those positions now walk clockwise to the next surviving position, and every other key keeps its owner. With N nodes, each node owns roughly 1/N of the circle, so removing one moves about 1/N of the keys. Adding a node inserts new positions and takes over the arcs that precede them, again about 1/N of the keys. Compare this with the n/(n+1) of modulo hashing, which converges to one as the cluster grows; the ring’s moved fraction converges to zero.

The moved keys are also contiguous in the ring’s order, which matters operationally. A joining node inherits a set of arcs, and the data for each arc can be streamed from its predecessor as one sequential transfer. The migration is expressible as “fetch the arc between these two hash values”, which is a range read, not a scatter of individual keys. Whether that range read is efficient depends on how the storage engine is partitioned internally, the tension described in Hash Partitioning and the Range Query It Destroys.

Why one position per node is not enough

A single position per node gives a correct but badly unbalanced ring. If node positions are drawn independently and uniformly, the arc lengths between consecutive positions are the spacings of a uniform random sample, and their distribution is far from equal. With N points on a circle, the expected largest arc is roughly (H_N / N) of the circle, where H_N is the Nth harmonic number. For N = 10 that is about 0.3 of the circle: one node owns nearly a third of the keys while the average node owns a tenth. For N = 100 the largest arc is about 0.052, still five times the mean.

The variance has a second, subtler cost. A node that owns a large arc receives a large share of the requests, and a node that owns a small arc is idle. Adding capacity does not fix the imbalance, because the imbalance is a property of the sample, not of the total. Removing the largest-arc node helps only until the next draw.

Virtual nodes fix the distribution by averaging. Each physical node claims V positions instead of one, and its share of the circle becomes the sum of V spacings. Summing V independent spacings produces a distribution whose relative standard deviation falls as 1/sqrt(V). With V = 1 the coefficient of variation is around 1; with V = 100 it is around 0.1, so a node’s share is within roughly ±10 per cent of the mean for most draws. With V = 256 it is around 0.06.

# expected largest node share of the circle: mean 1/n, plus a max-of-n term
import math
def worst_share(n: int, v: int) -> float:
    # each node's share is a sum of v spacings; CV of that sum is 1/sqrt(v)
    return (1 / n) * (1 + math.sqrt(2 * math.log(n) / v))

print(worst_share(10, 1))     # ~0.31
print(worst_share(10, 256))   # ~0.11

The trade is memory and metadata. Every virtual node position is an entry in the routing table that every participant must hold and gossip about. A cluster of 200 nodes with 256 positions each has 51,200 entries, each perhaps 40 bytes including the address, so a couple of megabytes of routing state. That is affordable. Ten thousand nodes with the same count is 2.56 million entries, and the table becomes the dominant memory cost of the membership layer and a significant cost to propagate on every change.

The second cost is migration granularity. A node’s V positions are scattered around the circle, so joining a node means fetching V separate arcs, each from a different predecessor, in V parallel streams. With V = 256 a join is 256 small transfers rather than one large one. Each transfer has a fixed setup cost, and the sources are many different machines, so the join is more network-wide but less concentrated. Raising V improves balance and worsens the per-join coordination; the usual compromise in deployed systems is a few hundred positions, or a fixed large number of logical partitions decoupled from the node count.

Virtual nodes as the unit of assignment

Once virtual nodes exist, it is natural to stop treating them as an artefact of the hash and start treating them as the assignable object. The ring holds a fixed set of positions, generated once from a fixed token space, and physical machines are assigned sets of those positions by a controller. Membership change becomes an assignment problem rather than a hashing problem.

This is the arrangement in wide use: the token space is fixed at creation, often at a few thousand or a few tens of thousands of tokens, and the mapping from token to machine lives in a metadata service. Adding a machine means assigning it tokens, and the controller can choose which tokens to move so as to minimise the number of sources and balance the resulting load. It can also respect rack or zone boundaries, ensuring that no machine’s token set is concentrated in one failure domain, which the pure hash gives no control over.

The cost is that the assignment table is now state that must be agreed upon, which pulls in the machinery of Routing Metadata Staleness and the Cost of a Wrong Guess. A pure ring is stateless apart from the membership list; a token assignment is a configuration that every client must eventually learn. The benefit is that rebalancing can be planned, throttled, and audited, instead of being an emergent consequence of a hash function.

There is a middle position, and it is common in caches: keep the ring pure, but make the ring’s hash function depend on a version, so that a controlled rehash moves a planned fraction of keys. This is not consistent hashing any more; it is a scheduled remap, and it has the same all-or-nothing character as a modulus change for the keys it touches.

Skew that the ring cannot fix

Consistent hashing balances the number of keys, not the load. Three sources of imbalance survive any improvement to the ring.

Key-size variance: a key that maps to a 4 KB value and a key that maps to a 4 MB value occupy the same arc. If values differ by orders of magnitude, equal key counts mean unequal bytes. A store that balances on count will overload the node holding the large values.

Access-frequency variance: a popular key receives many requests regardless of which arc holds it. The ring spreads keys, and the hot key stays hot on one node. The remedy is to split the key deliberately, or to cache it, and both change the data model rather than the placement.

Node-capacity variance: machines of different sizes should own different fractions of the circle. A pure ring assigns arcs by hash and ignores capacity, so heterogeneous hardware is wasted. Weighted assignment, giving a larger machine more tokens, restores the correspondence, and it is one of the reasons token assignment moved to a controller.

Each of these is a mismatch between the quantity being balanced and the quantity that matters. The ring balances positions. The operator cares about bytes, requests, and cost, and those three are only weakly correlated with position. Cassandra’s original design acknowledged this by keeping the ring but relying on an external tool to compute a balanced token assignment for the machines actually present, rather than trusting the hash to do it.

Replication sits on top of the ring

The ring describes ownership, and a replicated store needs more than one owner. The standard construction walks the circle clockwise from a key’s position and takes the first R distinct physical nodes, skipping repeats that arise when one machine holds several adjacent tokens. The walk is over distinct machines, not distinct positions, which is why a machine holding a contiguous block of tokens does not get counted twice.

The number of positions therefore interacts with the replication factor. If R is 3 and every machine holds a single token, the three replicas are three machines with adjacent positions, and a correlated failure that takes out a rack takes out replicas together unless the assignment was built with failure-domain awareness. With virtual nodes, the replicas are the three machines owning the next three positions, which are likely to be different machines but still arbitrary with respect to topology. Making replication respect topology is again a job for the assignment layer, not the hash.

Reads then have a choice: contact the first replica and fall back, or contact all and reconcile. Both paths need the key’s replica set computed identically by every participant, which means the membership view must agree. A node that computes a different replica set from the same key will send a read to a machine that does not hold the data, and the failure looks like data loss until the views converge.