Distributed systems · 11 min

Consistent hashing

Why adding one cache server can take a database down, and the ring that makes it move only about 1 key in 5 instead of 4 in 5.

It is 8:40 pm on the first night of a big sale. Your shop keeps its product pages in four cache servers: tokyo, osaka, kyoto and nagoya. They answer 95 of every 100 page reads, so the database only sees the other 5.

Traffic is climbing and the caches are running hot. Someone adds a fifth server, sapporo, to share the load. Within a minute the database is at full CPU, pages time out, and the sale is down.

Nothing was broken. The new server was fine. The problem was the one line of code that decides which server holds which item.

The line that sank the sale

Every cached item has a key, the name you look it up by, like user:sakura or cart:yui. To pick a server for a key, the shop used the obvious rule:

server = servers[hash(key) % servers.length]

Say hash("user:sakura") is 1,000,003. With 4 servers, 1,000,003 % 4 = 3, so it lives on servers[3], the fourth one: nagoya. Every read for user:sakura goes to nagoya and finds it there.

Now there are 5 servers. 1,000,003 % 5 = 3 as well, so user:sakura happens to stay put. But the rule asks a new question for every key, and most keys get a new answer.

A key that points to a new server is a miss: the item is sitting on the old server, but nobody asks there any more. So 80% of reads suddenly miss, all at once. The cache is cold: it is still running, but it holds almost nothing anyone is now asking for.

Assume every key is read about equally often, so 80% of keys means 80% of reads. The 20% that stayed put still miss at the usual 5%, which is another 1% of all reads. Add the two up and you get the damage:

The fix can’t be “never add servers”. What you want is a rule where adding one server moves only the keys that server should take, and leaves every other key alone.

Bend the numbers into a circle

Take every number a hash can produce, 0 up to about 4.3 billion, and bend that line into a circle, like a clock face with 0 at the top. Call it the ring.

1. Hash each server’s name. That number is the server’s spot on the ring.
2. Hash the key. That is the key’s spot.
3. From the key’s spot, walk clockwise. The first server you reach holds the key.
4. If you pass the top before meeting a server, carry on round from 0.

Notice what this rule does not use: the number of servers. Each key only cares about the next server clockwise from it.

Why only sapporo’s keys move

When sapporo joins, it lands at one spot on the ring. Start at sapporo’s spot and walk backwards (counter-clockwise) until you hit another server. Picture that stretch of ring. Keys in that stretch used to walk on past sapporo’s spot to the next server; now they stop at sapporo. Those are the only keys that change.

Every other key walks the same path to the same server as before. And all the moved keys go to sapporo, which is new and empty, so it would have had misses under any rule.

Removing a server works the same way in reverse: only its keys move, each to whichever server is next clockwise.

With 5 servers sharing the ring evenly, sapporo takes about 1 key in 5, so about 20% move instead of 80%. That 1 in 5 is one server’s share of the new total, so going from 10 servers to 11 would move about 1 key in 11.

The lopsided ring

The third try step shows the catch. A hash scatters the servers’ spots round the ring as if at random, and four random spots don’t cut a circle into four equal slices. In the demo tokyo’s slice is 2% of the ring and nagoya’s is 56%, so nagoya gets about 28 times as many keys as tokyo.

The same luck decides how many keys move. sapporo happened to land in the middle of nagoya’s huge slice and took more than half the ring, leaving nagoya with just 2%. Only nagoya’s keys moved, but that was most of them.

The fix is to give each server many spots instead of one. Hash “tokyo#0”, “tokyo#1”, … up to “tokyo#99”, and put tokyo at all 100 spots. Each spot is called a virtual node.

Now each server owns 100 small slices instead of one big or tiny one. Some slices are large and some are small, but over 100 of them the luck averages out. In the demo, with 100 spots each, the four servers own 27%, 27%, 23% and 22% of the ring.

And when sapporo joins with 100 spots of its own, it takes a small slice from every server instead of a giant one from a single unlucky neighbour. Removing a server works the same way: its 100 slices go to 100 different next-clockwise spots, so its keys spread over all the others.

What the lookup looks like

In code, the ring is just a sorted list of (spot, server) pairs. Look for the two things you already saw in the demo: “first spot at or after the key” and “wrap back to the start”.

SPOTS = 100                       # virtual nodes per server
ring = []                         # (spot, server), kept sorted by spot

add_server(name):
    for i in 0 .. SPOTS-1:
        ring.insert_sorted((hash(name + "#" + i), name))

remove_server(name):
    ring.remove_all where server == name

server_for(key):
    h = hash(key)
    i = first index where ring[i].spot >= h    # binary search
    if no such index: i = 0                    # passed the top: wrap round
    return ring[i].server

The sale, run again

Replay the sale with the ring and 100 spots per server. sapporo joins and takes about 1 key in 5, so about 20%. (In the demo sapporo owns 18% of the ring, but with only 112 keys, 27 of them, 24%, happened to fall in its slices. More keys bring it closer to its share.) Those reads miss, and the other 80% miss at the usual 5%.

24,000 is still almost five times the normal load, so you would add sapporo before the peak, not during it. But the gap matters: a database built to take, say, 30,000 reads a second survives 24,000 and falls over at 81,000. And sapporo warms up as people browse, so the misses fade within minutes.

You now have a rule of thumb for any “which server holds this?” design: if the number of servers will ever change, don’t divide by it.

Where this runs today

• Memcached servers don’t talk to each other; the client library picks the server for each key. Libraries such as libmemcached offer a ring mode (called “ketama”), so adding a cache server empties only its share of the cache.
• Cassandra, a database spread over many servers, puts each server on a ring at many spots; a setting called num_tokens says how many. To survive a server dying, it keeps copies of each row on the next few servers clockwise, so the ring also picks where the copies go.
• Amazon’s Dynamo paper (2007) made the ring with virtual nodes famous, and Riak and Cassandra followed its design.