When a hot key vanishes, every concurrent request becomes a candidate to recompute it, and the system needs an answer to three questions: who recomputes, who waits, and what the waiters get. This guide reconstructs that protocol from Facebook, Slack and Wikimedia postmortems, and from the implementations at Google, Instagram, Discord, DoorDash, Netflix, memcached, Rails, nginx, Varnish and Fastly.
The problem, who has solved it in production, and the finding that reorders how you should think about it.
Strip the vocabulary away and the problem is this: many requests want the same expensive result at the same moment, the saved copy of that result has just become unavailable or untrustworthy, and something must stop them all from doing the expensive work at once. Engineers call the failure a cache stampede, a dogpile, or a thundering herd; the Facebook memcache paper uses the third term, Rails and Python libraries the second, DoorDash and the VLDB literature the first. All three names describe the same amplification: at a 90% hit ratio the origin sees a tenth of the traffic, so losing the cache multiplies origin load by ten (arithmetic: 1/(1−hit ratio); the general amplification argument is worked through in the retry-storms guide in this collection).
The surprise in the public record, and the reason this guide leads with incidents rather than mechanisms: in the worst published cache outages, the stampede was not triggered by a hot key quietly expiring. It was triggered by the machinery that manages the cache. In Facebook's 2010 outage the code that "fixed" bad cache entries deleted keys and re-queried the database in a loop; the postmortem calls it an unfortunate handling of an error condition, and recovery required turning the site off. In Slack's 2-22-22 incident a routine Consul upgrade caused the cache-management system, Mcrib, to flush and promote nodes until the hit rate fell at peak traffic. Expiry-driven stampedes are real, but they are the well-defended case. The undefended case is your own control plane emptying the cache faster than the origin can refill it.
Scope. This guide covers the demand side of look-aside and read-through caches: stampedes, invalidation discipline, and cold starts, with the mechanisms that survive them. It deliberately does not cover eviction and admission algorithms, CPU or browser caches, cache coherence in the hardware sense, or the retry amplification that turns an overloaded origin into a metastable failure; that last topic has its own guide in this collection.
Twelve systems, three primitives, one recurring shape. The implementations disagree about where the machinery lives, not about what it does.
Read the implementations side by side and a common shape emerges. Every one of them is assembled from three primitives, in different mixtures. The sources use different names for each, so this guide names them once and maps the vocabulary.
Let one through. Elect a single recomputer per key and make everyone else not recompute. Facebook's leases do the election inside the cache server: on a miss, memcached hands the client a token, regulates tokens to one per key every 10 seconds, and rejects sets from stale tokens; the NSDI '13 paper reports peak database load during a stampede falling from 17K queries per second to 1.3K. Google's groupcache does it in the client library: the README describes coordinating cache fills so that "only one load in one process of an entire replicated set of processes populates the cache, then multiplexes the loaded value to all callers", and the underlying singleflight package is one mutex, one map and one WaitGroup. Instagram caches the in-flight computation itself: "we cache a Promise that will eventually provide the value", so concurrent misses find the promise and wait on one backend call. Discord moved the same idea into a dedicated Rust tier where the first request spawns a worker and later requests subscribe to its result, with consistent-hash routing by channel ID so requests for the same hot partition land on the same coalescer. nginx (proxy_cache_lock), Varnish (the waiting list) and Fastly (request collapsing, where "only one request actually escapes the data center to go to your origin") are the same election at the HTTP layer.
Lie a little. Give the non-elected requests a stale answer instead of a wait. RFC 5861 standardized this for HTTP in 2010 as stale-while-revalidate, "immediately return a stale response while it revalidates it in the background". Rails has shipped it as one parameter, race_condition_ttl, whose doc comment names the dog pile effect explicitly. memcached's meta protocol marks items stale on invalidation and serves them with an X flag while one winner recaches. MediaWiki's WANCache serves one-second "interim values" during the purge window for the same reason. The staleness tolerance is load-bearing: if your correctness budget is zero staleness, half the toolbox disappears, and you are left with waiting or failing.
Spread the edge. Stop expiries from synchronizing. The VLDB 2015 paper on probabilistic early expiration (XFetch) has each reader independently recompute early with a probability that rises as expiry approaches, shifted by delta·beta·log(rand()); it needs no coordination and, the authors show, the exponential variate is optimal. The Internet Archive built a public harness comparing plain fetch, lock-only, XFetch and XFetch-plus-lock, and its README is blunt: "locked and fetch are susceptible to cache stampede, congestion collapse, and starved workers. They do not scale well." TTL jitter at write time is the degenerate, zero-code version of the same primitive.
WANCache purges by SETting a short-lived tombstone (about 11 seconds) rather than deleting, because a delete "could be re-populated immediately with the same stale value" by a racing reader in a replicated deployment. memcached's meta delete grew an equivalent: the I flag marks stale and bumps CAS instead of removing.
Runs this way at: Wikimedia, memcached meta protocol
Netflix treats a new or replaced cache replica as something to fill before it serves: a replica warmer for scaling events, an instance warmer for replacements, moving petabytes over multi-attach EBS. Slack's incident is the counterexample: nodes rejoined empty at peak and the fleet's hit rate slid.
Twitter's OSDI '20 study of 153 production cache clusters (80 TB of traces) found TTL "an important and sometimes defining parameter of cache working sets", and many workloads far more write-heavy than the literature assumed. Your TTL distribution is your expiry schedule, which is to say your stampede schedule.
Source: Yang et al., OSDI '20, traces at twitter/cache-trace
Where the implementations diverge is placement, and the divergence is explained by who the callers are. A single-language service can use an in-process library (Go's singleflight, Kotlin coroutines at DoorDash, folly futures at Instagram). A polyglot fleet cannot share a library, which pushes the election into the cache protocol (Facebook's leases, now memcached's meta commands) or into a tier that owns the database (Discord, whose Rust data services sit between the API monolith and ScyllaDB precisely so coalescing happens once, regardless of caller language). At the HTTP boundary the proxy already sees every request, so the edge products ship it as configuration. Inferred rather than reported: nobody in this corpus runs only one layer; Facebook has leases in the cache and pools in the client, Discord has coalescing in the tier and caching inside it. Defence in depth is the norm.
Each fork with the condition that flips it. The waiters' contract is the one that gets skipped, and it is the one the incidents keep landing on.
| Decision | Chosen | Rejected | Because | Flips when | Evidence |
|---|---|---|---|---|---|
| Where the coalescer lives | In-process library (Go, Kotlin, folly) | Cache-server or tier machinery | One language, one process model; a library is a day of work | Fleet goes polyglot or a hot partition needs one coalescer: push into the protocol (leases) or a tier (Discord) | groupcache, Discord |
| Waiters' contract | Serve stale | Block on winner | Latency stays flat through refresh | Staleness is a correctness bug: block with timeout, or fail fast | RFC 5861, Rails |
| Invalidation | Mark stale / tombstone SET | DELETE | Delete races with repopulation under replication lag | Single node and strict freshness | WANCache, memcached md+I |
| Expiry shaping | Probabilistic early refresh | Locks alone | No coordination; the Internet Archive's harness found lock-only strategies starve workers | Key traffic is sparse: there is no reader to volunteer early, so jitter at write time instead | VLDB '15, IA harness |
| Cold replicas | Warm before serving | Serve cold, let misses fill it | A cold node at peak is a herd generator | Dataset refills from misses inside the latency SLO (small, cheap values) | Netflix, Slack |
| Uncacheable responses under coalescing | Hit-for-pass marker | TTL 0 and hope | Waiters cannot share an uncacheable response; Varnish then serializes them one by one | Never; this one is unconditional if you run coalescing | Varnish docs |
Every mechanism here is a composition of the same three primitives: elect one recomputer, give waiters a stale answer, spread the expiry edge. When you evaluate a cache product or a library, ask which of the three it implements and what it does for the other two. A product that only locks has decided your waiters' contract for you, and decided it badly.
Three published incidents and one documented failure mode, grouped into the three classes the record supports.
The incidents in this corpus sort into three classes. Class one, the repair path is the stampede: the machinery that corrects cache state does the damage. Class two, the cliff is above zero: a partial hit-ratio dip, not a wipe, is enough to saturate the origin. Class three, the protection backfires: coalescing or locking itself becomes the bottleneck. No published postmortem in this corpus describes a plain TTL expiry of a single hot key taking a site down, which is worth pausing on: either the classic textbook stampede is well-defended by now, or it dies too quickly to earn a postmortem. Both readings say the exotic cases in this section are the ones to design for.
Everything quantitative in the corpus, dated. Amplification math is derived and shown; everything else is measured or claimed by the source named.
| Metric | Value | At | Context | As of | Source |
|---|---|---|---|---|---|
| Peak DB rate during stampede, no leases | 17K queries/s | Measured over a week; same workload with leases below | 2013 | NSDI '13 | |
| Peak DB rate with leases | 1.3K queries/s | Lease token issued at most once per 10 s per key | 2013 | NSDI '13 | |
| Cache tier scale | >1B requests/s | "trillions of items"; memcache fleet-wide | 2013 | NSDI '13 | |
| Cache tier scale | ~30M requests/s | Netflix | Speaker's figure: EVCache peak, hundreds of billions of objects, tens of thousands of instances | 2016 | Strange Loop talk |
| Production trace corpus | 153 clusters / 80 TB | 54 clusters released publicly, 14 TB uncompressed | 2020 | OSDI '20, traces | |
| Hit-ratio dip that caused an incident | 52% | Wikimedia | Nine minutes; one extension's keys; p75 latency 300 ms to 1500–4000 ms | 2020 | Incident doc |
| Stampede-driven load during outage | 100Ks queries/s | "hundreds of thousands of queries a second" against one DB cluster; site off ~2.5 h | 2010 | Postmortem | |
| Tombstone hold-off / interim TTL | 11 s / 1 s | Wikimedia | Purge survives replication lag; interim value absorbs regeneration herd | checked 2026 | WANCache design |
| Origin amplification from cache loss | 1/(1−hit) | derived | 90% hit ratio means 10x origin load if lost; arithmetic, not measurement | — | derived, this guide |
| XFetch tuning burden | beta = 1.0 | VLDB '15 | Authors: "requires no parameter tuning"; exponential variate proven optimal | 2015 | paper |
Measured: the Facebook lease figures, the Wikimedia latencies, the Twitter trace corpus. Claimed: the Netflix talk-abstract scale figures and Facebook's fleet-wide request rate, both self-reported without an audit trail. Derived: the amplification row, arithmetic shown. Unknown, and nobody publishes it: how often stampede protection actually fires in production, and what stampedes cost in dollars. If you instrument one number after reading this page, make it lease-wait or coalescer-queue time; no public source reports it.
Every source behind this page, graded. The ledger with per-claim quotes ships alongside as sources.md.
The canonical cache-stampede incident: an automated repair path deleted keys on every database error, sustaining hundreds of thousands of queries per second after the root cause was fixed. Recovery meant turning the site off.
A Consul upgrade made cache nodes rejoin empty at daily peak; misses fell onto a cross-shard scatter query and Vitess cascaded. A complete anatomy of a control-plane triggered stampede.
Public incident doc with the rare thing: exact hit-ratio and latency numbers. A 52% hit ratio on one key family for nine minutes multiplied site-wide p75 latency by 5 to 13.
Mainline memcached's lease semantics, in the protocol itself: N and R flags let one client "win" the recache, W/X/Z tell everyone else to serve stale, retry or wait. Written against "dog piling" by name.
The design document for library-side coalescing: one load per replicated process set, multiplexed to all callers, with automatic mirroring of super-hot keys. Deliberately no delete, no expiry, no versioned values.
The whole election mechanism in about 60 lines: a mutex, a map of in-flight calls, a WaitGroup. Duplicate callers wait and share the winner's result and error.
Serve-stale-while-one-regenerates as a single fetch parameter, in a mainstream framework since 2011: bump the expired entry's TTL, let one process regenerate, others read the stale value. The doc comment names the dog pile effect.
A week of production traces from 54 cache clusters, 14 TB uncompressed, CC-BY. The only public dataset large enough to test a stampede-protection design against real key popularity and TTL distributions.
The proposal to add type parameters to singleflight, still open with no attached PRs. Thirteen years in, the de-facto standard coalescer remains in x/sync with an interface{} API that the community keeps re-wrapping.
The waiters' contract, standardized for HTTP: return the stale response immediately, revalidate in the background, and serve stale on origin error to trade freshness for availability.
The most complete public write-up of invalidation discipline: purges are SETs of 11-second tombstones because deletes race with stale repopulation under replication lag; 1-second interim values absorb the regeneration herd.
Introduces leases, which solve stale sets and thundering herds with one token: issued at most every 10 seconds per key, verified on set. Measured effect on one stampede-prone workload: peak DB queries 17K/s down to 1.3K/s.
153 production clusters analysed: TTL often defines the working set more than eviction does, many workloads are write-heavy, and FIFO is a surprisingly strong replacement policy in production.
XFetch: each reader recomputes early with probability rising near expiry, shifted by delta·beta·log(rand()). No locks, no coordination, no tuning; the exponential form is proven optimal.
Cache the in-flight computation: on a miss, insert a promise, and concurrent misses wait on it instead of dialling the backend. Motivated by empty-cache cluster turn-up, the cold-start herd in its purest form.
The multi-layer subtlety: an L1 in-process miss stampedes L2 and the database with parallel duplicate reads even when L2 is healthy. Solved with a coroutine debounce returning one shared Deferred per key.
Request coalescing promoted to its own Rust tier between the API and ScyllaDB: first request spawns a worker, later ones subscribe; consistent-hash routing by channel ID sends a hot channel's requests to one coalescer.
Replica warmer for scale-ups, instance warmer for replacements: EVCache nodes are filled from live replicas before they take traffic, so the fleet's hit ratio never dips on a topology change.
The warming pipeline at scale: dumpers write to multi-attach EBS volumes, populators stream into the new replicas. Warming is real infrastructure with its own controller, queues and failure modes.
The practitioner account of nginx's defaults: with the lock on and use_stale off, every request arriving during a refresh waits. The two directives only make sense enabled together.
Contemporary coverage fixing the blast radius of the 2010 incident: roughly 2.5 hours down or unreachable, the worst outage in over four years.
The reference semantics: proxy_cache_lock admits "only one request at a time" to populate an element; use_stale's updating parameter serves the stale copy during refresh. Both default off.
Varnish's coalescing queue, and its documented trap: uncacheable responses drain the waiting list one at a time. Hit-for-pass exists to bypass the queue for objects known uncacheable.
CDN-scale coalescing is hierarchical: fetches for an object are focused through one cache node per data center, and its queue lets a single request escape to origin.
Scott Mansfield's abstract puts numbers on the cache-as-a-service model: about 30 million requests per second at peak, hundreds of billions of objects, tens of thousands of memcached instances.
Jim Nelson's talk ships with a public harness comparing fetch, locked, xfetch and xlocked. Conclusion in the README: plain fetch and lock-only strategies "do not scale well"; xfetch plus a lock had zero misses and no duplicate recomputes.
Seven rungs from reproducing the herd to operating the protection. The line from toy to real is crossed at rung five.
A service with one cached endpoint (any KV store, 10 s TTL) backed by a query you make artificially slow (500 ms). Load it with a few hundred concurrent clients and graph origin queries per second across an expiry.
Done when: you can point at the origin-QPS spike at each expiry edge. Teaches: the herd is periodic and self-synchronizing, not random.
Wrap the miss path in singleflight (or a promise map in your language). Same load.
Done when: origin sees one query per key per expiry regardless of client count. Teaches: election, and that the coalescer shares errors as well as values.
Add a soft TTL: past it, serve the old value and refresh in the background; past the hard TTL, block. Copy the Rails race_condition_ttl shape.
Done when: p99 latency is flat through a refresh cycle. Teaches: the waiters' contract is a caller-visible API decision, not cache internals.
Implement XFetch: store the recompute duration with the value, refresh when now − delta·beta·log(rand()) passes expiry.
Done when: the origin-QPS graph shows recomputes scattered before expiry, no cliff. Teaches: coordination-free smoothing, in about ten lines.
Make the origin return errors for 60 seconds under load. Watch what your miss and invalidation logic does. Add stale-if-error and negative caching with a short TTL, and rate-limit any delete-on-error behaviour.
Done when: an origin brownout does not increase origin traffic. Teaches: Facebook 2010; the error path is where stampedes are born.
Flush 25% of cache capacity while at steady load, in homage to Slack's 2-22-22. Measure time-to-recover and origin peak. Then add either warming (prefill from a peer) or an admission throttle for cold nodes.
Done when: the drill's origin peak stays under your origin's measured capacity. Teaches: the cliff above zero, and what warming actually buys.
Emit per-key-family hit ratio, coalescer queue depth and wait time, stale serves per second, and refresh outcomes. Alert on hit-ratio dips and on coalescer wait, with a runbook that names the cold-fleet procedure.
Done when: a game-day hit-ratio dip pages before latency does. Teaches: the leading indicators; no public source ships these numbers, so yours are the benchmark.
The queries that found this material, grouped by what they surface. The domain vocabulary (stampede, dogpile, thundering herd, coalescing, collapsing, lease) is the key; each community uses a different word for the same mechanism.
"cache stampede" postmortem OR "incident review" OR "root cause"site:wikitech.wikimedia.org incident memcached outagesite:slack.engineering incident cache"thundering herd" outage "queries per second"memcached protocol.txt "dog piling" won recache stalesingleflight proposal site:github.com/golangrace_condition_ttl dog pile site:github.com/railsvarnish "waiting list" serialization "hit-for-pass""thundering herds" promises instagram engineering"request coalescing" "data services" discord rust"cache warming" replica warmer netflix EVCache"cache stampede" "we" debounce coroutines"optimal probabilistic cache stampede prevention" vldbmemcache leases "peak query rate" 17K nsdiosdi 2020 twitter cache clusters TTL working settwitter/cache-trace production traces github