Cache stampedes and why they happen
Caching is straightforward in its simplest form: a request hits the cache, and if the resource is there, it's served. If not, the request goes to the origin, the response is stored, and the cycle repeats until expiration. The trouble starts when a cached resource becomes stale while still being popular.
Consider an image service receiving 10 requests per second for the same picture, where the origin can only handle 1 request per second. When the cache entry expires, all 10 requests race to the origin simultaneously. That burst — a cache stampede — overloads the server until the cache is repopulated and can absorb the traffic again.
The standard fix is early revalidation: refresh the cache a few minutes before it actually expires. That prevents the stampede at expiration time, but it introduces a new problem. If 10 requests arrive during the revalidation window, all 10 still go to the origin because nothing collapses them into a single fetch.
The usual fix: a cache lock
The common solution is a cache lock — a coordination primitive that lets only one request through to the origin for a given cache key. A typical lock service exposes two operations:
try_lock: acquire the lock if free and returntrue; otherwise returnfalseunlock: release the lock
Requests that fail to acquire the lock serve stale content while the winner refreshes the cache. This works deterministically for the same key and scales predictably, which is why cache locks dominate production caching systems.
The trade-off is that locks add latency and a point of failure. Every revalidation must contact the lock service, which may live on a different machine or in a different region. If that service is unavailable, revalidation breaks. Probabilistic cache revalidation avoids that dependency entirely: instead of coordinating with an external service, each request computes a probability locally and decides whether to go to the origin.
Probabilistic revalidation with a fixed request rate
The simplest probabilistic approach sets a fixed probability of revalidating. If the origin can handle 1 request per second and the cache receives 10 requests per second, setting p = 1/10 means roughly 1 request per second reaches the origin.
Let r be the request rate and p the revalidation probability. The probability that at least one revalidation occurs within time t is:
E(r, t) = 1 − (1 − p)^(r × t)
With r = 10 and p = 1/10, after 1 second there's a 65% chance a revalidation has happened. Lowering the probability to p = 1/500 stretches that out: after 5 minutes, the chance of revalidation approaches 100%, while the origin sees on average only 1 request every 5 seconds. This works well when the request rate is stable and known.
The code is simple: if the cache entry is not close to expiration, serve it. If it is expired, revalidate. Otherwise, revalidate with the chosen probability.
Adapting to variable traffic
Stable request rates don't exist in practice, so a fixed probability is fragile. At 1 request per second, a probability tuned for 10 requests per second means revalidation barely happens before expiry. At 10,000 requests per second, the same probability sends 20 requests per second to the origin — too many for many backends.
The fix is a probability function that changes as the cache entry approaches expiration. Early in the revalidation window, when the entry has plenty of time to live, the probability is low — say 1/100,000 at high request rates, keeping origin traffic near 1 request every 10 seconds. As expiration nears, the probability rises so that even low-traffic periods eventually trigger a revalidation.
This piecewise approach — stepping up probability at discrete intervals — is practical, but a continuous function behaves more smoothly across all request rates.
The optimal approach: exponential probability
Research on probabilistic cache stampede prevention, notably the paper "Optimal Probabilistic Cache Stampede Prevention" by Vattani, Chierichetti, and Lowenstein (2015), suggests a continuous exponential function instead of discrete steps:
p(t) = e^(−λ × (expiry − t)), for t ∈ [0, expiry]
Here λ is the steepness parameter. For a revalidation window of 300 seconds, setting λ = 1/300 produces the desired behavior. The expected revalidation probability over time becomes:
E(r, t) = 1 − e^(−r × λ × t)
At high request rates this ensures revalidation almost certainly happens long before expiry. At low rates — 1 request per second, say — revalidation may or may not occur before expiration, which is acceptable: a quiet resource can always revalidate lazily at expiry.
The final implementation is a direct translation of this formula. Instead of a fixed probability check, each request computes p(t) based on the current time and the configured steepness parameter.
When to use this
Probabilistic revalidation is not a replacement for cache locks in every scenario. It provides no hard guarantee on the number of origin requests: occasionally zero revalidations occur in a window, occasionally several. Services that require deterministic single-flight behavior should stick with locks.
The probabilistic method shines when a service wants to avoid implementing and operating a lock service but still needs protection against stampedes. It performs well across widely varying request rates and needs no coordination between processes. In a production setting where a worker cannot use built-in stale-while-revalidate behavior, a probabilistic policy computed locally against Date.now() — possibly discretized for efficiency — is a viable, low-complexity alternative.
