In Module 14 you met consistent hashing as an idea: add a machine without moving everything. This lesson opens it up. You'll place nodes and keys on a ring by hand, count exactly how many keys move, see why a naive ring is lumpy, and learn how virtual nodes fix that and what they cost.
Tiffin's running example: by now its session and menu cache runs on a cluster of cache servers. Every request computes "which server holds menu:restaurant:4412?" millions of times a minute, and the cluster grows every Friday before the weekend rush.
Why plain modulo hurts
The obvious mapping is server = hash(key) mod N. It spreads keys evenly. The trouble is what happens when N changes. Going from 4 servers to 5 changes the answer for almost every key, because h mod 4 and h mod 5 agree only by luck.
| Change | Keys that move with mod N |
Keys that move with a ring |
|---|---|---|
| 3 to 4 servers | about 3/4 (75%) | about 1/4 (25%) |
| 10 to 11 servers | about 10/11 (91%) | about 1/11 (9%) |
| 100 to 101 servers | about 99% | about 1% |
For a cache, "almost every key moves" means almost every lookup misses at once, and the database behind it takes the full dinner-time load. That's the stampede from Module 3, triggered by a routine scale-up.