Drill 73 — The Cache Stampede

Theme: Concurrency & Race Conditions · Format: 20-min drill · Difficulty: core

The story

A brokerage runs a quote service that fans out to every trading screen, every mobile app, and a dozen internal risk systems. On the hot path it serves a consolidated price for each instrument out of Redis, keyed price:{symbol}, with a sixty-second time-to-live. Behind the cache sits the pricing database — a heavy join across order books, reference data, and the corporate-actions feed that takes about four hundred milliseconds to compute one price. During the day the cache absorbs it all: the database sees maybe fifty recompute queries a second and idles at ten percent CPU. This has been the architecture for two years and nobody thinks about it.

At market open the desk warms the cache: a startup job loops over the active universe and writes every price:{symbol} key in a tight burst, all with the default sixty-second TTL. It works beautifully — the first minutes of trading are fast. Then, sixty seconds after the warm-up, every key expires in the same instant. The most-watched symbol — the index future everyone is quoting — has eight thousand requests in flight when its key disappears. All eight thousand miss. All eight thousand find no value and, being correct, each goes to compute the price itself.

The pricing database goes from fifty queries a second to eleven thousand. Connections pile up, the four-hundred-millisecond join stretches to nine seconds under contention, and now the requests that are still waiting time out before anyone writes a fresh value back. The key stays empty. So the next wave of requests misses too, and stampedes again. The database sits pinned at a hundred percent CPU, p99 quote latency blows past twelve seconds, and the desk is screaming that prices are frozen at the busiest thirty seconds of the day. Every dashboard for the cache itself is green — hit rate was ninety-nine percent right up until it wasn't.

⏸ Stop here and ask the room: the cache was doing its job at a ninety-nine percent hit rate. So how did one key expiring take down the database behind it?

Run it — facilitator script

Timing for a 20-minute session: 2 min story · 10 min staged questions · 3 min reveal · 5 min transfer.

What exactly happens the instant that hot key expires — name the window.

Listen for: the miss window. Between the moment the key expires and the moment someone writes a fresh value, every concurrent request sees a miss and independently starts the expensive recompute. There is no coordination — N in-flight requests become N duplicate database queries for the same value. The expiry is a synchronized starting gun.
Weak signal: "just raise the TTL" or "add more cache nodes" — neither closes the window; they only change how often the stampede fires or how fast the herd assembles.

Why does it keep stampeding instead of recovering after the first wave?

Listen for: the miss window stays open because the recompute now takes longer than the request timeout — the database is saturated, the join that took four hundred milliseconds takes nine seconds, requests time out before writing back, so the key is never repopulated and the next wave misses identically. It is a positive-feedback loop: load causes slowness causes more misses causes more load.
Weak signal: treating it as a one-time spike that "settles down." It does not settle; the empty key plus the saturated backend is self-sustaining until load drops or something breaks the loop.

Where does the fix belong — and what is the single most important change?

Listen for: the recompute must be coalesced — only one request per key does the work while the rest wait for its result (single-flight / request coalescing). That one change turns eleven thousand duplicate queries into one. Everything else — jittered TTLs, early recompute, serving stale — reduces how often you hit the window or hides it from users, but coalescing is what caps the blast radius.
Weak signal: "scale the database to handle the peak." You would be provisioning for eleven thousand redundant queries that should have been one; the peak is an artifact of the missing coordination, not real demand.

The reveal

The team did not make the cache bigger or the database faster. They made three changes at the cache layer. First, request coalescing: on a miss, the first request acquires a short-lived per-key lock (lock:price:{symbol}, a SET NX with a five-second expiry) and does the recompute; every other request for that key blocks briefly and reads the value the winner writes — so one miss triggers exactly one database query, not eight thousand. Second, they jittered the TTL: instead of a flat sixty seconds, each key gets sixty seconds plus or minus a random ten, so the warm-up no longer arms every key to expire in the same instant — expiries smear across a twenty-second band. Third, stale-while-revalidate: a value carries a soft-expiry at sixty seconds and a hard-expiry at ninety, and between the two the cache serves the slightly-stale price immediately while one background refresh (coalesced) recomputes it — so users never wait on a recompute at all. Database peak QPS at open dropped from eleven thousand to about seventy. Quote p99 stayed under two hundred milliseconds through the open.

Why this happens — the mechanics

A cache is a shared read-through in front of an expensive computation, and its correctness story quietly assumes that a miss is rare and uncorrelated. Both assumptions break at once here. The miss is not rare because a hot key is read thousands of times a second, and it is not uncorrelated because a single TTL means every reader's miss happens on the same tick. So the cache converts one logical event — "this value needs recomputing" — into as many duplicate recomputes as there are concurrent readers. That is the stampede (also called a dog-pile, or a thundering herd on the backend): the read path has no notion of "someone is already computing this; wait for them." Each request is individually correct and collectively catastrophic.

The synchronized-expiry part is a self-inflicted amplifier. Warming the cache in a tight loop with a constant TTL is a best practice for a cold cache applied without noticing that it also synchronizes every future expiry — the whole universe now expires within one tick of itself, so you do not get one stampede, you get the entire book stampeding together. And once the backend saturates, the miss window can no longer close: the recompute outlives the request timeout, nothing writes back, and the empty key guarantees the next wave repeats. The failure is not a bug in the cache or the database individually; it is the missing coordination between them under concurrency, exactly the seam this theme keeps finding.

Diagrams

Problem — how the failure unfolds:

sequenceDiagram
    autonumber
    participant R as Requests (x8000)
    participant Cache as Redis
    participant DB as Pricing DB
    Note over Cache: hot key expires<br/>at market open
    R->>Cache: GET price index-fut
    Cache--xR: MISS — no value
    Note over R: all 8000 miss<br/>on the same tick
    R->>DB: recompute price<br/>(x8000 duplicate)
    Note over DB: 50 to 11000 QPS<br/>CPU pinned at 100%
    DB--xR: timeout at 9s<br/>before writeback
    Note over Cache: key stays empty<br/>next wave stampedes again

Solution — where the guardrail goes:

flowchart TD
    A["GET price:{symbol}"] --> B{"hit?"}
    B -->|"fresh hit"| C["serve value"]
    B -->|"soft-expired<br/>(stale-while-revalidate)"| D["serve stale now<br/>+ trigger 1 refresh"]
    B -->|"hard miss"| E{"SET NX lock<br/>acquired?"}
    E -->|"winner"| F["recompute once<br/>write value + jittered TTL"]
    E -->|"loser"| G["wait for winner<br/>then read value"]
    F -.-> AL["alarm: recompute QPS<br/>> 3x baseline"]
    G -.-> AL
    D --> C
    F --> C

What good looks like

Request coalescing (single-flight): on a miss, one caller wins a per-key lock (SET lock:{key} NX EX 5) and recomputes; the rest wait up to ~250 ms and read the winner's result. Target: duplicate recomputes per miss ≈ 1, and alarm if backend recompute QPS exceeds 3× the rolling baseline for more than ten seconds.
Jittered TTL: every write uses base ± rand(jitter) — e.g. sixty seconds ± ten — so expiries never synchronize. Warm-up jobs must jitter too; assert in a test that no two keys in a warmed batch share an expiry second.
Early / probabilistic recompute: refresh a hot key before it expires — recompute with probability rising as the key ages (XFetch-style), or unconditionally when remaining TTL drops below 20% — so the value is renewed off the hot path, not on a synchronized miss.
Stale-while-revalidate: carry a soft TTL (serve-until) and a hard TTL (delete-at); between them, serve the stale value in < 5 ms and kick off exactly one coalesced background refresh. Users never block on a recompute.
A backpressure cap on recompute concurrency: bound total in-flight recomputes to the backend (e.g. a semaphore of N = 2× DB core count); shed or serve-stale beyond it so a cache layer can never issue more than a safe number of concurrent expensive queries.
A stampede game-day: in staging, force-expire the hottest key under production-level read load and assert backend QPS rises by < 2× and stays there — prove the coalescing lock actually holds before you need it.

The lesson

A cache turns one expiring value into as many recomputes as you have concurrent readers unless something coordinates them — so put a single-flight lock on the miss path, jitter every TTL so expiries never synchronize, and serve stale while you refresh. The expensive work behind a hot key must happen once per expiry, not once per request.

Named concepts: cache stampede, request coalescing, jittered TTL, stale-while-revalidate.

Real-world echoes

Facebook's 2010 memcache "thundering herd." A hot memcached key expiring under massive concurrent read load sent a flood of identical regeneration queries at the database; Facebook's documented fix was lease-based coalescing (one client gets a lease to recompute, others wait or serve stale) — the productized version of this drill's single-flight lock. Instagram and others have written up the same jittered-TTL and stale-while-revalidate playbook for exactly this failure.

Transfer

Which hot cache key in your stack, if it expired right now with peak traffic reading it, would send an unbounded fan-out of identical recomputes at the thing behind it? "The cache would just refill" is the wrong answer — name what coalesces the miss.

Make it a ticket: pick your single hottest read-through key, add a single-flight recompute lock plus jittered TTL, and run a game-day that force-expires it under load, asserting backend QPS rises less than 2×.

Drill 69 — The Double-Charge Race — same theme; both are missing-coordination-under-concurrency, one on the write path, one on the read path.
Drill 21 — The Thundering Herd, theme 4 — the same herd viewed from the scale-and-cloud side (retries and reconnects synchronizing into a spike).
Drill 20 — The Agent That Wouldn't Stop, theme 3 — unbounded fan-out of identical work with no coordinator to cap it.
Pattern #118 — Request Coalescing / Single-Flight (the reusable fix).