Consistent hashing, step by step

Part of the free System Design course on LogicWiz, in the chapter: Databases at scale. The interactive whiteboard exercises and simulations run in the app.

The cache that forgot everything at once

"We added one cache server to help with the sale. Four out of five lookups started missing, and the database went down instead."

Kabir, on last year's festival sale

Why hash(key) mod N moves almost every key

Yesterday you met consistent hashing in one paragraph. Today you build it slowly. Interviewers ask about it often, and it is easy to recite but hard to explain.

Start with a SwiftKart cluster. The catalogue service keeps product details in a cache: a fast copy, held in memory, of data whose real home is the database. One cache server is not enough, so there are four. Each product key must live on exactly one of them, and every service instance must agree on which.

The simple rule: hash the key, then take the remainder after dividing by the number of servers.

server = hash(key) mod N

A hash is a function that turns any key, like "product 501 in Pune", into a number. The number looks random, but the same key always gives the same number. mod means the remainder: 22 mod 4 is 2, because 22 = 5 × 4 + 2.

With N = 4 the keys spread evenly. Then the sale arrives, and the team adds a fifth server. Watch four keys.

Take any 20 hash values in a row. Only 4 of them give the same remainder for 4 and for 5. So 16 in 20, about 80% of keys, now belong to a different server.

In a database, that means copying 80% of the data while the app is live. In a cache the damage is faster. A moved key is not on its new server yet, so the lookup misses and falls through to the database. Say the cache serves 20,000 lookups a second. Right after the change, about 16,000 a second miss. They land on a database that is comfortable at about 2,000. Adding capacity took the system down.

Kabir's question to Meera: can we place keys so that a new server takes only its fair share?

The ring: servers and keys on one circle

Picture a circular running track with markers from 0 to 99. After 99 comes 0 again, like a clock face.

1. Place the servers. Hash each server's name to a marker. Say A lands on 10, B on 35, C on 60 and D on 85.
2. Place the keys. Hash each key to a marker in the same way.
3. Walk clockwise. From a key's marker, walk forward until you meet a server. That server owns the key.

A key at 20 walks to B at 35. A key at 40 walks to C at 60. A key at 90 passes 99, wraps to 0, and stops at A at 10.

flowchart LR
  A["A at 10"] --> B["B at 35"] --> C["C at 60"] --> D["D at 85"] --> A
  K1["key at 20"] -.-> B
  K2["key at 40"] -.-> C
  K3["key at 90"] -.-> A

So each server owns a stretch of the ring, called an arc: from right after the previous server up to itself. B owns 11 to 35. A owns 86 to 99 and 0 to 10, because the ring wraps.

The track analogy stops working in two places. A real ring has about 4 billion markers, not 100, so keys almost never share one. And nothing walks: the code keeps the server positions in a sorted list and searches it. Each step of that search halves the list, so even 4,000 positions take about 12 steps.

Adding or removing a server moves one slice

The sale arrives again. Add server E, whose name hashes to 72.

Before, keys from 61 to 85 walked to D. Now keys from 61 to 72 meet E first. Keys from 73 to 85 still reach D. A, B and C see no difference at all.

flowchart LR
  C["C at 60"] --> E["E at 72, new"] --> D["D at 85"]
  M["keys 61 to 72"] -.->|"move from D to E"| E

Only the 12 markers from 61 to 72 change owner: about 12% of keys, not 80%. Every moved key comes from one place, D, so you know exactly what to copy.

Removing a server is the mirror image. Say B crashes. Its keys, 11 to 35, keep walking clockwise and reach C. Every other key stays where it was.

When positions are spread evenly, adding a server to N servers moves about 1/N of the keys: its fair share. From 4 to 5 servers, that is 1 in 5, about 20%. Back to the cache: about 4,000 lookups a second miss for a few minutes while the new server fills, not 16,000. A database with a primary and two read replicas, as earlier this week, handles about 6,000 a second. The bump is survivable.

Notice that E took only 12%, less than its fair 20%. That is a clue.

Uneven slices, and virtual nodes

After drawing the ring, Meera wrote in her notebook: "Consistent hashing makes the load even by itself." Kabir crossed it out.

Look again. The positions 10, 35, 60 and 85 were chosen by hand, 25 apart. Real positions come from a hash, so they land anywhere. Suppose the four servers land on 10, 18, 64 and 70.

• The server at 18 owns 11 to 18: 8% of keys.
• The server at 64 owns 19 to 64: 46%.
• The server at 70 owns 65 to 70: 6%.
• The server at 10 owns 71 to 99 and 0 to 10: 40%.

The busiest server carries almost eight times the load of the quietest. Failure is lopsided too. When a server dies, its whole arc lands on one neighbour, which may then fail as well.

The fix is virtual nodes: place each physical server on the ring many times, not once. Hash "A-1", "A-2" and so on up to "A-100", and put A at all 100 positions. Each position is one virtual node. Server A now owns 100 small arcs scattered around the ring, and so does every other server. Many small random arcs average out, so each server's total lands close to its fair share.

Virtual nodes fix the other problems as well.

• A new server takes a small slice from nearly every existing server, so no single server loses a big piece.
• A failed server's arcs fall to many different neighbours, so its load spreads across the cluster.
• A bigger machine can get more virtual nodes, say 200 instead of 100, and take a bigger share on purpose.

The price is small: four servers with 100 virtual nodes each make a sorted list of 400 positions. Every service that routes keys must hold the same list.

Try it below. Set 4 servers and 1 virtual node, and look at the load bars. Switch to 10 and then 50 virtual nodes and watch the bars even out. Then add a fifth server and compare the keys moved against mod-N hashing.

Copies: keep walking to the next servers

A cache can lose a key and fetch it again from the database. A database cannot lose one. So a sharded store keeps copies, and the ring says where.

Walk clockwise from the key as before. The first server you meet holds the main copy. Keep walking: the next two different physical servers hold the second and third copies. Keeping three copies is called a replication factor of 3.

Why "different physical"? With virtual nodes, the next marker may be A again. Two copies on A would vanish together if A died, so you skip ahead to the next server that is not A.

When the main server dies, the next server on the ring already holds a copy. Reads and writes carry on there while the store makes a fresh third copy elsewhere.

Where you will meet it

• Cache clusters. Many cache client libraries hash each key onto a ring to pick a server, so adding a server does not empty the cache.
• Sharded stores. Many distributed key-value and wide-column stores place data on a ring, with virtual nodes and copies on the next servers.
• The key-value store interview question. "Design a key-value store" expects this lesson: the ring, virtual nodes, copies on the next servers, and what moves when a server joins.
• Sticky connections. A balancer can hash a user id onto a ring of WebSocket gateways, so a user returns to the same gateway after reconnecting.

It is not the only answer. Some systems split keys into a fixed number of slots, say 1,024, and keep a small table of which server owns each slot. Moving a slot changes one row in that table. Mention both in an interview, and say why either beats mod N.

💡 Tip: In an interview, draw the ring with four servers and one key. Then add a fifth server and point at the one arc that moves. Thirty seconds of drawing beats two minutes of talking.

Now spread the catalogue cache yourself.

📌 Summary: Going from 4 to 5 servers, hash mod N moves about 80% of keys; a ring moves about 1/N. Virtual nodes even out the load. Copies live on the next servers clockwise.

What Meera learns next

The catalogue cache can now grow without falling over. Next week: caching itself. What to keep in it, for how long, and what happens when the copy goes stale.

Check your understanding

1. A ring runs from 0 to 99 with one position per server: A at 10, B at 35, C at 60 and D at 85. A key hashes to 87. Which server owns it?
2. SwiftKart's catalogue cache serves 20,000 lookups a second across 4 servers placed by hash(key) mod 4. A fifth server is added and the rule becomes mod 5. What does the database see right after?
3. Four servers hash to ring positions 10, 18, 64 and 70, one position each. The server at 64 owns 46% of the keys. What evens this out?
4. A store keeps 3 copies of each key and uses virtual nodes. Walking clockwise from one key, the ring positions belong to A, A, B, C, D. Where do the 3 copies go?