Skip to content

Research notes / Cache refresh

Cache stampedes: early refresh still needs a concurrency policy

Published / Source review and constructed arithmetic

An average of one refresh does not mean exactly one refresh. In the example below, twenty requests start about one refresh on average, but start two or more in 26.3% of cases. A refresh policy needs an explicit answer for both duplicate work and requests that must wait.

On this page7 sections

Decide when to refresh, then who may do it

A popular key can expose many callers to the same missing value. Early refresh moves work ahead of expiry; coalescing combines compatible work that is already outstanding. They act at different decisions.

Vattani, Chierichetti and Lowenstein's XFetch draws a random look-ahead scaled by the previous recomputation duration. A request refreshes when that gap reaches the expiry time. Larger positive tuning factors favor earlier work. The theoretical bounds concern an arrival model and expected behavior, not exclusive ownership of a refresh. [1, sections 2-5]

For a remaining lifetime r, previous duration delta and factor beta, the per-request probability is p = exp(-r / (beta * delta)). All time quantities must use the same units. This applies to a present value before expiry, with positive duration and factor. A missing value has a different entry condition.

Twenty decisions against the same expiry

Construct a simultaneous cohort of twenty requests. Every request sees the same cached value and expiry, draws independently, and finishes its decision before any refresh can publish a replacement. Set the previous duration to one second and beta to one. Only remaining lifetime changes between rows.

Twenty simultaneous requests; previous recomputation 1 s; beta 1. Expected starts are counts; outcome columns are probabilities.
Time leftPer requestExpected startsNo startOne startMultiple starts
1 s36.79%7.3580.01%0.12%99.87%
3 s4.98%0.99636.01%37.73%26.26%
5 s0.67%0.13587.35%11.85%0.80%

At three seconds remaining, each request refreshes with probability about 4.98%. The expected count is 20p = 0.996. But there is a 36.01% chance that none refresh, a 37.73% chance that exactly one does, and a 26.26% chance of multiple starts. The mean conceals all three outcomes.

For m requests the count K has a binomial distribution: P(K=0) = (1-p)^m and P(K=1) = m*p*(1-p)^(m-1). The remaining probability covers at least two starts. These are conditional probabilities, not measured frequencies or confidence intervals. Display rounding can affect totals.

Moving earlier reduces duplicate starts in this fixed cohort but increases the chance that no request starts a refresh. That trade-off alone cannot select a production setting: earlier arrivals and later requests are absent from the example. At the deadline every request qualifies, unless a separate coordination mechanism restricts the work.

One key, within which coordinator?

The Go singleflight API provides a concrete scope: a Group coordinates work by key. With Do, overlapping duplicate callers wait for the shared result. Forget changes that lifecycle by allowing a later call to start without waiting for an earlier call. [3]

Consequently, one Group in each of eight independent worker processes is not one shared coordinator. As an illustrative upper-count case, if each process has waiting callers for the same key, all eight can start one fetch. Local suppression can be correct while the backend still receives eight requests. This is a scope deduction, not a measurement of the library.

Key equality also needs semantic equality: tenant, authorization, object version and response options may affect whether a result can be shared. A result cache and an in-flight-work map have different lifetimes. Decide how errors, cancellation, retries and coordinator failure release waiters; this probability calculation does not implement those policies.

A completed fetch can already be stale

Nishtala and colleagues' memcache design validates a per-key refill token when a value is set. An intervening deletion can invalidate that token, preventing an older fetch from repopulating the cache. Regulating token issuance separately reduces repeated backend work. Serving an older cached value is an application freshness decision. [2, section 3.2.1]

The engineering implication is to separate three questions: when a refresh may begin, which callers share its work, and whether its result is still authorized for publication. A random early-refresh choice answers only the first. A lock or local work map does not by itself specify a freshness contract for the resulting value.

Use the example for the right decision

The simultaneous-cohort calculation is not the paper's expected stampede over a request process. It holds metadata fixed and excludes completion timing, feedback from overloaded storage, changing recomputation duration, failures and repeated expiration cycles. It cannot rank production policies or estimate their latency.

For an implementation evaluation, record refresh starts per key and expiry episode, outstanding work, rejected stale publications and waiting time. Keep backend requests distinct from frontend misses. The existing delayed-hit analysis explains why waiting for a fill need not be a resident cache hit.

Reproduce the table

The calculation, tests, result JSON and method notes use Python's standard library. An independent Bernoulli-convolution oracle checks 270 parameter configurations. No workload data or random seed is needed.

python3 -B model.py --check
python3 -B -m unittest discover -s . -p test_model.py

Stable definitions: cache stampede, XFetch and request coalescing.

Primary sources

  1. Vattani, Chierichetti and Lowenstein. Optimal Probabilistic Cache Stampede Prevention. PVLDB 8(8), 886-897 (2015), sections 2-5. Accessed 2026-11-20.
  2. Nishtala et al. Scaling Memcache at Facebook. NSDI 2013, pp. 385-398, section 3.2.1. Accessed 2026-11-20.
  3. Go x/sync/singleflight: Group, Do and Forget documentation. Accessed 2026-11-20.

Published by Hesela team · Published · Updated

Report a correction · Editorial standards · Reuse guidance

Change history

: first published.

: latest recorded update. A detailed change note is not available for this revision.

New-publication RSS · Correction RSS

Cite this page
Hesela team. Cache stampedes: early refresh still needs a concurrency policy. Hesela. 2026-11-20. https://hesela.com/analyses/cache-stampede-early-refresh/