One Key Expires and Five Hundred Instances Miss at the Same Millisecond

Concurrency owns the in-process version of this: a thundering herd, solved with singleflight or a mutex around the recompute. Architecture and Backend cover the single-service cache-aside pattern. The distributed case is a different quantity of the same shape, and the quantity is what makes it an outage.

Five hundred service instances, each handling forty concurrent requests for a popular product page. The key expires. Every instance misses, and within each instance forty requests miss simultaneously. That is 20,000 identical database queries arriving inside a few milliseconds for one key whose correct answer is a single row.

Per-instance singleflight collapses the forty into one, taking it to 500. That is the cheapest, most reliable mitigation and it should always be present — but 500 simultaneous queries for one row is still enough to saturate a connection pool, and if the recompute is expensive (an aggregate, a join, a model call) 500 is plainly too many.

Getting from 500 to 1 requires the instances to agree, and the only thing they all already talk to is the cache itself. So the shared cache becomes a coordination service, which means you have acquired a distributed lock and all of its problems — a lock holder that crashes, a lease that expires mid-recompute, waiters that block. That is Distributed Locks: What They Are Actually For and Leases: Authority With an Expiry Date arriving through the back door of a performance optimisation, and it is worth naming as such before adopting it.

1. TTL jitter. Write entries with ttl × (1 ± 0.1). Keys populated together no longer expire together, which dissolves the correlated-expiry class of stampede entirely. It costs one line, needs no coordination, and it is the fix people skip because it feels too small to matter. It is the highest value-per-effort item in this module. Note it does not help a *single* hot key, which expires once no matter how you jitter it — it helps the far more common case of a whole key space expiring in unison after a bulk load or a deploy.

2. Per-instance singleflight. One in-flight recompute per key per process; every other caller awaits the same promise. Local, free, no failure modes worth the name, and it divides the load by your per-instance concurrency. Always do this.

3. Stale-while-revalidate. Serve the expired value and refresh in the background. Readers never block, the origin sees one refresh, and the price is explicitly-served stale data. This is the best answer for most read paths, and its own failure mode deserves attention: if the background refresh keeps failing silently, you serve stale forever. It needs a hard staleness bound past which you refuse to serve, and a metric on refresh failures.

4. Probabilistic early expiry. Each reader independently decides to refresh slightly before the TTL, with a probability that rises as expiry approaches: recompute when now − delta × beta × ln(rand()) ≥ expiry, where delta is the measured recompute duration. Expensive-to-recompute keys are refreshed earlier, cheap ones later, and refreshes spread out across readers without any lock. It is the most elegant option and it is under-used because it looks like folklore — the paper is Vattani, Chierichetti & Lowenstein, "Optimal Probabilistic Cache Stampede Prevention" (VLDB 2015).

5. Distributed lease. One instance takes a short-lived lock in the cache (SET lock:k <token> NX PX 5000) and recomputes; others either wait briefly or serve stale. Gets you to exactly one origin query and introduces a lock holder that can die. The lease TTL becomes a latency cliff: if the holder crashes, everyone waits for the lease to expire. Use it only when the recompute is genuinely too expensive to do 500 times, and always pair it with stale-serving so waiters have something to return.

Expiry is the textbook trigger and it is not the most common one in production. Three others produce identical symptoms and are not fixed by anything above.

A cold start. A deploy replaces every instance, so every local cache is empty at once. The origin sees full traffic until the fleet warms. The fix is not a cache technique at all: stagger the rollout, gate readiness on a warm cache, and pre-warm the top keys before accepting traffic.

An eviction wave. The cache hits its memory limit and evicts a large fraction of keys under LRU pressure, or a cache node restarts and its share of the keyspace vanishes. With consistent hashing, losing one node of ten sends 10% of all keys to the origin simultaneously.

An invalidation storm. A bulk update at the source invalidates a hundred thousand keys at once — a price import, a permission change, a schema migration. Every one of those keys is now a miss, and the "invalidation" that was supposed to protect correctness has manufactured a stampede. This is where You Cannot Enumerate the Caches, So TTL Is the Bound and Invalidation Is the Optimisation and this lesson meet, and it is why bulk invalidations must be rate-limited rather than issued as fast as the source can emit them.

The unifying observation: a stampede is any event that correlates misses across the fleet. Expiry is one such event; deploys, evictions and bulk invalidations are others. The mitigations that survive all four are the ones that limit origin concurrency directly — singleflight, admission control at the origin, and serving stale — rather than the ones that only spread expiry times.