Consistent hashing

Why hash(key) % N wipes the cache on a resize

Naive sharding sends a key to node = hash(key) % N, where N is the node count. It spreads keys evenly while N holds still, but N sits inside the formula, so changing N recomputes the target for almost every key. Stanford's teaching example puts the damage at roughly (N-1)/N of all keys moving when you add or remove a single node, that is, nearly all of them.

For a cache this is worse than it sounds. A relocated key is a miss, so remapping almost every key at once turns a resize into a mass eviction: the next wave of reads all miss and stampede the origin. libketama's author said the pre-consistent-hashing mod approach "effectively wiped the entire cache."

Wrong "mod-N is fine, the cache warms back up." The warm-up is the problem, because every key misses at the same moment and the origin absorbs the full read load. Right keep the mapping stable so that changing N relocates only a small, bounded slice of keys.

The hash ring and the clockwise successor

Consistent hashing (Karger et al., 1997) treats the hash output range as a circle, for example 0 to 2^32 - 1, where the top value wraps back to the bottom. Each node is hashed to a position on the ring. A key is hashed onto the same ring and belongs to the first node reached by walking clockwise, its successor. Each node owns the arc between it and its predecessor.

ring (clockwise):   ... 0x91a2 [keyK] ... 0xB0FF [nodeB] ...
owner(keyK) = walk clockwise from hash(keyK) to the first node >= it (wrap at the top)
            = nodeB

When a node leaves, only its arc moves, to that arc's clockwise successor. When a node joins, it takes over the slice of its new neighbor's arc that now falls before it. Every other node is untouched.

Virtual nodes smooth an uneven ring

One random position per node makes lumpy arcs: some nodes own a wide arc and run hot, others a sliver. The fix is to hash each physical node onto many positions, called virtual nodes (or tokens). A node's load becomes the sum of many small random arcs, which averages out, and bigger machines get more positions so they carry proportionally more load. A virtual node is another ring position for the same machine, not an extra server and not a second copy of the data.

How little moves when a node joins or leaves

With K keys over N nodes, each node owns about K/N. Adding the nth node relocates about a 1/n fraction, roughly that one node's K/N worth, and leaves the rest in place. That bounded movement, not the ring picture itself, is the reason to reach for consistent hashing.

The fraction that moves versus the load that is lumpy

Two different numbers get confused here. The fraction of keys that relocate when the nth node joins is about 1/n, independent of how many keys K you store; K only scales the absolute count (about K/N keys move). Plain mod-N instead relocates about (n-1)/n of keys on any change, which is why it cannot front a cache.

Balanced movement is not the same as balanced steady-state load. One random position per node leaves arcs uneven, so some nodes run hot even when little is moving. Virtual nodes fix the steady state: hashing each physical node to many positions makes its load the average of many small arcs, which the law of large numbers smooths. On a join or leave, that averaging also spreads the moved keys roughly evenly across the remaining nodes instead of dumping them on one neighbor.

The virtual-node count is a trade-off

More virtual nodes per machine give smoother load but cost more metadata and slower operations. Cassandra shows the tension in its defaults: num_tokens was 256 for years, and 4.0 lowered it to 16 (CASSANDRA-13701), because 256 vnodes per node made repair and token allocation expensive. 4.0 pairs the lower count with allocate_tokens_for_local_replication_factor for even allocation, and DataStax has recommended as few as 8. More vnodes is not strictly better; you tune the count against operational and repair cost.

Where consistent hashing runs in production

Amazon Dynamo partitions its keyspace with consistent hashing plus virtual nodes and replicates each key at the N clockwise successor nodes, the preference list. Cassandra inherits the same token-ring model (Murmur3 maps a partition key into the partitioner's signed 64-bit range). memcached clients use ketama/libketama: each server sits at roughly 100 to 200 points (commonly 160) on a 0 to 2^32 continuum, and a key walks clockwise to the next point, so every client computes the same mapping with no coordination.

Redis Cluster uses 16384 slots, not a ring

Wrong "Redis Cluster is consistent hashing under the hood." Its own docs say it does not use consistent hashing. A key maps by HASH_SLOT = CRC16(key) mod 16384 into one of 16384 fixed slots (16384 = 2^14, so 14 of CRC16's 16 bits are used), and each master owns a roughly contiguous subset of slots. Right there is no ring, no random positions, and no clockwise-successor lookup. The slot map is small enough to ride inside gossip heartbeats, which is the reason for a fixed slot count rather than a ring. Adding a node moves whole slots between masters as an explicit admin operation (MIGRATING and IMPORTING states with MOVED/ASK redirection); a master failing instead promotes its replica for the same slots. Hash tags let {...} force user:{123}:profile and user:{123}:account into one slot for multi-key operations. Redis before 3.0 did shard client-side with consistent hashing, and Cluster replaced that with slots.