Adding a node without moving everything

Ten thousand keys, user:1 to user:10000, each drawn at the angle of its 32-bit MurmurHash3 and coloured by the node that owns it. The band around them is the hash ring: every arc belongs to the first virtual node clockwise from it. Hover a key to trace that walk.

When node-5 joins, it takes over only the arcs that end at its own points, each one from a single neighbour: the next virtual node clockwise. The keys in those arcs, 20.5% of them, are the only ones that change owner; the replay shows them flip from their old owner’s colour to node-5’s. Colour by mod N instead and the very same change moves 80.1%.

mod N. A key stays put only if h mod 4 = h mod 5, which holds for one hash in five. Growing from N to N + 1 nodes therefore moves N/(N + 1) of all keys (80.1% measured for 4 → 5), and three of every four moves shuffle keys between nodes that did not change at all.

Ring. A newcomer moves exactly the keys it now owns, about 1/(N + 1). How much it owns is luck that virtual nodes average out: a node’s share is a sum of V random arcs, so its spread shrinks roughly as 1/√V. Across 50 independent five-node rings the standard deviation of node shares was 76% of a fair share at V = 1, 22% at V = 16, 8% at V = 100 and 4% at V = 500.

Rendezvous. Every node scores the key with its own seeded hash and the highest score wins. A newcomer only takes the keys it outbids everyone on, so movement is minimal again, with no ring to store and nothing to tune; the price is N hashes per lookup instead of one binary search.

Apache Cassandra places data on a token ring and gives each node many tokens (virtual nodes, set by num_tokens). Amazon’s Dynamo paper (2007) popularised that design; consistent hashing itself goes back to Karger et al. (1997), rendezvous hashing to Thaler and Ravishankar (1996).

Redis Cluster skips the ring: 16,384 fixed hash slots (CRC16 of the key, mod 16,384), and resharding moves whole slots between nodes explicitly. Kafka’s default partitioner hashes a record’s key with murmur2 modulo the partition count, which is why adding partitions to a topic changes where existing keys’ new records land.

I’ve worked with all three — Redis, Kafka and Cassandra. Knowing which of these schemes sits underneath is how you predict what a resize will cost before you run it.