Q19 — What is a cache stampede — and how do you prevent it?

What is a cache stampede?

A cache stampede — also called a thundering herd — is a specific failure pattern where a large number of requests simultaneously discover a cache miss and all rush to the database at the same moment to regenerate the same piece of data.

Here's the setup: you have a popular piece of data — say, the front page of a news site, or a trending product page — cached under a single key. Thousands of requests per second are hitting that key. The cache handles all of them with no problem.

Then the TTL expires.

In the window between the TTL expiring and the key being repopulated, every incoming request finds a cache miss. All of them query the database for the same data. The database, which was designed assuming the cache would absorb 99% of this traffic, suddenly receives a thousand identical queries for the same row. Under this load it may slow down or fall over — and while it's slow, more requests arrive, also find a miss, and also hit the database. The situation compounds.

The irony: the more popular the cached item, the more catastrophic the stampede when it expires.

Why does this happen even with a cache?

The cache miss window is the root cause. Between the moment the old value expires and the moment a new value is written back to the cache, every concurrent request is flying blind. Each one independently concludes "the cache doesn't have this" and independently decides to go compute it from scratch.

None of these requests knows the others exist. There is no coordination — they're all stateless HTTP handlers running on different threads or servers. The cache gives them no signal that "someone else is already fetching this, please wait."

This is a coordination problem masquerading as a cache problem.

Solution 1: Cache locking (mutex on regeneration)

The most direct fix: when a request discovers a cache miss, it acquires a distributed lock before querying the database. The first request to acquire the lock fetches the data and repopulates the cache. All other concurrent requests that also found the miss either:

• Block and wait for the lock to be released, then read the freshly populated cache value
• Return a "please retry" response immediately, letting the client retry in a moment

In Redis, this is implemented with SET key value NX PX ttl — set only if the key doesn't exist, with a short TTL. Only one caller succeeds; the rest treat the failed set as "someone else is handling it."

The remaining problem: While the lock-holder is querying the database, all other requests are blocked or degraded. If the database query takes 500ms, every concurrent request waits 500ms. This is better than a stampede, but you've traded a database explosion for a visible latency spike to users.

Solution 2: Serve stale while revalidating

Instead of letting the key expire hard — where one moment it has a value and the next it's gone — keep serving the old (stale) value while simultaneously refreshing it in the background.

The mechanism: store two pieces of metadata alongside the cached value — the "soft TTL" (when the value should be refreshed) and the "hard TTL" (when the value must be considered invalid). When a request arrives after the soft TTL but before the hard TTL:

1. Serve the stale value immediately — no cache miss, no database hit, user gets a response now
2. Trigger a background refresh — one asynchronous task fetches fresh data from the database and updates the cache
3. Subsequent requests get the new value once the background refresh completes

This is called stale-while-revalidate, and it's conceptually clean: users always get a response (stale or fresh), and the database is only hit once per refresh cycle, not by every concurrent request.

The trade-off: users might see stale data for a brief period after the soft TTL. For a news headline, a product description, or a leaderboard — where data changes infrequently and a few seconds of staleness is acceptable — this is invisible in practice.

HTTP already supports this pattern via the Cache-Control: stale-while-revalidate=N header, and it's natively implemented in CDNs and browser caches.

Solution 3: Probabilistic early expiration (XFetch)

A clever alternative: don't wait for the TTL to expire. Start refreshing the key slightly before it expires, using probability to ensure only one request does the refresh.

The algorithm (called XFetch): each request that reads a cached value computes a random value and compares it against the time remaining until expiration. The closer to expiration, the higher the probability of triggering an early refresh. This means:

• Far from expiration: near-zero probability of early refresh — most requests just read normally
• Close to expiration: high probability — one request probabilistically "wins" the refresh and goes to the database while all other requests still see the valid cached value (it hasn't expired yet)
• At expiration: the value has already been refreshed by the early winner, so no stampede ever occurs

The key insight: because the refresh happens before the value expires, all concurrent requests during the refresh still have a valid cache value to serve. There is no miss window. No locking needed. No stale data served (the value is still valid when the refresh is triggered).

XFetch is elegant and requires no distributed coordination — each cache read independently computes its refresh probability.

Solution 4: TTL jitter

The simplest fix, and often overlooked: when multiple cache keys are populated at roughly the same time (a common pattern after a cache flush or deployment), they'll all expire at roughly the same time — causing a synchronized stampede across all of them simultaneously.

The fix: add randomness to TTL values. Instead of setting every key with TTL = 3600 seconds, use TTL = 3600 + random(-300, +300). Keys now expire in a 10-minute spread rather than all at once.

This doesn't prevent the stampede for a single popular key, but it prevents the mass synchronized expiration that wipes out a large portion of your cache at once. It's a cheap, zero-overhead addition to any cache-set operation.

Solution 5: Background refresh with persistent cache

The most robust approach: cache keys never expire in the traditional sense. Instead, a background job periodically refreshes popular keys on a schedule, independent of incoming requests.

A scheduler runs every 60 seconds, refreshes the top 1000 most-accessed keys, and writes fresh values to the cache. Requests always hit a valid, populated cache entry. The TTL on the key is set to, say, 10 minutes — long enough that even if the background refresh skips a cycle, the key is still valid.

The cost: requires knowing which keys to refresh proactively (needs access tracking), and the background job is now infrastructure you must maintain and monitor. But for genuinely hot, predictable data, this eliminates stampedes entirely.

The mental model

Cache stampede:
  Popular key TTL expires
  → N concurrent requests all find miss
  → All N query the database simultaneously
  → Database collapses under N identical queries
  → More requests arrive during collapse, repeat

Root cause: no coordination between concurrent requests during the miss window

Solutions:
  ├── Cache locking (mutex)
  │     First miss acquires lock → fetches DB → populates cache
  │     Others wait or retry
  │     Cost: latency spike during lock hold
  │
  ├── Stale-while-revalidate
  │     Serve old value → background refresh → no miss window
  │     Cost: brief staleness after soft TTL
  │
  ├── Probabilistic early expiration (XFetch)
  │     Refresh before expiration via probability
  │     No miss window, no locking, no coordination
  │     Best for high-traffic single keys
  │
  ├── TTL jitter
  │     Randomize expiry → no synchronized mass expiration
  │     Cheap to implement, handles bulk expiry problem
  │
  └── Background refresh
        Scheduler refreshes hot keys proactively
        Requests always hit populated cache
        Cost: infrastructure complexity, requires hot-key tracking

Cache stampedes are one of those failure modes that only appears at scale — a system that works perfectly under normal load suddenly falls over at the worst possible moment (peak traffic, after a deployment, after a Redis restart). The fix must be chosen based on how much staleness your application can tolerate and how much operational complexity you're willing to carry.