The Problem with Hard Expiry
Every cache entry with a fixed TTL (Time To Live) is a ticking time bomb. The moment it expires, every concurrent request that was relying on it hits the database simultaneously. The harder you lean on caching, the more catastrophic the stampede when it fails.
The Solution: Let the Cache Expire Gradually
Probabilistic Early Expiration (also called "soft expiry" or the XFetch algorithm) prevents stampedes by refreshing the cache before it expires, using randomness to ensure only one request does the refresh at a time.
The algorithm works as follows:
- Store the cache entry with its TTL and the time it took to compute (the "delta" — how long the DB query takes).
- On every cache read, calculate a score:
score = current_time - (delta * beta * log(random())) betais a tuning parameter (typically 1.0).random()returns a value between 0 and 1.- If
score > expiry_time, the current request proactively refreshes the cache, even though the entry hasn't technically expired yet. - All other concurrent requests get the still-valid cached value.
The key insight: as the expiry time approaches, the probability that any given request triggers an early refresh increases. But because it's probabilistic, only one request (statistically) triggers it at a time. By the time the TTL actually hits zero, the cache has already been refreshed.
Practical Implementation
A minimal implementation stores each cache entry alongside its expiry time and the delta (how long the original fetch took). On every read, it computes the same score formula described above; if the score has crossed the expiry threshold, that one request proactively re-fetches and re-stores the value (recording a fresh delta), while every other concurrent reader simply gets the still-cached value back.
When to Use Each Stampede Prevention Technique
| Technique | Best For | Trade-off |
|---|---|---|
| Probabilistic Early Expiration | Single popular keys with expensive fetches | Slightly complex logic; requires storing delta |
| Request Coalescing (Singleflight) | High-concurrency services with many duplicate requests | In-process only; doesn't work across multiple servers without coordination |
| Cache Warming on Deploy | Deployment-triggered invalidations | Requires a warming job; adds deploy complexity |
| Staggered TTL Jitter | Large numbers of keys expiring at similar times | Doesn't help when a single key is extremely hot |
For most production systems, request coalescing and probabilistic early expiration are complementary: coalescing handles the burst of concurrent misses, while early expiration prevents the miss from happening in the first place.