Advanced Distributed Caching: Stale-While-Revalidate and Cache Stampede Protection

1. The Cache Stampede (Thundering Herd) Disaster

A cache stampede happens when a hot key expires and a burst of concurrent requests, arriving within the same few milliseconds, all miss the cache at once and fall through to the origin — your database, or an expensive computed aggregate — simultaneously. Instead of one request paying the cost of recomputation, you get N requests paying it at the same time, and N is often in the hundreds or thousands for a genuinely popular key on a busy service.

The database does not see this as N independent slow queries; it sees a sudden burst of identical, expensive load hitting at once, which is exactly the pattern that saturates connection pools and pushes P99 latency into a wall. On a system already running near capacity, a stampede on a single key is enough to trigger connection pool exhaustion, which then cascades into unrelated requests timing out, because they are competing for the same finite pool of database connections.

The naive fix of simply lowering TTLs to keep data fresher makes this worse, not better, because it increases the frequency of expiration events and therefore the frequency of stampede windows. The real fix is not about the TTL value at all — it is about ensuring that when a key does expire, only one request is responsible for recomputing it, while every other concurrent request is served something reasonable instead of also hitting the origin.

2. Probabilistic Early Expiration with the XFetch Algorithm

XFetch (from the 2015 Vattani, Chierichetti and Lowenstein paper) attacks the stampede before it happens by making cache entries probabilistically recompute themselves before they actually expire, spreading recomputation out over time instead of concentrating it at the exact expiry instant. Each cached entry stores not just its value, but also the wall-clock time it took to compute (delta) and its expiry time. On every read, instead of a hard 'is it expired' check, you compute a probabilistic early-expiry trigger.

The core formula is: recompute early if `now - (delta * beta * ln(random()))` is greater than or equal to the expiry time, where beta is a tunable constant (commonly 1.0) and random() draws uniformly from (0,1]. Because ln(random()) is more often close to zero than large-magnitude, most reads pass through untouched, but as the true expiry approaches, the probability of triggering an early, background recomputation rises smoothly — so the recompute gets spread across many earlier reads instead of erupting all at once the moment the TTL hits zero.

Crucially, XFetch's early recomputation happens on a background path while the current cached value is still returned to the requester immediately — the client never waits on it. This means the actual expiry moment, the one where a hard miss forces a synchronous origin call, becomes rare, because in the overwhelming majority of cases some earlier read has already refreshed the value before the real TTL was reached.