Consistent Hashing and What Changes When a Node Joins

A cluster that maps keys to nodes with hash(key) % N is correct exactly until N changes. Add one node to a ten-node cluster and the modulus becomes eleven; a key that hashed to bucket 7 either stays at 7 or moves elsewhere, and it stays only if the two moduli happen to produce the same remainder. The fraction that moves is roughly N/(N+1), so about 9 of every 10 keys change owner. The cluster is fully functional at the end, but it has just rewritten nearly the entire dataset to add one machine’s worth of capacity, and the migration itself is the period of highest risk.

The property that modulo lacks

The property wanted is monotonicity: when the set of nodes grows, a key either stays where it was or moves to one of the new nodes, never to an existing node. Modulo hashing violates it because every key’s destination is a function of the whole node set. Consistent hashing restores it by making the destination a function of the key and of a small neighbourhood of the node set.

The construction is a circle. Hash every node identifier into the same space as the keys, for example the 32-bit output of a hash function mapped onto a ring of $2^{32}$ positions. Hash a key the same way. The key belongs to the first node at or after its position, walking clockwise. Adding a node inserts one point on the ring; only keys that fall between the new point and its predecessor change owner, and they all move to the new node. Removing a node moves its keys to its successor. Nothing else is affected, because no other key’s successor changed.

import hashlib, bisect

def ring_pos(token: str, bits: int = 32) -> int:
    h = hashlib.sha256(token.encode()).digest()
    return int.from_bytes(h[:4], "big") % (1 << bits)

class Ring:
    def __init__(self, nodes):
        # Virtual nodes: each physical node claims many ring positions.
        self.points = sorted((ring_pos(f"{n}#{i}"), n) for n in nodes for i in range(64))

    def owner(self, key: str) -> str:
        pos = ring_pos(key)
        i = bisect.bisect_left(self.points, (pos, ""))
        return self.points[i % len(self.points)][1]   # wrap to the start of the ring

The number of keys that move is now proportional to the new node’s share of the ring, not to the size of the dataset. If the new node owns $1/(N+1)$ of the ring, that fraction of keys migrates, and that fraction is the capacity it is being added to provide. The same argument holds for removal, which is what makes node decommissioning a bounded operation.

Why one point per node is not enough

With a single point per node, the ring is divided into N arcs whose lengths are determined by the hash values. The arc lengths are not equal. For a hash function behaving as a random oracle, the arc between consecutive points has an exponential distribution with mean $1/N$, so the largest arc in a cluster of ten nodes is routinely several times the average. The node that owns it receives several times the average load. The largest arc shrinks only as fast as $O(\log N / N)$ as N grows, so the ratio of the worst node’s load to the average actually grows, like $\log N$: a cluster of a hundred nodes still has nodes carrying several times the median.

The standard remedy is virtual nodes: each physical node claims many ring positions, using a distinct token per position. With $V$ positions per node, the load on a node is the sum of $V$ exponential random variables, so its standard deviation relative to its mean falls like $1/\sqrt{V}$. A few hundred virtual nodes per physical node brings the load spread into the range of a few percent, which is why the technique is essentially universal in systems built on a ring. The cost is memory for the ring structure and a slightly larger number of smaller migration units.

There is a second reason for virtual nodes beyond load balance: they decouple the ring from the physical topology. A physical node can be weighted by giving it more tokens, which is how heterogeneous hardware is handled without special cases. A node with twice the capacity receives twice the tokens and owns twice the ring, and the expected key count follows.

The lookup structure and its failure modes

The ring is a sorted array of positions; lookup is a binary search for the first position at or after the key’s hash, which is $O(\log VN)$ with the array in memory. In a distributed implementation no node holds the whole ring, so the lookup is either a cached copy of the ring metadata refreshed on membership change, or a routing hop through peers. The Dynamo design, which popularised the ring for key-value storage, keeps the ring metadata at every node and resolves a request locally in the common case, accepting a propagation delay when membership changes.

The failure modes are all about that propagation delay. A node that has just joined is not yet known to every peer, so some keys still route to their previous owner; the previous owner either serves the request or forwards it. A node that has just left is still in cached rings, so requests route to a dead endpoint and must be retried against the next live position. The correctness requirement is that the retry goes to the successor of the failed position, not to an arbitrary peer, because that is the node which owns the key once the failed node is removed. Retrying against a random peer can produce a read from a node that never held the data.

The wrap-around case is a persistent source of bugs. A key hashing above the last ring position belongs to the first position, and code that indexes into the array without taking the modulo will either crash or return the highest node instead of the lowest. The symptom is subtle: a small fraction of keys, chosen by hash, land on the wrong node, and only those keys misbehave.

Hot keys defeat ring balance

Ring balance is a statement about the distribution of keys, and it says nothing about the distribution of requests. A key that receives a disproportionate share of traffic lands on exactly one node under a single-copy ring, and no amount of virtual-node balancing helps, because the load being balanced is not proportional to the key count. The ring’s guarantee is that each node owns approximately the same fraction of the key space; the workload may not be spread evenly over that space.

Two mechanisms address it, and they solve different problems. The first is to keep the ring but bound the number of keys a node may own: a bounded-load variant caps each node’s share at a multiple of the average and redirects overflow keys to the next position, which converts an unbounded per-node load into a bounded one at the cost of a more complex lookup. The second is to replicate the hot key across several positions and let requests spread over the copies, which is what a cache layer in front of the store does.

The distinction matters when reasoning about capacity planning. A ring with virtual nodes gives a statistical guarantee about bytes per node, which is what a rebalancing operation needs. It gives no guarantee about requests per node, which is what a latency target needs. Both numbers have to be measured separately, and a cluster sized from the first will be unbalanced on the second whenever the workload has a head.

Ring placement versus rule-based placement

A ring is one answer to placement, not the only one. A rule-based scheme computes the destination directly from the key and a description of the cluster rather than by searching a ring. CRUSH, the placement function in Ceph, hashes the object identifier together with a numbering of the cluster’s hierarchical buckets and derives the target devices without any lookup table, which removes the metadata propagation problem entirely: every client that knows the cluster map computes the same answer. The cost is that the map must be recomputed and redistributed when topology changes, and the function must be deterministic across implementations, which constrains what it can use.

Ring placement keeps a small amount of state and tolerates arbitrary hashing; rule-based placement keeps no state but requires the cluster description to be an input. The ring’s advantage is flexibility in what can be a node; the rule-based scheme’s advantage is that adding a device moves only the data whose placement rule actually mentions that device, which can be a much smaller set than a ring arc. The details of that computation are in the CRUSH placement rule.

Membership change as the real workload

The steady-state behaviour of either scheme is uninteresting; the interesting behaviour is during rebalancing. A ring add moves $1/(N+1)$ of the keyspace, and those keys must be copied, verified, and deleted from the old owners. The copy must not disturb foreground reads, which means the migration is rate-limited, and the rate limit determines how long the cluster spends with some keys present on two nodes. During that overlap, reads may return either version, so the migration needs a notion of which copy is authoritative: usually the new owner, with the old owner forwarding until the copy completes.

The durability arithmetic interacts here in a way that is easy to miss. A key mid-migration has two copies in the cluster, but they may be in the same failure domain, because the ring assigned the new owner without consulting the topology. Placement by hash and placement by failure domain are separate constraints, and a ring that satisfies one can violate the other. Systems that need both layer the topology constraint on top of the ring, either by rejecting a new owner that shares a domain with the old one or by using the ring only to order candidates and then filtering by domain, which is how replica selection works in ring-based stores that place multiple copies.