Art of Codeartofcode
Lesson 4 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.3 How do you find a key's server?

3 min read+10 XP

At the table: Sit in your seat and look to your right. The first host you see is yours.

In the system:

  1. Keep the server positions in a sorted list.
  2. Hash the key.
  3. Binary search for the first server position greater than the key's hash.
  4. If you run off the end, wrap around to the first server.
python

That's O(log n) per lookup, where n is the number of points on the ring. Every client with the same list of servers computes the same answer independently, without asking a coordinator.

Use a stable hash (MD5, MurmurHash, xxHash), the same in every process and language. Python's built-in hash() changes between runs, so two servers would disagree about where keys go; the chapter's code uses MD5 for this reason.

Memory code: "Look to your right; the first host you see is yours."