Cache Stampede Prevention with Probabilistic Early Expiration

This page shows how to keep a single hot key's expiry from dropping a synchronized wall of concurrent misses onto your database, and how to recompute that key exactly once instead of thousands of times.

A cache stampede — also called a thundering herd or dog-piling — happens the instant a popular key expires: every in-flight request misses simultaneously, and every one of them independently decides to recompute the same expensive value against the source of truth. A key that absorbed fifty thousand reads per second while cached now sends fifty thousand identical queries at the database in the same millisecond, and the recompute latency that was hidden behind the cache is suddenly on the critical path for all of them. The database saturates, recompute times climb, the extended recompute widens the miss window, and more requests pile in — a self-amplifying collapse. This is a coordination problem layered on top of the advanced invalidation patterns that govern the rest of the cache: the data is not stale and no invalidation was dropped, yet a routine expiry still takes down the tier. The two mechanisms below solve it by controlling who recomputes and when, rather than whether the data is fresh.

# Architectural Trade-offs

Both strategies start from the same premise: only one request should recompute a hot key per expiry cycle, and every other request should either serve a slightly stale value or wait a few milliseconds for the winner to repopulate. They differ in how they elect that single recomputer. Probabilistic early recomputation elects it before expiry using randomness and no coordination; the mutex approach elects it at expiry using a lock and explicit coordination. The columns below are the axes that decide which cost your workload can absorb.

The rightmost two columns are where the two mechanisms genuinely diverge. XFetch never blocks a reader and never serves data older than the live cached value, but it recomputes probabilistically, so a mis-tuned parameter can recompute too often or too late. The mutex is deterministic — precisely one recompute per expiry — but it introduces a lock whose expiry, ownership, and release must be handled with the same rigor as any distributed lock, and a stalled holder can serialize or block the very requests it was meant to protect.

# Approach A — Probabilistic Early Recomputation (XFetch)

Probabilistic early recomputation, popularized as XFetch, removes the synchronized cliff entirely by refreshing a key slightly before it expires — and letting only a statistically small number of readers volunteer to do that refresh. Each cached entry carries two extra pieces of metadata alongside its value: delta, the wall-clock time the last recomputation took, and expiry, the absolute time at which the value is considered due for refresh. On every read the client evaluates a cheap inequality:

now - delta * beta * ln(rand()) >= expiry

rand() is uniform on the open interval (0, 1), so ln(rand()) is always negative and -delta * beta * ln(rand()) is always a positive lead time. That lead time is the key insight: it grows with delta (expensive keys volunteer earlier, because their recompute is what you most want to hide) and with beta, a tuning knob for eagerness that defaults to 1.0. Far from expiry the gap expiry - now is large and the random term rarely exceeds it, so almost every reader serves the cached value untouched. As now creeps toward expiry the gap shrinks, the probability of the inequality holding rises smoothly toward one, and a single early reader trips the trigger, recomputes, and writes a fresh entry — resetting the clock before the herd ever forms. Because the decision is per-request and independent, no locks, no coordination, and no extra round trips are needed.

import json
import math
import random
import time
from typing import Awaitable, Callable

import redis.asyncio as redis


async def xfetch_get(
    client: redis.Redis,
    key: str,
    recompute: Callable[[], Awaitable[str]],
    ttl: int,
    beta: float = 1.0,
) -> str:
    """Read a hot key, volunteering an early recompute with rising probability."""
    packed = await client.get(key)
    if packed is None:
        # Genuine miss (cold key or physically expired) — recompute now.
        return await _recompute_and_store(client, key, recompute, ttl)

    entry = json.loads(packed)
    now = time.time()
    # XFetch trigger: -delta*beta*ln(rand()) is a random positive lead time
    # that scales with recompute cost (delta) and eagerness (beta). As now
    # approaches expiry the odds of crossing it climb toward one, so a single
    # reader refreshes early instead of the whole herd missing at once.
    if now - entry["delta"] * beta * math.log(random.random()) >= entry["expiry"]:
        return await _recompute_and_store(client, key, recompute, ttl)

    return entry["value"]  # still comfortably fresh — serve from cache


async def _recompute_and_store(
    client: redis.Redis,
    key: str,
    recompute: Callable[[], Awaitable[str]],
    ttl: int,
) -> str:
    start = time.perf_counter()
    value = await recompute()                    # the expensive call we protect
    delta = time.perf_counter() - start          # measured cost feeds next XFetch
    entry = {"value": value, "delta": delta, "expiry": time.time() + ttl}
    # Physical TTL runs longer than the logical expiry so that if a volunteer
    # recompute is slow, late readers still find the old entry to serve rather
    # than falling through to a genuine cold miss.
    await client.set(key, json.dumps(entry), ex=int(ttl * 1.5))
    return value

The physical TTL deliberately outlives the logical expiry: the expiry field governs when readers start volunteering, while the longer Redis TTL is the backstop that keeps a value available to serve even while a volunteer is mid-recompute. This pairs naturally with the cache-aside pattern, where the application already owns the read-populate loop — XFetch is a drop-in refinement of the populate step, not a new architecture. XFetch shines for read-heavy keys with a steady request stream, because the algorithm relies on some reader arriving during the early window to trigger the refresh; the busier the key, the more reliably the herd is suppressed. Its one soft edge is that recompute cost is estimated from the last measured delta, so a workload whose recompute time swings wildly should smooth delta (an exponential moving average) rather than trusting a single sample.

# Approach B — Single-Flight via a Mutex Lock

The mutex approach makes the election explicit: when the key is genuinely missing, the first concurrent request to arrive races to acquire a short-lived lock, and only the winner recomputes. Everyone else either serves a briefly stale copy or waits a few milliseconds and re-reads the freshly populated key. The lock is a plain SET with NX (set only if absent) and PX (a millisecond expiry) — atomic acquisition in a single round trip, with the expiry acting as a dead-man's switch so a crashed holder cannot block the key forever. This is the same primitive that underpins full distributed locks for cache coordination; here it is scoped narrowly to guarding one recompute.

import asyncio
import uuid
from typing import Awaitable, Callable, Optional

import redis.asyncio as redis

# Compare-and-delete: only release the lock if we still own the exact token,
# so a lock that already expired and was re-acquired is never wrongly freed.
_RELEASE_LUA = """
if redis.call('get', KEYS[1]) == ARGV[1] then
    return redis.call('del', KEYS[1])
end
return 0
"""


async def single_flight_get(
    client: redis.Redis,
    key: str,
    recompute: Callable[[], Awaitable[str]],
    ttl: int,
    lock_ttl_ms: int = 3000,
    max_wait_s: float = 0.5,
) -> str:
    """Recompute a missing key exactly once; other callers wait or serve stale."""
    value = await client.get(key)
    if value is not None:
        return value  # fast path: the hot key is still present

    lock_key = f"lock:{{{key}}}"  # {..} hash tag co-locates lock with its key
    token = uuid.uuid4().hex
    # SET NX PX: exactly one concurrent miss wins the lock; PX bounds how long
    # a crashed or stalled holder can keep everyone else waiting.
    won = await client.set(lock_key, token, nx=True, px=lock_ttl_ms)

    if won:
        try:
            fresh = await recompute()                 # single flight to the DB
            await client.set(key, fresh, ex=ttl)
            return fresh
        finally:
            # Never blind-DEL: another worker may already hold the lock if ours
            # expired mid-recompute. The Lua check-and-delete keeps it fenced.
            await client.eval(_RELEASE_LUA, 1, lock_key, token)

    # Lost the race: poll briefly for the winner's fresh value before giving up.
    deadline = asyncio.get_event_loop().time() + max_wait_s
    while asyncio.get_event_loop().time() < deadline:
        await asyncio.sleep(0.02)
        value = await client.get(key)
        if value is not None:
            return value
    # Winner is unusually slow — recompute ourselves rather than error out.
    return await recompute()

Two production rules keep the mutex honest. First, release with a compare-and-delete rather than a blind DEL: if the holder's recompute overruns lock_ttl_ms, the lock expires and another worker legitimately acquires it, so a naive delete would free someone else's lock. The Lua script checks the token before deleting, closing that window. Second, size lock_ttl_ms to comfortably exceed the p99 recompute time; too short and the lock expires mid-recompute, re-admitting the herd, while too long and a genuinely crashed holder blocks the key for its full duration. The losers' branch is a deliberate design choice — polling for the winner's value keeps latency low for a fast recompute, and the final fallback recompute guarantees the request never hangs indefinitely if the winner stalls past max_wait_s. A stronger variant serves the last-known value to losers from a second, longer-lived key so no reader ever blocks, trading a bounded staleness window for zero added latency.

# When to Choose Which

Both mechanisms suppress the herd; the choice turns on three concrete production signals rather than preference. The diagram below shows why the two elect their single recomputer at different points on the key's lifetime; the numbered criteria refine the decision.

1. Recompute cost and variance. The more expensive the recompute, the more you want it hidden behind a live value rather than paid on the request path — favoring XFetch, whose delta-scaled lead time refreshes costly keys earliest and never makes a reader wait. When recompute time is highly variable, the deterministic mutex is easier to reason about because exactly one flight runs regardless of cost, whereas XFetch's delta estimate lags a sudden change.
2. Staleness tolerance. XFetch never serves a value older than the current cached entry — it refreshes proactively while the value is still valid, so there is no stale window at all. The mutex, in its non-blocking form, hands losers a briefly stale copy while the winner recomputes; if even a few hundred milliseconds of staleness is a correctness bug, either block the losers or prefer XFetch outright.
3. Traffic shape and spikiness. XFetch depends on a reader arriving during the early window to trigger the refresh, so it is ideal for keys under continuous high read pressure and weaker for bursty keys that go idle between spikes. The mutex has no such dependency — it fires on the first miss whenever that miss happens — making it the safer choice for spiky or cold-start-prone keys where no steady stream guarantees a volunteer. The full worked walkthrough, with beta tuning and a hybrid that layers both, lives in Implementing Probabilistic Early Recomputation in Python.

For most steadily-read hot keys, XFetch is the lighter and lower-latency default; reach for the mutex when the key is spiky, when zero-tolerance for a stale loser is not required, or when you already run a distributed lock for other coordination and want one consistent mechanism.

# Failure Modes and Diagnostics

Three failure modes account for most stampede-prevention incidents. Each has a fast diagnosis before you commit to a fix.

Stampede on a cold, never-populated key. Probabilistic early recomputation only helps keys that are already cached — its trigger reads delta and expiry from an existing entry. A brand-new key with no entry, or one flushed by a deploy or eviction, gives every concurrent request a genuine miss at once, and XFetch offers no protection because there is nothing to volunteer against. Diagnose by correlating a sharp keyspace_misses spike with a matching database load surge right after a cold start or flush:

redis-cli INFO stats | grep -E "keyspace_misses|keyspace_hits|expired_keys"

A keyspace_misses jump with no preceding expired_keys climb points at a cold key rather than a normal expiry. The fix is to gate the recompute of never-populated keys behind the single-flight mutex (Approach B), or to pre-warm known hot keys during deployment so the first production read always finds an entry to refresh.

Lock contention serializing every request. With the mutex, an oversized lock_ttl_ms or a recompute that hangs turns the lock from a herd suppressor into a bottleneck: the holder stalls, no one else may recompute, and every reader queues in the losers' poll loop until max_wait_s elapses. Throughput collapses to one recompute at a time even though the value is simply late. Diagnose by watching for blocked or waiting clients and a growing command backlog while a single slow recompute holds the lock:

redis-cli INFO clients | grep -E "connected_clients|blocked_clients"
redis-cli TTL "lock:{product:42}"   # a lock that never counts down = a stuck holder

A lock: key whose TTL sits near its full PX value across successive checks means the holder is not releasing. Fix by sizing lock_ttl_ms to the p99 recompute plus margin, capping recompute with its own timeout, and serving losers a last-known value instead of blocking them.

Recompute storms from a mis-tuned beta. XFetch's eagerness knob is a double-edged tool. Set beta too high (or feed it an inflated delta) and the lead time balloons, so many readers volunteer far ahead of expiry — the key is recomputed constantly, wasting database capacity even though nothing has changed. Set it too low and the window collapses onto the expiry instant, reviving the very herd XFetch was meant to prevent. Diagnose by counting recomputes per expiry interval against reads; a healthy XFetch key recomputes roughly once per expiry window, so a recompute-to-miss ratio far above one signals over-eager refresh:

# Watch recompute frequency: SET rate on the hot key should track ~1 per TTL,
# not spike with every read.
redis-cli --csv PSUBSCRIBE '__keyevent@0__:set' &
redis-cli INFO stats | grep -E "keyspace_misses|instantaneous_ops_per_sec"

The fix is to start beta at 1.0, smooth delta with a moving average so one slow sample cannot inflate the lead time, and cap the effective lead time at a fraction of the nominal TTL.

# Verification

Confirm the chosen mechanism actually collapses the herd to a single recompute before trusting it under load. The definitive test is to hammer one hot key across its expiry boundary and count how many recomputes occur.

Instrument the recompute path with a counter and drive concurrent reads through the key's expiry with a small load test — a correct implementation records exactly one recompute per expiry cycle no matter how many readers arrive:

import asyncio

recompute_calls = 0

async def counted_recompute() -> str:
    global recompute_calls
    recompute_calls += 1
    await asyncio.sleep(0.2)          # simulate an expensive source-of-truth read
    return '{"price": 1299}'

async def storm(client, key, ttl):
    # 500 concurrent readers cross the expiry window at once.
    await asyncio.gather(*(
        xfetch_get(client, key, counted_recompute, ttl) for _ in range(500)
    ))
    # A herd-safe implementation leaves recompute_calls at 1, not 500.
    assert recompute_calls == 1, f"stampede: {recompute_calls} recomputes"

Watch the live keyspace counters during that storm and confirm the miss spike does not translate into a proportional recompute spike at the database:

redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses"
# Run the load test, then re-read: keyspace_misses should rise by ~1 per
# expiry window, not by the full concurrent request count.

For the mutex, verify the lock is acquired exactly once and released cleanly, leaving no orphaned lock: key after the recompute completes:

redis-cli EXISTS "lock:{product:42}"   # expect 0 once the winner has released
redis-cli SLOWLOG GET 10               # confirm no recompute stalled under the lock

Track recompute count, hit ratio, and lock-wait latency as first-class metrics so a regression — a herd re-forming after a config change, or a beta drift into over-eager refresh — surfaces on a dashboard before it surfaces as a database incident. Pair these checks with the jittered TTL strategy that spreads expiries across many keys: jitter prevents different keys from synchronizing, while the mechanisms here prevent a single key's expiry from stampeding — the two are complementary defenses, not alternatives.

---

Up: Advanced Cache Invalidation Patterns & Synchronization

# Related

• Implementing Probabilistic Early Recomputation in Python — the step-by-step XFetch build with beta tuning and load-test harness.
• Distributed Locks for Cache Coordination — the lock lifecycle, fencing, and Redlock behind the single-flight mutex.
• Write-Through vs Write-Behind Caching — write-path strategies that change how often a hot key must be recomputed at all.