R1.05.2 · Cache stampede prevention — dive 2

Refresh before expiry.

No lock, no waiting. Each read may rebuild the key early, with a chance that rises as the TTL nears zero, so one request refreshes moments before it would expire.

Grounding: content/fundamental/cache-stampede-prevention.md.txt (Solution 1, the X-Fetch formula) · echo/apps/echo_cache/table.ex (the jittered expires_at) — the pattern, then the real applied mechanism.

Refresh chance vs time-to-expiry. Slide the time-to-expiry; select a beta to shift how eager the early refresh is. The chance is near zero when fresh, rising near expiry.

time to expiry (s) 60

readout · Slide and select a beta to read the early-refresh probability.

§1

Logical expiry, not physical

source · How It Works

Plain cache-aside sets a physical TTL: at the deadline the key vanishes and the next read misses. X-Fetch keeps a physical TTL too, but treats it as a logical deadline the value tries to beat. The trick is to refresh ahead of the deadline — while the key is still present and serving — so the key never has to physically expire under load.

To decide when, each read needs two facts stored alongside the value: the time the value was last computed, and how long that computation took (call it delta). The first gives the time remaining before expiry; the second sizes the head start a refresh needs, because a value that takes longer to rebuild should start rebuilding earlier. With those two numbers and one random draw, a read decides whether it is the one to refresh.

The outcome is statistical, not coordinated: no lock, no waiting, no central elector. Out of thousands of reads approaching the deadline, the formula makes it overwhelmingly likely that exactly one fires the early rebuild, and the rest carry on serving the fresh value.

§2

The X-Fetch formula

source · The Algorithm

The decision is the one the source gives. A read triggers a refresh when

# refresh early when this is true:
now - delta * beta * log(rand()) >= expiry
# equivalently, refresh when now is within  delta * beta * (-log(rand))  of expiry

The pieces: delta is the time the last regeneration took; beta is a tuning factor, conventionally 1.0; and rand() is a fresh uniform draw in the open interval (0, 1). Because rand() is below 1, log(rand()) is negative, so delta · beta · log(rand()) subtracts a positive margin from expiry — it brings the effective deadline earlier by a random amount.

That margin is what shapes the curve. When the key is fresh, now is far below expiry, and only an extreme random draw (a very small rand, giving a large margin) clears the threshold — so a refresh is rare. As now nears expiry, an ever-larger share of random draws clear it, and the refresh probability climbs toward one. Raising beta shifts the whole curve earlier; a larger delta — a costlier rebuild — also refreshes earlier, giving the slow rebuild the head start it needs.

delta: The time the last regeneration took. A costlier value refreshes earlier.
beta: A tuning factor, typically 1.0. Higher refreshes more eagerly; lower, later.
rand(): A fresh uniform draw in (0, 1). log(rand()) is negative, so it pulls the effective deadline earlier by a random margin.
now, expiry: The current time and the key’s logical deadline. The gap between them drives the rising probability.

The formula is a probability, so on rare runs two requests refresh, or a run of unlucky draws lets the key physically expire and falls back to a normal miss. That is why X-Fetch is often paired with a mutex fallback for the hard miss — the recommendation the module closes on.

§3

Roll the decision

source · the formula, computed

Run the formula. Pick a time-to-expiry and one of three fixed random draws, and the readout computes now − delta · beta · log(rand) against expiry with delta = 8s and beta = 1.0 — showing the early margin, the threshold, and whether this read fires the refresh. A draw near zero produces a large margin and refreshes early even when there is time left; a draw near one barely moves the deadline.

Compute the X-Fetch decision. delta = 8s, beta = 1.0. Select a random draw, slide the time-to-expiry; when the margin bar reaches the gap, the decision fires.

time to expiry (s) 20

readout · Select a draw and a time-to-expiry to compute the decision.

One formula over the time-to-expiry and a random draw decides each read: refresh early by a margin that grows as the deadline nears, so one request rebuilds before the key ever expires.

§4

On EchoCache — jitter, not XFetch

table.ex · expires_at/1 · verbatim

Here the honesty matters. EchoCache does not implement the probabilistic XFetch rule above — there is no now − delta·beta·log(rand) test in the code, and this dive does not claim one. What EchoCache runs against the same problem — a cohort that expires together and re-herds — is expiry jitter: every row draws its expiry from ttl ± ttl·jitter, so no two rows of a cohort hit the deadline at once.

defp expires_at(spec) do
  base = System.monotonic_time(:millisecond) + spec.ttl_ms
  spread = trunc(spec.ttl_ms * spec.jitter)

  if spread == 0 do
    base
  else
    base + :rand.uniform(2 * spread + 1) - spread - 1
  end
end

The two ideas share an aim — stop a synchronized expiry from creating the herd — but reach it differently: X-Fetch refreshes one read before the deadline; jitter spreads the deadlines so no two rows of a cohort hit it at once. The moduledoc states the goal directly: “Rows expire on a jittered clock — ttl ± ttl·jitter — so a cohort filled together never expires together.”

Notes on Valkeythe L2 row carries its expiry on the server’s own clock via SET … PX, so Valkey expires it even if every node forgets — the cohort never re-herds on either layer’s clock — valkey.io/commands/set.

the application · the jittered expiry, committed

A cohort filled together expires apart

The jitter is not a tuning aspiration — the committed drill shows the spread doing its work: a cohort filled within a few milliseconds expires over a wide window, with no synchronized re-herd. The zero-jitter control spreads only its own fill walltime, which is what proves the treatment.

content/bcs4.1.md · the jittered clock, against live Valkeyfrozen

400 rows filled in 24 ms
expire 138 ms apart at jitter 0.2   ← no synchronized re-herd
L2 row                        SET ... PX   ← PTTL 300 ms of 300, server clock

the pattern

Give the key a longer physical TTL and refresh it logically: each read rolls now − delta · beta · log(rand) ≥ expiry, so one request rebuilds early while the rest serve the fresh value. No lock.

its EchoCache application

EchoCache reaches the same goal by a different mechanism: expires_at/1 draws each row’s expiry from ttl ± ttl·jitter, so a cohort filled together never expires together — jitter spreads the deadlines instead of refreshing ahead of one.

Early refresh trades a tiny, bounded staleness for no lock and no waiting; EchoCache reaches the same no-re-herd outcome with jitter — the deadlines are spread, not beaten.

§5

References

sources · related

Sources

Valkey — SET — PX for the jittered millisecond TTL EchoCache writes to L2.
Redis — TTL — the remaining time-to-live X-Fetch inspects to size the gap to expiry.
Redis — Documentation — key expiry and the string commands that store the value with its timestamp and delta.
Sanfilippo, S. — antirez weblog — the Redis creator on expiry, eviction, and smoothing regeneration load.

Related in this course

R1.05 · Cache stampede preventionthe module hub
R1.05.1 · Lock-on-missthe deterministic alternative and the X-Fetch fallback
R1.05.3 · Request coalescingthe next dive
R1 · Cachingthe chapter
/elixir · Statethe OTP craft behind the echo data layer
/echomqthe protocol behind the coherence lane