Cache Stampedes Are a Capacity Problem, Not a Locking Problem

The standard advice for a cache stampede is a distributed lock: first miss takes the lock, recomputes, everyone else waits. I re-read that advice in March after O'Reilly Radar published Why Capacity Planning Is Back, and one line stuck with me. Under capacity pressure, the author writes, "peak demand simply converts into queue collapse." The piece is about GPU pools, but the sentence describes every lock-on-miss cache I have ever debugged.

So I built a small stampede rig to check my intuitions: an in-memory cache in front of a fake upstream that takes 400 ms per recompute and allows 8 concurrent calls, with 500 reads per second spread across 1,000 keys. What the experiment kept showing is that the stampede is never about the cache. It is about an upstream capacity budget that the cache layer spends without tracking. Once I framed it that way, the mitigation hierarchy inverted: the distributed lock — the answer most posts reach for first — became the last resort, and two cheaper mechanisms covered almost everything.

What a miss actually spends

A cache in front of an expensive resource is an amplifier with a budget. Every miss spends one recompute from the upstream's concurrency budget. The upstream in my rig affords 8 concurrent recomputes at 400 ms each — a throughput ceiling of 20 recomputes per second. As long as misses arrive below that ceiling, nobody notices the cache exists.

A stampede is the moment miss demand exceeds that ceiling, and it has two distinct triggers that demand different fixes:

• Synchronized expiry. A deploy, a bulk cache warm, or a uniform TTL gives thousands of keys the same expiry instant. Each key only needs one recompute, but they all need it now.
• Hot-key expiry. One key serving hundreds of reads per second expires. Every read during the recompute window misses on the same key, and each one triggers a redundant recompute of identical work.

In my rig, the synchronized case looked like this: all 1,000 keys warmed at the same instant with a flat 60-second TTL. At the minute mark, every read missed. The upstream could rebuild 20 keys per second, so refilling the working set took 50 seconds — 50 seconds during which read latency sat at queue depth times 400 ms instead of microseconds. The hot-key case was sharper: a single key at 300 reads per second produced 120 concurrent recompute attempts within one 400 ms window, against a budget of 8.

Same symptom on a dashboard — upstream saturation, latency cliff — but two different problems. The capacity framing makes the difference visible: synchronized expiry is a scheduling problem (legitimate work, terrible timing), while hot-key expiry is a deduplication problem (one unit of work, 120 requesters).

Lock-on-miss turns a blip into a queue

The distributed lock answers the deduplication problem, so it looks attractive. Here is what it cost in my rig.

A lock-on-miss design needs a lock TTL longer than the worst-case recompute, or the lock expires mid-recompute and a second client starts the same work. My fake upstream's p99 recompute under load was 1.8 seconds, so an honest lock TTL was 5 seconds. Then I killed the lock holder mid-recompute — one process crash, nothing exotic. The hot key's 300 reads per second piled up behind a lock that nobody would ever release. By the time the lock TTL expired, 1,500 requests were parked, each holding a connection and a thread upstream of the cache. The blip was 400 ms of recompute; the lock turned it into 5 seconds of queue growth followed by a synchronized retry burst — 1,500 requests stampeding the moment the lock freed. That is the queue collapse the O'Reilly piece describes, manufactured by the mitigation itself.

The deeper issue is what the lock optimizes for. It protects the cache slot — exactly one writer per key — when the thing that needs protecting is the upstream budget. Those sound similar but diverge under failure: a lock guarantees at most one recompute per key per lock period, at the price of coupling every reader's latency to the lock holder's health.

It is worth noticing what Facebook actually built when they faced this at scale. The leases mechanism in Scaling Memcache at Facebook (NSDI '13) is regularly cited as "a distributed lock," but read closely it is a rate limiter with a staleness policy: the server hands out a lease token for a missing key at most once every 10 seconds, and clients that arrive in between either wait briefly or are explicitly handed the stale value to serve. The design protects the database's recompute budget and names the trade-off — bounded staleness — in the protocol. From my reading of the paper, the lesson is not "use locks"; it is that even the disciplined version of locking had to become budget-shaped to work.

TTL jitter: the right fix, usually at the wrong dose

For synchronized expiry, the textbook fix is jitter: add randomness to each TTL so keys stop expiring in lockstep. The advice is correct. The number that travels with it — "add 10%" — is what failed in my rig, and the failure has a formula.

With ±10% jitter on a 60-second TTL, my 1,000 expiries spread across a 6-second window: roughly 167 recompute demands per second against a ceiling of 20. Still a stampede — politer, five times longer than the upstream could absorb. The jitter window has to be wide enough that the recompute work fits through the upstream throughput:

required_spread ≥ (keys_expiring × recompute_seconds) / max_concurrency

For my rig: 1,000 × 0.4 / 8 = 50 seconds of minimum spread. On a 60-second base TTL that is not a 10% tweak — it is jitter on the order of the TTL itself, something like ttl × uniform(1.0, 2.0). Once I sized it that way, the synchronized stampede disappeared entirely: expiries arrived under the 20-per-second ceiling and the upstream never queued.

Two things make jitter the first thing I reach for anyway. It is one line of code at write time, with no read-path cost, no coordination, no new failure modes. And its budget math is static — you can verify the formula above on paper before deploying, which is not true of any lock. What jitter cannot do is help the hot key: one key has one expiry, and randomizing a single sample shifts the stampede without shrinking it.

XFetch: one random number per read

The hot key needs something that decouples refresh from expiry. The cleanest mechanism I know is probabilistic early expiration — XFetch — from Vattani, Chierichetti, and Lowenstein's Optimal Probabilistic Cache Stampede Prevention (VLDB 2015). Store two extra fields alongside each value: delta, how long the last recompute took, and expiry. On every read, draw one random number:

read(key): value, delta, expiry = cache.get(key) if value is missing or now() - delta * beta * ln(rand()) >= expiry: start = now() value = recompute(key) delta = now() - start cache.set(key, (value, delta, now() + ttl)) return value

rand() is uniform in (0, 1], so ln(rand()) is negative and the term shifts the reader's view of "now" forward by a random amount scaled to the recompute cost. Far from expiry the shift almost never crosses the line; as expiry approaches, the probability of volunteering to refresh rises steeply. The paper proves the exponential distribution is the optimal shape for this gamble — it minimizes the chance of a synchronized recompute without inflating wasted early refreshes. beta defaults to 1; raising it trades earlier refreshes for stronger stampede protection.

Against my 300-reads-per-second hot key, XFetch with beta = 1 produced between 1 and 3 concurrent recomputes per expiry cycle across 50 cycles, against 120 for naive expiry. Not exactly one — XFetch is probabilistic, and two readers can both win the lottery inside the same delta window — but two orders of magnitude better, with zero coordination, zero shared state beyond the two extra fields, and no behavior change when a node dies.

Three traps I hit in my own tests are worth naming. First, the envelope: delta and expiry have to live with the value, which means touching the serialization format of every cache entry — a migration, not a flag flip. Second, cold keys get nothing: a key read once a minute with a 60-second TTL has almost no reads near expiry to volunteer, so it just expires and misses like before. XFetch protects keys whose read rate is high relative to 1/delta, which is exactly the hot-key population — fine, but worth knowing before expecting it to fix overall miss rate. Third, a slow upstream poisons delta: one 1.8-second outlier recompute stored as the new delta makes subsequent reads refresh 4.5× earlier than needed, and under sustained upstream degradation that feedback loop spends more budget exactly when budget is scarcest. Clamping delta to a ceiling fixed it in my rig.

For in-process caches the same idea ships ready-made: Caffeine's refreshAfterWrite serves the old value while exactly one asynchronous reload runs per key, memoizing redundant refresh attempts. That covers the single-process case the way XFetch covers the shared-cache case. And if duplicate suppression inside one process is the actual problem, single-flight coalescing is the precise tool — I wrote that pattern up separately in my Rust single-flight notes, including the math for why it stops working once the process becomes a fleet.

When a real lock earns its keep

After all of this, three situations remain where I would still deploy a distributed lock on the miss path:

• The recompute is not idempotent. If regeneration has side effects — it writes somewhere, increments a quota, triggers a downstream job — then 2 concurrent recomputes are not wasted work but a correctness bug. Probabilistic mechanisms tolerate duplicates by design; here duplicates are not tolerable.
• The budget is so small that duplicates blow it. A third-party API allowing 10 calls per minute has no room for XFetch's occasional 3 concurrent refreshes. When the budget is single digits, "rarely more than one" is not a guarantee worth betting on.
• Exactly-one recompute must hold across regions. Multi-region caches with one authoritative regeneration path need real coordination; no amount of local randomness provides it.

Even then, the lock should be lease-shaped: a token with a bounded issue rate per key and an explicit stale-serving policy for everyone who does not hold it, which is the Facebook design. A bare SETNX with a TTL and blocked waiters is the version that converted my 400 ms blip into a 5-second queue.

The rubric I actually use

The diagram below is the shape I keep drawing on whiteboards: upstream concurrency over time for the same expiry event under each mitigation, against a fixed capacity line.

​

The decision sequence, in budget terms:

1. Always: jitter, sized by the formula. Compute keys × delta / concurrency and make the jitter window at least that wide. One line, no read-path cost, kills synchronized expiry. If the computed spread exceeds what your staleness tolerance allows, that is not a jitter failure — it is the system telling you the upstream is undersized for its working set.
2. Hot keys: XFetch, or refresh-ahead in-process. Two extra fields and one random number per read buy a 100× reduction in duplicate recomputes for high-traffic keys. Clamp delta.
3. Duplicate suppression inside one process: single-flight. Cheapest exact deduplication there is, but its guarantee ends at the process boundary.
4. Exactly-one across the fleet: a lease, not a lock. Bounded issue rate per key, explicit stale-serving for non-holders, and acceptance that reader latency is now coupled to holder health.

What changed for me after the capacity reframing is the order. I used to start at step 4 because it is the most general mechanism. It is also the only one that adds a failure mode instead of removing one.

Takeaways

• A stampede is miss demand exceeding the upstream's recompute budget; identify whether the trigger is synchronized expiry (scheduling) or a hot key (deduplication) before picking a fix.
• TTL jitter works only when the window is wide enough: at least keys × recompute_time / max_concurrency. The folklore 10% is a placeholder, not a calculation.
• XFetch costs two stored fields and one random number per read, and cut duplicate recomputes by two orders of magnitude on my hot key. Clamp the stored delta against slow-recompute outliers.
• Lock-on-miss couples every reader's latency to the lock holder's health; one crashed holder parked 1,500 requests in my rig. If you need exactly-one, build a lease with a stale-serving policy.
• Reach for the lock when recompute is non-idempotent, the upstream budget is single-digit, or exactly-once must hold across regions. Avoid it everywhere else — the cheaper mechanisms protect the budget without adding a coordinator to the read path.