Cache Stampede Prevention: Request Coalescing and Early Expiry

How a thundering herd forms and what triggers it

A cache stampede starts when a hot key disappears. Every request that arrives before the first recompute finishes sees a miss, and each one independently queries the backing store and rebuilds the same value. The duplicate work lasts for one recompute latency. So the number of redundant calls is roughly the request rate on that key multiplied by the recompute time.

Illustrative estimate. Assume 2,000 req/s on one key and a 250 ms recompute. About 2,000 × 0.25 = 500 requests miss during that window, which means roughly 500 backing-store calls where one would do. The math gets worse under load. When the database slows down, recompute latency rises, the window widens, and more requests pile in.

Stampedes have four common triggers. They differ in how many keys go missing at once and whether any old value is still available, so each needs a different fix.

Early expiry only helps when the key exists and can be refreshed ahead of time. Cold starts and failovers have no such key, so they rely on limiting concurrent rebuilds instead.

Request coalescing within a process (single-flight)

Request coalescing, often called single-flight, makes sure each process sends at most one origin request per key at a time. The first caller for a key becomes the leader. Every caller that arrives while that request is in flight waits on the leader's result and does not issue its own fetch. If 500 concurrent misses land on one replica, the database receives one query from that replica instead of 500.

The mechanics

The implementation needs only a mutex, a map, and a future or promise type (or a condition variable):

1. Lock the map. If an entry exists for the key, take its future, unlock, and wait.
2. If no entry exists, create a future, insert it, unlock, and run the fetch as leader.
3. When the fetch finishes, resolve the future with the value or the error, so every waiter sees the same outcome.
4. Remove the map entry in a finally-style block. If the entry stays after a failure, every later caller inherits that error.

Each waiter needs its own timeout so one slow origin call cannot hang an unbounded queue. You also have to decide what cancellation means. If the leader's caller disconnects, you can either cancel the shared fetch, which fails every waiter, or detach the fetch from that caller's context so the waiters still get a result. Pick one, document it, and test it.

Key scope

The coalescing key must contain every input that changes the response, including tenant ID and auth scope. A key of user-profile:42 that leaves out the caller's permissions can give one tenant's data to another. Keys that are too broad cause a quieter problem: they merge requests that should stay distinct, and callers get results built for parameters they never sent.

Copyimport asyncio
from typing import Any, Awaitable, Callable, Hashable

class SingleFlight:
    def __init__(self) -> None:
        # One in-flight task per key. All code here runs on one event loop thread
        # with no await between get() and insert, so no lock is needed.
        # With OS threads, guard this dict with a threading.Lock.
        self._inflight: dict[Hashable, asyncio.Task] = {}

    async def do(self, key: Hashable, fetch: Callable[[], Awaitable[Any]],
                 timeout: float) -> Any:
        task = self._inflight.get(key)
        if task is None:
            # Leader: run the fetch as its own task, detached from this caller.
            # Policy: if the leader's caller goes away, waiters still get a result.
            task = asyncio.create_task(self._run(key, fetch))
            # Mark the exception as retrieved so the loop does not warn about it
            # if every caller has already timed out.
            task.add_done_callback(lambda t: t.cancelled() or t.exception())
            self._inflight[key] = task
        # Each caller has its own timeout. shield() keeps one caller's timeout or
        # cancellation from cancelling the fetch that other callers share.
        return await asyncio.wait_for(asyncio.shield(task), timeout)

    async def _run(self, key: Hashable, fetch: Callable[[], Awaitable[Any]]) -> Any:
        try:
            # The value or the raised error reaches every awaiting caller.
            return await fetch()
        finally:
            # Remove on success and on failure, so an error is never cached.
            self._inflight.pop(key, None)

# Usage: the key holds every input that changes the response, including
# tenant and auth scope, so two tenants never share one result.
# flight = SingleFlight()
# profile = await flight.do(
#     ("user-profile", tenant_id, auth_scope, user_id),
#     lambda: load_profile(tenant_id, user_id),
#     timeout=2.0,
# )

A minimal asyncio single-flight that keeps one shared task per key, sends its value or error to every caller, removes the entry when the task finishes, gives each caller its own timeout with shield(), and keeps the fetch running if the leader's caller goes away.

Coordinating across replicas with a short-lived lock or lease

Single-flight deduplicates only within one process. With 40 replicas behind a load balancer, a hot key that expires can still trigger up to 40 concurrent recomputes, one per replica. If the backing query is cheap or the replica count is small, that residual load is usually fine. It becomes a problem when the recompute is expensive (a heavy aggregation, a rate-limited upstream) or when autoscaling multiplies replicas during exactly the traffic spikes that cause misses.

To coordinate across replicas, take a short-lived lock in the cache itself. In Redis, SET lock:<key> <token> NX PX 5000 atomically creates the lock only if it is absent and attaches a 5-second expiry. The replica that wins recomputes and writes the value. The others take one of three paths:

• Serve stale, if a previous value is still retained.
• Wait with bounded backoff, re-reading the value key a few times before giving up.
• Fail fast with an error or a degraded response.

Copy replica A ──SET NX PX──▶ ┌────────────┐  OK   ──▶ backing store ──▶ write value
 replica B ──SET NX PX──▶ │   cache    │  nil  ──▶ stale / backoff / fail
 replica C ──SET NX PX──▶ │ lock:<key> │  nil  ──▶ stale / backoff / fail
                          └────────────┘

The lock TTL must exceed the worst-case recompute time, not the average. If the lock expires while the holder is still working, a second replica acquires it and the duplicate work slips through. The TTL also bounds failure: if the holder crashes, no replica can refresh the key until the lock lapses. Every miss also pays an extra round trip to acquire the lock.

Copyimport time, uuid
import redis

r = redis.Redis(host="localhost", port=6379)

LOCK_TTL_MS = 5000  # must exceed WORST-case recompute time, not the average

# Release the lock only if we still own it (token match), atomically,
# so a slow holder never deletes a lock another replica now holds.
RELEASE = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
  return redis.call('DEL', KEYS[1])
end
return 0
"""

def get_or_recompute(key, recompute, ttl_s=300, attempts=5):
    value = r.get(key)
    if value is not None:
        return value
    token = uuid.uuid4().hex
    # SET NX PX: one replica wins; expiry bounds how long a crashed holder blocks refresh
    if r.set(f"lock:{key}", token, nx=True, px=LOCK_TTL_MS):
        try:
            value = recompute()  # hits the backing store
            r.set(key, value, ex=ttl_s)
            return value
        finally:
            r.eval(RELEASE, 1, f"lock:{key}", token)
    # Loser: wait with bounded exponential backoff, re-reading the value key
    delay = 0.05
    for _ in range(attempts):
        time.sleep(delay)
        value = r.get(key)
        if value is not None:
            return value
        delay = min(delay * 2, 0.5)
    # Fail fast once the backoff budget is spent
    raise TimeoutError(f"{key} not refreshed within backoff budget")

A redis-py cross-replica lock using SET NX PX, a token-checked release, and losers that wait with bounded backoff before failing fast.

Probabilistic early expiration and stale-while-revalidate

Locks coordinate the stampede after it starts. Probabilistic early expiration aims to avoid the simultaneous miss altogether. In the XFetch approach, each cached value is stored in an envelope with three fields: value, delta (how long the last recompute took), and expiry (an absolute timestamp). On every read, a caller recomputes early if now - delta * beta * ln(rand()) >= expiry, where rand() is uniform on (0, 1].

Because ln(rand()) is negative, the term pushes now forward by a random, exponentially distributed margin. Most readers see a small margin and serve the cached value. As expiry approaches, the chance that one reader crosses the threshold rises, so a single caller usually refreshes before the others notice.

beta scales that margin. With beta = 1 the behavior is neutral. Values above 1 refresh earlier, and values below 1 refresh later. Multiplying by delta gives expensive keys a proportionally larger head start, so a recompute that takes two seconds begins early enough to finish before expiry.

The approach has costs:

• Steady-state load: recompute volume rises even when nothing is wrong.
• beta too high: refreshes run so early that the work is mostly wasted.
• beta too low: the margin shrinks and stampedes return.
• Cold keys: there is no protection, because there is no envelope to read yet.
• Payload and format: values grow, and the serialization format must be versioned.
• Skewed delta: a GC pause or a noisy neighbor can inflate one measurement and distort later refresh timing.

Stale-while-revalidate

This pattern stores two deadlines. Before the soft TTL, reads are fresh. Between the soft TTL and the hard TTL, readers get the stale value while exactly one background refresh runs, usually guarded by the lease from the previous section. After the hard TTL, the read is a true miss. The hard TTL is the upper bound on staleness.

Do not serve stale reads for authorization, pricing, or inventory decisions unless writes explicitly invalidate the key. A revoked permission or an oversold item is a correctness bug, not a latency problem.

Copyimport json
import math
import random
import time

ENVELOPE_VERSION = 1  # bump when the envelope layout changes

def make_envelope(value, delta_s, ttl_s):
    # Store the recompute cost (delta) and an absolute expiry beside the value.
    return json.dumps({
        "v": ENVELOPE_VERSION,
        "value": value,
        "delta": delta_s,             # seconds the last recompute took
        "expiry": time.time() + ttl_s,  # absolute Unix timestamp
    })

def should_refresh_early(env, beta=1.0, now=None):
    now = time.time() if now is None else now
    # 1.0 - random() lies in (0, 1], so ln() never sees zero.
    r = 1.0 - random.random()
    # ln(r) <= 0, so this moves 'now' forward by a random margin
    # that scales with delta (cost) and beta (aggressiveness).
    return now - env["delta"] * beta * math.log(r) >= env["expiry"]

def get(cache, key, recompute, ttl_s=300, beta=1.0):
    raw = cache.get(key)
    env = json.loads(raw) if raw else None
    if env and env.get("v") != ENVELOPE_VERSION:
        env = None  # unknown format: treat as a miss
    # Cold keys (env is None) get no protection from XFetch.
    if env is None or should_refresh_early(env, beta):
        start = time.monotonic()
        value = recompute()
        delta = time.monotonic() - start  # a GC pause here inflates delta
        cache.set(key, make_envelope(value, delta, ttl_s))
        return value
    return env["value"]

A versioned XFetch envelope that stores value, delta, and absolute expiry, plus the probabilistic check now - delta * beta * ln(rand()) >= expiry that lets one reader refresh early, with expensive keys starting earlier.

TTL jitter, warmup, and other alternatives

Even before any of the above, add jitter to every TTL. Keys written together, such as a batch import or a cache filled right after a deploy, otherwise expire at the same moment and miss in a burst. Setting each TTL to the base value plus or minus a random 10–20% spreads those expiries over a window. It costs one line and has no runtime overhead. It does nothing for a single hot key, though. That key still expires at one instant, and every concurrent reader misses together. Jitter decides when the herd forms, not whether it forms.

No technique survives a full cold start, a flushed cluster, or a failover to an empty replica. Every key misses at once, and coalescing only reduces that to one request per key. Three backstops cover this case:

• Warmup: preload the known hot keys before the instance takes traffic.
• Backing-store limits: cap concurrent queries to the database with a semaphore or connection pool limit, so excess misses queue or fail instead of piling onto the store.
• Load shedding: reject low-priority requests early when latency or queue depth crosses a threshold.

Copyimport asyncio
import random

BASE_TTL = 300        # seconds
JITTER = 0.15         # +/-15% spreads expiry of keys written together
DB_SLOTS = asyncio.Semaphore(20)  # cap on concurrent backing-store queries
QUEUE_TIMEOUT = 0.5   # seconds a miss may wait for a slot before being shed


class Overloaded(Exception):
    """Raised when the store is saturated; callers map this to a 503."""


def jittered_ttl(base=BASE_TTL, jitter=JITTER):
    # One line of protection against batch-written keys expiring in lockstep.
    # It does not help a single hot key, which still expires at one instant.
    return int(base * random.uniform(1 - jitter, 1 + jitter))


async def load(key, query, cache):
    # Backing-store limit + load shedding: excess misses wait briefly,
    # then fail fast instead of piling onto the database.
    try:
        await asyncio.wait_for(DB_SLOTS.acquire(), timeout=QUEUE_TIMEOUT)
    except asyncio.TimeoutError:
        raise Overloaded(key)
    try:
        value = await query(key)
    finally:
        DB_SLOTS.release()
    await cache.set(key, value, ttl=jittered_ttl())  # placeholder cache client
    return value


async def warmup(hot_keys, query, cache):
    # Preload known hot keys before the instance takes traffic. The same
    # semaphore bounds the boot burst; failures are tolerated, not fatal.
    results = await asyncio.gather(
        *(load(k, query, cache) for k in hot_keys), return_exceptions=True
    )
    return sum(1 for r in results if not isinstance(r, Exception))

A minimal asyncio sketch that combines jittered TTLs with a semaphore-bounded backing-store limit that sheds load on timeout, and reuses that limit to keep a boot-time warmup of hot keys from overwhelming the database.

Choosing a combination: who needs which layer and when to avoid each

Start from three questions: how skewed is key popularity, how expensive is one recompute, and how wrong can a response be for a few seconds. The answers map to a small number of combinations.

Teams with expensive recomputes or highly skewed popularity benefit most. For them, one popular key expiring can trigger a full herd, and each extra recompute is costly.

Skip the distributed lock when replica count is low and misses are cheap. With few replicas, single-flight already caps duplicates at roughly one per replica, so the lock adds a network round trip and a new failure mode for little gain. Skip early expiry on long-tail cold keys. Those keys are rarely read near their expiry, so an early refresh is mostly wasted work on data nobody will request. Skip stale serving for correctness-critical data such as balances, permissions, or inventory counts. In those cases a fast wrong answer is worse than a slow correct one.

These layers interact, so be careful when you stack them. Early refresh fires before expiry, but it can still hit lock contention. Callers that lose the lock may fall back to stale data or retry. Jitter then spreads expiries, which can turn one spike into a sustained trickle of refreshes with backoffs between attempts. Load-test the combination, not each layer in isolation.

Measuring, load-testing, and the cost in engineering time

What to instrument

• Miss rate per key. Use the hottest keys, not a global average. A 2% overall miss rate can hide one key that drives most backing-store load.
• Recompute concurrency. Track how many loads for the same key run at once. Coalescing should hold this at one per process.
• Backing-store QPS during expiry windows. Line this up with TTL boundaries.
• Lock contention. Count acquisition failures, wait time, and lease expiries before release.
• Served-stale counts. These show how often users actually got stale data.

Load-test before trusting anything

Start with a hot key under concurrent load and force it to expire. Then flush the whole cache. Then kill a cache node mid-test. Run each scenario with no protection, then add each layer one at a time and compare backing-store QPS.

Illustrative estimate (assumed numbers, not a benchmark):

Backing-store calls per expiry ≈ replicas × per-replica QPS for the key × recompute seconds

With 20 replicas, 50 QPS per replica, and 0.4 s recompute, that is 20 × 50 × 0.4 = 400 calls. In-process coalescing caps it at 20, one per replica.

If the store absorbs 20 concurrent calls easily, you do not need a distributed lock.

Engineering cost

Each layer adds code paths. Stale-while-revalidate needs stored timestamps, which changes serialization formats. Locks need tests for lease timeouts and holders that crash. On-call engineers also have to reason about more states during an incident.

Measure miss cost and key popularity first. Those numbers often show that coalescing plus jitter is enough. They also give you a baseline, which makes it faster to tell a stampede from an ordinary slow dependency during an incident.

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.
• The dependency graph answers "what does this touch?" in seconds instead of a manual audit.

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.
• You can size a change's blast radius before merging, avoiding surprise cross-team firefighting.
• 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.