Why Consistent Hashing?

You have N cache servers and a million hot keys, and every client must agree on which server holds which key. Before you build the structure that fixes this, you will build the obvious router and measure exactly how it breaks when the fleet changes size.

The one-line router

server = hash(key) % N

It is stateless, fast and balanced, and it is what most people write first. The trouble starts when N changes. Take a key whose hash is 37:

N = 4:   37 % 4 = 1   -> server 1
N = 5:   37 % 5 = 2   -> server 2   (moved)

How many keys survive a resize from 4 to 5? A key keeps its server only when h % 4 == h % 5. Both remainders depend on h % 20 (4 x 5), so look at one full cycle:

h % 20 :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
h % 4  :  0  1  2  3  0  1  2  3  0  1  2  3  0  1  2  3  0  1  2  3
h % 5  :  0  1  2  3  4  0  1  2  3  4  0  1  2  3  4  0  1  2  3  4
same?  :  =  =  =  =  x  x  x  x  x  x  x  x  x  x  x  x  x  x  x  x

Only the first four residues agree, so 20% of keys stay and 80% move. The general rule: going from N to N+1 servers keeps 1/(N+1) of the keys, so N/(N+1) of them move. Growing 99 to 100 servers remaps 99% of your data. The bigger the fleet, the closer a "small" scale-up is to a total reshuffle.

Why that is an incident, not a nuisance

A remapped key is a cache miss. When 80% of keys move at once, the hit rate collapses and the full read load lands on the database the cache was protecting. The fix is a placement rule where adding a server moves only the keys the new server must own. With K keys and N servers that is about K/N, which is the theoretical minimum, because a new server has to own something. That rule is consistent hashing (Karger et al., 1997, from Akamai's CDN work). It sits under memcached client libraries (libketama), Dynamo-style stores such as Cassandra and Riak, and CDN request routing. The next lessons build it.

The hash this course uses

Every client must compute the same placement, so the hash must be deterministic across processes, machines and languages. A language's built-in string hash is not: Python salts it per process, and C++ std::hash is implementation-defined. Production systems use MD5 (ketama), MurmurHash3 or xxHash. For the first two lessons we use one you can check on paper: add up the UTF-8 byte values of the string.

hsum("red")  = 114 + 101 + 100       = 315
hsum("blue") =  98 + 108 + 117 + 101 = 424

With 3 servers red lands on 315 % 3 = 0 and blue on 424 % 3 = 1. Resize to 4 and red moves to 315 % 4 = 3, blue to 424 % 4 = 0. Both moved, an unlucky draw, but a typical one.

Two properties of hsum matter. It works on bytes, not characters: é is two bytes (195 and 169), so hsum("café") is 662, not 531. And it is weak: ab and ba both sum to 195. Later lessons replace it with a hash that mixes.

Common mistakes

• Using the built-in hash. The first visible test expects exactly apple: 2. Only the byte sum produces that.
• Counting every key as moved. BEFORE 3 followed by AFTER 3 changes nothing, so it must print moved=0.
• Sorting naturally. Keys print in plain string order, so user10 comes before user2.
• Counting characters. A key with an accent hashes over its bytes.

Your exercise

Build the demonstration: record a key set, print each key's bucket under one modulus, then print the buckets under another and count how many keys changed. The starter reads the commands for you.