# Cache Stampede and Request Coalescing — Caching Strategies & CDN Design

Source: https://www.skillbyai.com/en/caching-strategies/x-stampede

> Prevent thundering herds when hot keys expire.

## Everyone misses at once

When a **hot key** expires, every request arriving in the next few milliseconds misses at the same time and all of them query the database and recompute the value: a **cache stampede** or **thundering herd**. For an expensive query on a popular page, this can overload the database exactly when traffic is highest. Defences: **request coalescing** (single flight), where only one caller recomputes and others wait for its result, implemented in-process or with a short distributed lock; **serving stale while revalidating**, where callers get the slightly expired value while one background task refreshes it; **probabilistic early expiration** (the XFetch approach), where each reader has a small, growing chance of refreshing the key before it expires, so refreshes spread out naturally; and **refresh-ahead** for known hot keys. Also cap the database's own concurrency so a stampede degrades rather than collapses it.

## A stampede and its cure

Without coalescing, all requests hit the database; with it, one request rebuilds while others wait.

![Left: many arrows passing an empty cache box straight into a strained database. Right: many arrows stopping at the cache box, with a single arrow continuing to a calm database.](assets/figures/caching-strategies/section-4-map.svg) — Figure 4.1 — Cache stampede versus request coalescing.

## Probabilistic early expiration (XFetch)

Readers occasionally refresh before expiry; the chance rises as expiry approaches and with longer recompute times.

```python
import math, random, time

BETA = 1.0   # >1 refreshes earlier, <1 later

def fetch(key, recompute, ttl):
    entry = cache.get(key)          # stores value, delta (recompute seconds), expiry
    now = time.time()
    if entry is None or now - entry.delta * BETA * math.log(random.random()) >= entry.expiry:
        start = time.time()
        value = recompute()
        delta = time.time() - start
        cache.set(key, value, delta=delta, expiry=now + ttl)
        return value
    return entry.value
# note: log(random()) is negative, so the subtraction adds a random head start
```

## Coalesce in-process first

Even without a distributed lock, letting only one request per instance recompute a key (a per-key future or promise) cuts a stampede from thousands of database calls to one per instance.

**Quiz:** What does request coalescing do during a cache miss on a hot key?

- [ ] Sends every request to the database in parallel
- [ ] Deletes the key permanently
- [x] Lets one caller recompute the value while others wait for that result
- [ ] Doubles the TTL of all keys

*Answer:* Lets one caller recompute the value while others wait for that result. Coalescing collapses many identical misses into one recomputation.