The mechanism
There are three ways to put a cache in front of a database, and they differ in who fills the cache and when.
- Cache-aside (also called look-aside, lazy loading or a side cache). The application reads the cache; on a miss it reads the database and writes the value into the cache. On a write it updates the database, then deletes the cache key. Facebook's memcache is this design, which its NSDI 2013 paper calls a "demand-filled look-aside cache". It deletes instead of updating "because deletes are idempotent". AWS's ElastiCache guide lists the trade-off: a miss takes three trips (cache, database, cache), but a failed node is not fatal, because a new empty node just fills again from misses.
- Read-through. The cache layer loads the value itself on a miss: an HTTP cache, a caching proxy such as Nginx's
proxy_cache, or a store-specific cache such as DynamoDB Accelerator. The application sees one API. Amazon's Builders' Library names the cost: when an inline cache is unavailable, "there is no opportunity for the client to compensate". - Write-through. Every write goes to the database and to the cache. AWS's guide says this keeps cached data current, at the price of two trips per write, keys missing from any new node until they are next written, and cache space spent on data nobody reads. It recommends combining write-through with lazy loading and a TTL.
Invalidation is where these designs go wrong. The Facebook paper defines a stale set: a server writes a value into the cache "that does not reflect the latest value that should be cached", which happens when "concurrent updates to memcache get reordered".
In cache-aside the classic race is a reader that misses, reads version 1 from the database, and stalls; meanwhile a writer commits version 2 and deletes the key; then the reader wakes up and writes version 1 into the cache, where it stays until something deletes it or the TTL expires. Write-through has the same problem with two concurrent writers whose database and cache updates land in different orders. So AWS's line that write-through data "is never stale" holds only when one writer updates a key at a time, every cache write succeeds after its commit, and no lazy-loading reader refills the key concurrently; AWS's own TTL section concedes the combined approach "doesn't guarantee that a value isn't stale." Two more rules follow:
- Always set a TTL, even on write-through keys. It is the upper bound on how long a lost race stays wrong.
- Don't fill the cache from a lagging replica unless the data tolerates staleness. The Facebook paper says a refill from a replica "should only be allowed after the replication stream has caught up", or the replica's stale value gets cached. Our episode You Saved It. Why Did It Disappear? follows one edit through replica lag.
Why stampedes happen
A stampede, also called dog-piling or a thundering herd, is many requests missing the same key at once and all recomputing it. Its size is the request rate times the time a refill takes. There are three kinds:
- One hot key expires or is deleted. Facebook's definition of a thundering herd is write-driven: a key with heavy reads and writes, where "the write activity repeatedly invalidates the recently set values" and the reads fall through to the database.
- Many keys expire together, because they were filled in the same burst with the same TTL. AWS's ElastiCache whitepaper warns that with one TTL everywhere, "many of your cache keys might expire within the same time window, even after prewarming your cache."
- The cache loses many keys at once: a node is replaced, a cluster restarts, or something stops refilling it. Database load follows the miss rate, not the hit rate.
The four defences
Request coalescing (single-flight). Only one request per key refills it; the others wait for that result or are served something else. Builders' Library: "only one pending request is out for uncached resources." It exists at three levels:
- *In the process.* Go's
golang.org/x/sync/singleflightmakes sure "only one execution is in-flight for a given key at a time"; a duplicate caller "waits for the original to complete and receives the same results". This caps a stampede at one refill per process, so a fleet of 40 processes can still send 40. - *In a proxy.* Nginx's
proxy_cache_lock(since 1.1.12) lets one request populate a new cache element while the others wait. The wait ends atproxy_cache_lock_timeout, 5 seconds by default, after which each waiting request goes to the origin and, since 1.7.8, its response is not cached. A refill slower than the timeout turns the lock back into a stampede. For an entry that already exists and has expired,proxy_cache_use_stale updatingis the setting that matters (see below). - *Across the fleet.* Facebook's memcached hands out a lease, a 64-bit token, to the client that missed. By default it issues a token for a key at most once every 10 seconds; other clients are told to wait a short time and retry, and "typically, the client with the lease will have successfully set the data within a few milliseconds."
The same lease fixes stale sets: a delete invalidates the token, so the late write of version 1 is rejected.
A home-grown version uses a lock key, such as Redis SET lock:key token NX PX 3000. If the holder pauses past the lock's expiry, a second refill starts, and the first one can still write an older value when it wakes up. Our episode Redis Lock Expired: Why Seat 14C Sold Twice works through that paused holder. For a cache a duplicate refill is cheap; the stale write is the part to guard with a version check or a short TTL.
Probabilistic early expiration (XFetch). Vattani, Chierichetti and Lowenstein's VLDB 2015 paper, "Optimal Probabilistic Cache Stampede Prevention", has each reader decide at random whether to refresh a key shortly before it expires, with the chance rising as expiry approaches. Their Figure 3, in Python-like form:
value, delta, expiry = cache_read(key) # delta: how long the last recompute took
if value is None or now() - delta * beta * log(rand()) >= expiry: # rand() in (0, 1]
start = now()
value = recompute()
delta = now() - start
cache_write(key, (value, delta), ttl)
return valuebeta defaults to 1, which the paper says "already provides effective prevention"; raise it to refresh earlier. If your cache cannot return a key's expiry, store it in the value. Two limits: XFetch only helps keys that are present, because a missing key still goes to the refill path, and it lowers the expected stampede without capping it, so keep in-process coalescing under it.
Jittered TTLs. Add randomness to each key's TTL so a burst of fills does not become a burst of expiries a TTL later. AWS's whitepaper example is ttl = 3600 + (rand() * 120), up to two extra minutes on an hour (its code comment says "+/- 2 minutes", but the expression only adds). Jitter does nothing for a single hot key; it only moves that key's expiry.
Serve stale while you refresh. Keep returning the old value for a bounded time while one request refreshes it. In HTTP this is RFC 5861: Cache-Control: max-age=600, stale-while-revalidate=30 means fresh for 600 seconds and servable stale for up to 30 more while it revalidates, and stale-if-error=1200 allows a stale response for up to 1,200 seconds past freshness when revalidation would return a 500, 502, 503 or 504. Nginx does the same with proxy_cache_use_stale updating plus proxy_cache_background_update (since 1.11.10). The Builders' Library describes the application version as a soft TTL, when the client tries to refresh, and a hard TTL, until which "the existing cache data will continue to be used" if the refresh fails.
Worked numbers
The first three calculations use made-up inputs and are illustrative; the paper figures quoted inside them are the paper's own. Put in your own rates and refill times.
Miss rate drives database load. Take 50,000 cache reads a second at a 99% hit rate: 500 reach the database. Lose one of ten equally loaded cache nodes and its 10% of reads all miss. The miss rate becomes 0.1 + 0.9 × 0.01 = 10.9%, and the database sees about 5,450 queries a second, roughly 11 times normal, until the new node fills. A database sized for twice its normal load does not survive one node replacement at peak. Slack's postmortem describes the worse case, where a miss triggers an expensive query: read load "increased superlinearly in relation to the percentage of cache misses."
One hot key. Take a key read 2,000 times a second whose refill takes 200 ms. When it expires with no protection, at least 2,000 × 0.2 = 400 requests miss during the refill and each runs the query (more in practice, because the stampede slows the refill). With in-process coalescing on 40 application processes, at most 40 do. With a fleet-wide lease, one does and the rest wait or get the stale value. With XFetch at beta = 1, the paper's expected stampede is about 2.4 refills, and refreshes start at most about ln 400 ≈ 6 recompute times, here about 1.2 seconds, before expiry.
Synchronized expiry. Warm a cache with 1,000,000 keys over 60 seconds, all with a one-hour TTL. An hour later they expire in the same minute: about 16,700 extra misses a second. Spread the TTLs uniformly over an extra 720 seconds (20% of the hour) and the peak falls to about 1,000,000 ÷ 720 ≈ 1,390 a second. AWS's 120-second example window gives a peak of about 1,000,000 ÷ 120 ≈ 8,300 a second here, which only halves the spike. Make the jitter window wide compared with how fast you fill.
Measured, not illustrative. Facebook measured a week of misses on keys particularly prone to thundering herds. Without leases, the peak database query rate was 17K/s; with leases it was 1.3K/s, about 13 times lower by our arithmetic. Facebook provisions its databases for peak load, so the paper calls this "a significant efficiency gain".
How it fails
- Errors treated as cache misses (Facebook, 23 September 2010). Facebook was down or unreachable for many users for about 2.5 hours. A system that checked cached configuration values and replaced invalid ones from the persistent store met a change to the persistent value itself that it read as invalid, so every client tried to fix it by querying one database cluster, which was "quickly overwhelmed" by "hundreds of thousands of queries a second". Clients then treated each database error as an invalid value "and deleted the corresponding cache key", so even after the original problem was fixed, "the stream of queries continued". To stop the loop, Facebook stopped all traffic to that cluster, "which meant turning off the site", then let users back in gradually. The lesson for any cache: a failed refill must not delete what you have. Serve the old value on error (
stale-if-error, a hard TTL) instead. - A cold cache in front of an expensive query (Slack, 22 February 2022). Just after 6 a.m. Pacific, "many users were unable to connect to Slack". A Consul agent upgrade on 25% of the fleet made cache nodes leave the service catalog. Slack's cache manager replaced them with empty spares, and rejoining nodes were flushed, so the hit rate dropped at peak traffic. A miss on group DM membership meant a query to every shard, read load rose superlinearly with the miss rate, and most of those queries timed out, "which meant that the cache could not be filled." Slack throttled client boots and raised the limit in steps. It changed the query to fetch only what memcached was missing, and to read it from replicas, which is safe because group DM membership never changes.
- The cache stops refilling (Honeycomb, 25 July 2023). From 13:40 to 14:48 UTC, Honeycomb had a total outage: "no data could be processed or accessed." After a switch between two clusters of its query engine, that engine failed to write the timestamps the schema cache uses to decide what to keep warm, and a feature-flag bug meant hosts told to stop writing never tried again. Reads shot up and overloaded the main MySQL database, which then hit an internal deadlock and ran out of connections. Recovery came in a fixed order: circuit breakers returning 5xx for all ingest traffic, failover to a replica, restarting the hosts that feed the cache, manually updating the timestamps, and only then removing the circuit breaker.
All three recoveries shed load, let the database recover and refilled the cache before readmitting traffic. Facebook and Slack readmitted traffic in steps; Honeycomb warmed the cache by hand before lifting its circuit breaker. If you have no way to throttle admissions, that is the first thing to build.
Traps without a published incident
- A coalescing timeout shorter than the refill. With Nginx's default 5-second lock timeout, an origin that takes 6 seconds sends each request that has waited 5 seconds to the origin, uncached, and
proxy_cache_lock_age(5 seconds by default) lets one more populating request through. Every extra request slows the origin further. - Not caching failures. The Builders' Library reports real cases where "a failure to cache negative responses led to increased failure rates and faults." Cache a not-found or error result under its own, shorter TTL.
Decision table
| Option | What it costs | Choose it when |
|---|---|---|
| Cache-aside, delete on write | Three trips on a miss; the stale-set race unless you use leases or version checks; every caller needs the fill logic | The default for read-heavy data that may be seconds stale; it keeps working when a node comes back empty |
| Read-through (HTTP cache, proxy, DAX) | If the cache is down, callers cannot route around it | You want coalescing and stale serving configured once, at the proxy or service in front |
| Write-through | Two trips per write; empty new nodes; space for data nobody reads; concurrent writers can still reorder | Values are read soon after they are written and one writer owns each key; add a TTL, and know that lazy loading brings back the reader race |
| In-process single-flight | One refill per process, not per fleet | Always: it is a few lines and caps the worst case at your process count |
| Fleet-wide lease or lock | Waiters need a retry or a stale path; an expired lock allows a second refill | Refills are expensive or the fleet is large |
| XFetch early refresh | Store the recompute time; some refreshes happen early | Hot keys whose expiry is predictable; it does not help missing keys |
| Jittered TTL | Keys live a little longer or shorter than the nominal TTL | Keys are filled in bursts: warm-ups, deploys, batch jobs |
| Stale-while-revalidate, stale-if-error | Readers see data past its TTL, for a bounded time | Staleness is acceptable, and you want a failed refill to keep serving instead of failing |
Write-behind, where the cache acknowledges a write and flushes it to the database later, is left out on purpose: the cache holds the only copy of the write until it flushes, which makes it a durability decision rather than a caching one.
A check you can run this week
Pick the hottest key your service reads and write down two numbers: its request rate and how long a refill takes. Their product is the minimum number of refills you get when it expires with no protection. Then test it in staging under production-shaped load: delete that key and count how many times its refill query runs in the next refill window, from your query log or traces. More than one per process means you have no coalescing.
Then read the error path of your cache wrapper. If a failed database read deletes the key, that is the loop that turned off Facebook in 2010; if it caches nothing and every caller retries, it is the uncached failure the Builders' Library warns about.
Sources
The primary sources this guide was checked against.
- Nishtala et al.: Scaling Memcache at Facebook (NSDI 2013)
- Vattani, Chierichetti and Lowenstein: Optimal Probabilistic Cache Stampede Prevention (VLDB 2015)
- Facebook Engineering: More details on today's outage (September 2010)
- Slack Engineering: Slack's incident on 2-22-22
- Honeycomb: Incident review, What comes up must first go down (incident 25 July 2023)
- Amazon Builders' Library: Caching challenges and strategies
- Amazon ElastiCache documentation: Caching strategies
- AWS whitepaper: Performance at Scale with Amazon ElastiCache (the thundering herd)
- RFC 5861: HTTP Cache-Control extensions for stale content
- Nginx documentation: proxy_cache_lock, proxy_cache_use_stale, proxy_cache_background_update
- Go documentation: golang.org/x/sync/singleflight
- Redis documentation: SET (NX and PX options)
Hear it discussed
Episodes of the show that work through this decision.