Art of Codeartofcode
Lesson 7 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.6 How does replication work on the ring?

3 min read+10 XP

At the table: Your main host looks after you, but if they step out, the next two hosts to the right already know your order. That only works if those are different people: if a host sitting in many seats is also "your backup", you have no backup at all.

In the system: To keep N copies of each key (Chapter 14), walk clockwise from the key and pick the first N distinct physical servers. Dynamo calls this the preference list: the first is the coordinator, the rest hold replicas.

walking clockwise, skip points from servers already chosen: B, D, A, not B, B, D.

Figure: with virtual nodes, skip points that belong to servers you already have.

With virtual nodes, the next few points often belong to the same server. Taking the next N points blindly puts two "replicas" on one machine. In the chapter's code, about half of all keys end up with a duplicate replica that way (the Level 4 bug); skipping already-chosen servers fixes it.

Real systems go further:

  • Skip servers in the same rack or availability zone, so one power or network failure can't take all copies.
  • Combine with quorums (Chapter 14): write to W of the N replicas, read from R, with W + R > N for overlap.
  • When a server is down, a write can go temporarily to the next healthy server (hinted handoff) and be passed back later.

Memory code: "Your backups are the next different hosts, not the same host in another seat."