DEV Community

Cover image for Hot keys in a distributed cache: why more shards don't help
DesignBeyondCode
DesignBeyondCode

Posted on Originally published at designbeyondcode.com

Hot keys in a distributed cache: why more shards don't help

Here's a cache problem that catches a lot of people. Your cache cluster has 64 nodes and plenty of spare room. Then one celebrity posts, and a single key gets a million reads a second. The cluster falls over anyway.

The usual first answer is "add more shards." It doesn't help, and the reason is worth understanding.

Why more shards don't help

A distributed cache splits keys across nodes with a hash. Each key lives on exactly one node. That's what makes it scale for many keys. But one key still hashes to one node, no matter how many nodes you add.

One node serves about 300,000 operations a second. A million reads a second on one key is more than three times that. It's also about half the node's network card, just for that key.

The second problem: when it expires

Now say that hot key expires. Every request in that millisecond misses. Every one of them goes to the database at the same time. This is called a stampede, or a thundering herd. The database was sized for a few hundred thousand misses a second across all keys, not a burst like that on one row.

So a hot key is two problems: too many reads on one node, and a herd when it expires.

Step 1: find hot keys automatically

You can't fix what you can't see. Each node samples 1 in 100 requests and reports any key above 50,000 reads a second. Nobody has to guess which keys are hot.

Step 2: a tiny cache inside each app

Every app process keeps its own small cache of the hottest few thousand keys, for 2 seconds. Now each process asks the cache cluster for a hot key at most once every 2 seconds. Most reads never leave the app.

The cost is up to 2 seconds of extra staleness on hot keys. For a like count, that's fine. For a bank balance, it isn't.

Step 3: copies on several nodes

With 20,000 hosts running 16 processes each, the near cache can still send 160,000 reads a second to one node. So store the hot key as 8 copies, key#1 to key#8, on 8 different nodes. Readers pick one at random. That's about 20,000 reads a second per copy.

The catch: every write and delete must now hit all 8 copies.

Step 4: let only one request refill it

This fixes the herd. When a request misses, the cache gives it a token, called a lease. Other requests for the same key get "wait" instead of a miss. They retry a few milliseconds later. Only the request holding the lease reads the database and fills the cache.

So a thousand misses become one database read. When Facebook added leases to memcache, peak database queries on one busy key fell from 17,000 a second to 1,300.

The short version

More shards spread many keys, not one key. For one hot key you need to find it, keep it close to the app, copy it, and let only one request refill it.


I wrote the full version on my site. It has the race that leases also fix, failover, eviction, a calculator for the numbers, and code in five languages. Design a distributed cache

Top comments (0)