What is a cache stampede (thundering herd), and how do you prevent it when a hot key expires?

#The Scenario

A single Redis key — product:42, homepage:featured, user:session-count — is read thousands of times per second and written once every 60 seconds. That asymmetry is exactly why you cached it: one cheap read replaces one expensive database query, over and over. Then the TTL hits zero. In the same millisecond, every one of those thousands of readers gets a cache miss, and every one of them independently decides to do the "obvious" thing: go recompute the value from the database. What used to be a 1000:1 read-to-write ratio just turned into 1000 identical, simultaneous writes to your source of truth — often enough to take the database down, which then makes the next attempt to repopulate the cache fail too, and the outage outlives the traffic spike that caused it.

This is a cache stampede, also called a thundering herd. It isn't caused by a bug in your caching logic in the narrow sense — the code usually does exactly what it was told to do (if not cached: compute and store). The bug is architectural: nothing coordinates the many callers that discover the miss at the same instant, so they all pay the recomputation cost independently instead of once.

#How It Unfolds

The sequence below shows the failure mode with three clients for clarity — in production it's whatever your peak concurrent request count is for that key, which for a genuinely hot key can be in the thousands.

Notice the last three lines: even the recovery is wasteful. Three (or three thousand) processes each pay the full query cost, and then each pay a write cost, to arrive at the exact same value. The cache did its job perfectly for 59.999 seconds and then, for one moment, actively made things worse than having no cache at all — with no cache, load would have been spread evenly instead of arriving as one synchronized spike.

#Mitigation 1: Single-Flight Lock (Mutex)

The fix that matches the diagram above one-for-one: make only one caller actually recompute the value, and have everyone else either wait for it or serve something stale in the meantime. Redis gives you an atomic primitive for exactly this — SET key value NX PX <ms> sets the key only if it doesn't already exist, and auto-expires it after ms milliseconds so a crashed worker can never hold the lock forever.

import time
import json
import redis

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

LOCK_TTL_MS = 5000        # safety net: max time a rebuild is allowed to hold the lock
CACHE_TTL_SECONDS = 60    # normal TTL for the cached value
RETRY_DELAY_MS = 50

def compute_expensive_value(key: str) -> str:
    # Stand-in for a slow DB query, aggregation, or external API call.
    time.sleep(0.3)
    return json.dumps({"key": key, "computed_at": time.time()})

def get_or_recompute(key: str, max_wait_ms: int = 2000) -> str:
    cached = r.get(key)
    if cached is not None:
        return cached

    lock_key = f"lock:{key}"
    waited = 0

    while waited < max_wait_ms:
        # NX: only the first caller wins the lock. PX: it self-expires even
        # if this process dies mid-rebuild, so we never deadlock forever.
        acquired = r.set(lock_key, "1", nx=True, px=LOCK_TTL_MS)

        if acquired:
            try:
                value = compute_expensive_value(key)
                r.set(key, value, ex=CACHE_TTL_SECONDS)
                return value
            finally:
                r.delete(lock_key)

        # Someone else is already rebuilding this key — back off and check
        # whether they finished, instead of also hammering the database.
        time.sleep(RETRY_DELAY_MS / 1000)
        waited += RETRY_DELAY_MS
        cached = r.get(key)
        if cached is not None:
            return cached

    # Nobody finished within our wait budget. Recompute ourselves rather
    # than blocking the caller indefinitely — a degraded fallback, not a hang.
    return compute_expensive_value(key)

The finally: r.delete(lock_key) matters as much as the SET ... NX — without it, a successful rebuild would hold the lock until LOCK_TTL_MS expires anyway, needlessly serializing the next legitimate rebuild. The retry loop is what turns "1000 requests hit the database" into "1 request hits the database, 999 requests poll Redis a few times and then get the fresh value" — polling Redis is orders of magnitude cheaper than re-running the query.

#Mitigation 2: Probabilistic Early Expiration

The lock approach is reactive? — it only kicks in once the miss has already happened. Probabilistic early expiration (the algorithm is sometimes called XFetch) is proactive: instead of waiting for a hard expiry, each reader near the end of a key's life recomputes it early, with a probability that rises the closer you get to the real expiry. Because only a small fraction of readers trigger an early recompute at any given moment, the herd never forms in the first place — the value gets refreshed by one lucky (or unlucky) reader well before the TTL would have caused a synchronized miss.

The formula uses how long the last computation took (delta) as a proxy for how expensive a refresh currently is, and a tunable beta to control how aggressively you refresh early:

import math
import random
import time

def get_with_early_recompute(key: str, ttl_seconds: int, beta: float = 1.0):
    stored = r.hgetall(f"xf:{key}")  # {"value", "expires_at", "delta"}
    now = time.time()

    if stored:
        expires_at = float(stored["expires_at"])
        delta = float(stored["delta"])  # how long the last computation took
        # Recompute early with rising probability as "now" approaches
        # expires_at, instead of waiting for a hard miss.
        if now - delta * beta * math.log(random.random()) < expires_at:
            return stored["value"]

    start = time.time()
    value = compute_expensive_value(key)
    delta = time.time() - start
    r.hset(f"xf:{key}", mapping={
        "value": value,
        "expires_at": now + ttl_seconds,
        "delta": delta,
    })
    r.expire(f"xf:{key}", ttl_seconds * 2)
    return value

Because random.random() returns a value in (0, 1), -log(random.random()) is an exponentially distributed positive number — small most of the time, occasionally large. Multiplying it by delta * beta means: cheap-to-compute keys barely ever recompute early, expensive keys start refreshing well before expiry, and the recompute is spread out in time across readers rather than synchronized on the TTL boundary.

#Mitigation 3: Stale-While-Revalidate

A third option sidesteps the problem instead of coordinating around it: keep serving the stale value while exactly one background task refreshes it, using two TTLs instead of one. A short "soft" TTL marks the value as due for a refresh; a longer "hard" TTL is the actual safety net past which the value is deleted outright. Between the two, every reader gets an instant cache hit (the stale value), and a single background job — not the request path — does the recompute. This is the same idea browsers and CDNs use via the stale-while-revalidate Cache-Control directive, just applied to your own cache layer instead of HTTP.

#Choosing a Strategy

🧠 Check your understanding
0/3 · 0/3 answered
1. What makes a cache stampede different from ordinary cache-miss traffic?
It is caused by choosing LFU instead of LRU evictionMany concurrent requests recompute the same expired key at once, multiplying load on the origin instead of the cache absorbing itThe cache server itself runs out of memoryIt only happens when a cache has no eviction policy configured
2. In the single-flight lock pattern, what does setting the lock with a millisecond TTL (PX) protect against?
Replay attacks on the cache keyA crashed or stalled worker holding the lock forever and starving every other requestThe lock key accidentally colliding with the cached value's keyClock skew between the Redis server and the application server
3. Probabilistic early expiration (XFetch) recomputes a cached value...
Only strictly after the TTL has fully expired, same as normal cachingOn a fixed schedule regardless of how expensive the last computation wasBefore the real expiry, with a probability that rises as the deadline approaches, using the last computation's duration as a signalOnly as a fallback when a distributed lock cannot be acquired