Catalog My learning Blog
System Design Roadmap: 100-Day Course for Engineers · Phase 4 · Lesson 39 · 5 min read

Thundering Herd and Cache Stampede Prevention

On this page
  1. Symptom: the database falls over every hour, on the hour
  2. Diagnose: what triggers a cache stampede
  3. Fix: four ways to prevent a cache stampede
  4. Prevent: cache warming and database protection
  5. Check yourself

Symptom: the database falls over every hour, on the hour

The home page's "top deals" entry is cached for exactly an hour and served 3,000 times a second. Recomputing it takes a 2-second query. At the top of each hour the entry expires, and in those 2 seconds about 6,000 requests miss and run the same expensive query. Database CPU hits 100 percent, other queries time out, and it recovers a minute later. That's a cache stampede, also called a thundering herd.

Diagnose: what triggers a cache stampede

  1. A hot key expires. As above: one popular entry, many concurrent misses.
  2. Many keys expire together. Keys loaded at the same moment with the same TTL expire at the same moment (Day 34).
  3. A cold cache. A cache cluster restarts or a new region comes online; every request misses until it warms up.

The signature in monitoring: cache hit rate dips sharply, database load and latency spike at the same moment, often on a regular schedule.

Without protection, many concurrent misses hit the database at once; with single-flight, one request recomputes while the others wait for its result.
Without protection, many concurrent misses hit the database at once; with single-flight, one request recomputes while the others wait for its result.

Fix: four ways to prevent a cache stampede

Single-flight (request coalescing). Only one request recomputes a missing key; the others wait briefly and then read the fresh value. Within one server, a per-key lock or a shared in-flight future does it; .NET's HybridCache does this for you (Day 31). Across servers, use a short-lived distributed lock, for example Redis SET key:lock token NX PX 5000. Day 9 of the Redis course walks through a tested implementation.

Plan for the lock holder failing. If the server recomputing the value crashes, waiters must not wait forever: give the lock a short expiry, give waiters a timeout, and let them fall back to the stale value or a cheap default.

TTL jitter. Add a random offset to every TTL so entries loaded together don't expire together: ttl = 3600 + random(0, 300).

Serve stale while refreshing. Keep the old value past its soft expiry. The first request after expiry triggers a background refresh while everyone, including that request, gets the stale value immediately. That's what stale-while-revalidate does at the HTTP layer (Day 38); you can do the same in application caches by storing a "refresh after" time next to the value.

Probabilistic early refresh. Instead of everyone waiting for the exact expiry, each request has a small chance of refreshing early, rising as expiry approaches and as recomputation gets slower. This approach, from a 2015 paper by Vattani and colleagues, is often called XFetch:

Python
# xfetch.py: probabilistic early refresh, so one hot key is recomputed before it expires
import math, random, time

def should_refresh(expires_at: float, compute_seconds: float, beta: float = 1.0) -> bool:
    # refresh early with a probability that rises as expiry approaches and as recomputation gets slower
    return time.time() - compute_seconds * beta * math.log(random.random()) >= expires_at

For a value that takes 2 seconds to compute, simulating 10,000 requests gave:

Code
  60s before expiry: 0.0% of requests refresh early
  10s before expiry: 0.7% of requests refresh early
   3s before expiry: 22.4% of requests refresh early

At 3,000 requests per second, some request almost certainly refreshes the value seconds before it expires, so the entry never goes missing. No locks needed.

Prevent: cache warming and database protection

  • Warm caches before sending traffic to a new cluster or region, from logs of popular keys.
  • Protect the database with limits: a connection pool cap and timeouts mean a stampede degrades gracefully instead of taking everything down.
  • Watch hit rate and miss bursts per key prefix, so hot keys are visible before they cause an incident.
  • Retry storms make it worse. When the database slows, clients time out and retry, adding more load to the same moment. Retries with backoff and jitter (Day 74) and a cap on concurrent database queries keep a stampede from feeding itself.

Large systems combine several of these. Facebook's memcache paper describes leases, which give one client the right to refill a missing key while others wait or use a slightly stale value, specifically to prevent thundering herds.

Check yourself

The lock holder crashed and waiters had no timeout. Give the lock a short expiry and waiters a deadline, with a stale value as the fallback.

When a hot key is missing, only the first request runs the expensive query; every concurrent request for the same key waits for that one result instead of starting its own. A thousand simultaneous misses become one database query, which is exactly the load spike a stampede would otherwise cause.

Each request independently has a small, rising chance to refresh before expiry. At high traffic, one request refreshes early, so the entry never expires under load.

Loading the most important keys into the cache before traffic arrives, for example after a deploy, a cache restart or before a known sales event. It prevents a cold cache from sending a burst of misses to the database at the worst moment.

Users get an instant response instead of waiting on the rebuild, and the database sees one refresh instead of a pile-up. For most data, being a few seconds out of date is far less harmful than a slow page or an outage.