Start practising

SYSTEM DESIGN · CONCEPTS · DATABASES · EPISODE 22

Consistent Hashing

Why hash(key) % N falls apart the moment you add a server, the hash ring that fixes it, how a key finds its node, virtual nodes for balance, and where it runs today: caches, Cassandra, DynamoDB, load balancers.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 13

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

Modulo hashing

Start with the simple version. Three cache servers. To find where a key lives, hash it and take modulo three. Fast, evenly spread, and no state to keep: every client computes the same answer. This is fine, right up until you touch the number three.

The simple way
server = hash(key) % N

N = 3
user:4817 → 1
user:9  → 0
user:77 → 2

fast, even, stateless

Add one server

Add a fourth server. Modulo four gives different answers for about three out of four keys. Each of those keys is now looked up on a server that has never seen it. Three quarters of your cache turns into misses at once, and every miss falls through to the database. You added a server to reduce load and created a stampede. Same story when a server dies.

N = 4
user:4817 → 1   (was 1)
user:9    → 1   (was 0)
user:77   → 1   (was 2)
user:300  → 0   (was 0)

about 3 of 4 keys moved
every moved key = cache miss
misses → the database

The goal

What do we want instead? When we add a fourth server it should take about a quarter of the keys, and the rest should stay exactly where they were. When a server dies, only its keys should move. That is the whole requirement, and a ring delivers it.

What we actually want
  • add a server:
  • only ~1/N of keys move
  • remove a server:
  • only its keys move
  • everything else stays put
  • so the cache stays warm

The ring

Picture the hash space as a circle. Zero to two to the thirty-two, or just zero to three hundred sixty degrees. Hash each server's name and place it on the ring at that angle. Four servers, four points.

Step 1: place the servers
ring = hash space 0 … 2^32
(think 0° … 360°)

hash("node-A") → 0°
hash("node-B") → 90°
hash("node-C") → 180°
hash("node-D") → 270°

Place the key

To find a key, hash it onto the same ring. User forty-eight seventeen lands at sixty degrees. Walk clockwise until you hit a server: B, at ninety. B owns every key between A and itself. Each server owns the arc just before it.

Step 2: find a key
hash("user:4817") → 60°

walk clockwise from 60°
first server you meet: B (90°)

so B owns everything
in (0°, 90°]

Add a server

Now add a server. E hashes to forty-five degrees. It takes only the keys between A and itself; those used to belong to B. Our key at sixty still walks to B. C and D never noticed. Roughly one fifth of the keys moved, exactly what we asked for. Remove a server and the same thing happens in reverse: its arc goes to the next node clockwise, and no one else moves.

Add node E at 45°
E now owns (0°, 45°]
B now owns (45°, 90°]

keys that moved: A → E arc only
user:4817 at 60°: still B

moved ≈ 1/N of keys
C and D: untouched

The catch

One catch. Hashes are random, so the servers do not land evenly. One node might own half the ring, another five percent. Worse: when a node dies, its entire arc dumps onto a single neighbour, which may then die too. We need more points on the ring.

Problem: uneven arcs
  • hashes are random, so
  • servers land unevenly
  • one node might own 50%
  • another 5%
  • and when a node dies, its
  • whole arc hits ONE neighbour

Virtual nodes

Virtual nodes. Instead of one point per server, give each one a hundred or two: hash node A hash one, node A hash two, and so on. Now every server owns many small arcs scattered round the ring, so the load averages out, and when a server dies its keys spread across all the others instead of crushing one. Bigger machine? Give it more virtual nodes.

Virtual nodes
each server gets many points:
hash("node-A#1") → 12°
hash("node-A#2") → 97°
hash("node-A#3") → 203°
… 100–200 per server

arcs average out
a dead node spreads its keys
across ALL the others

Interview answer

The interview answer in four lines. Modulo hashing moves almost everything on resize. Consistent hashing puts servers and keys on a ring, so adding or removing a server moves one over N of the keys. Virtual nodes keep the ring balanced. And for fault tolerance, store each key on the next K nodes clockwise too, so a dead node's data is already on its neighbour.

In the interview
  • "How do you distribute keys
  • across N cache servers?"
  • 1. modulo breaks on resize
  • 2. consistent hashing ring
  • 3. virtual nodes for balance
  • 4. replicate to next K nodes
  • for fault tolerance

In the wild

Where it runs. Memcached and Redis client libraries, the ketama algorithm. Cassandra, Riak and DynamoDB partition data on exactly this ring with virtual nodes. Load balancers use it to keep a client on the same backend. CDNs use it to decide which edge server caches a URL. The same idea, everywhere.

Where it runs
  • Memcached / Redis clients:
  • ketama, cluster slots
  • Cassandra, Riak, DynamoDB:
  • partition ring + vnodes
  • Load balancers:
  • sticky routing by client
  • CDNs: which edge caches a URL

How it fits

How does this fit with last episode? Sharding is the decision to split data by key. Consistent hashing is one way to map those keys to machines so the mapping survives machines coming and going. A sharded database might use a lookup table instead; a cache cluster almost always uses the ring.

Consistent hashing vs sharding
  • sharding (last episode):
  • which rows live where
  • key → shard, lookup or hash
  • consistent hashing:
  • HOW to map keys → nodes
  • so the mapping survives
  • nodes joining and leaving

Interview questions

Why does hash(key) % N cause a problem when a server is added?

Changing N changes the modulo result for almost every key (roughly (N-1)/N of them), so most keys now map to a server that does not have them. In a cache that means a wave of misses hitting the database; in a datastore it means a huge data migration.

How does consistent hashing place a key?

Servers and keys are hashed onto the same ring (0 to 2^32). A key is owned by the first server found walking clockwise from the key's position. Each server therefore owns the arc immediately before it.

How many keys move when a server joins or leaves the ring?

Only the keys in the arc the server takes or gives up: about 1/N of all keys. Every other key keeps the same owner, so the rest of the cache stays warm.

What problem do virtual nodes solve?

With one point per server the arcs are uneven (random hashes), and a failed server dumps its whole arc onto one neighbour. With 100-200 virtual points per server, load averages out across the ring, failures spread across all remaining servers, and a bigger machine can be given more points.

How does consistent hashing give fault tolerance for data stores like Cassandra?

Each key is stored on the next K nodes clockwise from its position (the replication factor). If a node fails, its keys already exist on its successors, and reads can continue immediately.

Name systems that use consistent hashing.

Memcached and Redis client libraries (ketama), Cassandra, Riak and DynamoDB partition rings, load balancers for sticky routing, and CDNs for mapping URLs to edge caches.

What is the difference between sharding and consistent hashing?

Sharding is the decision to split data across machines by a shard key. Consistent hashing is one technique for mapping keys to machines so the mapping stays mostly stable when machines join or leave. Sharded SQL systems often use a lookup table instead; caches and wide-column stores usually use the ring.

What is a hot key, and does consistent hashing fix it?

A single key that gets far more traffic than others (a celebrity profile). Consistent hashing spreads keys, not traffic for one key, so it does not fix hot keys. Fixes include caching the hot key in the application, replicating it to several nodes, or appending a random suffix to split it.