28. Consistent Hashing
1
The picture to keep in your head2
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 breaks11
Practice: five levels12
Interview questions13
Solutions14
Sources15
Code lab28. Consistent Hashing
28.2 What is the hash ring?
3 min read+10 XP
At the table: Instead of counting off, seat everyone at a round table. Hosts get seats by a fixed rule. Guests get seats by the same rule. Nobody's seat depends on how many hosts there are.
In the system: Consistent hashing (Karger and colleagues, 1997) maps both servers and keys onto the same circle of hash values (for example 0 to 2⁶⁴ − 1, wrapping round from the largest value back to 0):
- Each server is placed at
hash(server name). - Each key is placed at
hash(key). - A key belongs to the first server clockwise from it (28.3).
Figure: servers and keys share one circle; each key goes to the next server clockwise.
The key property: a key's position never depends on how many servers there are. Only the servers' positions do. So changing the set of servers only affects keys near the change (28.4).
Memory code: "Seat everyone at a round table, by name, not by count."