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
Memory card and where the analogy breaks
3 min read+10 XP
The memory card (tear this page out)
| # | Question | Memory code |
|---|---|---|
| 28.1 | Mod-N problem? | Count off again, and everyone changes host |
| 28.2 | Hash ring? | Seat everyone at a round table, by name, not by count |
| 28.3 | Finding a key's server? | Look to your right; the first host you see is yours |
| 28.4 | Adding and removing? | A new host only takes the guests right beside them |
| 28.5 | Virtual nodes? | Give every host many seats, and the work evens out |
| 28.6 | Replication? | Your backups are the next different hosts, not the same host in another seat |
| 28.7 | Where it's used? | Wherever helpers come and go, seat the crowd at a round table |
| 28.8 | Rendezvous hashing? | Every host bids for every guest; the highest bid wins |
The whole chapter in one line: Put servers and keys on one circle, give each key to the next server clockwise, use many virtual nodes for even load, replicate to the next distinct servers, and only about 1/N of keys move when servers change.
Where the analogy breaks
- Guests choose seats by name at random. Hash positions are random too, so without many seats per host, the split is uneven, which is the whole reason for virtual nodes.
- A guest who changes host just walks over. A key that moves means a cache miss or copying data over the network, which is why minimising movement matters.
- Everyone at a table sees who's sitting where. In a cluster, clients must agree on the list of servers, so membership needs its own mechanism (configuration, gossip or a coordinator).
Quick check
Five questions on this chapter. Pick an answer, then check it.
quiz