The Thundering Herd Problem: When Your Cache Expires
Your cache has a 99% hit rate and the database is idle. Then one popular key expires, ten thousand requests miss simultaneously, and every one of them tries to rebuild it. The cache didn't fail — it worked perfectly right up until the moment it didn't.
The Outage That Starts With a Timer
Your homepage feed is expensive to compute — a few joins, an aggregate, maybe a call to a recommendation service. Three hundred milliseconds. So you cache it with a five-minute TTL, and life is good. Hit rate sits at 99.8%. The database barely notices you exist.
Then, at some arbitrary moment, that key expires.
The next request misses, and starts rebuilding. So does the request that arrived a microsecond later. And the eight thousand that arrive during the 300ms the rebuild takes. None of them can see that the others are already doing the identical work, because the cache is empty and an empty cache says nothing about who's working on it.
Eight thousand identical expensive queries hit your database in the same instant. The database queues, slows, and now the rebuild takes 4 seconds instead of 300ms — which means the window for piling on is thirteen times wider, so more requests join. The pile grows faster than it drains.
This is a cache stampede, also called a thundering herd. Note what caused it: not a bug, not a traffic spike, not a failure. A timer expired.
Why Cache-Aside Has This Built In
The stampede isn't incidental to the standard caching pattern — it's a direct consequence of it.
When a cached value expires or is evicted, every concurrent request for that key misses at once and independently recomputes it. The cost is not one expensive computation but N of them, where N is your request rate multiplied by the recomputation time. The cache offers no coordination between the concurrent misses, because a miss is just an absence.
Do the arithmetic on your own system: requests per second for the hottest key, times seconds to recompute it. That product is how many duplicate computations one expiry buys you. At 2,000 rps and a 300ms rebuild, it's 600 — and that's before the feedback loop where a slowed database extends the rebuild time and recruits more.
⚠️ Synchronized expiry is the version that takes you down
The single-key stampede is survivable. The dangerous one is correlated expiry: a deploy warms 50,000 keys in the same minute with the same TTL, so five minutes later they all expire in the same minute. Or a cache node restarts empty. Or you flush the cache to fix a bug. Now it isn't one hot key stampeding — it's your entire working set, and the database sees the full uncached load of your application for the first time since launch.
Three Fixes, and What Each One Actually Solves
The mitigations attack different parts of the problem. Most production systems want two of them together.
| Technique | Mechanism | Solves | Costs |
|---|---|---|---|
| Locking / single-flight | First miss takes a lock and rebuilds; others wait or serve stale | Duplicate work on one key | Lock management; a stuck rebuild blocks waiters |
| Probabilistic early expiry | Each request may refresh slightly before the TTL, with rising probability | Herd arrival at the expiry instant | Slightly more recomputation overall |
| Background refresh | A worker recomputes hot keys before they expire; keys never go cold | The miss itself, entirely | Infrastructure; must know which keys are hot |
| TTL jitter | Randomize each key's TTL by ±10-20% | Correlated expiry across many keys | None worth mentioning — always do this |
| Serve stale on miss | Return the expired value immediately, refresh in the background | User-visible latency during rebuild | Users briefly see stale data |
Single-flight: only one rebuild wins
The direct fix. On a miss, try to acquire a short-lived lock for that key. Whoever gets it does the rebuild and writes the result; everyone else either waits briefly and re-reads, or immediately serves the stale value they can still see.
value = cache.get(key) if value is fresh: return value # Only one caller wins this. NX = set only if absent. got_lock = cache.set(key + ":lock", id, NX=true, EX=10) if got_lock: value = expensive_recompute() # exactly one of these runs cache.set(key, value, EX=300 + jitter()) cache.delete(key + ":lock") return value if value is stale_but_present: return value # best answer sleep(50ms); return cache.get(key) # otherwise, brief wait
The lock TTL matters. Too short and a slow rebuild releases the lock while still running, letting a second rebuild start. Too long and a crashed holder blocks every other request for that duration. Set it above your p99 rebuild time, and make sure the release is guarded — delete the lock only if the value still matches your own token, or you'll delete someone else's lock after your own timed out.
✅ Prefer 'serve stale' over 'wait for the lock'
If the lock's holder is rebuilding, the other requests have two options: block, or return the value that just expired. Blocking converts a caching problem into a latency problem — thousands of held connections waiting on one rebuild, which is its own kind of exhaustion. Returning data that's a few hundred milliseconds past its TTL is almost always the better answer. This is the pattern behind stale-while-revalidate in HTTP caching, and it's a good default well beyond HTTP.
Probabilistic early expiry: spread the refresh out
Rather than every request treating the TTL as a hard cliff, let each one independently decide, with a small probability that grows as expiry approaches, to refresh early. Statistically, one unlucky request refreshes the key slightly ahead of time while everyone else is still hitting a warm cache. The herd never forms because there's never a moment when the key is simultaneously absent for everyone.
The elegant version — XFetch — scales that probability by how long the recompute takes, so expensive keys get refreshed further in advance than cheap ones. It needs no locks and no coordination, which makes it attractive in distributed caches where a lock is another round-trip.
Background refresh: never miss at all
For a small set of genuinely hot keys — the homepage feed, the trending list, the config blob — stop treating them as cache entries that expire and start treating them as materialized values that a worker keeps current. The request path only ever reads. There's no miss, so there's no stampede, and your p99 stops containing a rebuild.
This is the strongest fix and the most work. It's worth it for the top handful of keys and unmanageable for the long tail, which is why it pairs with one of the others rather than replacing it.
The Neighbours: Two Related Failures
Stampede is one of three cache failure modes that get confused with each other. They have different fixes, so it's worth separating them.
| Failure | What happens | Fix |
|---|---|---|
| Stampede / thundering herd | A key expires; N concurrent requests all rebuild it | Single-flight, early expiry, background refresh |
| Cache penetration | Requests for a key that doesn't exist anywhere — every one falls through to the database | Cache the negative result; bloom filter for existence |
| Cache avalanche | A large fraction of keys expire together, or the cache node dies | TTL jitter, replication, circuit breaker on the database |
Penetration is the sneaky one, because it's the only one an attacker can trigger deliberately: request /api/user/99999999 repeatedly with random ids, none of which exist, and every request reaches your database no matter how good your cache is. Caching the "not found" answer for a short TTL closes it.
🔴 The cache is now on your critical path
Every one of these failures shares a root cause: your database is provisioned for cached load, not real load. A cache with a 99% hit rate means the database sees 1% of requests — so a cache-wide failure is a 100x traffic multiplier landing instantly. Know what fraction of full load your database can actually absorb, and put a limiter or circuit breaker between the cache-miss path and the database so a cold cache degrades service rather than destroying it.
Choosing Your Defence
Is this a small set of known-hot keys, or a long tail?
And regardless of which branch you land on: jitter every TTL. It costs one line, and it's the only thing standing between a cache restart and a synchronized expiry across your entire key space.
Key Takeaways
- A stampede is caused by an expiry, not a failure. N concurrent misses on one key produce N identical expensive rebuilds, where N = request rate × rebuild time.
- It's self-amplifying. A loaded database rebuilds slower, which widens the window, which recruits more requests into the herd.
- Single-flight ensures one rebuild per key. Guard the lock with a token and a TTL above your p99 rebuild time.
- Serving stale beats blocking. Thousands of requests waiting on a lock is a different resource exhaustion, not a fix.
- Probabilistic early expiry avoids locks entirely by making the refresh moment vary per request instead of being a shared cliff.
- Background refresh for the handful of keys that are always hot — the request path should never rebuild them.
- Always jitter TTLs. Correlated expiry after a deploy or a cache flush is how a single-key annoyance becomes a full outage.
- Size for the cold-cache case. A 99% hit rate means a cache failure is a 100x database load multiplier. Put a limiter between them.
References
- Optimal Probabilistic Cache Stampede Prevention — Vattani, Chierichetti, Lowenstein — the XFetch algorithm and the maths behind early expiry
- HTTP Cache-Control Extensions for Stale Content — RFC 5861 —
stale-while-revalidateandstale-if-erroras a standard - Redis — distributed locks and their pitfalls — safe lock acquisition, tokens, and expiry
- Caching Strategies: Cache Aside, Write Through, Write Behind — the patterns this problem lives inside