Consistent Hashing, Virtual Nodes & Rebalancing

Why hash mod N is the wrong primitive

The naive way to place keys across N nodes is node = hash(key) mod N. It spreads load evenly, and it is a disaster the moment N changes. Go from 10 nodes to 11 and the modulus changes for almost every key, so roughly 10 of 11 keys map to a different node. For a cache that means a near-total miss storm that stampedes the database; for a database it means moving nearly the whole dataset to add one machine. Since adding and removing nodes is the entire point of horizontal scale, mod N is the wrong primitive.

The ring

Consistent hashing fixes the remap cost. Imagine a ring of hash values from 0 to 2^32 - 1. Hash each node to a position on the ring, and hash each key to a position too. A key is owned by the first node clockwise from its position. Now add a node: it lands somewhere on the ring and takes over only the keys between it and its counter-clockwise neighbor. Remove a node: its keys pass to the next node clockwise. Either way you move only about 1/N of the keys, and only between adjacent nodes, instead of remapping the world. This is why Dynamo, Cassandra, Riak, and most distributed caches are built on it.

Plain consistent hashing has two problems. First, with few nodes the ring is lumpy: random placement means some nodes own huge arcs and others tiny ones, so load is uneven (a 2x imbalance is easy). Second, when a node leaves, all its load dumps onto a single neighbor rather than spreading.

Virtual nodes, bounded load, and rendezvous

Virtual nodes (vnodes) solve both. Instead of one point per physical node, give each physical node many tokens (say 128 or 256) hashed to many ring positions. Now each physical node owns many small arcs scattered around the ring, so load smooths out toward even, and when a node fails its many arcs are inherited by many different neighbors, spreading the rebalance rather than crushing one node. Vnodes also give you weighting: a machine with 2x the RAM simply gets 2x the tokens.

Bounded-load consistent hashing adds a cap: each node may hold at most (1 + epsilon) times the average load. When a key's target node is already at its cap, placement spills to the next node clockwise. This bounds hotspots at the cost of some keys not living on their "natural" node. Reach for it when even vnodes leave a hot node.

Rendezvous hashing (highest-random-weight, HRW) is a simpler alternative for some jobs: to place a key, compute hash(key, node) for every node and pick the highest. Same minimal-movement property without maintaining a ring, and selecting the top-k replicas is trivial (take the k highest). The tradeoff is O(N) per lookup, so it suits smaller or bounded node sets, like choosing replicas or a load-balancer backend, rather than a thousand-node ring.

Interview nuance: the phrase to earn is "only ~1/N keys move." If you are asked how a cache cluster survives a node loss and you say hash mod N, you have just described the failure. Say consistent hashing with vnodes, quantify the movement, and note that replicas are placed on the next distinct physical nodes clockwise.

hash mod N: add node -> ~all keys remap  (miss storm / full reshuffle)

consistent hash ring (with vnodes):
      [n2]...[n1]
     /            \      key -> first node clockwise
  [n3]    o key    [n1]  add node: steals ~1/N keys from one arc
     \            /      vnodes: many small arcs -> even load, spread rebalance
      [n2]...[n3]

Recap: hash mod N remaps nearly every key on resize; consistent hashing moves only ~1/N and only between neighbors; virtual nodes smooth load, spread rebalancing, and enable weighting; bounded-load caps hotspots; and rendezvous hashing is a ring-free alternative for small replica-selection cases.