Cache stampede

The problem it solves

A key is hot — the front page, a popular product, a feature flag every request reads. It sits in the cache with a ten-second TTL, serving three thousand requests a second at sub-millisecond latency. Then it expires.

In the interval between the expiry and the first successful recompute, every one of those three thousand requests per second finds a miss and goes to the database. If the recompute takes 400 ms, that is roughly 1,200 identical queries for the same row, arriving simultaneously, all computing the same answer. The database slows down under the load, so the recompute takes longer, so more requests pile in behind — and a cache that was protecting the database has just aimed every request it was absorbing at it, at once.

This is the most common cache-related outage there is. It has several names — thundering herd, dogpile, stampede — and one property worth remembering: it is triggered by success. The higher your traffic and the better your hit ratio, the bigger the herd when a key expires.

The mechanism

Four techniques address it, and they solve different parts of the problem.

Request coalescing (single-flight): when a miss occurs, the first requester takes a lock for that key and does the recompute; everyone else waits for its result. N identical misses become one query. This is the direct fix and it is a few lines of code — Go’s singleflight, a ConcurrentHashMap.computeIfAbsent, a promise cached under the key.

TTL jitter: instead of a fixed TTL, use ttl × (1 ± jitter). This does nothing for a single hot key — one key still expires at one instant — but it prevents the correlated case, where a thousand keys warmed by the same deploy or the same batch all expire in the same second.

Early recomputation (refresh-ahead, stale-while-revalidate): before the TTL expires, refresh the value in the background while continuing to serve the existing one. Nobody ever waits on a recompute, because the miss never happens. The probabilistic variant — XFetch — has each requester independently decide to refresh early with a probability that rises as expiry approaches, which spreads the refresh without coordination.

Serve stale on error: if the recompute fails, keep serving the old value rather than propagating the failure. This turns a dependency outage into a staleness problem, which is nearly always the better problem.

What the simulation shows

Run the default and watch the database-queries panel. Every TTL boundary produces a spike of near-identical queries — and the latency panel shows it is not merely a spike in count. As the database fills, each query takes longer, so the window in which requests can pile up is longer, so more pile up. That positive feedback is why the incident is not a blip: it is a stampede that sustains itself, the same metastable shape as a retry storm.

Now turn on coalescing. Thousands of identical misses become one query. The spike is gone from the database panel entirely, and the cost is that the waiting requests are slow for one recompute’s duration rather than fast-and-wrong.

Turn on jitter instead and watch what it does and does not fix: the single hot key still stampedes, because jitter randomises when one key expires, not how many requests arrive in the window. Jitter is for the correlated-expiry case; it is not a substitute for coalescing, and this is the most commonly confused pair on the page.

Then turn on early refresh: the miss disappears entirely. Nobody waits, because the value is renewed before anybody needs it to be.

The numbers worth carrying

The size of the herd is rps × recompute_time. At 3,000 requests per second and a 400 ms recompute, that is 1,200 concurrent identical queries. Compute this number for your hottest key before deciding whether you need coalescing; if it is 3, you do not, and if it is 1,200, no amount of database tuning will save you.

The feedback term is the reason it becomes an outage rather than a spike: recompute time is itself a function of database load, so the herd size grows as the herd arrives. Any concurrency limit on the origin — a bounded pool, a semaphore per key — breaks the loop even without coalescing, because it converts unbounded pile-up into a bounded wait.

Where it breaks down

Coalescing is per-process. A single-flight map lives in one application instance. With fifty instances, a stampede becomes fifty queries instead of 1,200 — a huge improvement, and not one. If one query is required, the lock must be shared (a SET NX lease in Redis with a short TTL), and now the lock has its own failure modes: the holder dies and everyone waits for the lease to expire, or the lease expires early and you have two computers doing the work anyway. See distributed locks for why a lease cannot promise mutual exclusion.

Waiting is not free. Coalescing converts thousands of database queries into thousands of waiting requests, each holding a connection or a thread for the whole recompute. If that pool is shared, you have moved the outage rather than removed it — see bulkheads. Give the wait a timeout shorter than the caller’s.

Early refresh costs recomputes. Refreshing at 80% of TTL on a key nobody will read again is wasted work. Probabilistic early expiry, gated on recent access, keeps that bounded.

Cold start defeats all of it. A cache tier that restarts has no entries to serve stale and nothing to refresh ahead of. That is a capacity problem, not a stampede problem, and its answer is staged restarts and warming.

What people get wrong

“Jitter fixes stampedes.” It fixes correlated expiry. The hot-key stampede is unaffected, and the simulation shows this in one click.

“Longer TTLs help.” They make stampedes rarer and no smaller. Rarer, bigger events are usually worse operationally than frequent small ones, because nobody is watching when they happen.

“The cache protects the database.” It protects the database on hits. On a miss it is a load amplifier — it takes traffic it was smoothing and delivers it as a burst. A cache in front of an origin that cannot survive the miss rate is a liability with good metrics.

“We will add a lock.” Which one, where, and what happens when its holder dies? Say it, because the interviewer will ask.

In production

Varnish, Nginx and most CDNs implement coalescing natively — Varnish calls it request collapsing, Nginx proxy_cache_lock. HTTP has stale-while-revalidate and stale-if-error in Cache-Control, which are exactly early refresh and serve-stale-on-error, and are supported by CDNs and browsers. Go’s golang.org/x/sync/singleflight is the canonical library implementation. Caffeine’s AsyncLoadingCache coalesces by default, which is one reason it is worth using over a hand-rolled map.

The pattern to reach for, in order: coalesce (always, it is nearly free), jitter TTLs (always, it is free), refresh ahead for the small set of genuinely hot keys, and serve stale on error. Then bound the origin’s concurrency anyway, because the fix you forgot to deploy is the one that will be tested.

The follow-up questions

“Your hottest key expires. Walk me through the next 400 milliseconds.” — Herd size arithmetic, feedback, and the fix.

“Coalescing across fifty app servers — how?” — Distributed lease with its caveats, or accept fifty queries and size the origin for that. Both are legitimate; unawareness is not.

“How do you avoid this at deploy time?” — Jitter, staged cache warm-up, and not invalidating everything at once.

“What if the recompute fails?” — Serve stale, with a metric on how stale. Failing the request because the refresh failed converts a dependency blip into a user-visible outage.