hard Cache Stampede: single-flight, soft TTL & dedup

When one key expires, N misses become N identical DB queries

A cache absorbs load only while the key is present. The instant a hot key expires, every request that was being served from memory misses at the same moment — and because the recompute takes real time, all of them start the same database query before the first one finishes and repopulates the cache. That burst of duplicated work is the cache stampede (a.k.a. thundering herd, dog-piling). The three fixes below all answer one question: how do we guarantee only one caller recomputes while the others don't pile onto the origin?

Trace it with real numbers

Say the key post:42 is served 5,000 reads/sec from cache (hit latency ~1 ms), and recomputing it from the database takes 50 ms. Watch the expiry:

t (ms)	Event	Origin (DB) load
0	TTL expires; cache no longer has post:42	0
0–50	During the 50 ms recompute window, 5 req/ms keep arriving — all miss	climbing
50	Naive: all 5 req/ms × 50 ms = 250 requests each issued their own query	250 identical queries
50	First result lands, cache repopulates; the other 249 queries were pure waste (and may have tipped the DB over)	—

The DB was provisioned for the cache-hit world (a trickle of misses). 250 simultaneous identical queries is 250× that, and if post:42 is one of many keys expiring on the same clock tick the multiplier stacks. The service can brown out from a single expiry.

Fix (a) — single-flight / request coalescing

Put a per-key lock (or an in-flight map) in front of the recompute. The first miss acquires the lock and runs the query; concurrent misses for the same key find the lock held and wait on the same in-flight result instead of starting their own. When the leader finishes it fills the cache and hands the value to every waiter. DB load for the expiry: exactly one query.

// Go: one recompute per key, everyone else reuses it
var g singleflight.Group
func GetPost(id string) (Post, error) {
    if v, ok := cache.Get(id); ok { return v.(Post), nil }
    v, err, _ := g.Do(id, func() (any, error) {   // only the FIRST caller runs the func
        p := db.LoadPost(id)                       // the 249 others block here, then share v
        cache.SetTTL(id, p, 60*time.Second)
        return p, nil
    })
    return v.(Post), err
}

In a single process an in-memory map/lock suffices. Across many app servers you need a distributed lock — e.g. Redis SET lock:post:42 <owner> NX PX 5000: whoever wins the NX recomputes, the rest briefly retry or serve stale. Give the lock a TTL so a crashed leader can't wedge the key forever.

Fix (b) — soft TTL / stale-while-revalidate (only WITH a lock)

Store two expiries: a soft TTL (e.g. 60 s) and a later hard TTL (e.g. 70 s). Between them the value is “stale but usable.” A request past the soft TTL is served the stale value immediately (users never block) while a refresh runs in the background. This is what a CDN does with stale-while-revalidate.

The trap: soft TTL alone does not prevent a stampede. If you just check “past soft TTL? then refresh,” then all 250 requests in the stale window each see “past soft TTL” and each fires a refresh — you’ve moved the 250-query stampede from the foreground to the background, not removed it. Soft TTL must be paired with a per-key lock/flag (e.g. an atomic SET refreshing:post:42 1 NX PX 5000) so that exactly one request triggers the refresh and the rest just serve stale. Soft TTL decides who waits (nobody); the lock decides who recomputes (one). You need both.

Fix (c) — probabilistic early recompute (XFetch)

Instead of coordinating at expiry, spread the recomputes to before expiry so they rarely coincide. On every read, recompute early with a probability that rises as the key ages. The XFetch rule (Vattani et al., VLDB 2015) is:

recompute now if:  now - delta * beta * ln(random())  >=  expiry
  delta  = how long the last recompute took (stored with the value)
  beta   = tuning knob, >= 1 (default 1); higher = recompute earlier
  random()  in (0, 1]   ->  ln(random()) <= 0, so the term SHIFTS now toward expiry

Because -delta·beta·ln(random()) is a positive random gap that grows with the recompute cost, expensive keys start rolling the dice earlier. In practice one request recomputes a little early, repopulates the key, and the expiry-with-a-crowd-of-misses simply never happens. No lock, no coordination.

Trade-off: it is probabilistic — two requests can still both fire on an unlucky roll (rare, and you can add a light lock), you must store delta per key, and you do slightly more total recompute work because you refresh a touch before you strictly had to.

Pitfalls

• Serving stale under a lock without a lock TTL. A leader that crashes mid-recompute while holding the lock wedges the key — every future request waits forever. Always give the distributed lock an expiry and have waiters fall back to stale-or-retry.
• Negative caching forgotten. If the recompute returns “not found,” cache that (briefly) too — otherwise a missing hot key stampedes the DB on every read (cache penetration).
• Synchronized expiry across keys. Setting the same TTL on a batch of keys makes them all expire on the same tick — a fleet-wide stampede. Add jitter to TTLs (XFetch does this implicitly).
• Waiters with no timeout. Single-flight waiters must bound their wait; a slow leader shouldn’t turn into unbounded latency for the herd.

Judgment — which one, and when

Approach	Guarantee	User latency at expiry	Cost
Single-flight / lock	hard: exactly one recompute	waiters block ~one recompute	lock + coordination (a distributed lock across servers)
Soft TTL + lock	hard (only with the lock)	none — always serve stale instantly	double bookkeeping + you serve stale data
XFetch (early recompute)	probabilistic: stampede becomes rare	none in the common case	store delta; a bit of extra recompute work; no hard guarantee

• Use single-flight when correctness/freshness matters more than a brief wait, or the value must be current on read (waiters getting the fresh value is fine). Simplest mental model.
• Use soft TTL + lock when latency is sacred and slightly-stale data is acceptable (feeds, counts, config) — nobody ever waits on a rebuild. But never ship soft TTL without the lock.
• Use XFetch when you want lock-free simplicity at scale and can tolerate the occasional double recompute; great for many independently-hot keys where a central lock would be a bottleneck.

Locking cost vs stampede risk: a per-key lock on every miss is pure overhead for cold keys (most keys are cold) and a bottleneck if the lock store is remote. So apply single-flight/lock selectively to keys you know are hot, or reach for XFetch which pays no coordination cost per read. The lock is cheap insurance exactly where the stampede is expensive — and wasted everywhere else.

Takeaways

• A single hot-key expiry turns N cached reads into N identical origin queries during the recompute window — size it: reads/sec × recompute time.
• Every real fix guarantees one recompute, many reuse: single-flight (block & share), soft TTL + lock (serve stale, one refresh), or XFetch (spread early).
• Soft TTL alone does not stop a stampede — it removes user waiting, not duplicate refreshes; it must be combined with a per-key lock/flag.
• Add jitter and negative caching; give distributed locks a TTL so a dead leader can’t wedge a key.

---

Sources: Vattani, Chierichetti & Lowenstein, “Optimal Probabilistic Cache Stampede Prevention” (VLDB 2015); Go golang.org/x/sync/singleflight; the HTTP stale-while-revalidate spec (RFC 5861); Redis/Memcached stampede literature and Cloudflare/Instagram engineering write-ups. See also: Cache Stampede & Invalidation, Caching strategies, Rate Limiting, Designing for Failure (load shedding), and (Concurrency) the lost-update race. Re-authored/Deepened for this guide.

I just read a lesson on **Cache Stampede: single-flight, soft TTL & dedup** (System Design) and want to truly understand it. Explain Cache Stampede: single-flight, soft TTL & dedup from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Cache Stampede: single-flight, soft TTL & dedup** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Cache Stampede: single-flight, soft TTL & dedup** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Cache Stampede: single-flight, soft TTL & dedup** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.