Art of Codeartofcode
Lesson 2 of 15

28. Consistent Hashing

1
The picture to keep in your head
2
28.1 What's the problem with mod N?
3
28.2 What is the hash ring?
4
28.3 How do you find a key's server?
5
28.4 What happens when you add or remove servers?
6
28.5 What are virtual nodes?
7
28.6 How does replication work on the ring?
8
28.7 Where is consistent hashing used?
9
28.8 What is rendezvous hashing, in brief?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
28. Consistent Hashing

28.1 What's the problem with mod N?

3 min read+10 XP

At the table: Counting off by four works perfectly, right up until a fifth host arrives. Then you count off by five, and nearly every guest has a new host. All the chatting and familiarity is lost.

In the system: The simplest way to spread keys over N servers is server = hash(key) mod N. It spreads keys evenly and every client can compute it. The trouble is changing N:

  • Going from 4 to 5 servers, a key stays put only if hash mod 4 happens to equal hash mod 5. That's about 1 in 5 keys.
  • So about 80% of keys move. In the chapter's code, 79.8% of 100,000 cached book pages map to a different server.

a table of hashes: mod 4 and mod 5 disagree for most keys.

Figure: changing N reshuffles almost everything.

For a cache, a moved key is a miss. You add a server to handle more load, and at that exact moment 4 in 5 lookups miss and go to the database (a self-inflicted stampede, Chapter 13). For a database or storage system, a moved key means copying data between machines: 80% of everything, over the network.

The same happens when a server fails (N drops by one) and when it comes back. In general, going from N to N + 1 servers moves about N ÷ (N + 1) of the keys.

Memory code: "Count off again, and everyone changes host."