What is Probabilistic Early Expiration, and how does it prevent a cache stampede?

Short answer

It probabilistically recalculates and refreshes cache entries in the background, with a chance that increases as expiration approaches, so a key does not suddenly disappear for every request.

Explanation

When a popular cache entry such as the home page expires, hundreds of requests may miss the cache and hit the database together (Cache Stampede / Dog-piling). Instead of a strict lock, this algorithm (known as XFetch) generates a random value whenever a request reads the key in its final minutes. If the probability threshold is met, that request refreshes the cache while everyone else gets a fast cached copy without interruption.

Code example

function rememberEarly(string $key, int $ttl, Closure $compute, float $beta = 1.0)
{
    $entry = Cache::get($key);   // ['value' => ..., 'delta' => seconds the computation took, 'expires' => timestamp]
    $now = microtime(true);

    // The closer to expiry (and the slower the computation), the likelier an early refresh
    if ($entry === null || ($now - $entry['delta'] * $beta * log(mt_rand() / mt_getrandmax())) >= $entry['expires']) {
        $start = microtime(true);
        $value = $compute();
        $entry = ['value' => $value, 'delta' => microtime(true) - $start, 'expires' => $now + $ttl];
        Cache::put($key, $entry, $ttl * 2);
    }

    return $entry['value'];
}

Common mistakes

• Relying only on a fixed TTL on large sites without handling the moment a popular key suddenly expires.

Follow-up questions

• How does Cache::remember work, and how do Atomic Locks protect a server?

Sources

• Laravel docs — Cache Atomic Locks and Stampede