Cache Stampede: When a Hot Key Expires

In one line

When a very popular key expires (or is evicted), thousands of concurrent requests miss at once and all hit the database for the same value. Prevent it with request coalescing, a rebuild lock, probabilistic early refresh, stale-while-revalidate, or background refresh.

0/7 · 0%

Think of it like this

A coffee shop's only pot of coffee runs out at 8:59, right before the morning rush. Instead of one barista brewing a new pot, every customer walks behind the counter and starts brewing their own. The kitchen is overwhelmed and nobody gets coffee faster.

Key ideas

01
Also called the thundering herd or dog-piling. The damage scales with request rate × rebuild time: at 50K requests/sec and a 200 ms query, ~10,000 identical queries hit the database before the first one refills the cache.
02
Request coalescing (single-flight) inside each app instance: concurrent misses for the same key share one in-flight load (a Future/Promise map, Caffeine's get(key, loader), Go's singleflight). With 100 instances, the database sees at most 100 queries instead of 10,000.
03
Distributed rebuild lock: on a miss, SET lock:product:9 <token> NX PX 5000. The winner rebuilds and writes the cache; the losers wait briefly and re-read the cache (or serve a stale copy). Always put an expiry on the lock so a crashed rebuilder doesn't block forever.
04
Stale-while-revalidate: store the value with a logical expiry inside it (for example {data, softExpiresAt}) and a longer physical TTL. After the soft expiry, the first request triggers an async refresh (guarded by the lock) while everyone keeps getting the slightly stale value. Users never see a miss.
05
Probabilistic early refresh (XFetch): each request recomputes early with a probability that increases as expiry approaches (now − delta × beta × ln(rand()) ≥ expiry), so one request usually refreshes before expiry without any lock. Elegant for many keys.
06
Background refresh: for a known set of hot keys (the homepage, top products), a scheduler refreshes them before they expire, so they effectively never expire.
07
TTL jitter doesn't stop a single hot key's stampede, but it prevents many keys from expiring together (avalanche, next topic).

Code & diagrams

stampede.mermaiddiagram

Rendering diagram…

swr_cache.pypython

Stale-while-revalidate with a rebuild lock: users always get a value; only one worker rebuilds.

import json, time, uuid, threading

SOFT_TTL, HARD_TTL = 60, 3600

def get_with_swr(r, key, loader):
    raw = r.get(key)
    if raw:
        entry = json.loads(raw)
        if time.time() > entry["soft_exp"]:
            refresh_async(r, key, loader)       # stale: refresh in background
        return entry["data"]                     # serve (possibly stale) value
    return refresh(r, key, loader, wait=True)    # true miss: someone must load

def refresh(r, key, loader, wait=False):
    token = uuid.uuid4().hex
    if r.set(f"lock:{key}", token, nx=True, px=5000):
        try:
            data = loader()
            entry = {"data": data, "soft_exp": time.time() + SOFT_TTL}
            r.set(key, json.dumps(entry), ex=HARD_TTL)
            return data
        finally:
            release_lock(r, f"lock:{key}", token)   # compare-and-delete Lua, Topic 12.1
    if wait:
        for _ in range(50):                      # another worker is loading
            time.sleep(0.02)
            raw = r.get(key)
            if raw:
                return json.loads(raw)["data"]
        return loader()                          # give up waiting: load ourselves
    return None

def refresh_async(r, key, loader):
    threading.Thread(target=refresh, args=(r, key, loader), daemon=True).start()

xfetch.javajava

Probabilistic early expiration: the chance of refreshing rises as expiry approaches.

// delta = how long the last recompute took (ms), beta ~ 1.0
boolean shouldRefreshEarly(long nowMs, long expiryMs, long deltaMs, double beta) {
    double r = ThreadLocalRandom.current().nextDouble();   // (0,1)
    return nowMs - deltaMs * beta * Math.log(r) >= expiryMs;
}

Interview problem

The problem

Product cache stampede at 12:00:00

10M users are refreshing the same product page during a launch. At 12:00:00 the cached product expires. Design the system so the database doesn't receive millions of identical requests.

You're given

~200K requests/sec for one product
Database query takes 150 ms
300 app instances
Page must stay up

The interviewer follows up

What happens if the lock holder crashes mid-rebuild?

Does Spring's @Cacheable(sync = true) solve stampedes?

When it breaks

Rebuild lock without an expiry

What you see

The rebuilder crashes; the lock stays forever; nobody rebuilds; the key stays missing and every request either waits and times out or falls through to the database.

Fix & prevent

Always SET lock NX PX <ms>; release with a token-checked delete; monitor lock age.

Losers of the lock race call the database anyway after a tiny wait

What you see

The lock only delays the herd by a few milliseconds; the database still gets thousands of queries.

Fix & prevent

Serve a stale value (stale-while-revalidate or an L1 copy), or wait long enough for a rebuild with a bounded retry loop, then degrade rather than query.

Explain it without notes

Explain stale-while-revalidate with soft and hard TTLs.

Why does per-instance request coalescing alone not fully solve a stampede?

Practice

Simulate a stampede: 500 threads read a key with a 1 s TTL whose loader sleeps 200 ms. Count loader calls without protection, then with the lock + stale pattern.

Trade-offs

↔
Stale-while-revalidate trades a little staleness for zero misses on hot keys.
↔
Locks add a round trip and complexity; XFetch avoids locks but still allows occasional duplicate refreshes.

Done when you can

I can quantify a stampede and pick protections for hot keys.
I can implement a rebuild lock, stale-while-revalidate and XFetch.
I know the limits of in-process coalescing and @Cacheable(sync=true).

Command Palette