Art of Codeartofcode
Lesson 9 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.8 What is rendezvous hashing, in brief?

3 min read+10 XP

At the table: A different trick: for each guest, every host makes a bid, using a fixed rule from the guest's name and the host's name. The highest bid wins the guest. If a host leaves, only the guests they had won need to look at the next-highest bid; if a new host joins, they win only the guests for whom their bid is the highest.

In the system: Rendezvous hashing (also called highest random weight, HRW) computes hash(key, server) for every server and picks the server with the largest value:

python
  • Minimal movement: like the ring, adding a server moves only about 1 ÷ (N + 1) of keys, all to the new server. In the chapter's code, going from 4 to 5 servers moves about 20% of keys, all to cache-4.
  • Even spread without virtual nodes, and no ring to maintain.
  • Easy replicas: take the top N scores.
  • Cost: a lookup is O(N) (score every server), which is fine for tens of servers and costly for thousands (there are tree-based variants for that).

Another option to know by name: jump consistent hash (Google, 2014): tiny, fast and perfectly even, but it maps keys to numbered buckets 0..N−1 and works best when servers are only added or removed at the end.

Memory code: "Every host bids for every guest; the highest bid wins."