Preventing Cache Stampede: Locking and Probabilistic Refresh

1. What a cache stampede is and why it becomes dangerous

A cache stampede, also called thundering herd, occurs when a heavily requested Redis key expires and, in that same moment, many concurrent requests hit that expired key. Without a protection mechanism, each of these requests handles the cache miss independently: each reloads from the database, and each subsequently writes the same value back into Redis. What a single database query would have satisfied turns into a hundred or a thousand parallel queries within milliseconds.

The danger of a cache stampede lies in its amplifying effect: precisely the most popular, most frequently read records are affected the most, because they receive the highest number of concurrent accesses. A database that is comfortably dimensioned for normal load can be briefly brought to its knees by a single cache stampede, with cascading effects on other requests sharing the same database. In high traffic systems, the cache stampede is therefore one of the most underestimated risks in caching design.

2. How thundering herd forms on TTL expiry

The mechanism behind a cache stampede is easy to trace. A key like product:bestseller:4711 has a TTL of 60 seconds and is read a thousand times during that window. In the second when the TTL expires, the next request arrives and finds GET returning (nil). Without coordination, this request immediately starts reloading from the database. Since some milliseconds typically pass between the expiry and the cache being refilled, every request arriving within that window sees the same empty cache and triggers its own database query.

It becomes especially critical for computationally expensive cache values, such as aggregated statistics or complex joins, where a single database query already takes several hundred milliseconds. In that case the critical window grows accordingly, and the number of requests arriving concurrently within that window grows proportionally with demand. A cache stampede on such a key can overload a database for several seconds, even though the key barely creates noticeable load under normal operation.

# Simulate the expiry of a popular key
redis-cli SET product:bestseller:4711 '{"views":18420}' EX 5
redis-cli TTL product:bestseller:4711
# (integer) 5

# After expiry: many parallel clients see (nil) at the same time
redis-cli GET product:bestseller:4711
# (nil)

# Without protection: each client independently starts a DB reload
# --> N concurrent database queries instead of just one

3. Mutex locking as the first line of defense

The classic solution against cache stampede is a distributed mutex lock that ensures only a single request actually queries the database, while all others either wait briefly or are served the last known value. In Redis, such a lock can be created atomically with SET lock:key value NX PX 5000: NX only sets the value if the key does not already exist, and PX defines an expiry time in milliseconds that prevents a crashed process from blocking the lock permanently.

The flow with a mutex lock: on a cache miss, the application first tries to acquire the lock. If it succeeds, it loads from the database, fills the cache, and releases the lock. If acquisition fails because another request already holds the lock, the application waits briefly and checks the cache again, or it returns a slightly stale value from a fallback key without a TTL. This second variant, often called "stale while revalidate", avoids any waiting time for the user entirely.

# Acquire the lock atomically, only if it does not exist yet
redis-cli SET lock:product:4711 "worker-1" NX PX 5000
# OK

# Second attempt while the lock is active: fails
redis-cli SET lock:product:4711 "worker-2" NX PX 5000
# (nil)

# Release the lock after a successful refresh
redis-cli DEL lock:product:4711

4. Implementing a mutex lock in PHP

In PHP, the mutex lock pattern can be added to an existing cache-aside implementation with just a few lines. It is important to tag the lock with a unique identifier so a process does not accidentally release another process's lock, and to always release the lock inside a finally block so that an exception never leaves a permanent lock behind.

The following implementation shows the complete pattern, including a short wait with a limited number of retries to avoid infinite loops on a permanently stuck lock.

<?php

declare(strict_types=1);

final class StampedeProtectedRepository
{
    public function __construct(
        private readonly \Predis\Client $redis,
        private readonly ProductDatabaseRepository $database,
        private readonly int $ttlSeconds = 60
    ) {
    }

    /**
     * Cache read protected against cache stampede via a distributed mutex lock.
     */
    public function find(int $productId): ?array
    {
        $key = "product:{$productId}";
        $cached = $this->redis->get($key);

        if ($cached !== null) {
            return json_decode($cached, true);
        }

        $lockKey = "lock:{$key}";
        $lockId = bin2hex(random_bytes(8));
        $acquired = $this->redis->set($lockKey, $lockId, 'NX', 'PX', 5000);

        if (!$acquired) {
            // Another process is already refreshing: wait briefly and retry
            for ($i = 0; $i < 20; $i++) {
                usleep(50_000); // 50ms
                $cached = $this->redis->get($key);
                if ($cached !== null) {
                    return json_decode($cached, true);
                }
            }
            // Fallback: still nothing, load directly to avoid an empty response
            return $this->database->find($productId);
        }

        try {
            $product = $this->database->find($productId);
            if ($product !== null) {
                $this->redis->setex($key, $this->ttlSeconds, json_encode($product));
            }
            return $product;
        } finally {
            // Only release the lock if we still own it
            $current = $this->redis->get($lockKey);
            if ($current === $lockId) {
                $this->redis->del([$lockKey]);
            }
        }
    }
}

5. Probabilistic early expiration in detail

Mutex locking solves the problem reactively, after the key has already expired. A more proactive strategy is probabilistic early expiration, where individual requests refresh the cache before the TTL actually expires, with a probability that increases as the expiry moment approaches. The best known technique for this is the XFetch algorithm, published by Vattani, Chierichetti and Lowenstein at Google.

The basic idea: every cache access does not just read the value, it also checks how long the last refresh took and how close the remaining TTL is to expiry. The formula (now - delta * beta * log(random())) >= expiry turns this into a probabilistic decision on whether this particular access should proactively refresh the cache. The beta parameter controls the aggressiveness: larger values trigger earlier, more frequent refreshes. The result is a smooth distribution of refresh load over time, instead of a concentrated spike exactly at TTL expiry.

6. The XFetch algorithm in PHP

Implementing XFetch requires two additional stored values alongside the actual cache value: the moment the value was last recomputed, and how long that recomputation took. Both values can be stored together with the actual value in a JSON structure and require no separate Redis operation.

In practice, XFetch is frequently used for cache values whose recomputation is expensive and whose TTL is deliberately chosen to be generous, such as aggregated reports or computationally heavy recommendation lists. The probabilistic early refresh spreads the expensive recomputation across many individual accesses instead of concentrating it exactly at expiry.

<?php

declare(strict_types=1);

final class XFetchCache
{
    public function __construct(
        private readonly \Predis\Client $redis,
        private readonly float $beta = 1.0
    ) {
    }

    /**
     * Probabilistic early expiration (XFetch) to smooth out refresh load.
     */
    public function get(string $key, int $ttl, callable $recompute): mixed
    {
        $raw = $this->redis->get($key);
        $now = microtime(true);

        if ($raw !== null) {
            $entry = json_decode($raw, true);
            $delta = $entry['delta'];
            $expiry = $entry['expiry'];

            // XFetch formula: probabilistically trigger early refresh
            $rand = mt_rand() / mt_getrandmax();
            $shouldRefresh = ($now - $delta * $this->beta * log($rand)) >= $expiry;

            if (!$shouldRefresh) {
                return $entry['value'];
            }
        }

        $start = microtime(true);
        $value = $recompute();
        $delta = microtime(true) - $start;

        $this->redis->setex($key, $ttl * 2, json_encode([
            'value' => $value,
            'delta' => $delta,
            'expiry' => $now + $ttl,
        ]));

        return $value;
    }
}

7. Combining both strategies

Mutex locking and probabilistic early expiration are not mutually exclusive, they complement each other in practice. XFetch drastically reduces the probability of a real cache miss by spreading most refreshes out before expiry. For the remaining cases where several requests still hit an expired key at the same time, for example after a cache flush or a deployment, the mutex lock acts as an additional safety net.

This combination is especially valuable in systems with strongly fluctuating load, such as flash sale events in e-commerce, where a single product key can shift from normal to extreme demand within a few minutes. A mutex lock alone would work in this situation, but every TTL expiry would still create brief waits for the first requests, while XFetch mostly avoids these waits entirely through proactive refresh.

8. Recognizing cache stampede in monitoring

A cache stampede shows up in monitoring through a characteristic pattern: short, sharp spikes in database query rate that line up exactly with the TTL expiry of popular cache keys. Redis's own SLOWLOG is less helpful here, because the individual Redis operations remain fast, the problem occurs at the database level. A query log or APM tool that detects concurrent, identical database queries within the same short window is more useful.

A simple indicator can also be tracked directly in Redis: a counter incremented on every cache miss, combined with a timestamp of the last refresh per key. If this counter rises sharply for a single key within a few milliseconds, that is a clear signal of an active cache stampede and an indication that this key would benefit from mutex locking or XFetch.

# Observe cache miss rate over time
redis-cli INFO stats | grep keyspace_misses

# Number of active locks as an indicator of parallel refreshes
redis-cli KEYS "lock:product:*" | wc -l

# Identify high frequency commands on the same key
redis-cli MONITOR | grep "product:bestseller"

9. Mutex lock and probabilistic refresh compared

Both strategies have different strengths and can be classified along the following criteria to make the right choice for the given use case.

In practice, most systems should start with mutex locking, since it is simpler to implement and provides immediate protection. XFetch is worth adding for individual, especially critical keys with expensive recomputation, where even brief waits during a lock would have a noticeable user impact.

10. Summary

A cache stampede occurs when many concurrent requests hit an expired Redis key and each of them independently burdens the database. Mutex locking with SET NX PX solves the problem reactively by letting only one request query the database while others wait briefly or fall back to a cached value. Probabilistic early expiration following the XFetch algorithm is more proactive and spreads refreshes out before the actual expiry, making genuine cache misses rarer.

Both strategies can be combined: XFetch drastically reduces the frequency of cache misses, mutex locking catches the remaining cases as a safety net. Anyone who identifies popular, expensive cache keys and secures them deliberately prevents a single TTL expiry from briefly overloading an otherwise well dimensioned database.

11. FAQ: Preventing Cache Stampede