Cache Stampede & the Thundering Herd

Caching is supposed to protect your database. But there’s a failure mode where the cache becomes the trigger for an outage: a single popular key expires, and in the microseconds before it’s repopulated, every request for it misses the cache simultaneously and slams the origin at once. That synchronized surge is a cache stampede (a thundering herd), and it has taken down systems that were running comfortably a moment earlier.

How a calm system suddenly falls over

Imagine a key served 10,000 times/second from cache, with the database never seeing that load. The key has a TTL. The instant it expires:

   t=0      cache has "homepage" → 10,000 req/s served from cache, DB idle
   t=TTL    "homepage" EXPIRES
   t=TTL+ε  10,000 concurrent requests all MISS → all 10,000 hit the DB at once
            DB melts → slow responses → cache stays empty → more pile on → cascade

The database wasn’t sized for 10,000 simultaneous identical queries because it never saw them — the cache absorbed them. Expiry removes that shield for a moment, and the herd tramples through. What did the cache buy us, and what did it cost? It bought enormous load reduction, but it quietly created a correlated failure at the expiry instant.

Fix 1: Locking / single-flight (request coalescing)

Let only one request recompute the value; everyone else waits for that result or briefly serves stale data.

   key misses → first request acquires a lock, recomputes, repopulates cache
   meanwhile → other requests see the lock → wait, or return last-known value
   → exactly ONE query hits the DB instead of 10,000

This is often called single-flight (coalesce concurrent identical loads into one). It’s the most direct fix — the cost is added coordination and deciding what the waiters do (block vs serve stale).

Fix 2: Stale-while-revalidate (early/async recompute)

Don’t wait for hard expiry. Serve the stale value immediately while a background task refreshes it, or recompute probabilistically before the TTL so the refresh is spread out rather than synchronized.

   key near expiry → serve current (slightly stale) value NOW
                   → trigger ONE async refresh in the background
   → users never see a miss; the DB sees one refresh, not a herd

The trade-off: you accept serving data that’s briefly stale in exchange for never exposing a cold-cache window. For most read-heavy content (feeds, product pages) that’s an easy yes.

Fix 3: Jittered / staggered TTLs

A subtler cause: if many keys are populated together (e.g. a cache warm-up or a deploy) with the same TTL, they all expire at the same instant — a herd across many keys at once. Add random jitter to each TTL so expirations spread out.

   BAD:  every key TTL = 3600s  → all expire together → synchronized stampede
   GOOD: TTL = 3600s ± random(0..300s) → expirations smeared across 5 minutes

This one-line change (randomize the TTL) prevents the correlated expiry that turns thousands of independent keys into a single thundering herd. It’s the cheapest fix and worth doing by default.

These compose

Real systems use all three: jittered TTLs to avoid synchronized expiry, single-flight so a miss on a hot key recomputes once, and stale-while-revalidate so users never wait on a cold key. Each targets a different facet of the same problem.

Related trap: cache penetration

A cousin of the stampede: requests for keys that don’t exist (often malicious — random IDs) always miss and always hit the DB, since there’s nothing to cache. Defend by caching the “not found” result for a short time, or with a Bloom filter to reject keys that definitely don’t exist before touching the database.

Under the hood — probabilistic early expiration

Fix 2 said “recompute probabilistically before the TTL.” Here’s the actual trick, sometimes called XFetch (from a 2015 paper on optimal stampede prevention). On every read of a cached value, each request rolls a die whose odds of “recompute now” rise as expiry approaches — and, cleverly, scale with how expensive the value was to compute last time. The standard form recomputes when:

now − ( recompute_cost × beta × ln(random()) )  ≥  expiry_time

Because ln(random()) is a small negative number that occasionally spikes large, one unlucky request volunteers to refresh slightly early while everyone else keeps serving the cached value. The hotter and more expensive the key, the earlier and more eagerly some single request steps up — so the refresh happens before the cliff, performed by exactly one caller, with no lock and no coordinated thundering herd. It’s the same goal as single-flight, reached with a coin flip instead of a lock.

It actually happened — Facebook’s 2010 cache cascade

On September 23, 2010, Facebook went down for hours in a self-reinforcing thundering herd. A bad configuration value made every web server believe its cached copy of that value was invalid, so all of them simultaneously hammered the authoritative database to “fix” it. The database, overwhelmed, returned errors — which the clients interpreted as still invalid, so they retried even harder. Every attempt to recover fed the stampede that was causing the failure. Facebook ultimately had to take the entire site offline to break the feedback loop, then bring it back slowly. It’s this page’s lesson at the largest scale: when a popular cached value disappears, every client acts in unison — and a naive retry turns that synchronized miss into a self-sustaining cascade.

The thread

What does this buy us, and what does it cost? A cache buys massive origin offload — but if you ignore the expiry instant, it quietly concentrates load into a synchronized spike that’s worse than no cache. The fixes (single-flight, stale-while-revalidate, jittered TTLs) cost a little staleness and coordination to buy a smooth, herd-free load curve. The lesson generalizes: any time many actors share a deadline, expect them to act in unison — and design to spread them out. (See also Caching Strategies.)

Check your understanding

1. Why can a database that was idle suddenly be overwhelmed the moment a single hot key expires?
2. How does single-flight / request coalescing reduce the load from a cache miss on a popular key?
3. What does stale-while-revalidate trade away, and what does it guarantee in return?
4. Why do identical TTLs cause a stampede across many keys, and how does jitter fix it?
5. What is cache penetration, and how does caching “not found” or a Bloom filter defend against it?

Show answers

1. While the hot key was cached, the database never saw that load — the cache absorbed all 10,000 req/s. The instant the key’s TTL expires, every concurrent request misses at once and all of them hit the DB simultaneously; it was never sized for that synchronized surge, so it melts, the cache stays empty, and more requests pile on — a cascade. The cache bought huge load reduction but quietly created a correlated failure at the expiry instant.
2. Single-flight lets only one request acquire a lock and recompute/repopulate the value while everyone else waits for that result or briefly serves stale data. So exactly one query hits the DB instead of 10,000 — the cost is added coordination and deciding what the waiters do (block vs serve stale).
3. Stale-while-revalidate trades away strict freshness — it serves a briefly stale value now while one async refresh runs in the background. In return it guarantees users never hit a cold-cache miss, and the DB sees a single refresh instead of a herd; for read-heavy content (feeds, product pages) that’s an easy yes.
4. If many keys are populated together with the same TTL (a warm-up or deploy), they all expire at the same instant, producing a herd across many keys at once. Adding random jitter (e.g. 3600s ± random(0..300s)) smears expirations across a window so they no longer fire in unison — the cheapest fix, worth doing by default.
5. Cache penetration is repeated requests for keys that don’t exist (often malicious random IDs): they always miss and always hit the DB since there’s nothing to cache. Defend by caching the “not found” result for a short time, or using a Bloom filter to reject keys that definitely don’t exist before touching the database.