Stochastic Model of Cache Stampede in Distributed Systems and Backend-Load Optimality of Request Deduplication

Source abstract

We develop a stochastic model of cache stampede in distributed systems with a time-to-live (TTL) caching layer. Requests for a cache key form a Poisson process of rate λ, and the backend recomputation time ξ has a general distribution F with finite first two moments μ and μ2. We formally introduce "the vulnerability window"—the interval during which a missing entry exposes the backend to redundant computation—and derive the exact stampede probability P=1−Lξ(λ), where Lξ(λ)=E[e−λξ] is the Laplace–Stieltjes transform of ξ, together with the expected backend load of 1+λμ calls per miss episode. The naive, mutex-lock, and request-deduplication (coalescing) strategies are compared within a common miss-episode model; probabilistic early expiration (XFetch), scoped to an implementation with a single-flight guard on the refresh path, is analyzed separately at the TTL-cycle level, since early refresh changes the renewal cycle itself. We prove that deduplication attains the minimum backend load among strategies that regenerate a fresh value after expiration—exactly one backend computation per miss episode, for every λ. The expected latency of a typical request in a deduplication window is (μ+λμ2/2)/(1+λμ), while the mean waiting time pooled over the non-initiating (coalesced) requests equals the mean residual computation time R=μ2/(2μ) for every λ—a manifestation of the inspection paradox. By contrast, a transient single-server FIFO backend under the naive strategy yields a mean window latency μ+λμ2/2 that grows linearly in λ. We further formulate an optimal-TTL problem balancing expected latency against a data-staleness cost over the exact renewal cycle (idle gap included) and obtain, under a mild explicit condition, the unique interior optimum τ∗=−d+d2+(2μ/λ+μ2−2cd)/γ−−−−−−−−−−−−−−−−−−−−√, d=μ+1/λ, in closed form, without relying on high-popularity approximations (here c is the cache-read latency and γ the staleness cost per unit of age). Monte Carlo simulation (N=2×105 runs for probabilities and 6×104 for latency) numerically verifies the analytical miss-episode and TTL results within the stated model: at the reference point λ=50 req/s the stampede probability for a lognormal backend, evaluated independently by numerical integration, agrees with simulation to 0.02%, and all verification metrics agree with theory to within 0.5%.