Pointer Walk

Consistent Hashing

Add a server and most keys stay where they are. The hash ring, compared with plain modulo hashing.

System DesignIntermediate10 min read

The problem: which server has my key?

One cache server is not enough, so you run four. Now every piece of data lives on one of them, and everyone who reads or writes needs to agree on which one. Asking "who has user:42?" over the network each time would be slow. The answer has to be computed from the key itself.

The tool for that is a hash function: it turns any text into a large number, and the same text always gives the same number.

The obvious way: divide and take the remainder

Hash the key, divide by the number of servers, and use the remainder. With 4 servers the remainder is 0, 1, 2 or 3, so it names a server.

python
servers = ["A", "B", "C", "D"]

def server_for(key):
    return servers[hash(key) % len(servers)]

It is one line, it spreads keys evenly, and it works well until the number of servers changes.

Example

Adding a fifth server

Take five keys whose hashes are 10, 11, 12, 13 and 14.

With 4 servers the remainders are 2, 3, 0, 1, 2.

With 5 servers the remainders are 0, 1, 2, 3, 4.

Every one of the five keys now points at a different server. The data is still sitting on the old server, so each of those lookups is a miss.

This is not bad luck. Going from 4 to 5 servers changes the remainder for about four keys out of five. For a cache, that means most of it is suddenly useless and the database behind it takes the full load, right when you were adding capacity because things were busy.

The ring

Consistent hashing fixes this by changing what the hash is compared with. The hash no longer depends on how many servers there are.

  1. Bend the number line into a circle

    Take every possible hash value and arrange them around a ring, like the minutes on a clock.

  2. Place each server on the ring

    Hash the server's name. That number is its position.

  3. Place each key on the ring

    Hash the key the same way.

  4. Walk clockwise from the key

    The first server you meet stores that key.

So each server owns the stretch of ring that comes just before it.

Try it: add a server

Both sides below store the same 30 keys. Each colour is a server. Press Add a server and compare the two "moved" numbers.

30 keys on 4 serversInteractive
Ring points

Modulo hashing

hash(key) % 4

moved–

123456789101112131415161718192021222324252627282930
  • A 7
  • B 7
  • C 6
  • D 10

Hash ring

next server clockwise

moved–

CDBAclockwise↻
  • A 4
  • B 10
  • C 10
  • D 6

Same keys, two ways to place them. Each colour is a server. Add or remove a server and watch how many keys change colour on each side.

On the left, most of the grid changes colour. On the right, only a handful of dots do.

Why so few keys move

When a new server joins the ring, it lands at one position. It takes over the keys between itself and the server before it. That is all. Every other stretch of the ring still ends at the same server as before, so those keys do not move.

Example

Four servers become five

With modulo hashing, about 4 keys in 5 move. With the ring, the new server takes roughly its fair share, about 1 key in 5, and all of them come from a single neighbour.

Removing a server is the mirror image. Its keys pass to the next server clockwise, and nobody else is touched. Try it with Remove a server.

This is what makes it practical to add and remove machines while the system is running, and why a server crashing only loses that server's share.

Evening it out with more points

Look at the counts under the ring with one point per server. They are uneven. Positions come from a hash, so by chance two servers can land close together. One of them then owns a tiny stretch and the other a huge one.

The fix is to put each server on the ring several times. Hash A-1, A-2, A-3 and so on, and place a point for each. These are called virtual nodes.

Switch the demo to 5 per server and compare the counts.

With many small stretches per server instead of one large one, the luck averages out. Real systems use dozens or hundreds of points per server. It has a second benefit: when a server leaves, its keys are shared among many others instead of all landing on one neighbour.

Where you will meet it

  • Distributed caches. Client libraries use a ring so that adding a cache server does not empty the whole cache.
  • Distributed databases. Each node owns ranges of the ring, and data is copied to the next few nodes clockwise for safety.
  • Load balancers. When a user must keep reaching the same server, a ring keeps most users in place as servers come and go. See Load Balancing.

Key takeaways

  • Hashing lets everyone compute which server holds a key without asking.
  • With modulo hashing, changing the number of servers moves almost every key.
  • On a hash ring, a key belongs to the first server clockwise from it.
  • Adding or removing a server only moves the keys next to it on the ring.
  • Several points per server (virtual nodes) even out how many keys each one holds.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress