Cache Stampede and Hot Keys: Single-Flight, Early Refresh, Jitter

What you'll learn: By the end of this lesson you will be able to explain why one expired cache entry can overload a database, estimate how many requests join the stampede, apply four fixes (single-flight, probabilistic early refresh, jittered TTLs and serving stale), say what each fixes and does not fix, tell a stampede from a hot key and name the mitigations for a hot key, and run a deterministic Java lab that shows each effect.

A printed price list hangs in an office. At nine o'clock it is out of date, and fifty people notice at once. Each walks to the archive for the new one. The archive has one clerk, who is now buried, so the walk takes longer, and more people notice the list is still out of date and set off too. Nobody did anything wrong; nobody coordinated.

Advanced Caching lists the remedies in a few lines. This lesson is the deeper look, with a lab. It assumes Eviction Policies and the TTL material in the LRU lesson.

Verified with Java 25.0.3 and Gradle 9.8.2 on 2026-11-08. The lab is examples/backend/labs/cache-stampede-protection.

The core idea

A cache stampede is many identical rebuilds triggered by one expiry. A popular entry expires, requests that arrive before the first rebuild finishes all see a miss, and each one runs the expensive query. The size of the stampede is the request rate times the rebuild time: Vattani, Chierichetti and Lowenstein's example is an item read 10 times per second that takes 3 seconds to recompute, so 30 requests recompute it.

Three kinds of example run through the lesson, each labelled:

• Minimal example: 50 threads miss one key in the lab, with and without protection.
• Realistic example: a ShopStream promotion on one hero product, in "In practice".
• Failure example: a deploy that empties every local cache at once.

Figure 1. How one expiry becomes many queries. How to read this: all three requests asked the cache before any rebuild had stored a value. Nothing in plain cache-aside makes them wait for each other.

An illustrative ShopStream number: a "fresh produce" list read 400 times per second and rebuilt in 250 ms gives about 400 x 0.25 = 100 requests inside one rebuild window.

Four fixes, four different ideas

Single-flight (request coalescing)

The first caller to miss registers a load for the key; callers that miss while it runs wait for its result instead of starting their own. Go's singleflight package describes the contract: "only one execution is in-flight for a given key at a time", and a duplicate caller "waits for the original to complete and receives the same results".

In Java, the lab keeps a ConcurrentHashMap of in-flight CompletableFutures. putIfAbsent is atomic, so exactly one caller wins the slot and runs the loader:

private V singleFlight(K key, Entry<V> seen, boolean early) {
    CompletableFuture<Entry<V>> mine = new CompletableFuture<>();
    CompletableFuture<Entry<V>> existing = inFlight.putIfAbsent(key, mine);
    if (existing != null) {
        if (early) {
            hits.incrementAndGet(); // someone is already refreshing: serve the valid entry we have
            return seen.value();
        }
        coalesced.incrementAndGet();
        return await(existing).value();
    }

Why not computeIfAbsent? The ConcurrentHashMap documentation says its computation is atomic but that "some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple". A database query is neither.

Two details decide whether single-flight is correct:

1. Double check after winning. Between looking at the map and winning the slot, another caller may have loaded the key, stored it and finished. The winner must look again, or it loads a second time. The lab has a test that loads 50 keys from 16 threads and asserts each key is loaded exactly once.
2. Failure is shared, not cached. A CompletableFuture completed exceptionally throws a CompletionException with the underlying exception as its cause, so every waiter gets the same failure, and the next request retries.

Its limit is scope. Single-flight inside one process gives one load per process, not per fleet: 40 app servers can still send 40 loads. Across servers you need a lock or a lease. Facebook's memcache paper describes leases: a memcached server returns a token on a miss and, by default, "only once every 10 seconds per key", telling other clients to wait a short time and retry. For a set of keys prone to herds, they report a peak database query rate of 17K/s without leases and 1.3K/s with them. Locks across processes bring their own failure modes (see Distributed Locks and Fencing Tokens).

Probabilistic early refresh (XFetch)

Instead of waiting for expiry, let readers refresh early, with a probability that grows as expiry nears. The paper's XFetch rule, with delta the time the last recomputation took and beta a parameter that defaults to 1, is to recompute when Time() - delta * beta * log(rand()) >= expiry. Since rand() is in (0, 1], the log is negative and the term is a random head start, usually small, occasionally large. The chance that a reader refreshes at a moment t before expiry works out to exp(-t / (delta * beta)): small far away, large close, and a longer delta (a costlier rebuild) refreshes earlier. The paper claims that this needs no tuning to the request rate; the lab's own table checks only the formula above, not that claim.

Figure 2. The early refresh decision. How to read this: only a reader that rolls "yes" does extra work, and only it waits. Everyone else gets the valid cached value.

Early refresh alone moves the stampede earlier: every reader that rolls "yes" at once still loads at once. Combine it with single-flight and the other readers are served the valid entry while the refresher works. Caffeine's refreshAfterWrite has the same shape: a key becomes eligible after the duration, a refresh starts only when the entry is queried, and "the old value (if any) is still returned while the key is being refreshed". A failed refresh keeps the old value.

Jittered TTL

Entries loaded together by a deploy, a warm-up or a bulk import expire together. Jitter gives each a random TTL, for example 60 s times a factor between 0.8 and 1.2. It does nothing for one hot key but flattens the cliff for many.

Serve stale

Amazon's Builders' Library describes two TTLs: a soft TTL after which the entry should be refreshed, and a hard TTL until which "the existing cache data will continue to be used". The same idea at the HTTP level is stale-while-revalidate, covered in HTTP caching in the front-end track. Serving stale is the right trade when a bounded amount of staleness is acceptable and wrong for stock counts and balances.

Hot keys are a different problem

A hot key is one key that receives a disproportionate share of traffic, whether or not it expires. In a partitioned cache one key lives on one node, so that node saturates while the cluster idles. The memcache paper observes that a single key can account for 20 percent of a server's requests.

Mitigations:

• A local cache in front with a seconds-long TTL, so most reads never leave the process.
• Key replication: store the value under key#r0 to key#r(n-1); readers pick one at random; writers and invalidations touch all of them. The memcache paper does a similar thing, replicating a category of keys within a pool so a request can go to any replica, at the price of delivering invalidations to all replicas.
• Detect and treat: track per-key request counts, because a healthy cluster average hides a saturated node.

Figure 3. Spreading reads, paying on writes. How to read this: each reader asks one derived key, so each cache node sees about a quarter of the reads. The writer must update every copy, so a hot key that also changes often is a poor candidate.

Build it

Goal. Reproduce the stampede and remove it step by step, with injected time, injected randomness and a loader the test controls.

Setup. From examples/backend:

./gradlew :labs:cache-stampede-protection:check
./gradlew -q :labs:cache-stampede-protection:run

The first runs 17 tests. The second prints the walk-through below. The code is in labs/cache-stampede-protection/src/main/java/buildingai/labs/stampede/.

How it works. LoadingCache takes a Policy that switches single-flight, jitter and early refresh on or off, a Loader, a clock and a random source. GatedLoader stands in for the database: it counts calls, holds callers at a gate until the test opens it, advances a manual clock by a fixed cost, and can fail. The threaded sections release the gate only when a counter shows that every request has either entered the loader or started waiting, never after a sleep, so the numbers do not depend on scheduling. The XFetch decision is a pure function:

public static boolean xfetchDecision(long now, long expiresAt, long deltaMillis, double beta, double u) {
    if (beta <= 0 || deltaMillis <= 0) {
        return false;
    }
    double safeU = u > 0 ? u : Double.MIN_NORMAL;
    return now - deltaMillis * beta * StrictMath.log(safeU) >= expiresAt;
}

Steps. Run the tests, then the Demo: 1 the stampede, 2 a shared failure, 3 jitter, 4 the early-refresh probability against its formula, 5 early refresh with single-flight, 6 key replication. Expected output, captured from a real run (Java 25.0.3, 2026-11-08):

Cache stampede lab: a hot key, 50 simultaneous requests, a slow source

== 1. The stampede, and single-flight stopping it ==
The entry for product:42 is missing (just expired). 50 requests arrive together; the loader is held at a gate
until every request has either entered it or started waiting for someone who did.

policy          requests  loader calls  peak concurrent loads  callers that waited  got the value
unprotected           50            50                     50                    0             50
single-flight         50             1                      1                   49             50

Unprotected: the source sees 50 identical queries at once. Single-flight: one query, 49 callers share its answer.

== 2. When the one load fails ==
loader calls: 1   requests that failed: 50   distinct exception objects: 1
entry cached after the failure: false
next request retries the loader (calls now 2) and gets product:42#1
A failure is shared by everyone who waited, is never cached, and does not poison the next request.

== 3. Jittered TTL: 1000 keys all loaded at t=0 with a 60 s TTL ==
Expiry times counted in 6 s buckets.

no jitter
  60-66 s  1000  ##################################################
  most keys expiring in one bucket: 1000

jitter 0.2 (TTL uniformly in 48 s to 72 s)
  48-54 s   246  ############
  54-60 s   248  ############
  60-66 s   233  ###########
  66-72 s   273  #############
  most keys expiring in one bucket: 273

== 4. XFetch: the chance that one read refreshes early ==
Entry expires at t=60000 ms and took 2000 ms to load. Each row is 10000 reads at a fixed moment (seeded random).
Rule: refresh if now - delta * beta * ln(u) >= expiry, u uniform in (0, 1]. Formula: probability = exp(-(time left) / (delta * beta)).

   time left    beta=1 measured   beta=1 formula    beta=2 measured   beta=2 formula
    30000 ms              0.000            0.000              0.001            0.001
    10000 ms              0.006            0.007              0.081            0.082
     5000 ms              0.084            0.082              0.288            0.287
     2000 ms              0.368            0.368              0.608            0.607
     1000 ms              0.600            0.607              0.782            0.779
      500 ms              0.782            0.779              0.878            0.882

Far from expiry almost nobody refreshes; close to it, a refresh becomes likely, so the entry is usually replaced before it expires.

== 5. Early refresh with single-flight: readers keep getting a valid value ==
t=0 first load, 2000 ms. Entry now expires at t=62000 (generation 1).
t=61000 one request reads the entry (1000 ms before expiry), decides to refresh, and the loader blocks.
10 more requests arrive while the refresh runs (each would also refresh, by the same rule).
  answered at once with the still-valid generation-1 value: 10 of 10
  loader calls so far: 2 (the first load and the one refresh)
refresh finished. Next read returns product:42#2. Stats: Stats[hits=11, misses=1, loads=2, coalesced=0, earlyRefreshes=1, loadFailures=0]

== 6. A different problem: one key is hot, not expired (key replication) ==
10000 reads of product:42 spread over 4 derived keys: product:42#r0=2430  product:42#r1=2527  product:42#r2=2475  product:42#r3=2568
A write or an invalidation must now touch 4 keys: [product:42#r0, product:42#r1, product:42#r2, product:42#r3]
Whether those keys sit on different cache nodes depends on how the cache hashes them; this lab does not model placement.

Break it. In Demo section 1, run both rows with the unprotected policy and see 50 loads again. In singleFlight, replace the double-check condition with false: the exactly-once test is a race detector, and when this lab was written it failed on 1 of 3 runs without the check. A race test that passes does not prove the race is absent.

Stretch. Add stale-while-revalidate with a grace period, or a negative cache for "not found".

What the model leaves out. Eviction and size (see the LRU lab), more than one process (so no leases or distributed locks), real time and real databases, and cache node placement for hot keys. The refresh probability table verifies the formula, not the paper's optimality claims.

Trade-offs

In practice: a promotion on one hero product

This is the realistic example. It is an educational scenario on the course's running example, ShopStream, and nothing in it describes a real company. Figures are illustrative.

This is a realistic scenario, not a case history.

The situation

ShopStream will feature one hero product on the home page for an evening promotion. The product page and a "customers also bought" list are cached with a 5-minute TTL. The expected load is tens of times the usual rate for that one product, and the rebuild of the page takes a few hundred milliseconds of database time.

Starting architecture

Figure 4. Two problems share one key. How to read this: every server asks the same Redis node for the same key, which is the hot-key limit, and on expiry every server's misses go to PostgreSQL, which is the stampede.

Options considered

The decision

Option B now, C only if measurement shows fleet-wide duplicates still hurt. A scheduled job pre-warms the hero key before the promotion. Stock stays out of the 2-second local copy: it is shown in coarse buckets and purchase checks the database.

Figure 5. Match the fix to the pattern. How to read this: first name what you see in the metrics, because the fixes for expiry and for heat are different and one does not cure the other.

Rollout and verification

A rollout would run the protections in shadow mode, then canary on a low-traffic product, then load test at twice the last peak while deleting the hero key mid-test. The checks: loader calls per key per minute, peak concurrent loads at the database, p99 read latency and per-node request counts.

The 2 a.m. failure

The page reads: PostgreSQL connections at the limit, with no hot key involved. A deploy had restarted every app server, which emptied all their local caches at the same moment. Single-flight limited each server to one load per key, but there were thousands of different keys and dozens of servers, so thousands of different queries arrived together. The checks: loads per key stay at one per server, while the total number of distinct keys loading explodes. Single-flight is per key, so it cannot stop this. The mitigations: a cap on concurrent loads per process (a bulkhead, see Resilience Patterns), staggered restarts, pre-warming the hottest keys first, and serving stale or a degraded page for the rest while the source recovers.

Architect's notes

• Name the pattern before choosing a fix. One key expiring, many keys expiring and one key being hot need different tools.
• Put timeouts on the loader. Waiters share the slowest load, so an unbounded loader turns one hang into many.
• Measure per key. The average hides both a hot key and a stampede.

Common mistakes

• Early refresh without single-flight. Every reader that rolls "yes" reloads at once.
• Calling a slow loader inside computeIfAbsent. It can block other updates to the map.
• Forgetting the double check after winning the slot, so a key is loaded twice.
• Identical TTLs for bulk-loaded data.
• Replicating a hot key that changes constantly. Every write now costs several.

Key takeaways

• A stampede is the request rate times the rebuild time, all rebuilding the same value.
• Single-flight makes one caller load and the others share its result, including its failure.
• XFetch refreshes early with probability exp(-t / (delta * beta)); combine it with single-flight.
• Jitter spreads expiry across keys; it does nothing for one key.
• A hot key is about heat, not expiry: use a local cache or key replication.
• Single-flight is per key and per process: many cold keys or many servers need more.

Practice exercises

Exercise 1 (30 min). Run the Demo. For section 1, compute the expected stampede size from a request rate of 400 per second and a 250 ms rebuild, and compare it with the lab's 50.

Exercise 2 (1 hour). Add a timeout to the single-flight wait, so a waiter gives up after a limit and loads on its own. What invariant does that break, and when is it worth it?

Exercise 3 (2 hours). Design the lease version for 40 servers: where the token lives, its expiry, what a waiter does, and what happens when the holder dies mid-load.

Related reading

• Advanced Caching: write policies, invalidation, distributed caches.
• Eviction Policies: LRU, LFU and TTL: what a full cache drops.
• Build an LRU Cache in Java: TTL and thread safety, the lab this one builds on.
• Cache Layers: where each cache sits.
• Distributed Locks and Fencing Tokens: what a cross-server lock needs.
• HTTP Caching (front end): stale-while-revalidate in the browser and CDN.
• ShopStream Stage 2: the read path this scenario extends.

Official documentation

• Vattani, Chierichetti and Lowenstein, Optimal Probabilistic Cache Stampede Prevention (PVLDB 8(8), 2015): the stampede model and XFetch.
• Nishtala et al., Scaling Memcache at Facebook (NSDI 2013): leases, hot-key replication.
• Go, singleflight: the duplicate-suppression contract.
• Oracle, ConcurrentHashMap and CompletableFuture (Java 25).
• Caffeine, Refresh and Population.
• Amazon Builders' Library, Caching challenges and strategies: request coalescing, soft and hard TTLs.