Cache Stampede: The Thundering Herd

The Problem

You have a very popular piece of data cached — say, the homepage configuration for an e-commerce site, which takes 2 seconds to compute from the database. It has a TTL of 1 hour.

At exactly 10:00 AM, the TTL expires. The entry vanishes from the cache.

At 10:00:00.001 AM, 5,000 simultaneous users request the homepage:
1. All 5,000 requests check the cache at the same instant.
2. All 5,000 get a Cache Miss.
3. All 5,000 simultaneously turn and fire the expensive 2-second query at the database.
4. The database, suddenly receiving 5,000 concurrent copies of the same expensive query, is overwhelmed. Response times spike. Other queries are starved. The database may crash entirely.

This simultaneous rush triggered by a single cache expiration is called a Cache Stampede or Thundering Herd. It is particularly dangerous because it is self-reinforcing: the database slowdown means the cache repopulation takes longer, which means more requests pile up waiting, which makes the database even slower.

The Solutions

1. Mutex Locking (Cache Lock)
When a cache miss occurs, before querying the database, the application tries to acquire a distributed lock for that specific cache key. Only the first request acquires the lock and queries the database. All other requests either wait briefly and then read the freshly populated cache value, or serve a slightly stale value if one is available.

import redis
import time

r = redis.Redis()
LOCK_KEY = "lock:homepage_config"
CACHE_KEY = "homepage_config"

def get_homepage_config():
    cached = r.get(CACHE_KEY)
    if cached:
        return cached

    # Try to acquire lock (NX = only set if not exists, EX = expire in 5s)
    lock_acquired = r.set(LOCK_KEY, "1", nx=True, ex=5)
    if lock_acquired:
        try:
            result = expensive_db_query()
            r.set(CACHE_KEY, result, ex=3600)
            return result
        finally:
            r.delete(LOCK_KEY)
    else:
        # Another process is refreshing — wait briefly and retry
        time.sleep(0.1)
        return r.get(CACHE_KEY)

2. Probabilistic Early Expiration (PER)
Instead of waiting until the exact TTL expiry, the application starts probabilistically triggering a cache refresh before the TTL expires. As the remaining TTL shrinks, the probability of triggering an early refresh increases. This means a single background request refreshes the cache while the old value is still being served to everyone else — the stampede never happens because the cache is never actually empty.

The formula used in the XFetch algorithm: a refresh is triggered early if current_time - (beta * log(random())) >= expiry_time, where beta controls aggressiveness.

3. Staggered TTLs
If you have many cache keys that are all populated at the same time (e.g., during a cache warm-up after a restart), add a small random jitter to each TTL so they don't all expire simultaneously:

import random
base_ttl = 3600
jitter = random.randint(0, 300)  # 0 to 5 minutes of jitter
cache.set(key, value, ttl=base_ttl + jitter)