Art of Codeartofcode
Lesson 5 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.4 What happens when you add or remove servers?

3 min read+10 XP

At the table: A new host sits down between two others. Only the guests sitting between the previous host and the newcomer now look right and see the newcomer first. Everyone else sees the same host as before. If a host leaves, their guests just look further right to the next one.

In the system:

adding server E takes over only the arc between D and E, which used to belong to A.

Figure: only the arc next to the change moves.

  • Add a server: it takes over the keys between its position and the previous server's position, which used to belong to the next server clockwise. No other key moves.
  • Remove a server (or it fails): its keys move to the next server clockwise. No other key moves.

On average, adding one server to N moves about 1 ÷ (N + 1) of keys: the new server's fair share. In the chapter's code, going from 4 to 5 servers moves 22.9% of keys (close to the ideal 20%), versus 79.8% with mod N. And every moved key goes to the new server; no keys shuffle between old servers.

For the bookstore's 10 million cached pages, that's about 2 million misses instead of about 8 million.

One catch: with a single point per server, a removed server's whole load lands on one neighbour, which may then be overloaded. Virtual nodes fix that too (28.5).

Memory code: "A new host only takes the guests right beside them."