Art of Codeartofcode
Lesson 1 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

The picture to keep in your head

3 min read+10 XP

Every question below is answered twice: first at the table, so you can picture it, then in the system, so you know exactly how it works. Each answer ends with a memory code to lock it in.

The picture to keep in your head

A wedding has one long dinner and four hosts. The first plan: guests count off by four, and number 1s go to host 1, number 2s to host 2, and so on. It works, until a fifth host arrives. Now everyone counts off by five, and almost every guest ends up with a different host. Total chaos for one extra person.

Better plan: a big round table. Hosts take seats around it. Each guest also gets a seat, by a fixed rule from their name. A guest is looked after by the first host to their right. When a fifth host sits down, only the guests between that new host and the previous host switch to the newcomer. Everyone else keeps their host. If a host leaves, only their guests move one seat along.

And to stop one host getting a huge stretch of table while another gets a tiny one, each host sits in many seats around the table, scattered all over.

That's consistent hashing: put servers and keys on a circle, and a key belongs to the next server clockwise, so adding or removing a server moves only a small share of keys.

Our running example: the bookstore's cache cluster. About 10 million cached book pages are spread across 4 cache servers. For the Big Book Sale, we add a 5th. How many cached pages suddenly become misses? (Counts are assumptions for practice.)

At the tableIn the system
Counting off by four, then by fiveHash mod N
The round tableThe hash ring
The first host to your rightFinding a key's server
A new host sits down; a host leavesAdding and removing servers
Each host sitting in many seatsVirtual nodes
Your host plus the next two as backupsReplication on the ring
Where wedding planners use thisWhere it's used
"Every host bids; the highest bid wins you"Rendezvous hashing

counting off, the round table, the next host clockwise, many seats and backups mapped to mod N, the ring, lookup, virtual nodes and replication.

Figure: when a host joins or leaves, only the guests next to them change seats.