Cache Stampede and Request Coalescing

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.

Probabilistic early expiration (XFetch)

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

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.

Quick check: 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
• Lets one caller recompute the value while others wait for that result
• Doubles the TTL of all keys