The cache is working. The hit rate is 98%, the database is bored, and the dashboards are green. Then, once every five minutes, the database spikes to 100% CPU for a couple of seconds and a handful of requests time out. Nobody can reproduce it, it never lines up with a deploy, and it has been happening for months.
That is a cache stampede, and the arithmetic behind it is a single multiplication that almost nobody performs.
The multiplication
A cache miss is not one request going to the database. It is every request that arrives while the first one is still computing.
The paper that formalised this — Vattani, Chierichetti and Lowenstein, VLDB 2015 — gives the arithmetic in one sentence: "if the cache item is accessed 10 times per second, and the recomputation of the item takes 3 seconds, then 30 requests will recompute the item." It also names the feedback loop that turns a spike into an outage: "several concurrent re-computations will increase the time of each individual recomputation by bogging down the system, in turn causing even more requests to be part of the stampede."
That loop is the reason this fails badly rather than gracefully. Sixty concurrent queries make the database slower, the recomputation takes three seconds instead of 1.5, so the next stampede is 120 requests, which makes it slower still. It is the same self-amplifying shape as a queue with no backpressure: the system's response to overload is to generate more of it.
The second multiplication nobody plans for
The per-key number is bad. The thing that turns it into an incident is that your keys are not independent.
Consider how hot keys get written. A deploy invalidates the cache and the first traffic after it warms every popular key within a second or two. A cache flush during an incident does the same. A cold Redis after a failover, a scheduled job that primes the cache at midnight, a feature launch — all of them write a batch of keys at nearly the same moment, with identical TTLs.
Five minutes later, all of those keys expire at nearly the same moment too. Fifty keys at sixty requests each is three thousand concurrent recomputations against an origin that handles forty.
This is why the spike is periodic and why it is so hard to trace. It has a period equal to your TTL, it started at some deploy nobody remembers, and it has nothing to do with the traffic pattern.
What jitter actually fixes
The standard advice is to randomise the TTL: instead of 300 seconds, use 300 seconds plus or minus 10%. That is good advice and it is half a fix.
Look at the bottom row. Even at ±50% jitter — an enormous amount, enough that your cache freshness guarantee becomes vague — the concurrent work only falls to sixty. That sixty is the per-key stampede, and no amount of spreading the keys out touches it, because those sixty requests are all for the same key and they all arrive during the same recomputation.
Jitter fixes the correlation between keys. It does nothing about the correlation between requests for one key, and that is the part that grows as your traffic grows. A service that is fine today at 40 requests a second per key has a 600-request stampede when it reaches 400.
The fix is to stop recomputing more than once
Two mechanisms, and they solve the same problem from different directions.
Single-flight (or locking): the first request to see the miss takes a lock and recomputes; everyone else either waits for it or serves the stale value. The concurrent work becomes one per key, independent of traffic. The paper is even-handed about its costs: it "requires one extra write for the locking mechanism (doubling the number of write operations), tuning a time-to-live for the lock itself... and implementing a locking mechanism", and "this approach is not fault-tolerant: if the request acquiring the lock fails while re-generating the item, no item or a stale item will be served until the lock expires".
Probabilistic early expiry: every reader independently decides, with a probability that rises as expiry approaches, to refresh the value before it expires. Because the decision is independent and usually negative, one unlucky request does the work while everyone else keeps hitting a warm cache. There is never a moment when the key is missing.
The paper's contribution is showing which probability distribution to use. Earlier implementations used a uniform distribution — "a probabilistic early expiration strategy is used in Perl's unified Cache Handling Interface (CHI)... CHI uses the uniform distribution" — and the paper shows "the uniform distribution is far from being optimal, while the exponential distribution is much more efficient (on all axes) and close to optimality."
The resulting algorithm, XFetch, is five lines:
function XFetch(key, ttl; β = 1)
value, Δ, expiry ← CacheRead(key)
if !value or Time() − Δ·β·log(rand()) ≥ expiry then
start ← Time()
value ← RecomputeValue()
Δ ← Time() − start
CacheWrite(key, (value, Δ), ttl)
end
return value
endΔ is how long the last recomputation took, stored alongside the value. rand() is uniform on (0,1), so −log(rand()) is exponentially distributed with mean 1, and multiplying by Δβ scales the gap to the cost of the work. An expensive value starts refreshing earlier than a cheap one, automatically.
The property that makes it practical: "the parameter λ needs not to depend on the rate of requests in order to effectively reduce stampedes. This property makes our solution very attractive in that, in its simplest form, it requires no parameter tuning to perform effectively."
| How it behaves | Single-flight / locking | Probabilistic early expiry |
|---|---|---|
| One recomputation per key, guaranteed | A small number, not guaranteed to be one | |
| Needs a lock: an extra write, a lock TTL | No coordination at all, one extra field | |
| A crashed holder blocks until the lock expires | A failed refresh just means someone else tries | |
| Other requests wait, or serve stale | Nobody waits: the cache was never empty | |
| Works across processes only with a shared lock | Works per process, no shared state needed | |
| Refreshes exactly at expiry | Refreshes a little early, scaled to recomputation cost |
In practice you want jitter and one of these. Jitter is one line and removes the synchronised thundering herd after a deploy. Single-flight or XFetch removes the per-key pile-up that grows with traffic. Neither substitutes for the other.
Work out your own numbers
calculator · cache stampede
What hits your database the moment the cache expires
concurrent recomputations at the origin, by countermeasure
what jitter alone buys you, at this TTL and recomputation time
The stampede size is the arithmetic from the VLDB paper: every request arriving during a recomputation sees the miss, so it is the request rate multiplied by the recomputation time. The jitter model assumes expiries spread uniformly over the jitter window, which is what a random TTL gives you. The XFetch row uses a small constant rather than a precise figure: the paper's result is that the expected stampede size does not grow with your request rate, and the exact constant depends on the β you pick.
Things worth trying:
Set jitter to 10%. The number drops by twenty times and is still above the origin's capacity. This is the experiment that explains why teams add jitter, see an improvement, and keep having the incident.
Double the recomputation time. Everything gets worse twice over: the per-key stampede doubles because the miss window is longer, and the origin is slower because it is doing more work. This is the feedback loop, visible.
Raise the request rate to 20,000. Jitter's benefit is unchanged and the per-key floor grows tenfold. That is the difference between a countermeasure that scales and one that does not.
At the HTTP layer, it already has a name
If your cache is a CDN or a reverse proxy rather than Redis, the same problem has standard answers.
RFC 5861 defines stale-while-revalidate: "caches MAY serve the response in which it appears after it becomes stale, up to the indicated number of seconds", and the cache "SHOULD attempt to revalidate it while still serving stale responses (i.e., without blocking)". One header — Cache-Control: max-age=600, stale-while-revalidate=30 — and the expiry no longer produces a gap where the origin is exposed.
Its sibling stale-if-error handles the other half: "when an error is encountered, a cached stale response MAY be used to satisfy the request", where an error is "any situation that would result in a 500, 502, 503, or 504 HTTP response status code being returned." That is a free circuit breaker for the case where the stampede already happened and the origin is down.
Proxies add request coalescing on top: nginx's proxy_cache_lock means "only one request at a time will be allowed to populate a new cache element", while the others "wait for a response to appear in the cache or the cache lock for this element to be released". That is single-flight by another name, and it is off by default. Its proxy_cache_use_stale updating setting is the other half: it "permits using a stale cached response if it is currently being updated". If you run a CDN, check whether coalescing is on by default — several do it, and it quietly removes a problem you would otherwise have to solve in application code.
quick check
You add ±10% TTL jitter and the periodic database spike gets much smaller but does not go away. What is left?
Jitter decorrelates different keys from each other. It does nothing about the requests piling onto a single key during its recomputation window, because those all arrive while that one key is missing. That floor is rate × recomputation time, and it only goes away with single-flight or probabilistic early expiry.
What the arithmetic leaves out
Requests are not uniform. The model assumes a steady rate, so the stampede size is a mean. Real traffic is bursty, and a burst that coincides with an expiry is larger than this suggests. The paper notes its approach is "very robust to bursts", which is another argument for the probabilistic fix over tuning TTLs.
Not every miss is an expiry. Eviction under memory pressure produces the same pile-up with none of the predictability, and no TTL strategy helps because the key did not expire — it was thrown out. If your cache is running near its memory limit, you have a second source of stampedes that the calculator will not show you, and the fix is capacity rather than cleverness.
The origin capacity number is a simplification. Treating the database as "handles N concurrent recomputations" hides that concurrency and throughput are not the same thing, and that past a point more concurrent queries make the database do less total work. That is the same effect as oversizing a Postgres connection pool, and it is why a stampede degrades so sharply rather than gradually.
Serving stale is a product decision, not an engineering one. Every fix here either makes someone wait or serves them an older value. For a product listing, thirty seconds of staleness is invisible. For an account balance it is a support ticket. Decide that per key, not per system.
A stampede can be a symptom. If a value takes 1.5 seconds to compute and is requested forty times a second, the interesting question may not be how to cache it better. It may be why it costs 1.5 seconds. Caching is what you do when you have decided not to answer that question, which is often correct and occasionally an expensive way to avoid a missing index.
questions people ask
What is a cache stampede?
When a popular cached value expires and every request that arrives during its recomputation also sees a miss and recomputes it. The size is the request rate on that key multiplied by the recomputation time, so 40 requests a second against a 1.5-second recomputation gives about 60 simultaneous queries for the same value.
Does adding TTL jitter fix cache stampedes?
Only partly. Jitter stops many keys expiring at the same instant, which is the spike you see after a deploy warms the cache. It does nothing about the requests piling onto one key during its own recomputation window, and that is the part that grows with your traffic.
What is the difference between single-flight and probabilistic early expiry?
Single-flight uses a lock so exactly one request recomputes while the others wait or serve stale; it needs an extra write, a lock TTL, and it stalls if the lock holder dies. Probabilistic early expiry has each reader independently decide to refresh slightly before expiry, so the cache is never empty and no coordination is needed, at the cost of the occasional extra recomputation.
How do I implement XFetch?
Store the recomputation duration alongside the value, and on every read refresh early if Time() − Δ·β·log(rand()) ≥ expiry, where Δ is that stored duration and rand() is uniform on (0,1). With β = 1 it needs no tuning, and expensive values start refreshing earlier than cheap ones automatically.
What TTL jitter percentage should I use?
Ten to twenty per cent is plenty for decorrelating keys, and beyond that you are trading away freshness for something jitter cannot fix anyway. If the number is still too high at ±20%, the problem is the per-key stampede and jitter is the wrong lever.
Can I fix this at the CDN instead of in code?
Often, yes. stale-while-revalidate lets the cache serve the old response while one request refreshes it, and stale-if-error covers the case where the origin is already failing. Many proxies and CDNs also coalesce concurrent requests for the same key by default, which is single-flight without any application change.
The short version
A cache stampede is a multiplication: requests per second on a key, times how long it takes to recompute. Do it once for your hottest key and the number is usually larger than the origin can absorb.
Then it is multiplied again, by every key that was written at the same moment and therefore expires at the same moment. That is the periodic spike nobody can trace, and its period is your TTL.
TTL jitter fixes the second multiplication and leaves the first one intact, which is why teams add jitter, see the graph improve, and keep the incident. The fix for the first is to stop letting more than one request recompute: a lock, or five lines of probabilistic early expiry that need no coordination and no tuning. At the HTTP layer the same idea ships as stale-while-revalidate.
Add both. Jitter is one line and removes the post-deploy herd; the per-key fix is what keeps working when your traffic triples.