Consistent Hashing

Plain hash(key) % N sharding (from the Sharding lesson) has one specific, expensive problem: changing N — adding or removing a single node — changes the result of mod N for almost every key, meaning almost the entire dataset has to move. Consistent hashing is the technique that fixes exactly this, and it shows up constantly, because it's also how a sharded cache like Redis or a load balancer's consistent-hashing routing decides which node owns a given key.

The ring

Both nodes and keys get hashed onto the same circular space (commonly visualized as a ring of hash values, 0 to 2^32 - 1). A key belongs to whichever node is the first one found going clockwise from the key's position on the ring. Adding a new node only affects the keys between it and the next node clockwise — everything else on the ring keeps its existing owner, unlike mod N where every key's owner can change at once.

Only a fraction of keys move on a change

Removing a node only reassigns the keys that node owned — to whichever node is next clockwise — leaving every other key's owner untouched. This is the entire point: with N nodes, adding or removing one moves roughly 1/N of the keys, not close to all of them.

Virtual nodes fix the uneven-distribution problem

A plain ring with a handful of real nodes can distribute keys unevenly by chance — one node might end up owning a much longer arc of the ring than another, simply based on where its hash happened to land. The fix is virtual nodes: each physical node is hashed onto the ring multiple times under different virtual identities (e.g. node-3#1, node-3#2, node-3#3, ...), so its total share of the ring is an average across many positions instead of one, smoothing out the imbalance. More virtual nodes per physical node means a more even distribution, at the cost of more ring entries to maintain.