What is a cache stampede, and why does it look like a database incident?
A cache stampede happens when a single hot key expires and many concurrent requests miss on it at the same moment. Every one of those requests sees an empty slot, concludes that it should rebuild the value, and runs the same expensive query or computation against the backing store. The cache was absorbing that load, and for a short window it stops absorbing any of it.
The size of the burst is roughly the request rate for the key multiplied by the time it takes to recompute the value. Recomputation does not finish instantly, so every request that arrives during that window also misses. Illustrative estimate, with assumed inputs: a key serving 2,000 requests per second with an 800 ms rebuild query produces about 1,600 identical queries before the first one repopulates the cache. The burst also feeds itself. As the database slows under load, recompute latency grows, the miss window widens, and more requests pile into it.
This is why stampedes show up as database incidents. On-call engineers see connection pool exhaustion, CPU spikes and slow-query logs full of one statement. The cache itself reports nothing unusual, because a miss on an expired key is normal behavior.
This section is aimed at backend and platform engineers who run hot keys that are expensive to compute behind a TTL cache. Cold starts and full cache flushes are a separate problem, because they involve many keys missing at once rather than one key. They need different remedies, such as cache warming and gradual ramp-up.
How does request coalescing (singleflight) work inside one process?
The core structure is a map from cache key to an in-flight future, guarded by a mutex. On a miss, a caller takes the lock and looks up the key. If no entry exists, it inserts a new future, releases the lock, and becomes the leader: it loads from the database, writes the cache, and completes the future. Any caller that finds an existing entry is a follower. It releases the lock and waits on that future. Holding the mutex only for the lookup and insert matters, because holding it across the database call would serialize every key behind one slow query.
The leader must delete the map entry on every exit path: success, returned error, and panic or exception. In Go that means a defer, and in Java or Python a finally block. If the delete is skipped, followers either hang forever or keep receiving a stale error. The map also grows without bound, a memory leak that only shows up under high key cardinality. Deleting the entry after an error also means one failure doesn't stick, so the next request retries.
Run the shared load under its own deadline, detached from the leader's request context. If the leader's client disconnects, cancelling the load would fail every follower too. Each follower still applies its own timeout while waiting.
A single global mutex becomes a contention point once many distinct keys miss at the same time. Shard the map by key hash into a fixed number of independently locked maps. Go's singleflight package implements the per-key coalescing, but it does not shard the map or apply a timeout for you.
import java.util.*;
import java.util.concurrent.*;
import java.util.function.Function;
public final class ShardedSingleflight<V> {
private static final int SHARDS = 64; // fixed shard count; each shard has its own lock
private final Map<String, CompletableFuture<V>>[] shards;
private final ExecutorService loaders = Executors.newFixedThreadPool(16);
private final long loadDeadlineMs = 2_000; // deadline for the shared load, not for any one caller
@SuppressWarnings("unchecked")
public ShardedSingleflight() {
shards = new Map[SHARDS];
for (int i = 0; i < SHARDS; i++) shards[i] = new HashMap<>();
}
public V get(String key, Function<String, V> loader, long waitMs) throws Exception {
Map<String, CompletableFuture<V>> shard = shards[(key.hashCode() & 0x7fffffff) % SHARDS];
CompletableFuture<V> f;
boolean leader = false;
synchronized (shard) { // lock held only for lookup + insert, never across the DB call
f = shard.get(key);
if (f == null) { f = new CompletableFuture<>(); shard.put(key, f); leader = true; }
}
if (leader) {
CompletableFuture<V> mine = f;
// Runs on the loader pool, so an interrupted or abandoned leader thread does not kill the shared load.
// supplyAsync captures any Throwable from the loader, so failures still reach whenComplete.
// orTimeout fails the future at the deadline; it does not stop a blocked loader thread.
CompletableFuture.supplyAsync(() -> loader.apply(key), loaders)
.orTimeout(loadDeadlineMs, TimeUnit.MILLISECONDS)
.whenComplete((v, err) -> {
synchronized (shard) { shard.remove(key, mine); } // runs on success, error, and timeout
if (err != null) mine.completeExceptionally(err); else mine.complete(v);
});
}
// Leader and followers each wait with their own timeout. A caller timing out does not cancel f.
return f.get(waitMs, TimeUnit.MILLISECONDS);
}
}
A sharded in-process singleflight in Java. Each key's first caller starts one detached load with its own deadline, and later callers wait on the same CompletableFuture with their own timeouts. The map entry is removed on every completion path, so errors do not stick and the map does not leak.
What does coalescing guarantee across N replicas?
Coalescing guarantees at most one in-flight recompute per key per process, not per fleet. Each replica has its own map and its own waiters, and none of them knows the others exist. With N replicas behind a load balancer, a hot key that expires everywhere at once can still produce up to N concurrent recomputes.
replica 1: r r r r ... (30 waiters) ──► 1 call ─┐
replica 2: r r r r ... (30 waiters) ──► 1 call ─┤
... ├──► database: 20 concurrent queries
replica 20: r r r r ... (30 waiters) ──► 1 call ─┘
Illustrative estimate, not a measurement. Assume 20 replicas, 2,000 req/s on one key spread evenly (100 req/s per replica), and a 300 ms recompute. Every request that arrives during the 300 ms after expiry misses the cache.
| Scenario | Misses in the 300 ms window | Recomputes hitting the database |
|---|---|---|
| No coalescing, 20 replicas | 600 | 600 |
| Coalescing, 20 replicas | 600 | 20 |
| Coalescing, 60 replicas after scale-out | 600 | 60 |
The uncoalesced row understates the problem. When 600 identical queries arrive at once, each one runs slower, so the window lengthens and even more requests miss.
The bound tracks replica count, not traffic. Autoscaling usually adds replicas because load is rising, which is also when a stampede does the most damage, so the ceiling rises at the worst time. In this illustrative example, with the assumed inputs above, coalescing cuts database recomputes from 600 to 20, a 30× reduction; the actual factor in your system depends on your request rate, recompute time and replica count. For many keys a reduction of that kind is enough. For keys where N concurrent recomputes are still too many, use the techniques in the following sections.
2,000 req/s on one hot key; cache entry just expired
│
┌───────────┴───────────┐
│ load balancer │
└───┬───────┬───────┬───┘
│ │ │ 100 req/s per replica
┌─────────────────┘ │ └─────────────────┐
▼ ▼ ▼
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐
│ replica 1 │ │ replica 2 │ ... │ replica 20 │
│ 30 waiters │ │ 30 waiters │ │ 30 waiters │
│ r r r r ... r │ │ r r r r ... r │ │ r r r r ... r │
│ └─┴─┴─┴─┬───┘ │ │ └─┴─┴─┴─┬───┘ │ │ └─┴─┴─┴─┬───┘ │
│ ▼ │ │ ▼ │ │ ▼ │
│ 1 recompute/key │ │ 1 recompute/key │ │ 1 recompute/key │
└─────────┬─────────┘ └─────────┬─────────┘ └─────────┬─────────┘
│ 1 call │ 1 call │ 1 call
└─────────────────────────┼─────────────────────────┘
▼
┌───────────────────────┐
│ database │
│ 20 concurrent queries │
│ 1 per replica │
└───────────────────────┘
Illustrative estimate, not a measurement: with assumed inputs of 20 replicas, 2,000 req/s on one key and a 300 ms recompute, each replica collapses its roughly 30 local waiters into one backend call, but the database still receives one concurrent recompute per replica (20 in this example).
How does probabilistic early expiry (XFetch) spread refreshes over time?
Coalescing limits how many recomputes run at once. Probabilistic early expiry, known as XFetch, aims to have one reader refresh a hot key shortly before it expires, so the miss never happens.
On every read, the reader computes now - delta * beta * ln(rand()) and refreshes if the result is at or past the stored expiry. Here rand() is uniform in (0, 1]. Because ln(rand()) is never positive, the term adds a random, exponentially distributed lead time. Far from expiry, almost no draw is large enough to trigger a refresh. Close to expiry, most draws are. A hot key gets many draws, so one of them usually fires early and the other readers keep serving the cached value.
delta is how long the last recompute took. A value that takes two seconds to rebuild has to start earlier than one that takes five milliseconds. The cache cannot infer this, so the writer measures it and stores it in the entry next to the value and the expiry.
beta defaults to 1. Values above 1 refresh earlier, which costs more redundant recomputes. Values below 1 refresh later, which risks the key expiring before anyone refreshes it.
Illustrative estimate (assumed numbers, not a benchmark). The chance that a single read refreshes at time t before expiry is exp(-t / (delta * beta)). Assume delta = 200 ms, beta = 1 and t = 1 s. That gives e⁻⁵ ≈ 0.7% per read. At an assumed 100 reads/s, you would expect roughly 0.7 early refreshes per second at that point, and the rate climbs as t shrinks.
XFetch spreads refreshes for one key across its readers. It does nothing for many keys that share an expiry. Keys written together after a deploy or cache warm-up all expire together, and cold keys receive too few reads to refresh early. To prevent this, multiply each TTL by a random factor, such as 0.9–1.1, when you write the entry.
import math
import random
import time
BETA = 1.0 # >1 refreshes earlier (more recomputes), <1 later (more misses)
BASE_TTL = 300.0 # seconds
JITTER = 0.10 # +/-10% so keys written together expire at different times
def jittered_ttl(base=BASE_TTL, jitter=JITTER):
return base * random.uniform(1.0 - jitter, 1.0 + jitter)
def should_refresh_early(entry, beta=BETA):
# random.random() is in [0, 1); flip it to (0, 1] so log() never sees 0.
r = 1.0 - random.random()
# -ln(r) >= 0, so this adds a random lead time scaled by recompute cost.
lead = -entry["delta"] * beta * math.log(r)
return time.time() + lead >= entry["expiry"]
def get(cache, key, recompute):
entry = cache.get(key)
if entry is None or should_refresh_early(entry):
# In production, wrap this in the coalescing lock from the previous section.
start = time.monotonic()
value = recompute()
delta = time.monotonic() - start # measured by the writer, not guessed
entry = {
"value": value,
"delta": delta, # stored next to the value for future readers
"expiry": time.time() + jittered_ttl(),
}
cache[key] = entry
return entry["value"]
A minimal Python sketch of the XFetch early-refresh check, with the measured recompute time stored in the cache entry and a jittered TTL applied on every write.
Combining coalescing, early expiry and stale-while-revalidate
Each technique covers a gap the others leave open. Early expiry turns most expirations into a single early refresh, so fewer requests ever reach a hard miss. Coalescing handles the concurrent misses that still occur, such as cold keys, post-deploy waves, and evictions, by sending one query per key per process. Stale-while-revalidate removes the remaining latency, because callers get the old value while one background refresh runs.
A combined read path stores each entry with two timestamps: a soft expiry and a hard expiry.
- Fresh (before soft expiry, and the XFetch check does not fire): return the value.
- Stale but within the hard bound: return the value and start a coalesced background refresh. Concurrent requests for the key join that one refresh instead of starting new ones.
- Past hard expiry, or missing: the caller waits on the coalesced leader, using a timeout shorter than the request deadline.
The hard bound is your staleness contract. Past it, the cache must not serve the old value no matter what state the backend is in.
Cache errors and "not found" results for a short time, with a TTL of seconds rather than minutes. Without this, a failing query or a burst of lookups for absent keys turns every request into a database call.
Emit these metrics per key family:
- coalesced-waiter count
- refresh count
- stale-served count
- leader timeouts
With these four signals, a stampede shows up as a trend you can tune: adjust the TTL, the early-expiry factor, or the hard bound. That replaces an incident reconstructed from database load graphs, and turns repeated firefighting into a few configuration changes.
import asyncio, math, random, time
from collections import Counter
TTL, HARD, ERR_TTL, BETA = 60.0, 300.0, 5.0, 1.0 # seconds; HARD is the staleness contract
metrics = Counter() # replace with your metrics client, tagged by key family
cache, inflight = {}, {} # key -> (value, soft_exp, hard_exp, delta); key -> Task
def _unwrap(value):
if isinstance(value, Exception): raise value # cached error, short TTL
return value
async def _refresh(key, loader):
metrics["refresh"] += 1
start = time.monotonic()
try:
value = await loader(key)
ttl = ERR_TTL if value is None else TTL # negative results get a short TTL
except Exception as exc:
value, ttl = exc, ERR_TTL
now, old = time.monotonic(), cache.get(key)
if isinstance(value, Exception) and old and now < old[2]:
cache[key] = (old[0], now + ERR_TTL, old[2], old[3]) # keep last good value, never past hard
else:
cache[key] = (value, now + ttl, now + (HARD if ttl == TTL else ttl), now - start)
def _start(key, loader): # coalescing: at most one refresh per key per process
if key in inflight:
metrics["coalesced_waiter"] += 1
return inflight[key]
task = inflight[key] = asyncio.ensure_future(_refresh(key, loader))
task.add_done_callback(lambda _: inflight.pop(key, None))
return task
async def get(key, loader, wait_timeout=0.5): # wait_timeout < request deadline
now, entry = time.monotonic(), cache.get(key)
if entry and now < entry[2]:
value, soft, _, delta = entry
if now - delta * BETA * math.log(1 - random.random()) < soft: # XFetch did not fire
return _unwrap(value)
_start(key, loader) # early or stale: refresh in background, serve what we have
metrics["stale_served"] += now >= soft
return _unwrap(value)
try: # hard miss: wait on the leader; shield so a timeout does not cancel it
await asyncio.wait_for(asyncio.shield(_start(key, loader)), wait_timeout)
except asyncio.TimeoutError:
metrics["leader_timeout"] += 1
raise
return _unwrap(cache[key][0])
An asyncio read path that combines XFetch early expiry, per-key coalescing and stale-while-revalidate, with a hard staleness bound, short-TTL caching of errors and not-found results, and the four counters described above.
When should you add a distributed lock, and what are the alternatives?
Coalescing caps origin load at one recompute per key per replica. As an illustrative example with assumed replica counts: with 4 replicas, that is usually fine. With 60 replicas and a recompute that runs a heavy aggregate query, 60 simultaneous queries for one key can still saturate the database. Once N multiplied by recompute cost is more than the origin can absorb, add a short-lived lease in the shared cache.
The lease is an atomic set-if-absent with a TTL, written to a lock key whose value is a unique token. Put it under in-process coalescing. Only the local leader attempts the lease, so each replica makes at most one lock call per key. This adds one cache round trip, and only on the miss path.
Losers. Replicas that fail to get the lease should serve stale data if they have it. If not, they poll the value key for a short, bounded time.
Slow holders. If the holder runs past the lease TTL, a second holder can start a duplicate recompute. To limit this:
- Set the lease TTL above the recompute's p99.
- Release with an atomic compare-and-delete on the token, so a slow holder never deletes someone else's lease.
Degraded cache. If the lock call errors or times out, fall back to coalescing-only and go to the origin. Never block a request waiting on the lock. This fallback is required, because the lock is an optimisation, not a correctness guarantee.
| Technique | Cross-process dedup | Latency impact | Complexity | Failure mode |
|---|---|---|---|---|
| Plain TTL | None | Miss spikes | Trivial | Full stampede |
| Coalescing only | No (N per key) | Followers wait | Low | Scales with replicas |
| Early expiry | Probabilistic | Rare early refresh | Low | Cold keys still stampede |
| Stale-while-revalidate | No | Near zero | Medium | Serves stale data |
| Distributed lock | Yes | One round trip on miss | High | Lease expiry, cache outage |
| Background refresh/warm-up | Yes (single refresher) | None on read | Medium–high | Refresher lag, wasted work |
When should you avoid these techniques, and what do they cost to build?
Where these techniques hurt
Data that must not be stale. Permissions, account balances and inventory checks should not go through stale-while-revalidate or early expiry at all. A revoked permission served for one more refresh window can be a security incident. Read these from the source of truth, or invalidate on write. Coalescing alone is acceptable only if waiters can tolerate a result that was computed before their own request arrived.
Rarely read keys. XFetch decides on each read whether to refresh early. A key read a few times per TTL cannot stampede, so early expiry adds nothing. If beta is set high or the recorded compute time is overestimated, most reads trigger a refresh, and you increase load on the backend for no benefit.
Failure propagation. With coalescing, a leader that errors fails every waiter, and a leader that hangs blocks every waiter. Put a deadline on the shared call. Do not cache errors beyond a short negative TTL. After a leader failure, cap how many waiters retry independently.
Cold starts and full flushes. When every key is missing at once, coalescing removes duplicate work per key but not the load from thousands of distinct keys. Handle this with cache warm-up, admission control or load shedding.
What each layer costs
| Layer | Build cost | Ongoing cost | Add when |
|---|---|---|---|
| Coalescing + TTL jitter | Low | Low | Always, as the baseline |
| Probabilistic early expiry | Low–medium | Tuning beta, tracking compute time | Hot keys still show miss spikes at expiry |
| Stale-while-revalidate | Medium | Staleness bounds, background errors | Refresh latency is visible to users |
| Distributed lock | High | Lease tuning, lock-store outages | Replica-count × miss cost overloads the source |
Start with coalescing and jitter. Add the other layers only when per-key miss rates and backend load metrics show the baseline is not enough.
How OneEnv can help
Disclosure: OneEnv is the product behind this blog.
OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.
Applied to cache stampede prevention, this is where it helps:
Saves time
- Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
- One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
- Changing a shared variable is one edit and one review instead of editing every service's
.envby hand.
Saves cost
- Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
- Less duplicated configuration to maintain: one shared definition inherited by many services.
- A wrong or stale value is caught at review time by the services it affects, not by a failed deploy.
- OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.
These are qualitative benefits, not measured results — how much you save depends on how many services share the value.
Want to try it? Start at oneenv.io.