Cache stampedes: what happens when a hot key expires

A page or a query result is cached for five minutes and is requested a hundred times a second. Most of the time the cache hides a slow database query. At the moment the key expires, every request in flight misses, and all of them run the slow query together. The database, which the cache was protecting, takes the whole burst at once.

Why it is worse than it sounds

The burst is proportional to traffic on that key, and the recomputation takes the longest exactly when the database is loaded. If the recomputation takes two seconds and the request rate is a hundred a second, two hundred identical queries run in parallel. They slow each other down, which makes the recomputation take longer, which lets more requests pile up. Systems have gone down from one expired key.

Techniques

Spread out expiry times. If many keys are created together (a deployment that warms a cache, a cron job that fills it), give each a TTL with random jitter, for example ttl = base + random(0, base * 0.1). They no longer expire in the same second.

Let only one request recompute. Take a short lock with an atomic command and let the others wait or use an old value:

The lock needs an expiry, or a crashed worker leaves it held forever. Release it only if you still own it: store a random token as the value, and delete with a small Lua script that compares the token first, so that a slow worker whose lock has expired does not delete someone else's.

Serve stale while refreshing. Store the value with a soft expiry inside it and a longer hard TTL on the key. After the soft expiry, the first request refreshes in the background while everyone else keeps getting the slightly old value. Users almost never wait for a recomputation.

Refresh early, probabilistically. Each reader that finds the value close to expiry has a small chance of refreshing it before it actually expires, and the chance rises as the deadline approaches and as the recomputation cost grows. The scheme was described in a 2015 paper (Vattani, Chierichetti and Lowenstein, "Optimal Probabilistic Cache Stampede Prevention") and needs no locks.

What not to assume

Helpers such as Django's cache.get_or_set fetch and store, but on their own do not stop several processes from computing the value at the same moment. Check what your library actually does under concurrency.

Also useful

• Cache the negative result ("no such record") with a shorter TTL, otherwise requests for missing keys always reach the database.
• Bound concurrency at the database itself, with a connection pool and a statement timeout, so that even a stampede cannot use every connection.
• Measure the hit rate and recomputation time of your hottest keys. The first few keys usually decide how your system behaves.

A second layer, inside the process itself

Everything above coordinates across separate worker processes through Redis. A complementary technique works entirely inside one process, for the specific case of many concurrent requests to the same worker asking for the same missing key at nearly the same moment: keep an in-memory dictionary of keys currently being computed, mapped to a future or event other coroutines can await, so that the second and further concurrent callers inside that one process attach to the first caller's in-flight computation instead of starting their own, even before any of them touch Redis.

_inflight = {}

async def get_cached(key):
    value = await redis.get(key)
    if value is not None:
        return value
    if key in _inflight:
        return await _inflight[key]           # attach to the request already running
    _inflight[key] = asyncio.ensure_future(compute_and_store(key))
    try:
        return await _inflight[key]
    finally:
        _inflight.pop(key, None)

This collapses concurrency within a single process to one caller, which reduces how many processes ever reach the Redis-level lock in the first place, and it is a natural complement to the distributed lock above rather than a replacement for it, since it does nothing for the many separate worker processes each making their own single request to Redis at the same moment.