Chapter 5: Caching for Scale: Cache Stampede and Invalidation at Scale

Why this matters

Caching is one of the highest-leverage scaling tools available, and also one of the most common sources of a specific, severe failure mode: a cache that's supposed to protect a backend system from load can, under the wrong conditions, cause a sudden, catastrophic overload of that exact backend — precisely when the cache is needed most. This chapter treats cache stampede as a reliability failure mode in its own right, not just a performance edge case.

Cache stampede, precisely, and why it gets worse at real scale

[BEGINNER] Already introduced conceptually in the companion OOP, Networking, and Database books (thundering herd): a cache stampede occurs when a popular cache entry expires (or the cache itself restarts, losing all entries at once) and a large number of concurrent requests all simultaneously discover the miss and all hit the backend simultaneously to regenerate it. At real production scale, this isn't a rare edge case — it's a near-certainty for any sufficiently popular cached value with a fixed expiration, and the backend overload it causes can be severe enough to cause a genuine outage, not just a brief slowdown.

At small scale: a cache miss on a moderately popular item causes maybe
                 a dozen concurrent requests to hit the backend --
                 manageable, barely noticeable.

At large scale: a cache miss on a HIGHLY popular item (a trending
                 product, a viral post) can cause THOUSANDS of
                 concurrent requests to hit the backend simultaneously
                 -- easily enough to overwhelm a backend that was
                 never provisioned to handle that much direct load,
                 since the cache's entire purpose was avoiding exactly this.

Preventing stampede: beyond the basic single-flight lock

[SENIOR INSIGHT] The companion Database book's Chapter 12 covered the basic single-flight/locking pattern (only one request regenerates, others wait). At real scale, two additional techniques are worth adding:

Probabilistic early expiration: instead of every request treating a cache entry as fully valid until its exact expiration instant, have requests probabilistically decide to proactively regenerate the value slightly before it actually expires — with the probability increasing as the entry approaches its expiration time. This spreads regeneration load out over a window of time instead of concentrating it all at the exact expiration instant, which is precisely what causes the stampede in the first place.

import random
import time

def should_proactively_refresh(cached_at: float, ttl: float, beta: float = 1.0) -> bool:
    """XFetch-style probabilistic early expiration: probability of
    proactive refresh increases as the entry approaches its TTL."""
    delta = time.time() - cached_at
    # As delta approaches ttl, this becomes increasingly likely to return True --
    # different requests will "decide" to refresh at different, spread-out moments,
    # rather than ALL requests waiting until the exact same expiration instant.
    return random.random() < (delta / ttl) ** beta

Never-expire, background-refresh caching: for extremely hot, critical data, some systems deliberately never let the cache entry expire from the client's perspective at all — instead, a background process refreshes it proactively on a schedule, and if that background refresh ever fails, the cache continues serving the last-known (now stale) value indefinitely rather than ever falling through to an uncached, direct backend hit. This trades some staleness tolerance for eliminating the stampede risk entirely for the specific, most business-critical cached values.

Cache invalidation and the cache's own reliability as a dependency

[IN PRACTICE] A cache introduces a genuine, new reliability dependency of its own: if the cache infrastructure itself fails entirely (not just a single key expiring, but the whole cache cluster becoming unavailable), every request that was relying on cache hits suddenly falls through to the backend simultaneously — this is a cache-cluster-wide stampede, the same fundamental problem as a single-key stampede, just triggered by infrastructure failure rather than TTL expiration. This is precisely why a cache's own reliability (its redundancy, per Chapter 3, and its failure mode) needs to be designed with the same seriousness as the primary system it's protecting — a cache that "can't fail because it's just a cache" is a dangerous, common misconception; a cache failing can cause a worse outage than not having a cache at all, specifically because the backend was sized assuming the cache's protection would always be present.

Common mistakes

1. Assuming a basic single-flight lock is sufficient protection at any scale, missing that extremely popular items at real production scale may need additional techniques (probabilistic early expiration, never-expire background refresh) to avoid concentrated regeneration load even with locking in place.
2. Not considering what happens if the cache infrastructure itself fails entirely, missing that this produces the same stampede dynamic at a much larger, cluster-wide scale — precisely when the backend is least prepared to absorb the sudden, full load.
3. Sizing the backend assuming the cache will always be present and effective, rather than explicitly considering (and testing, per Chapter 10) what happens to backend load if the cache's protection disappears.
4. Using a fixed TTL for extremely popular cache entries without probabilistic spreading, guaranteeing that regeneration load concentrates at the exact expiration instant rather than being spread across a window.

Discussion / interview questions

1. "Why does a cache stampede get worse, not just proportionally larger, as a system scales up?" Strong answer: At larger scale, a popular cached item can have orders of magnitude more concurrent requests hitting it during a miss window, and the backend (sized assuming the cache absorbs most load) is even less prepared to handle that sudden direct load than it would be at smaller scale — the mismatch between expected (cached) and actual (stampede) backend load grows with scale.

2. "What is probabilistic early expiration, and how does it help prevent cache stampede?" Strong answer: Instead of every request treating a cache entry as valid until its exact TTL expiration, requests probabilistically decide to proactively refresh slightly before expiration, with probability increasing closer to the deadline — this spreads regeneration load across a time window rather than concentrating it all at one instant.

3. "What happens to a system's backend if its entire caching layer fails, and why is this a serious reliability concern?" Strong answer: Every request that would have hit the cache instead falls through to the backend simultaneously — a cluster-wide stampede, the same fundamental problem as a single-key stampede but at a much larger scale, precisely when the backend (sized assuming cache protection) is least prepared to absorb the full, un-cached load.

4. "Should a cache's own infrastructure reliability be taken as seriously as the primary system it's protecting?" Strong answer: Yes — treating a cache as something that "can't really fail because it's just a cache" is a dangerous misconception; a cache failure can cause a worse outage than having no cache at all, specifically because the backend was never sized to handle direct load at that scale, making the cache's own redundancy and failure mode a genuine reliability design concern.

Chapter summary / cheat sheet

• Cache stampede — many concurrent requests regenerating the same expired entry simultaneously — becomes a genuine outage risk, not just an edge case, at real production scale for popular items.
• Beyond single-flight locking: probabilistic early expiration spreads regeneration load across a time window; never-expire background-refresh caching eliminates stampede risk entirely for the most business-critical cached values, at the cost of tolerating more staleness.
• A cache-cluster-wide failure causes the same stampede dynamic at a much larger scale — the cache's own infrastructure reliability deserves the same design seriousness as the primary system it protects.
• Never assume a backend can absorb its full, un-cached load "just in case" — explicitly consider and test (Chapter 10) what happens if the cache's protection disappears.

---