Why Consistent Hashing?

You have N cache servers and a million hot keys. The obvious router is one line:

It is balanced, stateless, fast — and it detonates the moment N changes. Watch one key whose hash is 37:

N=4:                  37 % 4 = 1   -> node 1
add one node, N=5:    37 % 5 = 2   -> node 2   (different!)

How bad is it across ALL keys? A key stays put only when h % 4 == h % 5, which happens exactly when h % 20 < 4 — 4 residues out of 20, so 20% of keys survive. Adding one server to four moves 80% of your data. In general, growing from N to N+1 nodes remaps N/(N+1) of all keys — the bigger the cluster, the closer a "small" scale-up is to a total reshuffle (100 to 101 nodes moves ~99%).

For a cache fleet this is a production incident: every moved key is a miss, hit rate collapses, and the full read load lands on the database the cache was protecting. This exact failure is why consistent hashing exists (Karger et al., 1997, born from Akamai's CDN work). Its promise: when membership changes by one node, only about K/N of your K keys move — the theoretical minimum, since a new node must own something.

Who runs on it:

• memcached clients, via libketama's hash ring
• Dynamo-family stores — DynamoDB, Cassandra, Riak — partition their keyspace on a ring
• CDN request routing (Akamai and descendants): same object, same edge cache
• DHTs (Chord, IPFS): the same ring idea, fully decentralized

Deterministic hashes only

One rule before any code: placement hashes must be deterministic. Python's builtin hash() is salted per process (PYTHONHASHSEED) — the same string hashes differently on every run and on every machine. Route with it and two clients will disagree about where every key lives, and yesterday's cache is unreachable today. Real systems use MD5 (ketama), MurmurHash3 (Cassandra), or xxHash. This course uses a hash you can check on paper:

hsum("apple") = 97+112+112+108+101 = 530 and hsum("banana") = 609. With 3 buckets, apple lands in 530 % 3 = 2 and banana in 609 % 3 = 0; grow to 4 and apple stays at 530 % 4 = 2 while banana moves to 609 % 4 = 1. One key of two remapped by one resize — and that's a lucky draw.

Your exercise

Implement the demonstration. KEYS records the working set, BEFORE <n> prints each key's bucket under hsum(key) % n, AFTER <n> prints the new buckets plus how many keys changed bucket since the last BEFORE. Format is exact: <key>: <bucket> (colon, one space), keys in sorted order, final line moved=<count> with no spaces. The grader catches three specific mistakes. Using Python's hash() instead of the byte sum — the first visible test demands exactly apple: 2 and banana: 0, which only hsum produces. Counting a key as moved when it kept its bucket — AFTER 4 following BEFORE 3 must print moved=1: apple stayed at 2, only banana moved. And a hidden test runs BEFORE 3 then AFTER 3 — same modulus — expecting moved=0; if your AFTER counts unconditionally, that one fails.