Skip to content

Preventing Cache Stampedes in asyncio

A cache stampede is what happens when a popular key expires: every request that was being served from cache misses simultaneously, and all of them call the origin. Measured with 50 concurrent requests for one key whose rebuild takes 200 ms, the unprotected version made 50 origin calls; with a per-key lock, one. An async service makes this worse than a threaded one, because thousands of requests can be in flight on one loop — the concurrency that makes asyncio fast is exactly the concurrency that turns one expiry into a thundering herd. This guide measures four tactics, including one that made things worse.

Prerequisites

Origin calls for 50 simultaneous cache misses 2 bars comparing no protection with the others. Origin calls for 50 simultaneous cache misses no protection 50 origin calls per-key lock 1 origin call Fifty concurrent requests for one key whose rebuild takes 200 ms. One lock per key turns a stampede into a single rebuild that everyone waits on.

1. Add a per-key lock and double-check

The fix that does most of the work is one lock per key, with a second cache read after acquiring it:

_locks: dict[str, asyncio.Lock] = {}


async def get_or_build(redis, key: str, ttl: int = 60):
    value = await redis.get(key)
    if value is not None:
        return value
    lock = _locks.setdefault(key, asyncio.Lock())
    async with lock:
        value = await redis.get(key)                   # the winner may have filled it
        if value is not None:
            return value
        value = await build(key)
        await redis.set(key, value, ex=ttl)
        return value

Verified: 50 concurrent misses produced 1 origin call rather than 50, at the same wall-clock cost (0.21 s vs 0.20 s), because the 49 waiters are waiting on a lock rather than on the origin.

The double-check is not optional. Without it, every task that queued on the lock rebuilds in turn, and you have serialised the stampede rather than eliminated it.

One detail for long-lived services: _locks grows with every key ever requested. Bound it — an LRU dictionary, or removing the entry when no waiters remain — or the lock table becomes the memory leak that the cache was supposed to prevent.

Verify: count origin calls under concurrent misses; it should be one per key per TTL.

2. Know that early expiry alone can make it worse

Probabilistic early expiration — recompute slightly before the TTL, with a probability that rises as expiry approaches — is the textbook refinement. Applied without a lock, it made things worse:

20 readers over 1.5 s with a 1 s TTL (lock only):  2 origin calls
same load with probabilistic early expiry:        28 origin calls

The reason is obvious in hindsight: the whole point of early expiry is that several readers may decide to refresh, and nothing stopped all of them from doing so. It is a way to avoid the moment where everyone misses at once — not a substitute for deduplicating the rebuild.

Combined with the lock it behaves, at a cost: 4 origin calls over the same run instead of 2, buying a smaller chance that a reader arrives at the instant the key is gone. Whether that trade is worth it depends on whether your readers can tolerate waiting for one rebuild.

Verify: measure origin calls before and after adding early expiry; if they rise, the deduplication is missing.

Four tactics, and what each actually buys A grid of 4 rows by 2 columns. Four tactics, and what each actually buys tactic origin calls reader latency per-key lock 50 -> 1 on a cold miss everyone waits for the rebuild early expiry, no lock 2 -> 28: worse no improvement stale-while-revalidate 3 over the same run p50 0.76 ms after warm-up negative caching stops repeated misses fast failures instead of slow Measured on the same workload: the lock is the big win, and early expiry needs it too.

3. Serve stale while refreshing in the background

The tactic that actually removes reader latency is to stop making readers wait at all. Keep two horizons — a soft expiry after which the value is stale but usable, and the real TTL — and refresh in a background task:

async def stale_while_revalidate(redis, key, ttl=60, soft=30):
    value, fresh_until = await redis.mget(key, f"{key}:fresh_until")
    if value is None:
        async with lock_for(key):                      # cold start: someone must wait
            value = await redis.get(key)
            if value is None:
                value = await build_and_store(redis, key, ttl, soft)
        return value

    if float(fresh_until or 0) < time.time() and not lock_for(key).locked():
        task = asyncio.create_task(refresh(redis, key, ttl, soft))     # nobody waits
        _refresh_tasks.add(task)
        task.add_done_callback(_refresh_tasks.discard)
    return value                                       # stale, but immediate

Measured over the same workload: 3 origin calls, p50 of 0.76 ms per read. The p99 stayed at 203 ms, which is exactly the cold start — twenty readers arriving before anything was cached. After that first fill, no reader ever waited for a rebuild again.

Two requirements. The refresh task must be tracked, or it can be garbage collected or discarded at shutdown, as covered in running background tasks safely. And the application must tolerate data up to ttl - soft old — which is a product decision, not a technical one.

Verify: after warm-up, read latency is the cache's own latency regardless of refreshes.

Stale-while-revalidate in one key’s life 3 lanes over time. Stale-while-revalidate in one key’s life cache entry fresh stale but served fresh again readers always answered immediately refresh task one rebuild, in the background time → Only the cold start blocks: measured p50 was 0.76 ms with refreshes happening throughout.

4. Cache the misses too

A key that does not exist is the stampede nobody plans for: every request misses, every request calls the origin, and the origin returns "not found" every time. Negative caching fixes it with a shorter TTL:

NEGATIVE = object()

value = await redis.get(key)
if value == b"\x00miss":
    raise NotFound(key)                                # cached absence
if value is None:
    result = await build(key)
    if result is None:
        await redis.set(key, b"\x00miss", ex=NEGATIVE_TTL)   # much shorter than the real TTL
        raise NotFound(key)

Keep the negative TTL short — seconds, not minutes — so a key that appears becomes visible quickly. This matters most for user-supplied identifiers, where a scan of random ids is otherwise a direct path to your database, and it pairs naturally with the retry budget idea: absences are cheap to remember and expensive to recompute.

Verify: repeated requests for a non-existent key produce one origin call per negative TTL.

5. Spread the expiries

Everything above protects one key. The fleet-level version of the same problem is many keys expiring together — after a deploy that warms a cache, or because everything was written in one batch with the same TTL. The fix is jitter at write time:

await redis.set(key, value, ex=int(ttl * random.uniform(0.9, 1.1)))

Ten percent of jitter turns a synchronised wall of expiries into a smooth trickle, and costs nothing. The same reasoning applies to scheduled cache warms: stagger them across instances rather than running them all at the top of the minute, for exactly the reasons described in scheduling cron jobs inside an asyncio service.

Verify: a histogram of key TTLs is spread rather than spiked.

Which protection does this key need? A decision on What does a rebuild cost with 3 outcomes. Which protection does this key need? What does a rebuild cost? cheap, and freshness matters a per-key lock simplest thing that works expensive, stale is fine stale-while-revalidate readers never wait expensive, stale is not fine lock plus early refresh accept some extra rebuilds Start with the lock; add the rest only when a measurement says the lock is not enough.

Verification

Stampede protection works when:

  • Concurrent misses produce one origin call per key, measured.
  • The lock table is bounded, not growing with every key ever seen.
  • Early expiry is paired with deduplication, or left out.
  • Refresh tasks are tracked and cancelled at shutdown.
  • Absences are cached with a short TTL.
  • TTLs carry jitter so keys do not expire in unison.

Pitfalls & edge cases

  • Forgetting the double-check after the lock. Each waiter rebuilds in turn — the stampede, serialised.
  • A global lock instead of per-key. One slow rebuild blocks every unrelated key.
  • Per-process locks only. With N instances you get N rebuilds; a Redis lock makes it one, at the cost of a round trip.
  • Unbounded lock dictionaries. A memory leak keyed by everything your service has ever been asked for.
  • Serving stale without saying so. Downstream code that assumes freshness will be wrong; expose the age.
  • Caching exceptions. A transient failure cached for the full TTL turns a blip into an outage; cache absences, not errors.

Frequently Asked Questions

What is a cache stampede?

The pattern where a popular cache key expires and every concurrent request misses at once, so all of them call the origin. Measured with 50 concurrent requests for one 200 ms rebuild, the unprotected version made 50 origin calls; a per-key lock reduced that to one.

How do I prevent a cache stampede in asyncio?

Give each key an asyncio.Lock, and re-read the cache after acquiring it so waiters use the value the winner stored. That alone takes concurrent misses from N origin calls to one. Bound the lock dictionary so it does not grow with every key seen.

Does probabilistic early expiration help?

Only alongside deduplication. On its own it made things worse in testing — 28 origin calls against 2 for a plain lock — because it invites several readers to refresh and nothing stops them all doing so. Combined with a lock it cost 4 calls instead of 2, buying a smaller chance of a hard miss.

What is stale-while-revalidate and when should I use it?

Serving the cached value past a soft expiry while a single background task refreshes it. Readers never wait for a rebuild: measured p50 was 0.76 ms, with the only slow reads being the cold start. Use it when data slightly out of date is acceptable, which is most read-heavy caching.

Should I cache negative results?

Yes, with a much shorter TTL than positive entries. Without it, repeated requests for a missing key are an uncached path straight to the origin — which is exactly what a scan of random identifiers produces. Seconds of negative TTL are usually enough.