Consistent hashing, visually

A few years ago we added a fifth memcached box to a cluster of four, on a Tuesday afternoon, because the four were running out of memory. Within about a minute the database was pinned at 100% CPU and the site was crawling. Nothing was wrong with the new box. The problem was the one line of client code that picked which server a key lived on:

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

With four servers a key goes to hash % 4. With five it goes to hash % 5. Those agree only when hash mod 20 is 0, 1, 2 or 3, which is 4 values out of 20, so 80% of keys suddenly lived on a different server. Every one of those lookups was a cache miss, every miss went to the database, and the database had been sized on the assumption that the cache would catch about 95% of reads. We pulled the fifth server back out, waited for things to calm down, and did it again at 3 AM after switching to a client library that used consistent hashing (the switch itself remapped everything one last time, but at 3 AM nobody cared). I’d known the term for years. That afternoon is when I actually learned it.

The general version is worse than my example. Going from N to N+1 servers with mod hashing moves about N/(N+1) of your keys, so the bigger your cluster the larger the share that moves. Ten to eleven servers moves about 91%. What you want is to move only the keys that the new server is going to own, about 1/(N+1) of them, and leave everything else alone.

The ring

The idea is from a 1997 paper by Karger and others at MIT, the work that Akamai was built on. Take the output range of your hash function, say 0 to 2³²−1, and bend it into a circle so that the largest value wraps back around to 0. Now hash each server onto that circle too, using its name or IP. To find where a key lives, hash the key to a point on the circle and walk clockwise until you hit a server. That server owns the key.

When D joins, it lands somewhere on the circle, and the only keys that change owner are the ones on the arc between D and the server before it, which used to belong to the server after it. Everything else stays where it was. Remove a server and the reverse happens: its keys slide clockwise to the next one and nobody else notices. In a cache that’s the difference between a 1-in-5 miss rate for a few minutes and a thundering herd.

Lookups are cheap. Keep the server positions in a sorted array, hash the key, and binary search for the first position greater than or equal to the key’s hash, wrapping to index 0 if you fall off the end. That’s O(log N) on a list that fits in L1 cache. The libketama library that came out of Last.fm around 2007 does more or less exactly this, and most memcached clients either use it or copy it.

Why one point per server doesn’t work

The diagram above cheats a bit. I put the servers where I wanted them. In real life you hash them, and three random points on a circle almost never divide it into equal thirds. One server ends up owning a huge arc and another a sliver.

I ran a quick simulation to see how bad it is: 10 servers, 100,000 keys, MD5 for the hash. With one point per server the busiest server got 2.7x its fair share of keys and the least busy got 0.16x.

The fix is virtual nodes. Instead of putting server A on the ring once, put it on 100 times, as A-0, A-1, … A-99, and the same for every other server. Each server now owns lots of small arcs scattered around the circle, and the randomness averages out. In the same simulation, 10 virtual nodes per server brought the spread down to 0.59x–1.59x, and 100 per server brought it to about 0.89x–1.09x. Going to 200 didn’t make much more difference in my run, which roughly matches what I’ve seen people use in practice: somewhere between 100 and a few hundred.

Virtual nodes have two side benefits that I didn’t appreciate until later. When a server dies, its load doesn’t all land on one unlucky neighbor, it gets spread over every server that owns an arc next to one of its hundred points, which is basically all of them. And you can weight servers: give a box with twice the memory twice as many points.

Where you’ve already seen this

Amazon’s Dynamo paper from 2007 is the one that made the ring famous outside of CDN circles, and Cassandra and Riak both use descendants of it. Dynamo adds replication on top in a nice way: a key is stored on the first server clockwise and the next N−1 distinct servers after it, so replicas fall out of the same walk around the circle. If you read one distributed systems paper this year, that one has aged well.

It isn’t the only way to get the “move only 1/N” property. Google published jump consistent hash in 2014, which is a handful of lines of code, uses no memory for a ring at all, and spreads keys almost perfectly evenly. The catch is that servers are numbered 0 to N−1 and you can only add or remove at the end, so it suits storage shards that you grow over time much better than a pool of cache boxes where any one of them might die. There’s also rendezvous hashing (highest random weight), which is older than the ring paper: hash the key with every server name and pick the highest score. It’s O(N) per lookup, which is fine for 10 servers and silly for 10,000.

The new wrinkle: bounded loads

The one thing consistent hashing doesn’t fix is a hot key. If one video, or one user, or one cache key gets a tenth of all your traffic, the server that owns it is going to have a bad time no matter how evenly the keys are spread.

Last month Vimeo’s engineering blog had a good write-up of exactly this problem. They route video requests to cache servers with consistent hashing, so a given video’s chunks stay on the same few boxes, and popular videos were overloading individual servers. Their fix came from a 2016 paper by Mirrokni, Thorup and Zadimoghaddam, Consistent Hashing with Bounded Loads. You pick a capacity for each server, a little above average load, say (1+ε) times the average. When a request’s natural server is already at capacity, you keep walking clockwise to the next one that isn’t. The paper’s result is that with that bound in place, the number of keys that move when servers come and go stays small, so you keep most of the cache affinity and lose the hot spots. They implemented it in HAProxy.

I like this a lot, mostly because it’s one of those ideas that seems obvious once someone writes it down. “If the server’s full, try the next one” is what any of us would have hacked in under pressure. The contribution is showing that the hack has good bounds instead of falling apart under churn.

If you’re picking a scheme today, my rough guide is the ring with 100-ish virtual nodes for caches and anything where servers come and go unpredictably, jump hash for shards that only grow, and bounded loads on top if you have a small number of extremely hot keys. And if you’re still on hash % N with a cache in front of a database, please don’t add a server on a Tuesday afternoon.*

* Hash tables have the same resizing problem internally, which is why they rehash everything when they grow. The difference is that a hash table can afford to, because it’s all in one process’s memory. A cluster can’t.