backend / caching / redis / 02_cache_stampede.md

Cache Stampede and Mitigation Patterns

6 interview angles 6 min read source

Cache Stampede and Mitigation Patterns

A.k.a. dogpile, thundering herd. When a hot key expires, every concurrent request misses the cache and hits the origin simultaneously. Origin overloads; sometimes crashes. Cache-aside is correct in theory and catastrophic in this one specific case.

The setup

def get_user_profile(user_id):
    key = f"profile:{user_id}"
    cached = r.get(key)
    if cached:
        return json.loads(cached)
    profile = expensive_db_query(user_id)        # 200ms, hits DB hard
    r.setex(key, 300, json.dumps(profile))       # 5 min TTL
    return profile

Steady state: 1000 RPS, 99.9% cache hit. DB sees 1 read every few seconds.

At second t=300, the cache entry expires. Between t=300 and t=300.005, 1000 incoming requests miss the cache and all kick off expensive_db_query. DB load spikes 1000×.

For a moderately hot cache, this is a problem. For a viral celebrity-profile workload, it’s an outage.

Pattern 1: probabilistic early expiration (XFetch)

Recompute before the cache expires, with rising probability as you approach expiry. Most requests still hit the cache; one of them refreshes early.

import random
import math
import time

BETA = 1.0   # tuning constant

def get_with_xfetch(key, compute, ttl=300):
    raw = r.get(key)
    if raw is None:
        return _refresh(key, compute, ttl)

    obj = json.loads(raw)
    delta = obj["delta"]             # compute time, recorded at last refresh
    expiry = obj["expiry"]           # epoch when this entry expires
    now = time.time()

    # Probability of refreshing: rises as we approach expiry
    if now - delta * BETA * math.log(random.random()) >= expiry:
        return _refresh(key, compute, ttl)
    return obj["value"]

def _refresh(key, compute, ttl):
    start = time.time()
    value = compute()
    delta = time.time() - start
    expiry = time.time() + ttl
    r.setex(key, ttl, json.dumps({"value": value, "delta": delta, "expiry": expiry}))
    return value

Why it works: the closer to expiry, the more likely a given request decides “refresh now”. Only one or two requests actually trigger the refresh; the rest serve stale-but-acceptable. Worst case bounded.

Paper: “Optimal Probabilistic Cache Stampede Prevention” (Vattani et al.).

Pattern 2: singleflight / request coalescing

Lock the recompute so only one request runs it; others wait for the result.

import threading
locks = {}            # in-process
lock_factory_lock = threading.Lock()

def get_singleflight(key, compute, ttl=300):
    cached = r.get(key)
    if cached:
        return json.loads(cached)

    with lock_factory_lock:
        lock = locks.setdefault(key, threading.Lock())

    with lock:
        # Check again — another thread may have populated it
        cached = r.get(key)
        if cached:
            return json.loads(cached)
        value = compute()
        r.setex(key, ttl, json.dumps(value))
        return value

Within one process, only one thread runs the compute. Good in a single process.

For multi-process / multi-pod, the lock must be distributed:

def get_with_redis_lock(key, compute, ttl=300):
    cached = r.get(key)
    if cached:
        return json.loads(cached)

    lock_key = f"lock:{key}"
    # Try to acquire the lock
    if r.set(lock_key, "1", nx=True, ex=30):
        try:
            value = compute()
            r.setex(key, ttl, json.dumps(value))
            return value
        finally:
            r.delete(lock_key)
    else:
        # Someone else is computing; poll briefly or serve stale
        for _ in range(10):
            time.sleep(0.05)
            cached = r.get(key)
            if cached:
                return json.loads(cached)
        # Fallback: just hit origin yourself (better than infinite wait)
        return compute()

The Go community has singleflight package. Python doesn’t have a stdlib equivalent; roll your own or use cachetools patterns.

Pattern 3: stale-while-revalidate

Serve the stale value, refresh in the background. Users always get an answer; the cache eventually catches up.

def get_swr(key, compute, ttl=300, stale_ttl=600):
    entry = r.get(key)
    if not entry:
        return _refresh(key, compute, ttl)

    obj = json.loads(entry)
    now = time.time()
    if now < obj["expiry"]:
        return obj["value"]                                  # fresh

    # Stale but within stale window
    if now < obj["expiry"] + stale_ttl:
        # Trigger background refresh (best-effort)
        threading.Thread(target=_refresh, args=(key, compute, ttl), daemon=True).start()
        return obj["value"]                                  # serve stale

    # Truly expired
    return _refresh(key, compute, ttl)

HTTP Cache-Control: stale-while-revalidate=60 is the same idea at the HTTP level — CloudFront and CDNs support it natively.

Pattern 4: external pre-computation

Don’t lazy-cache. A background job updates the cache on a schedule.

# In a Celery beat / cron
@app.task
def refresh_top_profiles():
    for user_id in top_users():
        profile = expensive_db_query(user_id)
        r.setex(f"profile:{user_id}", 600, json.dumps(profile))

Cache always populated; requests always hit. Works when:

  • You know the hot keys in advance.
  • You can afford to refresh ALL hot keys regularly.
  • Source data updates aren’t more frequent than your refresh interval.

The pattern behind Spotify-style “Daily Mix” — pre-computed nightly per user.

Pattern 5: jittered TTL

For caches with many keys all set at similar times (mass invalidation after a deploy), add randomness:

ttl = base_ttl + random.randint(0, base_ttl // 10)   # 10% jitter
r.setex(key, ttl, value)

Spreads expiry over time; no synchronized stampede on the entire cache fleet at once.

What about the very first miss?

A brand-new cache (e.g., after deploy) is cold. Every request misses. If you have 100 RPS and 5s queries, you’re queuing 500 simultaneous queries to origin. Even singleflight per-key won’t help if every key is different.

Fixes:

  • Warm-up phase — replay top N keys before accepting traffic.
  • Capacity headroom — origin can handle the surge briefly.
  • Rate limit at the edge — gateway throttles requests during warm-up.
  • Gradual rollout — slow ramp-up, cache populates organically.

Don’t forget: cache failure mode

When Redis itself dies, your cache hit rate goes to 0. If your DB can’t handle 100% of traffic, you have a cache-induced outage. Plan:

  • Soft fail on Redis errors — return DB result without caching; log the failure.
  • Circuit-breaker the cache — temporarily skip cache lookups under sustained errors.
  • Capacity — origin must absorb a brief 100% miss rate.

Real-world common combinations

For a typical caching layer in front of a Postgres DB:

  1. TTL with jitter — avoid synchronized expiry.
  2. Singleflight via Redis lock — coalesce concurrent rebuilds.
  3. Background refresh for known-hot keys — top N by traffic, refreshed by cron.
  4. Soft-fail on Redis errors — never block on cache.
  5. DB headroom for at-least 50% miss rate — sane disaster recovery.

Interview angle

  • “What’s a cache stampede and what causes it?” — a hot key expires; many concurrent requests all miss simultaneously and hit the origin. Spike load on the origin (often hundreds or thousands of times normal) for the few milliseconds until the cache repopulates.
  • “How do you prevent it?” — several techniques: (a) probabilistic early expiration (XFetch) — refresh probabilistically as you approach TTL; (b) singleflight / request coalescing — one rebuild via distributed lock, others wait; (c) stale-while-revalidate — serve stale and refresh in background; (d) pre-compute hot keys via background job; (e) jittered TTLs to avoid synchronized expiry. Usually combine 2-3.
  • “How would you implement singleflight with Redis?” — SET lock:KEY 1 NX EX 30 to claim the rebuild. Winner runs the compute and populates the cache. Losers poll briefly for the new value or fall back to direct origin. Use a short lock TTL so a crashed rebuilder doesn’t lock indefinitely.
  • “What’s stale-while-revalidate?” — serve the expired value for up to N seconds while a background task refreshes the cache. Users never wait on a cold cache; staleness is bounded. HTTP Cache-Control: stale-while-revalidate=N is the same pattern at the CDN level.
  • “What happens to your service if Redis goes down?” — depends on the design. Cache-aside soft-failing means full DB load; your DB must absorb 100% miss rate or you’ve created a coupled outage. Always design for cache-down scenarios with circuit breakers and origin capacity headroom.
  • “What’s XFetch?” — algorithm where each request computes now - delta * BETA * log(random()) against the expiry; closer to expiry, more likely to refresh. Probability-weighted singleflight without an actual lock. Paper: Vattani et al., “Optimal Probabilistic Cache Stampede Prevention”.
Previous
What is Redis?