Consistent hashing

When you shard data or a cache across N nodes, you need a function from key to node. The obvious choice — hash(key) % N — is a trap at scale: it couples the mapping to the count of nodes, so changing the count rewrites the mapping for nearly every key.

keys 0..9 with hash(k) = k

N = 4:  k % 4  -> 0 1 2 3 0 1 2 3 0 1
N = 5:  k % 5  -> 0 1 2 3 4 0 1 2 3 4
        almost every key moves to a new node

Why modulo rehashes everything

Adding one node (N → N+1) changes the divisor, so hash(key) % N and hash(key) % (N+1) disagree for roughly (N-1)/N of all keys. For a cache that means a near-total cold start: every moved key is a miss, every miss hits the source at once — exactly the stampede from the last lesson, triggered by a routine scale-up. For a database it means moving almost all your data to rebalance one node. The operation that should cost 1/N of your data costs nearly all of it.

The ring and virtual nodes

Consistent hashing places both nodes and keys on the same circular hash space (0 to 2^m). A key is owned by the first node found walking clockwise from the key's position. Add or remove a node and only the keys in the arc between that node and its predecessor move — about 1/N of keys, not all of them.

ring:  ...--[A]----key--[B]--------[C]--...
       key walks clockwise -> owned by B

add D between key and B:
       ...--[A]----key--[D]--[B]----[C]--...
       only keys in A..D's arc remap; rest untouched

One node per position gives lumpy arcs — some nodes own huge slices, others tiny ones. Virtual nodes fix this: each physical node is hashed to many points on the ring (e.g. 100–200 vnodes each). With many small arcs per node, the law of large numbers smooths ownership toward even, and removing a node spreads its load across all survivors instead of dumping it on a single neighbor. This is the machinery behind Dynamo-style stores, Cassandra, memcached client routing, and CDN edge selection.