Consistent Hashing

The problem: hash mod N

When one server can't hold all the keys or answer all the lookups, you spread them over several servers. The simplest rule is server = hash(key) mod N: every client works out the same server without asking anyone, and the keys spread evenly.

The trouble starts when N changes. A key stays on its server only if its hash gives the same answer mod 3 and mod 4, which happens for 3 of every 12 hash values. So going from 3 servers to 4 moves about 3 in 4 keys. From 10 servers to 11, about 10 in 11 keys move.

Six keys, with hashes from 0 to 99 to keep the numbers small:

key   hash   mod 3   mod 4
kim    14      2       2     stays
eve    28      1       0     moves
leo    47      2       3     moves
max    66      0       2     moves
ned    78      0       2     moves
zoe    93      0       1     moves

Five of the six move. For a cache, every moved key is a miss. Say the app makes 20,000 lookups a second and the cache answers 90% of them, so 2,000 reach the database. Right after the switch, 3 in 4 of the 18,000 hits turn into misses: about 15,500 lookups a second reach a database that answers about 5,000, three times its limit, until the cache fills up again. For a sharded database, every moved key is data copied to another server.

How it works: the ring

Bend the range of hash values into a circle. The example uses positions 0 to 99; real systems use the far bigger range of a hash function. Hash each server (its name or address) onto the same ring as the keys. The rule: a key lives on the first server clockwise from its position, and after 99 the ring wraps round to 0.

servers: A at 5, B at 35, C at 60

B owns 6 to 35          kim (14), eve (28)
C owns 36 to 60         leo (47)
A owns 61 round to 5    max (66), ned (78), zoe (93)

Each server owns the slice of the ring that ends at it. Look at ned: C at 60 is nearer, but the rule is clockwise, so ned walks on past 99 and lands on A.

Adding and removing a server

Add server D at 85. Only the keys between C (60) and D now meet D first: max and ned move from A to D. Every other key stays where it was, so 2 of the 6 keys move, where mod 4 moved 5. A new server takes only the slice that ends at it, all from one neighbor. With the servers spread evenly, the fourth takes about a quarter of the keys.

Removing a server is the same rule. If B crashes, kim and eve keep walking clockwise past B's old spot and land on C. A and D don't change at all. For a cache, that's a slice of misses instead of a flood; for a database, one slice is copied instead of most of the data.

The catch: uneven slices

Server positions come from a hash, so slice sizes are left to chance. With the four servers at 5, 35, 60 and 85, B owns 30 positions and A only 20. After B's crash it gets worse: C owns 6 to 60, 55 of the 100 positions, and holds 3 of the 6 keys, while A owns 20 and holds only zoe. A crash dumps a whole slice on one neighbor, which may then be the next to fall over.

Virtual nodes

The fix is to hash each server several times, so it sits at several points on the ring: A1, A2, A3 and so on. Each point is a virtual node. A server now owns several small slices spread round the ring, and their sizes average out. In the example, four servers get three points each:

positions owned (of 100)    A    B    C    D
one point each              20   30   25   25
three points each           26   24   26   24
three each, B crashed       33    -   34   33

When B crashes, each of its three points hands its slice to the next point clockwise, and those belong to three different servers: C, A and D. B's load spreads over everyone instead of landing on one neighbor. A new server likewise takes a small slice from many servers, and a bigger machine can get more points. Real systems give each server many more points than three. The price is a bigger table of points to keep and search.

Replicas on the ring

To keep copies of each key, a common design stores it on its owner and on the next servers clockwise. With 3 copies on the four-server ring, eve (28) lives on B, C and D. With virtual nodes, skip points of a server that already has a copy, so the copies land on different machines. If B fails, C, the next server clockwise, already has a copy of eve, so nothing is lost.

The choices and their trade-offs

• hash mod N: simple and even, but changing N moves most keys. Fine when the number of servers never changes.
• A ring, one point per server: a change moves one slice, but slices are uneven and a crash loads one neighbor.
• A ring with virtual nodes: the usual choice: even slices and crashes spread over many servers, for a bigger lookup table.

Where it shows up in design interviews

Anywhere keys are spread over servers that come and go:

• Distributed caches: servers are added for busy times and fail without warning, and most keys stay in place.
• Sharded databases and key-value stores: Cassandra and other Dynamo-style stores place data on a ring, and Amazon's Dynamo paper (2007) described it. It's the heart of "design a key-value store".
• Load balancers that hash by user: the same user keeps reaching the same server, and a change moves only a slice of the users.

It's the wrong tool when any server will do, or when queries need ranges of keys: hashing scatters neighboring keys, so "every order between two dates" would ask every server.

Common interview questions

Why not just use hash mod N?

Because changing N moves almost every key: from 3 servers to 4, about 3 in 4 keys land somewhere else. In a cache that's a flood of misses on the database; in a database it's most of the data copied over the network.

What happens when you add a server?

It lands at one point on the ring and takes the keys between the server before it and itself, all from the server after it. With virtual nodes, it takes small slices from many servers instead.

Why do you need virtual nodes?

With one point per server, slice sizes are random, so some servers get far more keys than others, and a crash dumps a whole slice on one neighbor. Several points per server even the slices out, spread a lost server's keys over many servers, and let bigger machines take more.

How do you find which server holds a key?

Keep the points sorted by position and binary search for the first point at or after the key's hash, wrapping to the first point when the hash is past the last one. That takes O(log n) steps for n points.

How do replicas work on a ring?

Store each key on its owner and the next servers clockwise, skipping points of servers that already hold a copy. When a server fails, the next server clockwise already has a copy of its keys.

Summary

• hash mod N moves about 3 in 4 keys when a 4th server joins: a flood of cache misses.
• The ring: servers and keys hash onto one circle, and a key lives on the first server clockwise.
• Adding or removing a server moves only one slice of keys: 2 of 6 in the example.
• Uneven slices: with one point each, a server can end up with 55 of 100 positions.
• Virtual nodes even the slices out (24 to 26 each) and spread a crashed server's keys over the others.
• Replicas: copies on the next servers clockwise.