CachingGENERALRUNTIME-SPECIFICSCALE-SPECIFIC
Cache Stampede
One popular key expires, every in-flight request misses at the same instant, and all of them run the same expensive query at once.
The requirement, the obvious build, and why it breaks
Every lesson starts where the work starts: someone asked for something, and the first implementation that comes to mind has a problem.
The question
A single key expires and the database falls over. How does one missing entry become an outage?
The requirement
The homepage feed is expensive to compute, so it is cached. It should stay fast, including in the second after the cached copy expires.
The obvious build
Cache-aside with a TTL. On a miss, recompute and store. Misses are rare because the key is popular, so the miss path does not need to be fast.
Why it breaks
Popularity is exactly what makes it dangerous. Consider a key served to thousands of concurrent requests: at the instant it expires, every request in flight takes the miss path, because none of them can see a populate that has not happened yet.
How it breaks in production
- Popularity is exactly what makes it dangerous. Consider a key served to thousands of concurrent requests: at the instant it expires, every request in flight takes the miss path, because none of them can see a populate that has not happened yet.
- The origin now receives that many copies of a query it normally serves once per TTL. If the query holds a connection, the pool is exhausted; every *other* endpoint sharing that pool starts timing out too (Connection Pool Exhaustion).
- The recomputation slows down under its own load, so it takes longer than usual, so more requests pile into the same window, so the herd grows. This is a positive feedback loop, not a spike.
- Clients time out and retry, adding a second herd on top of the first (Retry Storms).
- When one instance finally populates the key, everything recovers instantly — which is why the incident is short, dramatic, and leaves no obvious cause in the logs.
Requirement→API Contract→Application Logic→Data Access→External Deps→Concurrency→Failure→Security→Observability→Deployment→Scale
What is actually happening
- A stampede — also called a thundering herd or dogpile — happens because a cache miss is not atomic with its populate. Between the miss and the populate, the cache still says "empty" to everyone who asks (Thundering Herd).
- The herd size is bounded by concurrency, not by request rate: it is roughly the number of requests that arrive during the *loader's* duration. A slow loader collects a bigger herd, which is why the loop reinforces itself.
- Three distinct events produce herds and they need different mitigations. Expiry of one hot key hits one loader. Mass expiry of a synchronised cohort hits many. Cold start — a restart, a flush, a failover, a new region — hits every key at once and is the worst case (Cache Warmth and the Real Cost of Migration).
- The four mitigations attack different points. Single-flight makes only one request run the loader per key per process. Distributed locking extends that across the fleet. Jittered TTL stops cohorts forming. Stale-while-revalidate removes the blocking miss entirely by serving the old value while one refresh runs.
- Note the layering: jitter reduces how often herds form, coalescing reduces how large they get, and stale-while-revalidate removes the user-visible latency. They are not alternatives.
How one expiry becomes a herd
Work through the sequence. The key expires. A request arrives, finds nothing, and starts the loader — which takes some time to run. Every request that arrives during that time also finds nothing, because the populate has not happened yet, and each starts its own loader. The herd size is the arrival rate multiplied by the loader duration, and both of those numbers get worse as the herd grows.
That is the feedback loop: more concurrent loaders make the origin slower, a slower origin makes each loader run longer, and a longer loader collects more requests into the herd. It ends only when one populate finally lands — which is why recovery is instantaneous and the postmortem finds nothing wrong with any individual component.
UserLLMAgentToolDataDecisionHumanGuardrail
The four mitigations, and what each one costs
These are layers, not options. In practice you want jitter and single-flight in almost every cache (they are nearly free), stale-while-revalidate on expensive derived data, and a distributed lock only where N duplicate loads is genuinely unaffordable.
Read the last column carefully. Every one of these leaves something unfixed, and picking one and declaring the problem solved is the most common way teams have this incident twice.
| Mitigation | What it does | What it costs | What it does NOT fix |
|---|---|---|---|
| Single-flight (per process) | One loader run per key per process; everyone else awaits that promise | A dozen lines and a map. Needs an atomic get-or-insert on threaded runtimes | Cold start across N instances — still N loader runs |
| Distributed lock | One loader run per key across the whole fleet | A lock service on the read path, a lease, renewal, and a crashed-holder failure mode | Waiters still hold threads and connections while they sleep |
| Jittered TTL | Prevents cohorts of keys expiring together | One line; expiry becomes non-deterministic | A single genuinely hot key, and cold start |
| Stale-while-revalidate | Serves the old value while one refresh runs — no request blocks | A soft/hard deadline pair, and users knowingly served stale data | The very first population of a key; a silently failing refresher |
| Pre-warm on boot | Populates the hot set before traffic arrives | Slower startup and a warm-set list to maintain | Mid-life expiry of anything not on the list (Cache Warmth and the Real Cost of Migration) |
| Bounded loader | Caps concurrent expensive queries regardless of herd size | Excess requests fail fast or queue instead of running | The herd itself — it limits the blast radius, not the cause (Resource Limits) |
Single-flight is a map of in-flight promises
RUNTIME-SPECIFICWritten for a single-threaded event loop, where get-then-set on the map is safe because no other task can run between the two statements. On the JVM, Go or .NET this exact code has a race: two threads both see an empty map and both start the loader. Use the runtime's atomic primitive instead (Double-Checked Locking: The Canonical Cautionary Tale).
The mitigation with the best cost-to-benefit ratio in this whole module is a map from key to the promise of its in-flight load. The first request to miss creates the entry; every subsequent request finds it and awaits the same promise. One loader run, one populate, N satisfied callers.
Two details make it correct rather than nearly-correct. The entry must be removed in a finally, or one failed load poisons the key for the process lifetime. And the map must be keyed on the *full* cache key — including tenant and user — because coalescing two requests with different authorization means serving one caller the other's data.
Per-process request coalescing
1const inFlight = new Map<string, Promise<unknown>>()2 3function singleFlight<T>(key: string, loader: () => Promise<T>): Promise<T> {4 const existing = inFlight.get(key)5 if (existing) {6 metrics.inc('cache_coalesced', { prefix: prefixOf(key) })7 return existing as Promise<T>8 }9 // On a single-threaded event loop nothing can interleave between the get10 // above and the set below. On a threaded runtime this needs an atomic11 // get-or-insert (computeIfAbsent / singleflight.Group) instead.12 const p = loader().finally(() => inFlight.delete(key))13 inFlight.set(key, p)14 metrics.inc('cache_loader_runs', { prefix: prefixOf(key) })15 return p16}17 18// The key MUST carry everything that decides who may see the value.19// Coalescing two callers with different permissions is a data leak.20const feed = await getOrLoad(21 `feed:${tenantId}:${userId}`,22 jitter(300),23 () => singleFlight(`feed:${tenantId}:${userId}`, () => buildFeed(tenantId, userId)),24)The finally is load-bearing: without it a rejected load stays in the map and every future request for that key awaits a promise that will never resolve again. The metric pair — coalesced versus loader runs — is what tells you the mitigation is actually firing.
How to build it
Most important first.
- Add single-flight per process first. It is a map from key to in-flight promise, it is a dozen lines, it needs no infrastructure, and on a fleet of N instances it reduces the herd from "every concurrent request" to "at most N" (Request Coalescing).
- Add jittered TTLs second. Also one line, and it prevents cohorts from forming at all (TTL and Expiry).
- Add stale-while-revalidate for anything expensive where slightly-stale is acceptable. This is the mitigation that removes the latency spike rather than shrinking it, and it makes the refresh path invisible to users.
- Reach for a distributed lock only when N concurrent loader runs is genuinely unaffordable — a minutes-long report, a rate-limited third-party call. It buys fleet-wide coalescing and costs you a lock with a lease, a renewal story and a failure mode where the holder dies mid-computation (A Mutex on Server A Does Nothing About Server B).
- Bound the loader independently: a timeout and a concurrency limit on the expensive query, so even a herd that gets through cannot exhaust the pool (Resource Limits).
- Plan for cold start explicitly. Warm the top keys on boot before accepting traffic, or ramp traffic in — a readiness probe that passes before the cache is warm sends full load to an empty cache (Liveness vs Readiness).
What can go wrong
Failure modes
- Single-flight is per-process, so it cannot help a cold start across the fleet. N instances still means N loader runs, and if N is large that is still a herd.
- A distributed lock whose holder crashes mid-load: without a lease and expiry, every other request blocks until someone notices. With too short a lease, two holders run concurrently and you are back where you started (Deadlock).
- Waiting on the lock turns a fast failure into a slow one — a hundred requests sleeping on a lock hold a hundred connections and threads while doing nothing.
- Stale-while-revalidate whose refresher fails silently, serving indefinitely-stale data with no error.
- Refresh-ahead that recomputes every key on a timer regardless of demand, which is a scheduled load spike wearing a mitigation's name.
- Mitigating the stampede and leaving the loader unbounded, so the next unrelated burst exhausts the pool anyway.
What can race
- The defining race: N concurrent readers observe a miss on the same key before any of them populates it.
- Single-flight map insertion is itself a race in a genuinely multi-threaded runtime — two threads can both find no in-flight entry and both create one. It needs an atomic get-or-insert, not a check-then-set (Double-Checked Locking: The Canonical Cautionary Tale).
- Lock acquisition versus lease expiry: the holder's lease expires mid-computation, a second holder starts, and now two loaders run and two populates race.
- Stale-while-revalidate: multiple readers past the soft deadline each start a refresh unless the refresh is itself coalesced.
- A populate racing a concurrent invalidation, so the herd resolves by writing a value that was already stale (Cache Invalidation).
Security
- A stampede is a denial-of-service amplifier an attacker can trigger deliberately: find the expensive uncached path, request it concurrently, and each request costs you far more than it costs them (Rate Limiting).
- Cache penetration is the same attack against keys that will never be populated — request ids that do not exist, so every request is a guaranteed miss. Negative caching and a membership filter are the defences (Bloom Filter).
- Coalescing has a correctness requirement: only coalesce requests whose *authorization* is identical. Sharing one in-flight load between two callers with different permissions serves one caller's data to the other. Key the single-flight map on the full cache key, including tenant and user (Tenant Isolation).
- Rate-limit before the cache lookup, not after. A limiter that only counts misses lets an attacker generate misses freely (Authenticate First, or Rate-Limit First?).
Misreads
- "Stampedes only matter for slow queries." A fast query multiplied by thousands of concurrent requests is still a pool exhaustion event. Concurrency is the multiplier, not duration.
- "A shorter TTL reduces the risk." A shorter TTL means *more* expiry events, so more chances to stampede. It reduces staleness, not herd risk.
- "We use Redis, so this cannot happen." Redis serves the miss faithfully to every caller. The stampede is on the origin behind it and is entirely independent of the cache product.
- "The lock solves it." A lock without a lease is a distributed deadlock waiting for a crashed holder; a lock with too short a lease permits concurrent loaders. The lock is a coordination problem you have chosen to take on (Pessimistic Locking).
- "It resolved itself in thirty seconds, so it was a blip." Self-resolution is the signature of a stampede, not evidence it was harmless. It will recur on the same schedule as the TTL.
Operating it
How you see it in production
- Concurrent loader executions per key — a gauge you have to add deliberately, and the only signal that says "stampede" rather than "the database was slow".
- The signature in existing signals: a miss-rate spike, an origin query-rate spike and a latency spike that all start in the same second and end in the same second (From Symptom to Root Cause).
- Connection-pool wait time. A stampede shows up as pool saturation before it shows up as errors (Connection Pool Saturation: Waiting in Front of an Idle Database).
- A periodic sawtooth in miss rate with a period equal to the TTL means synchronised expiry, which is a stampede you have not noticed yet.
- For single-flight: count requests coalesced versus loader runs. The ratio is exactly what the mitigation is buying you.
- Log at loader entry with the key, sampled. Several log lines for the same key in the same second is the herd, visible directly.
What changes at 10x and 100x
- Herd size scales with concurrency, so the same code that is fine at low traffic becomes an outage at high traffic with no change to the cache configuration. This is the classic "worked until it did not" failure.
- At 100x, per-process single-flight is no longer sufficient on a cold start, because N instances each running the loader is itself significant load. That is where distributed coordination starts to pay for itself.
- Hot keys concentrate on one cache node. At high scale a stampede on a hot key can saturate that node's connection handling even before the origin notices (Hot Keys: When Aggregate Metrics Hide a Saturated Node).
- Autoscaling makes cold starts routine rather than rare: every scale-out event adds an instance with an empty local cache (Autoscaling a Backend).
What this costs
- Single-flight: nearly free, no infrastructure, and only coalesces within one process. Fleet-wide it leaves you N loader runs.
- Distributed lock: fleet-wide coalescing, and it adds a lock service on the read path, a lease-expiry decision, and a failure mode where the lock holder dies and everyone waits.
- Jittered TTL: one line, prevents cohorts, and does nothing for a genuinely hot single key or a cold start.
- Stale-while-revalidate: removes the user-visible spike entirely, and it means users are served deliberately stale data during every refresh, plus a second state to reason about.
- Pre-warming: turns a cold start into a slower start, and the warm set has to be maintained as usage patterns change.
Where this applies
Backend advice is context-sensitive. These labels say what each claim is specific to, and where a different stack or scale would differ.
- GENERALThe herd forms because miss and populate are not atomic. That is true of every cache, every language and every product.
- RUNTIME-SPECIFICSingle-flight is easiest on a single-threaded event loop (Node, asyncio), where a map from key to in-flight promise needs no locking because nothing can interleave between the lookup and the insert. On a multi-threaded runtime — JVM, Go, .NET — the same map needs an atomic get-or-insert such as
computeIfAbsentorsingleflight.Group, or two threads will both start the loader. - SCALE-SPECIFICBelow roughly one loader-duration's worth of concurrent requests per key, the herd is a handful of duplicate queries and is not worth coordinating away. The mitigations earn their complexity once concurrency on a single key is high.
Where the depth lives
This domain teaches the application-side mechanism and hands the rest off.