CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 2 of 8 · 2 min read

The rehashing problem

Why the simple formula breaks when the number of servers changes.

Think of a school that seats pupils at four tables by the last digit of an ID number divided by four. A table is closed for repair, so three tables are left, and the rule changes to division by three. Almost every pupil must find a new seat.

The book "System Design Interview" begins with this problem. With n cache servers, a common way to balance the load is serverIndex = hash(key) % N, where N is the size of the server pool. It works when the pool size is fixed and the data is evenly spread. Trouble starts when servers are added or removed. If one server goes offline, N drops by 1. The hash of a key stays the same, but the remainder changes, so a key maps to a different server. The book's result: most keys are redistributed, not just those on the lost server. Most clients then look on the wrong server, which causes a storm of cache misses.

A worked example (hash values made up). Eight keys with these hashes: 3, 8, 13, 18, 23, 28, 33, 38.

Hash Server with N = 4 (hash mod 4) Server with N = 3 (hash mod 3) Moved?
3 3 0 yes
8 0 2 yes
13 1 1 no
18 2 0 yes
23 3 2 yes
28 0 1 yes
33 1 0 yes
38 2 2 no

Six of eight keys, 75 percent, move. Server 1 held only two keys (13 and 33), 25 percent. The least that had to move was those two. The formula moved three times more than needed. With a cache, each moved key is a miss, so the database gets a flood of reads.

Consistent hashing

Consistent hashing is a way of assigning keys to servers so that when a server is added or removed, only a small fraction of the keys change server. On average only k ÷ n keys are remapped, where k is the number of keys and n the number of servers (or slots).

Example: with 10 servers and 1,000,000 keys, adding an 11th server moves about 1,000,000 ÷ 11 ≈ 91,000 keys, not 909,000.

The book quotes this definition and contrasts it with traditional hash tables, where a change in the number of slots remaps nearly all keys.

Check yourself:

  • Keys with hashes 10, 11, 12, 13, 14, 15. How many change server when N goes from 3 to 2?
  • Why is a storm of cache misses a problem?