Consistent Hashing
Mapping keys and nodes onto a ring so adding a node moves only ~K/N keys, not all of them.
Consistent hashing places servers and keys on the same hash ring; a key belongs to the next server clockwise. Adding or removing a node only remaps the keys in its arc — on average K/N — instead of the whole keyspace, which is why it backs distributed caches and databases.
Worked example: with plain hash(key) % N, growing from 4 to 5 servers changes the modulus for nearly every key, so almost the whole cache misses at once — a stampede on your database. On the ring, adding a 5th node only pulls the keys in one arc (~1/5 of them) off their current owners; everything else stays put. Gotcha: one point per server makes the ring lumpy — some servers own huge arcs and run hot. Real systems give each server many virtual nodes so arcs even out and a dead node’s load spreads across many survivors, not one neighbor.