This Fixes: The Cache Stampede When a Hot Key Expires

A single popular cache key expires. In the same millisecond a thousand in-flight requests miss, and every one of them turns round and hammers the database to rebuild the same value. That is a cache stampede, and it takes out the database precisely when traffic is highest.

The symptom is unmistakable in the graphs: cache hit rate is fine, then a cliff-edge dip, a database CPU spike, a latency spike, and often a cascade as connection pools saturate. The cause is almost always one or two hot keys expiring under concurrency. The fix is three cheap mechanisms layered together — a per-key lock, a serve-stale window, and early refresh — none of which requires a new piece of infrastructure. This walks through all three with Redis 7.4 and redis-py.

Why the herd forms

The naive cache-aside pattern is: read the key; if it is missing, compute the value and write it back. That is correct for one request at a time and catastrophic under load. When a hot key expires, every concurrent request sees the same miss, and every one of them runs the expensive branch. There is no coordination between them, so the work is done not once but as many times as there are requests waiting on that key. A value that costs 200ms to build and is read 5,000 times a second becomes 5,000 simultaneous 200ms database queries the instant it expires.

Three things make it worse. Keys created together — warmed at deploy, or written in a batch — expire together, so several hot keys can stampede at once. Longer rebuild times widen the window in which new requests keep arriving and missing. And retry logic, added in good faith, multiplies the load exactly when the database is already struggling. The goal of the fix is simple to state: when a hot key needs rebuilding, exactly one request should do the work, and everyone else should get an answer without touching the database.

One rebuild, not a thousand: the SET NX lock

The coordination primitive is a per-key lock built on a single atomic command. SET lock:key token NX EX 10 sets the key only if it does not already exist (NX) and gives it a short expiry (EX) so a crashed worker cannot hold the lock forever. The command is atomic, so under a thousand concurrent attempts exactly one succeeds. That winner recomputes the value; the losers do not.

Two details matter. First, the lock must carry a random token and be released with a compare-and-delete, not a plain DEL — otherwise a worker whose lock has already expired can delete a lock a different worker now holds. Redis has no atomic check-and-delete for this, so the release runs as a tiny Lua script. Second, the lock TTL has to comfortably exceed the worst-case rebuild time, or the lock expires mid-rebuild and a second worker joins in. This is the same single-flight discipline that makes idempotency keys in FastAPI and Redis safe to retry.

Serve stale while one worker revalidates

The lock stops duplicate work, but it leaves a question: what do the losing requests return while the winner rebuilds? Blocking them all until the value is ready just moves the stampede from the database to your request threads. The better answer is stale-while-revalidate: keep the old value available past its logical expiry and serve it to everyone except the one worker doing the rebuild.

That means separating two lifetimes. The logical expiry is when the value is considered due for refresh. The physical Redis TTL is set longer — logical TTL plus a grace window — so the key still exists, and can still be served stale, while a rebuild is in flight. Store the value together with its logical expiry and the duration of the last recompute, so the read path has everything it needs.

import json
import math
import random
import time

import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

LOCK_TTL = 10          # seconds a recompute lock may be held
RELEASE = r.register_script("""
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
end
return 0
""")


def _store(key, value, ttl, stale_grace, delta):
    """Write the payload plus the metadata the read path needs."""
    now = time.time()
    entry = {
        "value": value,
        "expiry": now + ttl,     # logical expiry (jittered by the caller)
        "delta": delta,          # how long the last recompute took
    }
    # Physical TTL outlives logical expiry so stale data survives to be served.
    r.set(key, json.dumps(entry), ex=int(ttl + stale_grace))


def _recompute(key, compute, ttl, stale_grace):
    started = time.time()
    value = compute()                     # the expensive call: DB, upstream API
    delta = time.time() - started
    jittered = ttl * random.uniform(0.9, 1.1)   # +/- 10% TTL jitter
    _store(key, value, jittered, stale_grace, delta)
    return value


def get_or_compute(key, compute, ttl=300, beta=1.0, stale_grace=60):
    now = time.time()
    raw = r.get(key)

    if raw is not None:
        entry = json.loads(raw)
        # XFetch: recompute early with a probability that rises near expiry.
        # log(random()) is negative, so the term grows as now -> expiry.
        early = now - entry["delta"] * beta * math.log(random.random())
        if early < entry["expiry"]:
            return entry["value"]         # fresh enough: serve it

    # Either a hard miss or an early-refresh trigger. Exactly one worker rebuilds.
    lock_key = f"lock:{key}"
    token = str(random.random())
    if r.set(lock_key, token, nx=True, ex=LOCK_TTL):
        try:
            return _recompute(key, compute, ttl, stale_grace)
        finally:
            RELEASE(keys=[lock_key], args=[token])

    # Lost the race. If we hold a stale copy, serve it rather than pile on.
    if raw is not None:
        return json.loads(raw)["value"]

    # Cold key, no stale copy: wait briefly for the winner, then read.
    for _ in range(50):
        time.sleep(0.05)
        raw = r.get(key)
        if raw is not None:
            return json.loads(raw)["value"]
    return compute()                       # last resort under a slow rebuild

Refresh before it expires: probabilistic early recomputation

Serving stale is a safety net for the moment of expiry. Better still is to never reach that moment with a cold key. Probabilistic early expiration — the XFetch algorithm from Vattani, Chierichetti and Lowenstein’s 2015 paper on optimal cache stampede prevention — has each reader roll a die on every read and, with a probability that rises as the key nears expiry, volunteer to recompute early.

The test is the one line in the read path above: recompute when now - delta * beta * log(random()) crosses the logical expiry. Because log(random()) is negative and its magnitude grows as the random draw approaches zero, the recompute window opens gradually before expiry rather than all at once. The delta term scales this by how expensive the value is to build, so costly keys are refreshed earlier and cheap ones later. beta tunes the aggressiveness: raise it above 1.0 to refresh sooner, lower it to refresh later. Combined with the lock, exactly one of those volunteers wins and does the work, well before any request ever sees a miss.

Jitter so keys do not die in lockstep

The last mechanism addresses correlated expiry. If you warm a hundred keys in a loop at deploy with an identical 300-second TTL, they all expire in the same second five minutes later, and you get a hundred simultaneous rebuilds — a stampede across keys rather than within one. Adding a small random spread to every TTL breaks the synchronisation. The wrapper does this by multiplying the TTL by random.uniform(0.9, 1.1) on each write, so no two keys share an expiry instant. It costs nothing and removes an entire class of correlated failure.

Jitter also matters for keys that are rebuilt on a schedule. A cron that refreshes a cache at the top of every hour concentrates load into one minute; spreading refresh times across the interval flattens it. The principle is the same in both cases: never let independent things become synchronised, because synchronised load is what breaks systems.

Measure the thing you fixed

None of this is visible until you instrument it. Track cache hit rate, the count of lock acquisitions per key, and the number of stale reads served. A healthy system after the fix shows a near-flat database query rate through key expiry, a small steady trickle of lock acquisitions rather than spikes, and a hit rate that no longer dips at TTL boundaries. If you already report on recovery and latency for governance — the kind of operational evidence behind the DORA Four metrics — these counters belong in the same dashboard, because a stampede is a self-inflicted incident with a measurable mean time to recovery.

The pattern generalises. Any cached value with an expiry and enough read volume — a rendered page, an authorisation decision, a set of signing keys — is a candidate for a stampede, which is why the same locking and refresh discipline shows up in getting JWKS caching and rotation right. The lesson holds wherever a popular thing expires: coordinate the rebuild, serve something in the meantime, and refresh before the cliff — not at it.