system-design

The Thundering Herd and Cache Stampedes

The moment a popular cache entry expires, thousands of requests all miss simultaneously and stampede the database at once. A self-inflicted outage that appears exactly when traffic is highest.

Prerequisites: Caching, Retries & Timeouts Time to read: ~14 minutes

The problem

A thundering herd is when many clients all do the same expensive thing at the same instant, overwhelming a resource that could easily handle them if they were spread out.

🚨 The classic case — the cache stampede:

A hot key is cached, serving 10,000 requests/second from Redis. The database is idle.
The key's TTL expires.
Now all 10,000 concurrent requests MISS simultaneously.
All 10,000 hit the database at once — for a key the database was sized to serve 0 times/second.
The database falls over.
When it recovers and repopulates the cache... the TTL expires again later, and it repeats.

🚨 The cruel irony: the stampede hits hardest for the most popular keys (most concurrent requests at expiry) and at peak traffic (most requests in flight). The cache was protecting the database perfectly — until the one instant it didn’t.

The variations

Thundering herds appear in several forms:

Cache stampede — a hot key expires, all requests miss at once (above).
Cache avalanche — 🚨 many keys expire simultaneously (because they were all created together — a deploy, a cache warm, a restart), so the database gets the full uncached load in one instant, not just one key’s worth. → Caching
Retry storm — a service slows, all clients retry at once, amplifying load. → Retries
Reconnection storm — a server restarts, all its clients reconnect simultaneously → WebSockets.
Wake-up stampede — many processes waiting on one event all wake and act at once (the original OS “thundering herd”).

The common shape: synchronized demand hitting a resource all at once. The fixes all break the synchronization or collapse the duplicate work.

The fixes

🚨 The core techniques — know these, they’re common follow-ups:

1. Request coalescing / single-flight — the key fix for stampedes

🚨 When many requests miss the same key simultaneously, only one recomputes; the rest wait for its result. One database query instead of 10,000.

10,000 requests miss "hot_key" at once
→ the first acquires a lock, computes the value, populates the cache
→ the other 9,999 wait for that result (or briefly serve stale)
→ database sees 1 query, not 10,000

This is Go’s singleflight, and the standard stampede fix. 🚨 The single most important technique here.

2. Jittered TTLs — prevent avalanches

🚨 Add randomness to expiry times so keys don’t all expire at the same instant:

❌ TTL = 300s  → keys created together all expire together → avalanche
✅ TTL = 300s + random(0, 60s)  → expiry spreads out → no synchronized miss

📐 One line of code, and it prevents the avalanche entirely. The cheapest, most valuable fix — and a frequent interview point.

3. Stale-while-revalidate — never miss on a hot key

🚨 Serve the stale value immediately while refreshing in the background. The expiring key is refreshed by one background task before/as it expires, and users never experience a miss — they get the slightly-stale value instantly.

✅ Users never wait for a cache miss on hot keys; database load is smooth (one refresh, not a stampede). Built into HTTP (stale-while-revalidate). → HTTP caching

4. Probabilistic early expiration

🚨 Refresh a key before it expires, with increasing probability as expiry approaches — so one unlucky request refreshes early and the rest never miss. Avoids the synchronized-miss instant entirely.

if now - value.computed_at > ttl - beta * abs(log(random())):
    refresh()      # one request refreshes early; others keep using the cached value

5. For retry/reconnection storms: backoff + jitter

🚨 Exponential backoff with jitter so retries/reconnections spread out instead of synchronizing. → Retries & Timeouts. The jitter is the essential part — backoff alone leaves them synchronized.

6. Circuit breaker / load shedding — the backstop

If a stampede does hit, a circuit breaker in front of the database fails fast rather than letting the stampede pile up and cause a cascade, and load shedding keeps the database serving some traffic.

🚨 Different from a stampede but worth knowing (caching): requests for keys that don’t exist anywhere miss the cache and the database (nothing to cache). An attacker requesting random non-existent IDs bypasses the cache entirely, hammering the database.

Fix: cache the negative result (cache “not found” with a short TTL), or a Bloom filter to reject definitely-missing keys before touching anything.

The unifying principle

🚨 Every thundering herd is synchronized demand; every fix either de-synchronizes it (jitter, backoff) or collapses the duplicate work (coalescing, stale-while-revalidate). When you see “everyone does X at the same instant,” reach for one of those two.

🎙️ “The cache stampede fix is request coalescing — when a hot key expires, one request recomputes and the rest wait, so the database sees one query not ten thousand. And jittered TTLs so keys don’t all expire together in an avalanche — that one line prevents a whole class of outage. For retry storms, backoff with jitter to de-synchronize.”

⚖️ Trade-offs

Fix	Gain	Cost
Request coalescing	Collapses the stampede to 1 query	Waiters block briefly; lock complexity
Jittered TTLs	Prevents avalanche, one line	Slightly variable freshness
Stale-while-revalidate	Users never miss on hot keys	Serves slightly-stale data
Probabilistic early expiry	No synchronized miss	Some early refreshes (minor waste)
Backoff + jitter	De-synchronizes retries/reconnects	Slightly slower recovery
Circuit breaker / shedding	Backstop against cascade	Some requests fail fast
Negative caching / Bloom filter	Stops penetration	Extra structure

In the real world

Cache stampedes are a classic production outage — a popular item’s cache entry expires under high traffic, the database gets slammed by the synchronized miss, and it cascades. The fixes (coalescing, jitter, stale-while-revalidate) are standard mitigations that every high-traffic caching layer implements.
Facebook’s memcache paper documents “leases” — their mechanism for exactly this: preventing stampedes by having one client hold a lease to recompute while others wait. It’s the reference for handling stampedes at extreme scale.
The reconnection storm is a well-known operational hazard for services holding many persistent connections (chat, real-time) — a deploy disconnects everyone, and without jittered reconnect backoff, the simultaneous reconnection takes down the replacement instances. Jitter is the standard fix.

🚨 Interview traps

Not knowing the cache stampede — a very common caching follow-up.
No coalescing — the key stampede fix.
No jittered TTLs — the one-line avalanche prevention.
Backoff without jitter for retry storms — leaves them synchronized.
Not distinguishing stampede (hot key expires) from avalanche (many keys expire) from penetration (key doesn’t exist).
Ignoring the cache’s failure mode — what happens when the cache is down and all traffic hits the database.

🎙️ Soundbites

“A cache stampede is when a hot key expires and thousands of requests miss at once, slamming the database — worst for the most popular keys at peak traffic. The fix is request coalescing: one request recomputes, the rest wait, so the database sees one query not ten thousand.”
“Jittered TTLs prevent the avalanche where many keys expire together — one line, ttl + random, and a whole class of outage disappears.”
“Stale-while-revalidate means users never wait for a miss on a hot key — serve the stale value instantly while one background task refreshes.”
“Every thundering herd is synchronized demand — either de-synchronize it with jitter and backoff, or collapse the duplicate work with coalescing. That’s the whole toolkit.”
“For a reconnection storm after a deploy, clients reconnect with exponential backoff plus jitter, or a million clients reconnect in the same second and take down the replacements.”

🛠️ Try it

1. Cause a cache stampede. Cache-aside with a 10-second TTL, load-tested at 500 concurrent requests for one hot key. Watch the database QPS spike every 10 seconds like a heartbeat as the key expires and everyone misses at once. This is the single most instructive caching exercise.

2. Fix it with coalescing. Add single-flight (one request computes, others wait). Watch the database spikes flatten to one query per expiry.

3. Prevent an avalanche with jitter. Populate 1,000 keys with identical TTLs, then observe the database spike when they all expire together. Add ttl + random(0, 60) and watch the expiry spread out smoothly. One line, whole class of outage gone.

4. Simulate a reconnection storm. Hold 1,000 connections, kill the server, restart it. Watch what happens with instant reconnect (all at once, overwhelming) vs jittered backoff (spread out). The jitter difference is dramatic.

Check yourself

1. What is a cache stampede and why does it hit hardest at the worst time?

A cache stampede is when a cached entry expires and, because it's being requested heavily, many concurrent requests all miss the cache at the same instant and hit the underlying resource (usually the database) simultaneously — for a key the database was sized never to serve, because the cache had been absorbing all of it. If a key served 10,000 requests/second from cache, its expiry means 10,000 concurrent database queries in one instant, overwhelming a database provisioned for the ~0 requests/ second it normally sees for that key. It hits hardest at the worst time for two compounding reasons: the stampede is proportional to the key's popularity (the more popular the key, the more concurrent requests are in flight at the moment it expires, so the biggest keys cause the biggest stampedes), and it's proportional to overall traffic (more total requests means more concurrent misses), so it's worst at peak load. The cruel irony is that the cache was protecting the database perfectly right up until the single instant of expiry — and it recurs, because when the database recovers and the cache repopulates, the TTL expires again later and the stampede repeats. So a system that looks perfectly healthy periodically self-inflicts an outage exactly when it's busiest.

2. What is request coalescing (single-flight) and why is it the key stampede fix?

Request coalescing means that when many requests simultaneously miss the same cache key, only *one* of them actually recomputes the value (queries the database), while all the others *wait* for that single computation to finish and then use its result. So instead of 10,000 concurrent misses producing 10,000 database queries, the first request acquires a lock (or is designated the "leader"), computes the value, and populates the cache, and the other 9,999 either block until it's done or briefly serve a stale value — and the database sees exactly one query. It's the key stampede fix because it directly attacks the root cause: the stampede is *duplicate work* (thousands of requests all recomputing the same value that only needs to be computed once), and coalescing collapses that duplicate work to a single execution. It's implemented as Go's `singleflight`, Facebook's memcache "leases," and similar mechanisms everywhere. The costs are modest: the waiting requests block briefly (adding a little latency for them), and you need a coordination mechanism (a lock or in-flight-request registry). But it transforms the stampede from a database-crushing flood into a single query, which is why it's the first thing to reach for when a hot key can expire under load.

3. What's the difference between a cache stampede, a cache avalanche, and cache penetration?

They're three distinct caching failure modes. A **cache stampede** is when *one hot key* expires and its many concurrent requesters all miss at once, slamming the database with duplicate queries for that single key — the problem is synchronized misses on a popular key, fixed by request coalescing and stale-while-revalidate. A **cache avalanche** is when *many different keys* expire at the same instant — typically because they were all created together (a deploy, a cache warm-up, a restart) with identical TTLs — so the database gets the full uncached load across many keys simultaneously, not just one key's worth; it's a broader synchronized-expiry problem, fixed by jittering TTLs so keys don't expire in lockstep. **Cache penetration** is entirely different: requests for keys that *don't exist anywhere* — not in the cache and not in the database — so every such request misses the cache and then misses the database (there's nothing to cache), giving the cache zero protective value; an attacker requesting random non-existent IDs exploits this to bypass the cache and hammer the database. It's fixed by caching the *negative* result (cache "not found" with a short TTL) or using a Bloom filter to reject definitely-missing keys before touching the database. Distinguishing them matters because they have different causes (hot key expiry vs synchronized bulk expiry vs nonexistent keys) and different fixes (coalescing vs jitter vs negative caching), and interviewers probe whether you know which is which.

4. Why do jittered TTLs prevent cache avalanches, and why is it such a valuable fix?

A cache avalanche happens when many keys expire at the same instant, which occurs whenever they were populated together with the same TTL — for example, a deploy that warms the cache, a restart that repopulates it, or a batch job that loads many keys at once, all with `TTL = 300s`. Exactly 300 seconds later, they all expire simultaneously, and the database gets a synchronized flood of misses across all those keys. Jittering the TTL — using `TTL = 300s + random(0, 60s)` instead of a fixed 300s — spreads the expiry times across a window, so the keys expire gradually over that 60-second range rather than all at the same moment, and the database sees a smooth trickle of misses it can easily absorb rather than a cliff. It's such a valuable fix because it's essentially free (one line of code adding a random offset to the TTL), requires no coordination or additional infrastructure, and eliminates an entire class of outage — the synchronized-bulk-expiry avalanche — that is otherwise easy to trigger accidentally (any bulk cache population creates the risk). The general principle it embodies — add randomness to de-synchronize events that would otherwise align — recurs throughout distributed systems (jittered retry backoff, jittered reconnection, jittered scheduled jobs), and for caching specifically, jittered TTLs are one of the highest-value-per-effort mitigations available.

5. What's the unifying principle behind all thundering-herd fixes?

Every thundering herd — cache stampede, cache avalanche, retry storm, reconnection storm, wake-up stampede — is fundamentally *synchronized demand hitting a resource all at once*: many actors doing the same expensive thing at the same instant, overwhelming a resource that could easily handle them if the demand were spread out. Correspondingly, every fix works by one of two mechanisms: **de-synchronizing the demand** so it spreads over time instead of arriving simultaneously — jittered TTLs (expiry spreads out), exponential backoff with jitter (retries and reconnections spread out), probabilistic early expiration (one key refreshes early rather than all at the expiry instant); or **collapsing the duplicate work** so the synchronized demand produces one unit of work instead of thousands — request coalescing / single-flight (one request recomputes, the rest wait), stale-while-revalidate (one background refresh serves everyone). Recognizing this unifying pattern is the practical payoff: whenever you see "everyone does X at the same moment and it overwhelms Y," you immediately know to reach for either de-synchronization (add jitter/randomness to spread the timing) or work-collapsing (deduplicate so the herd's demand becomes a single operation), rather than treating each thundering-herd variant as a separate mystery. It also connects the caching fixes (coalescing, jitter) to the resilience fixes (backoff, circuit breakers) as instances of the same underlying idea.