Cache Stampede Mitigation: Stale‑While‑Revalidate & Coalescing

Stop the Cache Stampede: Practical Patterns for Cache Stampede Mitigation

Cache stampedes (aka thundering herds) happen when a popular cache entry expires and hundreds or thousands of concurrent requests race to rebuild it. The result: your origin gets hammered, latency spikes, retries amplify the load, and the whole service can degrade or fail.

You don't need a big architectural rewrite to fix this. Start with three lightweight, production‑ready patterns I’ve used: stale‑while‑revalidate (SWR) with a distributed lock, request coalescing (single‑flight), and probabilistic early expiration (XFetch). Add TTL jitter as baseline hygiene. These patterns are composable and can be deployed incrementally.

Why naive cache-aside fails

A standard cache-aside flow (GET → miss → origin load → SET) works until many clients observe the same miss simultaneously. If N requests miss at once, you can get N origin queries. That’s a cache stampede.

Common triggers:

• Identical TTLs from batch warms or deploys
• Pod restarts (local caches cleared)
• Evictions on memory pressure
• High QPS on a single hot key

The goal of mitigation is simple: ensure that when a miss occurs for a hot key, only one expensive recomputation reaches the origin (or at least bound the number of concurrent recomputations), while keeping user-visible latency and staleness within acceptable limits.

Pattern 1 — Stale‑While‑Revalidate + distributed lock

What it does

• Serve a slightly stale value immediately when TTL has expired or is about to expire.
• Have one worker refresh the value in the background using a cheap distributed lock (SET NX / Redlock or similar).

Why it helps

• Prevents blocking requests and eliminates p99 spikes during high QPS.
• Keeps origin queries at ~1 per key while allowing a short window of staleness.

Minimal, safe lock pattern (Python/Redis‑style):

# Acquire a short-lived lock (token is unique per process)
if redis.set(lock_key, token, nx=True, px=lock_ttl_ms):
    value = recompute_from_origin()  # slow call
    redis.set(cache_key, value, ex=base_ttl)
    # Release only if we still own the lock
    lua_release = "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) end"
    redis.eval(lua_release, 1, lock_key, token)
else:
    # Another worker is recomputing: return cached stale value or poll briefly
    return redis.get(cache_key)

Implementation tips

• Set lock TTL longer than your p99 recompute time (tune from metrics).
• Use token-safe release (Lua compare-and-del) to avoid deleting someone else’s lock.
• Decide what losers do: poll, return stale, or fail fast.

Tradeoffs

• SWR serves stale data for a short window. If correctness demands fresh reads, restrict SWR to non-critical keys.

Pattern 2 — Request coalescing (single‑flight)

What it does

• Deduplicate concurrent in‑process requests for the same key so only one computation runs and other callers await the same promise/future.

Why it helps

• Reduces duplicate work inside each process (or shard). For extreme concurrencies, combine with a distributed lock to coordinate across replicas.

Minimal in‑process single‑flight (TypeScript/Node):

function createSingleFlight() {
  const inflight = new Map();
  return async function run(key, loader) {
    if (inflight.has(key)) return inflight.get(key);
    const p = (async () => { try { return await loader(); } finally { inflight.delete(key); } })();
    inflight.set(key, p);
    return p;
  }
}

// Usage: wrap the cache miss loader so concurrent callers share the same promise

Implementation tips

• Attach timeouts to loaders; a hung loader should not block waiters forever.
• Keep the coalescing scope narrow (per cache key or hashed buckets) to avoid over-serialization.

Tradeoffs

• Adds per-process memory/state for in‑flight entries and requires async-friendly call chains.
• Single‑flight inside a pod does not dedupe across pods; combine with a distributed lock when needed.

Pattern 3 — Probabilistic early recomputation (XFetch)

What it does

• Trigger background refreshes probabilistically before TTL hits zero. The probability increases as expiry approaches (exponential/XFetch is common).

Why it helps

• Smooths recomputations across time and avoids synchronized expirations without locks.
• Lock‑free and coordination‑free in steady state.

Simple decision (JS‑style):

// metadata includes expiry and lastDelta (seconds it took to recompute)
const now = Date.now()/1000;
const timeRemaining = metadata.expiry - now;
// scaled gap sampled from exponential: -delta * ln(rand())
if (now - (metadata.expiry - metadata.delta * beta * Math.log(Math.random())) >= 0) {
  // trigger background refresh (attempt to acquire bg lock first)
}

Implementation tips

• Store last recompute duration (delta) with the cached value to scale the sampling.
• Typical beta ≈ 1.0; tune if you need more/less aggressiveness.

Tradeoffs

• Slightly increases background load but keeps origin QPS bounded; accepts brief and controlled staleness.

Baseline hygiene — TTL jitter

Always add jitter when setting TTLs, especially for batch warms or bulk updates. Example: base_ttl + random(0, 30s). Jitter turns a cliff into a slope—cheap and effective.

Concrete example

On a shopping site we saw thousands of concurrent misses after disabling SWR. Reintroducing SWR + Redis SETNX locks dropped concurrent misses from thousands to ~1 per key. Origin stayed healthy through peak traffic and latency recovered immediately.

How to roll this out (practical checklist)

1. Audit top hot keys by read rate and rebuild cost. Start with the top 10.
2. Add TTL jitter everywhere (one‑line change).
3. Implement in‑process single‑flight for request handlers (cheap and low risk).
4. Add SWR + distributed lock for the hottest, expensive keys.
5. If you still see rare spikes, enable XFetch for those keys.
6. Monitor: cache rebuild counts, "stampedes_suppressed", origin QPS, and stale‑serving rates.

Closing thoughts

Cache stampede mitigation is coordination and probability—pick small, predictable patterns first. Jitter + single‑flight + SWR with a light probabilistic prefetch usually gives the best ROI. If you need more, consider ML pre‑warming for the top N keys, but ship the simple defenses before optimizing.

What’s one pattern you’ll try first this week to avoid the next cache cliff?