Four cache servers, and you pick one with hash(key) % 4. Clean, even, fast.
Then traffic grows and you add a fifth.
The modulo changes, so almost every key now resolves to a different server — around 80% of them move. Every cache is suddenly wrong. Every request misses. The database takes the full load of a system that spent months assuming it was cached.
Consistent hashing changes the question. Instead of dividing keys among servers, put both on the same circle.
Hash the key to a point on the ring. Hash each server to a point on the ring. Walk clockwise from the key, and the first server you meet owns it.
Add a server now and it lands somewhere on that ring, taking only the slice between itself and its neighbour. Roughly a fifth of the keys move instead of four fifths.
Real implementations hash each physical server onto the ring 100–200 times rather than once. The spread evens out, and when a server dies its load scatters across many neighbours instead of landing entirely on whoever comes next.
