Cache stampedes and hot keys
What happens when a popular key expires, and the locks and jitter that prevent it.
01The intuition
The problem it solves
A cache works because one answer is reused many times. Now think about the one key everyone wants at the same moment: the home page of a news site, the score of a cricket final, the profile of a celebrity who just posted. Suppose 10,000 requests a second ask for it and it has a 60-second TTL. For 59.9 seconds all is well. Then the entry expires.
In the next 10 milliseconds, 100 requests arrive, all miss, and all go to the database to recompute the same answer. If recomputing takes 200 ms, by the time the first one finishes another 2,000 have piled up behind it. The database, which was comfortable at a few hundred queries a second, now gets thousands for one key. It slows down, every other key starts missing too, and the site falls over. This is a cache stampede, also called the thundering herd. A single expiring key did it.
A cousin problem is the hot key that never expires: one key gets so many reads that the single cache machine holding it saturates its network card while the other machines sit idle.
Build it one piece at a time
Step 1: see the storm. Trace what happens when key home expires with 100 simultaneous readers and a 200 ms recompute.
| Time | Cache | Readers waiting | Database queries in flight |
|---|---|---|---|
| 0 ms | home expired | 100 | 100 |
| 100 ms | still empty | 1,100 | 1,100 |
| 200 ms | first write lands | 2,100 | 2,100 (most still running) |
Step 2: a lock on the refill. When a reader misses, it tries to take a short lock named after the key, for example lock:home with a 1-second expiry. The one reader that gets the lock recomputes and writes the cache. The other 99 do not go to the database; they either wait a few milliseconds and retry the cache, or serve the old value if one is kept. Now the database sees one query, not thousands.
| Time | Cache | Lock holder | Database queries |
|---|---|---|---|
| 0 ms | home expired | reader 1 | 1 |
| 100 ms | empty, 1,099 readers polling cache | reader 1 | 1 |
| 200 ms | home refilled | released | 1 |
Step 3: serve stale while refreshing. Keep the old value past its TTL, marked as stale. A reader that finds a stale value returns it immediately and, if nobody is already refreshing, kicks off one refresh in the background. Nobody waits 200 ms and the database still sees one query.
Step 4: refresh early, with jitter. Instead of letting the key die at exactly 60 seconds, a reader that finds it older than about 55 seconds refreshes it with a small probability. Each reader rolls a die, so the refresh happens a little before expiry and at a random moment. Keys that were all loaded at startup no longer expire in the same second.
Step 5: spread the hot key. For a key that is too popular for one machine, store it under ten names, home#0 to home#9, on ten machines, and have each reader pick one at random. The load on any one machine drops to a tenth. Servers can also keep a tiny local copy of the hottest few keys for a second, so most reads never leave the process.
Why it works, with the numbers
Without protection, the number of database queries caused by one expiry is the arrival rate times the recompute time:
queries ≈ r × t = 10,000 per second × 0.2 s = 2,000
With a lock, it is 1. With early refresh at probability p per read once the key is near expiry, the expected number of reads before someone refreshes is 1/p; at p = 0.01 and 10,000 reads a second that is about 10 ms of lateness, invisible to users. The invariant you keep is simple: at most one recompute per key is in flight at any time. Failure modes: the lock holder crashes, so the lock must expire on its own; a stale value is served for a few hundred milliseconds longer than the TTL promised, which you must be allowed to do.
The trade-off you must say out loud
Every fix trades a little freshness or a little complexity for stability. Serving stale means the TTL is a soft promise. Locks add a second round trip to the cache on every miss. Key spreading multiplies memory by the spread factor. Say which keys are hot enough to deserve this, and say that the database must be sized for a cold cache anyway, because one day the cache will restart and every key will miss at once. The follow-up question is usually "how do you warm the cache before taking traffic", and the answer is a script that replays yesterday's most popular keys.
Where it shows up in the 100 Google problems
- Distributed cache: the design must say what happens when a key expires under 100,000 readers, and how one node holding a celebrity's key does not melt.
- Social news feed: a celebrity's post is the textbook hot key; it is copied to several cache nodes.
- 10x traffic surge: a stampede is the usual way a surge turns into an outage, and lock-and-stale is the usual rescue.
- Search autocomplete: the top prefixes are refreshed in the background so they are never recomputed on the request path.