At the end of the last lesson, hash(key) % N looked perfect until N changed. Add one machine and most keys move. This lesson is about the trick that fixes that, called consistent hashing. It's one of the most quoted ideas in system design, and the core of it fits on a napkin.
We'll cover the idea and how systems use it here. The details of the ring, virtual nodes and the alternative called rendezvous hashing get a full treatment in Module 19.
The problem, with real numbers
Tiffin caches restaurant menus in Redis (Module 3). By now the menu cache is 10 cache servers, and each app server picks one with:
const server = servers[hash(restaurantId) % servers.length]
At 7:45pm on a Friday, the cache is running hot, so someone adds an 11th server. What fraction of menus now map to a different server?
A key stays put only if hash % 10 and hash % 11 happen to be equal. For a random hash, that's true about 1 time in 11. So roughly 10 out of 11 keys, about 91%, move.
For a cache, "move" means "miss". The new server for each key has never seen it. In one instant, 91% of menu lookups fall through to the database at the start of the dinner rush. That's exactly the stampede from Module 3, triggered by trying to add capacity.
For a database, it's worse. "Move" means copying 91% of all the data between machines.
What we want: when you go from N machines to N + 1, only about 1 / (N + 1) of the keys should move. That's the new machine's fair share, and nothing more.