Consistent Hashing and What Resharding Costs a Cache Tier

A cache tier larger than one process needs a rule that maps a key to a node. The obvious rule is hash(key) mod N, and it is a trap: change N and almost every key changes node. In a cache, a key that changes node is a key that is not found, so a resharding operation that would be a metadata change in a database becomes a wave of misses against the backing store. Consistent hashing exists to make the fraction of keys that move proportional to the fraction of capacity that changed, and the schemes built on top of it differ mainly in how they trade that property against memory, balance, and simplicity of implementation.

The modulo cliff

With N nodes and a uniform hash, each node owns 1/N of the key space. Add one node and the modulus becomes N+1. A key keeps its assignment only when hash(k) mod N == hash(k) mod (N+1), which happens for roughly 1/(N+1) of keys. Going from ten nodes to eleven moves about ten elevenths of the keys — roughly 91 percent. Every moved key is a cache miss, and the backing store receives them all within the time it takes the tier to repopulate, which is exactly the stampede problem multiplied across the entire working set.

The same arithmetic applies to losing a node: with modulo, the departure of one node remaps every key, not just the keys that node held. A cache tier that survives a node failure by remapping should lose only that node’s share and re-read it; modulo loses the whole cache.

The ring, and the keys that move

Consistent hashing places both nodes and keys on the same circular hash space, typically by hashing to a 32-bit or 64-bit value and interpreting it modulo the space size. A key belongs to the first node at or after its position, walking clockwise. Adding a node inserts one point in the ring and takes over the arc between its predecessor and itself; only keys in that arc move, and their count is proportional to the arc’s length, which on average is 1/(N+1) of the space.

The original formulation in the Karger et al. paper also gives each node several positions, for reasons that are about balance rather than mapping. A single point per node gives each node an arc whose length is exponentially distributed, so with ten nodes the largest share can easily be two or three times the average. That imbalance means the least-loaded node sits idle while the most-loaded one evicts, and the tier’s effective capacity is set by the worst node.

Virtual nodes fix the variance: each physical node is placed at v points, so its total load is the sum of v exponential arcs, which concentrates around the mean. The standard deviation of a node’s share falls roughly as 1/√v, so a hundred virtual nodes per physical node brings the standard deviation to about ten percent of the mean, and a thousand brings it to about three. The price is memory and lookup cost: the ring holds N × v entries, and a lookup requires a search over them, which is a binary search on a sorted array — logarithmic in N × v, cheap — or a scan of a small array if the count is modest.

Virtual nodes also change what a node addition moves. Because the new node’s virtual points are scattered, its takeover is spread across all the existing nodes rather than concentrated on one neighbour, which means the additional load is evenly withdrawn instead of one node suddenly serving half as much. For a cache, that matters less than for a storage system: the misses are distributed either way, but the per-node request rate during rebalancing is smoother.

Rendezvous hashing and jump hashing

Two alternatives achieve the same movement bound with different mechanics.

Rendezvous, or highest-random-weight, hashing computes a hash of the key combined with each node’s identity and assigns the key to the node with the highest value. No ring, no virtual nodes, no shared state: any client can compute the mapping from the node list alone, which makes it attractive when clients and servers can disagree about membership. The cost is O(N) hash computations per lookup, which is fine for tens of nodes and unacceptable for thousands. Adding a node moves only the keys for which the new node wins, which is the same 1/(N+1) bound.

Jump consistent hash, described by Lamping and Veach, computes the bucket in O(ln N) time with no memory beyond a counter, using a sequence of pseudo-random jumps that skip buckets with decreasing probability. It is ideal for a fixed, numbered set of buckets that only grows at the end, such as a sharded store where shards are numbered and added in order. It does not support arbitrary removal from the middle, which rules it out for a cache tier where nodes fail and are replaced by identity.

The choice among them is mostly about where the mapping code runs. Ring-based schemes need the ring built and shared; rendezvous needs only the node list; jump needs only the shard count. All three beat modulo by the same asymptotic factor, and all three still move real keys when capacity changes.

Fixed slots: the cluster approach

Redis Cluster takes a different route: the key space is divided into a fixed 16,384 slots, each key’s slot is CRC16(key) mod 16384, and slots rather than keys are assigned to nodes. Resharding migrates slots one at a time, and during migration the cluster can redirect a client for a key whose slot is in flight. The fixed slot count decouples the mapping from the node count, so adding a node means moving a subset of slots, and the fraction of keys that move is the fraction of slots reassigned — controllable and incremental rather than all-at-once.

The cost is in the details. Multi-key operations must stay within one slot, which is why the client-side convention of hash tags exists: a substring in braces, as in {user:42}:profile and {user:42}:sessions, is the only part hashed, forcing related keys into the same slot. Without tags, a batch of reads for several related keys can be split across nodes and either fail or require client-side fan-out. Slot migration also has a per-key cost that the slot abstraction hides: each key must be serialized, sent, and acknowledged, so migrating a slot holding many small keys is slower per byte than migrating a few large ones.

The other consequence of fixed slots is that a slot is the unit of failure. When a node dies, its slots are reassigned, and the keys in them become misses at the new owner. The cluster’s replication may serve them instead if a replica is promoted, which converts the miss wave into a failover delay rather than a cache flush — but only if replication was keeping up.

What resharding actually costs

The movement bound is the easy part. The operational cost has three components.

The first is the miss wave. Moving 1/(N+1) of the keys means re-reading that fraction from the source, and doing it in the time it takes clients to notice the new mapping. A tier at 90 percent hit ratio serving a million reads per second moves roughly a hundred thousand reads per second to the source if a tenth of the keys move at once. Staged migration — one slot or one virtual node at a time, with a pause — turns a spike into a plateau, which is the difference between a capacity problem and an outage.

The second is double ownership during migration. A key in flight may exist at both the old and the new owner, and a write during that window may reach only one. For a cache this is benign, because the value is derivable; for a cache holding session data or computed results with side effects, it is not. The usual rule is that migration must be safe for concurrent reads and writes, which in practice means routing all requests for a migrating slot to one owner and only switching after the copy is complete.

The third is that the mapping change is a code-and-configuration change visible to every client. A client with a stale node list sends requests to the wrong node; a ring-based client with a stale ring does the same. Both need to detect the error and refresh, and the refresh must not itself be a thundering herd of metadata requests. This is the same problem as request coalescing one level up: the mapping is a cached value with its own stampede.

Planning for growth

The practical consequence is that cache capacity should be added in a way that keeps the moved fraction small and predictable: many small virtual nodes rather than few large ones, slots migrated in batches, and a target of adding capacity before the tier is at its memory ceiling rather than after. The alternative — running the tier hot and resharding under pressure — combines the miss wave with the eviction pressure that made resharding necessary, and the source absorbs both. Sizing the tier so that steady-state occupancy leaves headroom is the same arithmetic that governs hit ratio, taken up in hit ratio arithmetic and working-set sizing.