jonnify·redis /redis-patterns/caching/cache-stampede-prevention

R1.05 · Caching — module hub

Cache stampede prevention.

Prevent multiple clients from simultaneously regenerating an expired cache key using locking, probabilistic early refresh, or request coalescing.

Grounding: echo/apps/echo_cache · table.ex (the single-flight flights map, the jittered expires_at) · content/bcs4.1.md — every figure verbatim from a committed record.

The flood at expiry. Set the read rate and the regeneration time; the readout counts the concurrent source reads an unprotected hot key takes at the moment it expires.
10000
200
expiry regen window ends 1 read · the target 2000 concurrent source reads, no protection
readout · Set the rate and the regen window to count the flood at expiry.
§1

The problem

source · the thundering herd

Consider a cache key accessed ten thousand times a second. While it is present every read is a hit and the source is untouched. The instant it expires, the picture inverts:

  1. Thousands of requests arrive within milliseconds.
  2. All take a cache miss.
  3. All query the source simultaneously.
  4. The source becomes overloaded.
  5. Response times spike across the entire system.

This is particularly dangerous for keys with expensive regeneration costs — complex queries, aggregations, external API calls. The danger scales with two factors: how hot the key is, and how expensive its regeneration is. Plain cache-aside has no defence here — every miss is independent, so N concurrent misses become N source reads. The cost of a miss is what makes the herd dangerous: in the measured EchoCache record an L1 hit costs 762 ns, while the L2 GET it replaces costs 31 us — the L1 hit is 40 times cheaper, and a herd pays that round trip N times at once.

With no protection, every miss is its own source read, so a hot key turns one expiry into a flood the size of the request rate over the regeneration window.

§2

Solution 1 — probabilistic early expiration

source · X-Fetch

This technique decouples logical expiration from physical expiration. The idea is to give any request a small probability of refreshing the cache before it actually expires.

How it works. Set the physical TTL longer than needed — one hour, say. As requests arrive, each one calculates whether it should proactively refresh based on how close the key is to expiration and a random factor. When the key is fresh the probability of refresh is near zero; as expiration approaches the probability increases, until one request triggers a refresh while all others continue serving the slightly stale value.

The algorithm. The decision to refresh is based on:

current_time - (expiry_time - delta * beta * log(random()))

Where delta is the time needed to regenerate the value, beta is a tuning parameter (typically 1.0), and random() produces a value between 0 and 1. The formula ensures that as the gap to expiration shrinks, the probability of any single request triggering a refresh increases. Instead of thousands of simultaneous source reads at expiration, a single request refreshes the cache moments before expiration while others continue serving cached data. The traffic spike is smoothed away.

X-Fetch beats the deadline: one read rebuilds early, the rest serve the fresh value, no lock and no waiting — the early-refresh dive computes the formula, then grounds the applied part in EchoCache’s jitter.

§3

Solution 2 — mutex locking

source · SET NX PX

A deterministic approach where only one process is allowed to regenerate the cache. When a cache miss occurs:

  1. Attempt to acquire a lock using SET lock:mykey <token> NX PX 5000.
  2. If the lock is acquired, query the source and update the cache.
  3. Other requests either wait and poll, or return a stale or default value.
  4. Release the lock after the cache is populated.

Redis commands. The acquire is one command:

SET lock:popular_key abc123 NX PX 5000

The NX ensures only one client acquires the lock. The PX 5000 sets a five-second timeout to prevent deadlocks if the lock holder crashes. Clients that fail to acquire the lock have options: poll (sleep briefly and check the cache again), return stale data (serve a stale copy if one is available), return a default (serve a degraded response), or fail fast (return an error immediately).

Releasing the lock. The lock must be released safely. A plain DEL risks deleting another client’s lock if yours already expired. Use a Lua script that checks the token matches before deleting:

if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
end
return 0

Mutex locking is the deterministic defence: one winner reads the source, the losers wait or serve stale, and a token-checked release deletes only the lock this request still owns — the lock-on-miss dive runs the race.

§4

Comparison

source · the three regimes

The three regimes trade along three axes — complexity, source reads at expiry, and staleness:

ApproachComplexityDatabase queriesStaleness
No protectionLowN (one per request)None
X-FetchMedium1–2Brief window
Mutex lockHigherExactly 1None
Compare the regimes. Select a regime to read its source-read count, complexity, staleness, and what the waiting requests do while one rebuilds — the bar shows reads at expiry.
none lock X-Fetch coalesce
readout · Select a regime. All three solutions converge a flood of misses to one regeneration; they differ in complexity and staleness.

All three converge a flood of misses to a single regeneration; they differ in complexity, in whether any request reads a stale value, and in whether the guard spans one process or the whole fleet.

§5

Recommendation

source · what to reach for

For most applications, start with mutex locking — it is easier to reason about and provides strong protection. Consider X-Fetch for extremely high-traffic keys where even brief lock contention is problematic. Some systems combine both: X-Fetch for normal operation, with a mutex fallback for hard cache misses. The early-refresh formula is a probability, so an unlucky run can still let the key physically expire — the lock catches that hard miss.

Notes on ValkeySET key value PX <ms> writes the value and its millisecond expiry atomically — the form EchoCache uses for the jittered TTL. A separate EXPIRE after SET leaves an immortal key if the process dies between the two — valkey.io/commands/set.

the application · one fill per herd, measured

EchoCache stops the herd by construction

EchoCache does not bolt a lock on after the fact: misses route through the table’s owner, concurrent misses on one id coalesce onto a single in-flight load, and rows expire on a jittered clock so a cohort never re-herds. The cost the herd would have paid is the committed figure — an L1 hit against the L2 GET it replaces:

content/bcs4.1.md · the cache hit cost, against live Valkeyfrozen
L1 hit reads/s                1311621        ← 762 ns each, caller-side ETS
L2 GET                        31 us          ← the round trip a herd multiplies
the L1 hit is                 40 times       cheaper than the round trip it replaces
§6

The three dives

lock → refresh early → coalesce

Each dive takes one solution and runs it on a hot key, in the arc lock → refresh early → coalesce: a deterministic per-key lock, a probabilistic refresh that beats expiry, and the coalescing EchoCache really does. Read them in order — the lock is the one to reach for first.

R1.05.1built

Lock-on-miss

A per-key regeneration lock with SET NX PX: one request wins and rebuilds, the rest wait or serve stale, and a token-checked release stops a stale lock deleting another holder’s.
R1.05.2built

Probabilistic early refresh

X-Fetch the pattern: recompute before expiry with a rising probability, using the real delta·beta·−log(rand) formula — then grounded in EchoCache’s real expiry jitter.
R1.05.3built

Request coalescing

Concurrent misses on one id collapse into a single in-flight fill — the EchoCache flights map and the :coalesced counter; every waiter reads the one answer.
the pattern

When a hot key expires, do not let every reader rebuild it. Elect one regeneration — by a lock, by a probabilistic early refresh, or by coalescing — and let the rest wait or serve the previous value.

its EchoCache application

EchoCache fuses two of these into the owner: the single-flight flights map coalesces concurrent misses onto one load (the :coalesced counter), and the jittered expires_at spreads a cohort’s expiry — one fill per herd, no synchronized re-herd.

Three dives, one rule: a hot key expires once, and it is rebuilt once too — not once per reader.

§7

References

sources · related

Sources

Related in this course