Metastable failure, fencing tokens, and production postmortems

A stampede lasts 10 seconds. Four hours later the DB is still at 100% CPU. The stampede is over — but the system cannot self-recover. This is the metastable failure pattern: once the system falls into the retry storm, it stays there.

The metastable failure sequence

A cache stampede can escalate into a self-sustaining failure:

1. T=0 — TTL fires, herd hits DB. DB CPU saturates.
2. T=0–5s — queries queue. Queue depth grows past client request timeout (e.g., 5 s).
3. T=5s — client timeouts begin. Most client SDKs auto-retry with exponential backoff. Backoff is short (100 ms to 1 s) because the original timeout looked like a transient network failure, not an overloaded server.
4. T=5–30s — retries multiply the herd. Original 10,000 misses become 30,000 in-flight requests (3 retry attempts per client). DB is now serving retries instead of fresh queries. Cache rebuild cannot complete because DB is too busy to answer rebuild queries.
5. T=4h — system remains saturated. Every new arrival retries. Retries prevent DB recovery. DB prevents cache rebuild. Cache emptiness generates more retries. Self-sustaining loop.

The system has two stable states: healthy (cache full, low DB load) and storm (cache empty, DB at 100%). A perturbation moved it from healthy to storm. It cannot move back on its own.

Why the system cannot self-recover

The loop is: no cache → retries → DB overload → no DB capacity → no cache rebuild → no cache. Each component is correctly following its designed behaviour. No component “knows” it is in a storm. The client SDK retries because it sees timeouts. The DB processes queries in order. The cache does not rebuild because the DB never answers fast enough.

Recovery requires breaking the loop from outside:

1. Load-shedding at the gateway — return 503 Service Unavailable immediately when DB CPU exceeds 90%. Most client SDKs treat 503 as “do not retry immediately” and back off with long jitter. After 30–60 s the queue drains, the DB recovers, and the cache rebuilds.
2. Circuit-breaker on the rebuild path — if the rebuild query fails or takes too long, serve stale forever until the DB recovers. This breaks the dependency between cache rebuild and DB health.
3. Manual cache warmup — operators write known-good values directly to the cache, bypassing the rebuild path. Immediately returns the system to the healthy state.

The fencing token fix for lock TTL races

A Redis lock with SET lock:key uuid EX 30 NX has a race condition when the rebuild outlasts EX:

1. Request-1 acquires lock with uuid-A, EX=10 s. Starts a 12-second rebuild.
2. T=10 s: lock auto-expires. Request-2 acquires lock with uuid-B.
3. T=12 s: request-1 finishes rebuild. Writes to cache.
4. T=12 s: request-2 also finishes rebuild. Writes to cache.
5. Result: duplicate writes. If there is a concurrent invalidation from a DB write, request-1’s stale value may overwrite a newer-correct value.

Fix 1: increase EX above rebuild p99.9. Most duplicates prevented. Not proof against all races.

Fix 2: fencing token check before write.

# Before writing the rebuilt value:
current_lock = GET lock:key
if current_lock != my_uuid:
  ABORT  # we lost the lock; someone else is rebuilding
ELSE:
  SET cache:key new_value EX 60  # write only if still holding lock

Fix 3: monotonic version per key. Include a version in every cache write. The DB or cache layer rejects writes with version ≤ current version. Stale rebuilds write with an old version and are silently rejected. Martin Kleppmann’s 2016 critique of RedLock formalised this: distributed locks alone are insufficient for correctness; fencing is required.

XFetch: why the exponential is optimal

Vattani et al. (VLDB 2015) prove no coordination-free algorithm can do better than exponential at keeping expected refreshes per TTL window at exactly 1. Any tighter rule either:

• Requires coordination (distributed lock, lease) to bound variance, or
• Accepts higher variance (some windows get 0 refreshes → stampede, some get many → wasted work).

The exponential is uniquely optimal because: the minimum of N independent Exp(λ) draws is Exp(N·λ). As fleet size N grows, the “winning” reader fires sooner — but the expected total remains 1. No other distribution has this scaling property while remaining memoryless (no state required per-reader).

Four production postmortems

Reddit 2017. A feed-cache change shipped without single-flight. Result: 3× DB peaks at every TTL boundary. On-call paged on DB CPU 30 minutes after deploy; rolled back within 1 hour.

Shopify 2020 (Black Friday). A flash-sale homepage had TTL=30 s and no SWR. At 12:00:30 the TTL fired under 10× normal traffic. The entire storefront edge had multi-second outages at every TTL boundary for the first 10 minutes of the sale. Fixed by deploying stale-grace=5 min on the next push.

Twitter 2022. An unrelated cache invalidation bug triggered 30M concurrent rebuild attempts. The DB connection pool saturated for 4 hours. Recovery required load-shedding + manual cache seed.

Cloudflare 2024. A KV cache coalescing bug briefly allowed N requests for the same key to bypass coalescing during a deploy window. The origin saw proportional load during the window. Fixed by deploying a guard flag that disabled coalescing rollout until the bug was patched.

Pattern across all four: stampede protection was either absent, misconfigured, or had a bug that defeated it under load. The cost was proportional to the protection gap.

Full-stack composition design

A production cache stack for a global high-traffic site needs protection at every tier:

Each tier must independently bound its herd — a failure at any tier cascades to the one below. SWR at the CDN absorbs 99% of TTL-boundary traffic. XFetch prevents the next layer’s stampede by refreshing before expiry. Single-flight collapses per-node herds. The Redis lock collapses cross-node herds for the hottest 1% of keys. TTL jitter desynchronises multi-key boundaries. Together they reduce 10,000 concurrent misses to 1 rebuild anywhere in the stack.