A read-through cache that stampedes exactly once

The homepage had a latency spike at the top of every hour: p99 went from 180 milliseconds to four seconds for about twelve seconds, then recovered. It had been happening for months and had been attributed to a scheduled job, to a cron, and at one point to the hosting provider.

The symptom

$ ./bin/p99 --route=/ --step=60
08:58  0.184
08:59  0.181
09:00  4.102        ←
09:01  0.902
09:02  0.188

$ grep 'homepage.feed.recomputed' app.log | 
    awk '{print substr($1,12,5)}' | uniq -c
    412 09:00
    398 10:00
    401 11:00

# 412 requests recomputing the same thing, at the same
# moment, once an hour.

Four hundred and twelve recomputations of an entry that needs computing once is the whole problem. The recomputation takes about three seconds — eleven queries and a template render — and four hundred of them at once saturates the database connection pool.

Why it happens

A read-through cache with a one-hour TTL expires an entry at a specific instant, and every request arriving after that instant misses. The requests were synchronised because the cache had been warmed by a deploy, so every entry shared an expiry.

The naive read-through — check, miss, compute, store — has no coordination between concurrent misses, which is correct for a single request and catastrophic for four hundred.

The fix

A lock, and the requests that then wait

$value = $this->store->get($key);

if ($value !== null) {
    return $value;
}

$lock = $this->store->lock("recompute:{$key}", 10);

if ($lock->get()) {
    try {
        $value = $compute();
        $this->store->put($key, $value, $ttl);

        return $value;
    } finally {
        $lock->release();
    }
}

// 411 requests arrive here. and then what?
return $this->waitFor($key, 3) ?? $compute();

The lock removes the stampede on the database and replaces it with four hundred and eleven requests holding connections while they wait, which is a different resource exhausted for the same reason. The fallback to computing anyway on timeout is the honest ending and reintroduces the original problem under load.

Serving stale while one request refreshes

// two TTLs per entry: the logical one, and a grace window
$this->store->put($key,
    ['value' => $value, 'fresh_until' => time() + $ttl],
    $ttl + $grace);

$entry = $this->store->get($key);

if ($entry === null) {
    return $this->computeUnderLock($key, $ttl, $compute);
}

if ($entry['fresh_until'] > time()) {
    return $entry['value'];
}

// stale but present: one request refreshes, everybody else
// gets the stale value immediately
if ($this->store->lock("refresh:{$key}", 30)->get()) {
    RefreshCacheEntry::dispatch($key);
}

return $entry['value'];

Nobody waits and nobody stampedes, at the cost of serving a value that is up to the grace window old. That is the right trade for a homepage feed and is wrong for a stock level, which is the decision the grace window encodes — and it has to be set per cache rather than globally.

Dispatching a job rather than refreshing inline is what keeps the request fast, and it means the refresh happens on a worker with its own timeout and retry. A cold cache still needs the lock path, because there is no stale value to serve.

Probabilistic early expiration, which avoids the lock

// XFetch: recompute early, with a probability that rises
// as expiry approaches and scales with the compute cost
$now      = microtime(true);
$delta    = $entry['compute_seconds'];
$expiry   = $entry['expires_at'];
$beta     = 1.0;

if ($now - $delta * $beta * log(mt_rand() / mt_getrandmax()) >= $expiry) {
    return $this->recomputeAndStore($key, $compute);
}

return $entry['value'];

One request recomputes slightly early while everybody else is served the still-valid entry, which avoids both the stampede and the queue. The compute cost has to be stored alongside the value because the probability scales with it — an expensive entry starts refreshing earlier, which is exactly right and is what makes this better than a fixed early refresh.

The beta parameter tunes how aggressively it refreshes early: above one it refreshes sooner and wastes more computation, below one it refreshes later and occasionally still stampedes. One is the documented default and there was no reason to change it here.

Desynchronising the TTLs

// every entry warmed by a deploy expires at the same
// instant, which is what made this a spike rather than
// a trickle
$ttl = 3600;

// jitter, so the expiries spread across a window
$ttl = 3600 + random_int(-300, 300);

// which alone would have turned a 12-second spike into a
// 10-minute elevation of a few percent — a much better
// failure, and not a fix.

Jitter on the TTL is one line and is worth adding regardless of which coordination strategy is used, because it removes the synchronisation that turns a manageable miss rate into a spike. It is a mitigation rather than a solution: four hundred requests spread over ten minutes still recompute four hundred times.

What was chosen, and why

  homepage feed    stale-while-revalidate, 60s grace —
                   nobody waits, and it is a feed
  product price    probabilistic, no stale window —
                   correctness matters, and the compute
                   is 40ms rather than 3s
  category counts  jitter only — cheap to compute, and a
                   stampede of 400 costs nothing

three caches, three strategies, and the reasoning recorded
next to each one.

One strategy applied everywhere is the mistake, because the cost of a stampede and the cost of staleness are both per-cache. Recording the reasoning next to each cache definition is what stops somebody consolidating them into one helper six months later.

Verifying it worked

$ grep -c 'homepage.feed.recomputed' app.log   # per hour
1

# the p99 across the hour boundary: 0.184, 0.191, 0.186

# and the load test that proves it, rather than waiting:
$ ./bin/stampede-test --key=homepage.feed --concurrency=400
  recomputations: 1
  max latency: 3.104s (the one that computed)
  p99 latency:  0.088s (the 399 that waited on nothing)

A load test that asserts on the recomputation count rather than on latency is the check worth automating, because it is deterministic and it is the property that matters. Waiting an hour to see whether the spike returns is not a test.

What this costs

A cache that can serve wrong data deliberately, for a window somebody chose. That is a correctness decision made in a caching layer, and the person who set the grace window to sixty seconds is not the person who will be asked why a price was a minute out of date — which is why the window belongs in a comment with a reason rather than in a constant.

The two-TTL scheme also means the cache no longer works with a plain get, so anything reading the key directly gets an array rather than a value. That is a compatibility break inside the application and it found three places on the first deploy, all of them in code written before the helper existed.