R1.05.1 · Cache stampede prevention — dive 1

The regeneration lock.

One request wins the lock and rebuilds the hot key. The rest wait, serve a stale copy, or fail fast — but never read the source.

Grounding: content/fundamental/cache-stampede-prevention.md.txt (Solution 2) · echo/apps/echo_store/table.ex (the single-flight flights map) — the lock idea, applied.

The lock race. Select what the losing requests do; one winner reaches the source, the rest are turned back. The readout names the source reads, the staleness, and the latency.

readout · Select what the losers do; the winner always reads the source once.

§1

Acquire with NX and PX

source · Redis Commands Used

The lock is one command. SET lock:set:EMS0ODMggk1d5N <token> NX PX 5000 sets the lock key to a unique token only if it does not already exist (NX), with a five-second expiry in milliseconds (PX 5000). The reply is the gate: OK means this request holds the lock and may rebuild; nil means another request already holds it.

The two options carry the whole guarantee. NX makes the acquire atomic — under a thousand concurrent attempts on one key, the engine admits exactly one. PX bounds the lock’s life so a winner that crashes mid-rebuild cannot hold the key forever; the lock expires and the next miss elects a fresh winner. The token matters for the release, not the acquire: each request generates a unique value so that later it can prove the lock it deletes is still its own.

# Try to win the regeneration lock for one hot key.
# NX: set only if absent (one winner). PX 5000: self-expire in 5s.
SET lock:set:EMS0ODMggk1d5N "a1b2c3-unique-token" NX PX 5000
# -> OK    : this request holds the lock; read the source and refill
# -> (nil) : another request holds it; this request waits or serves stale

NX: Set only if the key does not exist. Makes one client — and only one — win the lock.
PX 5000: Expire the lock after 5000ms. A crashed holder cannot deadlock the key; the lock self-clears.
token: A unique value per request. Proves ownership at release time, so a stale lock is not deleted by the wrong holder.

This is a single-Valkey lease, not a distributed lock across independent nodes. The multi-node contrast — Redlock — is the R2 Coordination chapter; here one Valkey is the source of truth.

§2

What the losers do

source · Handling Waiting Clients

The point of the lock is what the requests that lose it do: not read the source. Each loser has four options, weighing freshness against latency and load. Pick one in the race above, or read them here:

Poll — sleep briefly, then re-read the cache. The winner’s fill lands within a rebuild, so a short poll loop returns the fresh value with no source read and no staleness. The cost is a little added latency for the losers.
Serve stale — if a previous value is kept (a longer physical TTL than the logical one), serve it immediately while the winner rebuilds. Zero added latency, at the cost of a brief, bounded staleness.
Return a default — serve a degraded or placeholder response when no stale copy exists and latency matters more than completeness.
Fail fast — return an error at once. The bluntest choice; it sheds load but surfaces the miss to the caller.

Whatever the losers do, the invariant holds: exactly one request reads the source per expiry. The flood of N misses becomes one source read.

The lock’s value is in the losers: one request rebuilds, and every other request waits, serves stale, or degrades — but does not add to the source’s load.

§3

Releasing the lock safely

source · Releasing the Lock

Releasing looks trivial — delete the lock key after the refill — and a naive DEL is a bug. If request A wins the lock but its rebuild runs long and the PX 5000 expiry fires, the lock is free; request B acquires it with a fresh token. If A then calls a plain DEL lock:set:EMS0ODMggk1d5N, it deletes B’s lock — two requests now run as the holder at once. The guard against this is the token: read the lock, check the stored token equals this request’s, and delete only on a match — as one atomic Lua script.

-- release only if this request still owns the lock (atomic)
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
end
return 0
-- KEYS[1] = lock:set:EMS0ODMggk1d5N   ARGV[1] = this request's token
-- returns 1 (released) or 0 (the lock is no longer this one's — do nothing)

Run the release below against either an owned lock or one that already expired and was re-acquired by another request. The readout shows the GET comparison and whether the DEL fires.

Token-checked release. Select what the lock now holds; the readout compares it with this request’s token and shows whether the DEL fires.

readout · Select the lock state to run the token-checked release.

the application · one fill per herd at the owner

EchoStore elects the single fill in-process

EchoStore reaches the same one-winner guarantee without a separate lock key: a miss calls the owner with {:fill, id}, and the owner’s flights map admits one load per id. The first miss launches a flight; a concurrent miss appends its caller to the waiter list and bumps the :coalesced counter. The cost the lock saves is the committed figure — the L1 hit against the L2 GET a herd would multiply:

bcs.4.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 the herd avoids
the L1 hit is                 40 times       cheaper than the round trip it replaces

Notes on ValkeySET key value NX PX <ms> acquires and bounds the lock in one atomic command — the NX admits one writer, the PX self-expires it so a crashed holder cannot deadlock the key — valkey.io/commands/set.

the pattern

On a hot-key miss, contend for a short-lived SET NX PX lock. One winner reads the source and refills; the losers poll or serve stale. Exactly one source read per expiry.

its EchoStore application

EchoStore serializes the fill through the table’s owner: the flights map admits one load per id, concurrent misses coalesce onto it (the :coalesced counter), and every waiter reads the one answer — the lock idea, in-process.

Lock-on-miss is the deterministic defence: one lock, one winner, one source read — and a token-checked release so the lock is never deleted out from under another holder.

§4

References

sources · related

Sources

Valkey — SET — the NX and PX options that make one client acquire a self-expiring regeneration lock.
Redis — SET — the canonical command reference for the lock.
Redis — Documentation — expiry, atomic Lua scripting, and the patterns the token-checked release is built from.
Sanfilippo, S. — antirez weblog — the Redis creator on a single-instance lock, the token, and check-and-delete with Lua.

Related in this course

R1.05 · Cache stampede preventionthe module hub
R1.05.2 · Probabilistic early refreshthe next dive
R1.05.3 · Request coalescingone fill per herd, every waiter served
R1 · Cachingthe chapter
/elixir · Statethe OTP craft behind the echo data layer
/echomq/cachethe EchoStore per-key single-flight, in depth