Cache stampede on a hot key

What it is

A cache stampede (also called dog-piling or a thundering herd) is what happens when a popular cache entry expires and every concurrent request for it misses at the same moment, so all of them go to the origin simultaneously. A key served 2,000 times a second from cache becomes 2,000 concurrent origin requests the instant its TTL elapses.

It is commonly confused with two neighbours. A hot key is a key with disproportionate traffic, which is a load distribution problem and exists whether or not the cache is working. A cold cache is a cache with no useful entries, typically after a restart or a flush, which is a capacity problem across many keys. A stampede is specifically the synchronisation problem: many clients transitioning from hit to miss at the same instant on the same key.

The reason it deserves its own name is that the failure is self-amplifying. The origin, now serving 2,000 concurrent requests instead of one, slows down. Slower origin means the recomputation takes longer, which means more requests arrive during the miss window, which means more concurrent origin load. Add client retries and you have a positive feedback loop, which is how a cache expiry takes down a database.

The problem it solves

The reason caches have TTLs at all is that invalidation is hard: a TTL is a declaration of the staleness you will tolerate rather than an attempt to be correct. The stampede is the bill for that convenience, paid all at once, on a schedule you set yourself when you chose the TTL.

Preventing it means arranging that at most one client recomputes a given key at a time, or that the transition from fresh to stale is not simultaneous across clients, or that clients can be served something useful while the recompute happens. Those are the three families of solution, and a good answer names all three and picks.

Mechanics

Approach 1: request coalescing (singleflight, or a lock)

Exactly one caller recomputes; the rest wait for that result. In-process this is trivial and free:

import "golang.org/x/sync/singleflight"

var group singleflight.Group

func GetProduct(ctx context.Context, id string) (*Product, error) {
    if p, ok := cache.Get(id); ok {
        return p.(*Product), nil
    }
    // Every concurrent caller for the same key blocks on the SAME call.
    // The origin sees exactly one request per process, no matter how many
    // goroutines arrive during the miss window.
    v, err, _ := group.Do(id, func() (interface{}, error) {
        p, err := db.LoadProduct(ctx, id)
        if err != nil {
            return nil, err
        }
        cache.SetWithTTL(id, p, 5*time.Minute)
        return p, nil
    })
    if err != nil {
        return nil, err
    }
    return v.(*Product), nil
}

That collapses the herd per process. With 40 pods you still get 40 concurrent origin requests, not 2,000, which is usually enough. If it is not, you need a distributed lock:

-- Redis: acquire a short-lived recompute lock, atomically.
-- KEYS[1] = lock key, ARGV[1] = holder token, ARGV[2] = lock TTL ms
-- Returns 1 if we won the right to recompute, 0 if someone else is on it.
if redis.call('SET', KEYS[1], ARGV[1], 'NX', 'PX', ARGV[2]) then
  return 1
else
  return 0
end

The loser has two choices, and this is the design decision people skip: wait and poll for the winner's result (adds latency, and if the winner dies you wait for the lock TTL) or serve stale immediately (needs a stale copy, which Approach 3 provides). Serving stale is almost always the better answer. A lock without a stale fallback converts a stampede into a latency spike, which is an improvement but not a fix.

The lock TTL must exceed the worst-case recompute time or two clients will recompute concurrently, and the holder token must be checked before release or a slow client will delete a lock it no longer owns.

Approach 2: probabilistic early expiration

Instead of expiring at a fixed instant, each client independently decides, slightly before expiry, whether to recompute. The probability of recomputing rises as expiry approaches, so exactly one client typically refreshes early and the rest keep hitting a fresh entry.

The clean formulation is XFetch, from Vattani, Chierichetti and Lowenstein's 2015 paper. Store, alongside the value, the time the recomputation took ($\delta$). Recompute when:

$$\text{now} - \delta \beta \ln(U) \geq \text{expiry}$$

where $U$ is uniform on $(0,1]$ and $\beta$ is a tuning constant, typically 1.

import math, random, time

def get(key, ttl=300, beta=1.0):
    packed = redis.get(key)
    if packed is not None:
        value, delta, expiry = unpack(packed)
        # The more expensive the recompute (delta) and the closer to expiry,
        # the likelier this particular caller volunteers to refresh early.
        if time.time() - delta * beta * math.log(random.random()) < expiry:
            return value                       # still fresh enough, serve it
    start = time.time()
    value = recompute(key)                     # expensive origin call
    delta = time.time() - start
    redis.set(key, pack(value, delta, time.time() + ttl), ex=ttl + 60)
    return value

The elegance is that it needs no coordination at all: no lock, no shared state beyond what you were already storing. The cost is that you must measure and store the recompute duration, and that expensive keys get refreshed earlier and more often, which is the correct behaviour but does raise origin load slightly in steady state.

Jittered TTLs are the poor relative of this idea and are worth doing regardless: write ttl + random(0, ttl * 0.1) so a batch of keys populated together does not expire together. That fixes stampedes across many keys, which is the restart-and-warm case; it does not fix a stampede on a single hot key, because all clients read the same stored expiry.

Approach 3: serve stale while revalidating

Keep two clocks on the entry: a freshness deadline and a hard deadline. Between them, serve the stale value immediately and trigger exactly one background refresh. At the HTTP layer this is a standard header:

Cache-Control: public, max-age=60, stale-while-revalidate=300, stale-if-error=86400

max-age=60 means fresh for a minute. stale-while-revalidate=300 means for the next five minutes the cache may serve the stale copy immediately while refreshing in the background, so no client ever waits on the origin. stale-if-error=86400 means if the origin is down, keep serving the stale copy for a day rather than returning an error, which converts an origin outage into a staleness incident.

This is the highest-leverage of the three because it removes the latency of a miss as well as the herd. It requires that stale data be acceptable, which for product pages, search results, feature flags and configuration it almost always is, and for account balances it is not.

A worked example

A product detail endpoint. 3,000 requests per second across 40 pods, cached in Redis with a 5 minute TTL. Origin cost is a 400 ms Postgres query joining four tables. One product accounts for 40 percent of traffic during a promotion.

Without protection: every 300 seconds, that key expires. In the 400 ms it takes to recompute, $3000 \times 0.4 \times 0.4 = 480$ requests arrive and all miss. The database receives 480 concurrent copies of a 400 ms query, its connection pool of 100 saturates, the query slows to 3 seconds under contention, and now $3000 \times 0.4 \times 3 = 3600$ requests are queued on a pool that is full. The endpoint's p99 goes from 15 ms to a timeout, and the outage lasts until traffic drops, not until the recompute finishes.

With in-process singleflight only: 40 concurrent queries instead of 480. The pool holds. p99 for the unlucky 480 requests is 400 ms instead of 15 ms, but nothing falls over. This alone is often sufficient, and it is one import.

With singleflight plus stale-while-revalidate: 40 background refreshes, and zero requests wait. p99 stays at 15 ms through the refresh. Users see data up to 300 seconds old plus the 400 ms refresh window, which for a product page is irrelevant.

With XFetch instead of a lock: the refresh happens before expiry, typically by one caller, so there is no miss window at all in the common case. Comparable outcome with less machinery, at the cost of storing $\delta$.

The full answer to "prevent a cache stampede, three approaches" is those three, and then the sentence that matters: combine coalescing with stale-serving, because coalescing alone converts a stampede into a latency spike and stale-serving alone still lets many clients trigger redundant refreshes.

Production evidence

Facebook's memcache paper (Nishtala et al., NSDI 2013) describes leases, which are the canonical production implementation of coalescing: on a miss, memcached hands the requesting client a lease token and, for a short window, tells other clients requesting the same key either to wait and retry or to use a slightly stale value. The paper attributes both stampede prevention and a class of consistency fix to this one mechanism, and it is the citation to reach for.

Nginx ships proxy_cache_lock, which allows only one request to populate a cache element while others wait, with proxy_cache_lock_timeout bounding the wait, and proxy_cache_use_stale updating to serve stale during the refresh. Varnish coalesces requests for the same object into a single backend fetch by default. Cloudflare documents concurrent request collapsing at the edge for cacheable resources. These are three independent CDN and proxy implementations of the same idea, which is a strong argument that it is the standard answer rather than a clever trick.

golang.org/x/sync/singleflight originated in Brad Fitzpatrick's groupcache, where it is the mechanism that keeps a cache fill from being duplicated across concurrent callers; it is now used widely inside Kubernetes and the Go ecosystem.

stale-while-revalidate is standardised in RFC 5861 and implemented by every major CDN and by browsers.

The debate

The credible alternative to all three is not to expire hot keys at all: use explicit, event-driven invalidation, or versioned keys where a write publishes a new key rather than invalidating the old one. product:123:v7 is never stale and never stampedes, because a new version is a new key that is populated before it is referenced. This is genuinely better where you can do it, and where you cannot is instructive: it requires that every writer knows every cache that derives from its data, which is a coupling most systems do not have.

Between the three approaches:

Coalescing is the most universally applicable and the least invasive. Start here. Its weakness is that the waiters' latency is now the origin's latency, and that a distributed lock adds a failure mode (lock holder dies).
Probabilistic early expiration is the most elegant and needs no coordination, which makes it attractive across many processes. Its weakness is that it is unfamiliar, so the next engineer will not understand the code, and that it slightly raises steady-state origin load.
Serve stale has the best user-visible outcome by a wide margin and is the only one that also protects you when the origin is down. Its weakness is that it requires staleness tolerance, and it requires you to store the value past its nominal expiry, which is a correctness decision someone must sign off on.

My position: default to serve-stale plus in-process coalescing. That combination removes both the herd and the latency, needs no distributed lock, and degrades correctly when the origin fails. Add a distributed lock only when per-process coalescing still leaves too many origin requests, which means when your fleet is large and the origin is genuinely fragile. Reach for XFetch when you cannot tolerate serving stale but also cannot tolerate the miss latency, which is a narrow but real case.

Stampede protection is the wrong thing to work on when the real problem is that the key should not be recomputed at all: if the value changes once a day and you have set a 60 second TTL, fix the TTL. A startling share of stampede incidents are a TTL chosen by reflex.

Follow-up Q&A

"Prevent a stampede on a hot key. Three approaches." Request coalescing so only one caller recomputes and the rest wait or get stale; probabilistic early expiration so clients independently refresh slightly before expiry and the transition is not synchronised; and stale-while-revalidate so the stale value is served immediately while one background refresh runs. Jittered TTLs help across many keys but not on a single hot key, and saying that distinction unprompted is the depth signal.

"Your distributed lock holder crashes mid-recompute. What happens?" Everyone waiting blocks until the lock's TTL expires, then one of them wins and recomputes. So the lock TTL is a latency bound on your failure case, and it must be longer than the worst-case recompute (or the herd returns) and short enough that a crash does not stall traffic for minutes. This tension is the reason to prefer serve-stale: the waiters have something to return, so the lock's expiry is no longer on the critical path.

"How is this different from a cold cache after a deploy?" A stampede is many clients missing one key at one instant; a cold cache is all keys missing across a sustained window. Coalescing fixes the first and does nothing for the second. The fixes for a cold cache are different: warm the cache before shifting traffic, roll pods gradually so a warm subset always exists, use a shared distributed cache rather than per-instance caches so a restart does not lose anything, or admit load gradually with a slow-start ramp on the load balancer.

"When would you deliberately not protect against this?" When the origin can absorb the herd trivially, for example a value computed from an in-memory structure, and the protection would add more failure modes than it removes. And when the data must never be stale and the recompute is cheap: a lock and a wait is fine, and stale-serving is forbidden.

"How would you detect that this is happening in production?" Origin request rate is the tell: a periodic spike at exactly your TTL interval, synchronised across pods, with cache hit rate dropping to zero for a few hundred milliseconds and recovering. Plot origin QPS and cache hit ratio on the same graph at one-second resolution; the sawtooth is unmistakable. At coarser resolution it averages away, which is why teams miss it.

Common misconceptions

The most common is that jittering TTLs fixes it. Jitter desynchronises different keys that were populated at the same time. On a single hot key, every client reads the same expiry from the same cache entry and misses together regardless of how the TTL was chosen. Jitter is necessary and not sufficient, and confusing the two is the most frequent wrong answer to this question.

The second is that a distributed lock is the sophisticated answer and in-process coalescing is the naive one. In-process coalescing usually reduces the herd by the number of pods, which is a factor of 10 to 100, at the cost of one import and zero new failure modes. Reaching for Redlock first is over-engineering.

The third is that no-cache means "do not cache". It means "revalidate before use"; no-store means do not cache. Getting this backwards in an interview is a cheap and avoidable error.

Interview delivery note

Say this: "Three families: coalesce so one caller recomputes and the others wait or get stale, probabilistically refresh early so clients do not all transition at the same instant, or serve stale while revalidating in the background. I would combine the first and third, because coalescing alone just turns the stampede into a latency spike, and stale-while-revalidate also covers me when the origin is down. Jittering TTLs helps across many keys but does nothing for a single hot key, because every client reads the same expiry."

The depth signal is that last sentence and the amplification loop: naming that the origin slowing under the herd lengthens the miss window, which enlarges the herd, is what distinguishes someone who has watched this take down a database from someone who has read the definition.

The Staff & Team Lead Interview Reference