Cache Stampedes: Request Coalescing, Probabilistic Early Expiration, Stale-While-Revalidate and Choosing Between Them

The problem and its size

A cache entry for a popular key expires. Every request that arrives before the first recomputation finishes sees a miss and starts its own recomputation. The 2015 paper that gave the problem its best-known treatment uses a simple example: an item read ten times a second whose recomputation takes three seconds produces thirty simultaneous recomputations. The number scales with request rate times recompute time, so the entries that stampede are exactly the ones that are both hot and expensive, which is why the stampede so often takes the backing database down with it. Invalidation strategy, covered in the cache invalidation guide, decides when an entry becomes stale; this article is about what happens in the seconds after it does.

Defence one: request coalescing

Coalescing makes the first miss do the work and every concurrent miss wait for it. In a single process this is a per-key in-flight future: a miss checks a map of futures, joins an existing one or creates and registers its own, and removes it when the value is stored. Guava and Caffeine loading caches do this inside get: concurrent callers for a key whose loader is running wait for that one load. In front of an origin, nginx's proxy_cache_lock does the same across requests: only one request populates a given cache key, the others wait up to proxy_cache_lock_timeout, five seconds by default, after which they are passed to the upstream but their responses are not cached.

Illustrative python, checked for syntax; adapt names and storage to your system.

import asyncio, time

class Coalescer:
    """One recompute per key at a time; concurrent misses share the result."""
    def __init__(self, cache, compute, ttl):
        self.cache, self.compute, self.ttl, self.inflight = cache, compute, ttl, {}

    async def get(self, key):
        hit = self.cache.get(key)
        if hit and hit["expiry"] > time.time():
            return hit["value"]
        fut = self.inflight.get(key)
        if fut is None:
            fut = asyncio.get_running_loop().create_future()
            self.inflight[key] = fut
            try:
                value = await self.compute(key)
                self.cache[key] = {"value": value, "expiry": time.time() + self.ttl}
                fut.set_result(value)
            except Exception as exc:
                fut.set_exception(exc)
            finally:
                del self.inflight[key]
        return await fut

Coalescing removes the duplicate work but not the latency: every waiter still waits for the whole recomputation, and across many processes each process coalesces only its own requests, so a fleet of fifty servers still makes fifty recomputations. A distributed lock in the cache store fixes the fleet case at the cost of a lock round trip and a timeout policy for a holder that dies.

Defence two: probabilistic early expiration

The second idea is to recompute before expiry, randomly, so that one request refreshes the entry while it is still fresh and nobody ever sees the miss. The naive version picks a uniform random point in a window before expiry; the 2015 paper shows the uniform choice is far from optimal and that an exponential distribution is close to optimal and needs no tuning. The algorithm, which the authors call XFetch, stores alongside each value the time its recomputation took, delta. On every read, a request recomputes if the current time minus delta times beta times the natural log of a uniform random number in (0,1) is at or past the expiry. Because the log of a number in (0,1) is negative, the subtraction pushes the effective time forward by a random amount whose scale is the recomputation time, so entries that take longer to compute are refreshed earlier. Beta defaults to 1; raising it refreshes earlier still, trading freshness for even fewer stampedes. The paper proves that the expected stampede size stays below a constant that does not depend on the request rate, at the price of refreshing earlier as the rate grows, roughly in proportion to its logarithm; that is what makes the rule safe to deploy without per-key tuning.

Illustrative python, checked for syntax; adapt names and storage to your system.

import math, random, time

def xfetch(cache, key, recompute, ttl, beta=1.0):
    """Probabilistic early expiration after Vattani, Chierichetti and Lowenstein (2015)."""
    entry = cache.get(key)
    now = time.time()
    if entry is None or now - entry["delta"] * beta * math.log(random.random()) >= entry["expiry"]:
        start = time.time()
        value = recompute(key)
        delta = time.time() - start
        cache[key] = {"value": value, "delta": delta, "expiry": start + ttl}
        return value
    return entry["value"]

Early expiration needs no locks and works across a fleet, because every process applies the rule independently and the expected number that fire within one recompute time stays a small constant, a few rather than hundreds. Its weaknesses are the mirror of coalescing: it does nothing for a cold key, and a key that is read rarely may expire before any reader triggers a refresh, which is fine, because a rare key cannot stampede.

Defence three: serve stale, revalidate behind

The third defence changes the contract: a stale entry may be served while one refresh runs in the background. RFC 5861 defines two Cache-Control extensions for HTTP caches. stale-while-revalidate=N lets a cache serve a stale response for up to N further seconds while it revalidates asynchronously; stale-if-error=N lets it serve a stale response when the origin returns an error. nginx implements the pattern with proxy_cache_use_stale, whose updating value serves the stale copy while one request refreshes it, and proxy_cache_background_update, which performs that refresh as a background subrequest so that even the refreshing client is answered from cache. In-process, Caffeine's refreshAfterWrite returns the old value and reloads asynchronously, with the loader's reload method as the hook.

Served-stale is the only defence that also removes the latency spike, and it degrades gracefully when the origin is down. Its cost is a bounded staleness window that the owner of the data must accept, and the RFC is explicit that the server should set the two extensions to the longest total freshness it can tolerate.

Choosing between them

In practice the three compose. A fleet of application servers reading a shared cache does well with early expiration on every read plus coalescing inside each process for the cold-key case. A CDN or reverse proxy in front of an origin does well with a cache lock plus stale-while-revalidate, which is the nginx pairing of proxy_cache_lock with proxy_cache_use_stale updating and background updates. What does not compose is early expiration with a very short TTL: if the TTL is comparable to delta, the rule fires on nearly every read and the cache stops caching.

Worked example: a pricing page at a flash sale

In this illustrative case a price list for a category takes 2 seconds to assemble from three services and is cached for 60 seconds. At the start of a sale the category page is requested 200 times a second across 40 application servers. With plain TTL expiry, each expiry produces about 400 recomputations, 2 seconds times 200 per second, and the three services see that spike every minute. Adding per-process coalescing cuts that to 40, one per server, which still saturates the slowest service. Adding XFetch with beta of 1 means that each read refreshes with probability e to the power of minus g over delta, where g is the time left before expiry. At 200 reads per second and a delta of 2 seconds, the first refresh typically fires about delta times the log of 200 times delta, roughly 12 seconds, before expiry; a 4,000-run simulation of the rule put the median at 12.7 seconds, with most runs between 10 and 17. Reads that arrive during that 2-second recompute still see the old entry and may fire too, so a refresh averaged 2.7 recomputations instead of 400, close to the small constant the paper derives. The services see a few recomputations about every 48 seconds per category instead of a 400-wide spike every minute, and no reader waits for one.

The remaining exposure is the moment the sale starts, when the key is cold on every server at once. Early expiration cannot help a cold key. The team pre-warms the ten largest categories a minute before the sale and keeps coalescing in place for the rest, which is the combination the comparison table predicts.

Failure modes worth testing

• Coalescing without a timeout. A recompute that hangs makes every waiter hang. Bound the wait, and let a timed-out waiter either serve stale or fail fast.
• Early expiration with a stored delta of zero. The first write often records a tiny delta if the value came from a fast path; a zero delta disables the rule for that entry. Record a floor.
• TTL close to delta. The rule fires constantly. Keep the TTL at least an order of magnitude above the recompute time.
• Serving stale forever. If the background refresh keeps failing, a cache with a long stale-if-error window hides an outage for as long as the window. Alert on refresh failures, not only on misses.
• The lock holder dies. In nginx, proxy_cache_lock_age releases a stuck population after five seconds by default; in your own code, a lock in a shared store needs an expiry and a fencing check.
• Cold keys at a known moment. No read-time defence helps. Pre-warm.
• Negative caching forgotten. A miss for a key that does not exist can stampede too. Cache the absence briefly.

What to do next

1. Find the keys with the largest product of request rate and recompute time; those are the ones that can stampede.
2. Store the recompute duration with each cached value and apply the XFetch rule on reads.
3. Add per-process coalescing with a bounded wait for cold keys.
4. In front of an origin, enable the cache lock and stale-while-revalidate with a window the data owner has agreed to.
5. Load-test the expiry moment and the cold start separately; they fail differently.

Practice and related reading

Further reading:

• Cache invalidation strategies, in depth
• LRU cache architecture
• CloudFront CDN architecture
• Retry, exponential backoff and jitter, in depth
• Database connection pooling

Sources and scope

Checked against these sources on 19 October 2026. Examples and figures are illustrative, not measurements.

• Vattani, Chierichetti and Lowenstein 2015, Optimal Probabilistic Cache Stampede Prevention (PVLDB 8)
• RFC 5861: HTTP Cache-Control extensions for stale content
• nginx documentation: ngx_http_proxy_module (proxy_cache_lock, proxy_cache_use_stale, proxy_cache_background_update)
• Caffeine wiki: Population (loading and asynchronous caches)
• Guava wiki: CachesExplained (LoadingCache, refresh)