Sep 18, 2026

The Thundering Herd Problem in Distributed Caching: Why Your Cache Invalidation Storms the Database

The Hook

Your cache key for “trending_products” expires at 12:00:00. At 12:00:01, 50,000 requests hit your database simultaneously. The thundering herd just killed your primary. This isn’t a cache miss — it’s a cache synchronization failure. Here’s why it happens and how to fix it.

The Thesis

The thundering herd isn’t a cache miss problem — it’s a synchronization problem. When a hot key expires, all waiters simultaneously miss and recompute. The solution isn’t “add more cache” — it’s desynchronizing expiration and coalescing recomputation.

The Science

The Math of the Herd

Scenario: Hot key, 10K req/s, 200ms DB query, TTL = 300s.

When key expires:

Requests 1-10,000 arrive in first 100ms
All miss cache
All execute DB query
DB load: 10,000 × 200ms = 2,000 seconds of CPU in 100ms
Result: DB CPU 100%, queue backs up, cascade failure

Why Standard Solutions Fail

Solution	Problem
Longer TTL	Stale data; doesn’t fix synchronization
Random TTL jitter	Helps but doesn’t eliminate; still synchronized waves
Simple mutex	Single-threaded recompute = queue backs up
Background refresh	Complex; still has race conditions

The Solutions (Ranked by Effectiveness)

1. Probabilistic Early Expiration (Best for Most Cases)

Idea: Each request independently decides to refresh early with probability p = (time_until_expiry) / TTL.

import random
import time

def get_with_probabilistic_refresh(key, ttl=300, compute_fn=None):
    """
    Probabilistic early expiration (Facebook/Instagram approach).
    Each request independently decides to refresh early.
    """
    entry = cache.get(key)
    now = time.time()
    
    if entry is None:
        # Cache miss - compute and store
        value = compute_fn()
        cache.set(key, {"value": value, "expires": now + ttl})
        return value
    
    # Check if expired
    if now >= entry["expires"]:
        # Hard miss - must compute
        value = compute_fn()
        cache.set(key, {"value": value, "expires": now + ttl})
        return value
    
    # Probabilistic early refresh
    time_remaining = entry["expires"] - now
    refresh_probability = 1.0 - (time_remaining / ttl)
    
    if random.random() < refresh_probability:
        # Background refresh (non-blocking)
        spawn_background_refresh(key, compute_fn, ttl)
    
    return entry["value"]

def spawn_background_refresh(key, compute_fn, ttl):
    """Fire-and-forget background refresh."""
    try:
        value = compute_fn()
        cache.set(key, {"value": value, "expires": time.time() + ttl})
    except Exception:
        pass  # Log but don't block

Why it works:

Only ~1 request per TTL/p triggers refresh
At 10K req/s, TTL=300s, p≈0.5 at halfway → 5 refreshes over 150s vs 10,000 at once
No coordination needed

2. Stale-While-Revalidate (HTTP Cache-Control Pattern)

Idea: Serve stale content while asynchronously refreshing.

def get_stale_while_revalidate(key, ttl=300, grace_period=60, compute_fn=None):
    """
    Stale-while-revalidate: serve stale content up to grace_period
    while background refresh happens.
    """
    entry = cache.get(key)
    now = time.time()
    
    if entry is None:
        value = compute_fn()
        cache.set(key, {"value": value, "expires": now + ttl})
        return value
    
    # Fresh - return immediately
    if now < entry["expires"]:
        return entry["value"]
    
    # Stale but within grace period - serve stale, trigger refresh
    if now < entry["expires"] + grace_period:
        spawn_background_refresh(key, compute_fn, ttl)
        return entry["value"]
    
    # Beyond grace - hard miss
    value = compute_fn()
    cache.set(key, {"value": value, "expires": now + ttl})
    return value

Cache-Control header equivalent:

Cache-Control: max-age=300, stale-while-revalidate=60

3. Distributed Lock with Lease (For Critical Keys)

Idea: Only one recomputes; others wait or get stale.

import redis
import uuid
import time

def get_with_distributed_lock(key, ttl=300, compute_fn=None, lock_ttl=10):
    """
    Distributed lock with lease for critical keys.
    Only one recomputes; others wait briefly or get stale.
    """
    lock_key = f"lock:{key}"
    lock_value = str(uuid.uuid4())
    redis_client = redis.Redis()
    
    entry = cache.get(key)
    now = time.time()
    
    # Fresh - return immediately
    if entry and now < entry["expires"]:
        return entry["value"]
    
    # Try to acquire lock
    acquired = redis_client.set(lock_key, lock_value, nx=True, ex=lock_ttl)
    
    if acquired:
        try:
            # We won the lock - compute
            value = compute_fn()
            cache.set(key, {"value": value, "expires": time.time() + ttl})
            return value
        finally:
            # Release lock only if we still own it
            redis_client.eval(
                "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end",
                1, lock_key, lock_value
            )
    else:
        # Didn't get lock - wait briefly for refreshed value
        time.sleep(0.05)  # 50ms
        entry = cache.get(key)
        if entry and time.time() < entry["expires"] + 60:  # grace
            return entry["value"]
        # Fallback: compute anyway (lock holder may have died)
        return compute_fn()

4. Probabilistic Cache Refresh (Twitter’s Approach)

Idea: Decouple cache lifetime from refresh trigger.

def get_with_probabilistic_refresh_v2(key, ttl=300, compute_fn=None):
    """
    Twitter-style probabilistic refresh.
    Refresh triggered probabilistically based on request rate.
    """
    entry = cache.get(key)
    now = time.time()
    
    if entry is None or now >= entry["expires"]:
        value = compute_fn()
        cache.set(key, {"value": value, "expires": now + ttl})
        return value
    
    # Track request count in separate key
    rate_key = f"rate:{key}"
    count = cache.incr(rate_key)
    if count == 1:
        cache.expire(rate_key, ttl)
    
    # Refresh probability increases with request rate
    # At 1000 req/s: p ≈ 0.01 per request
    refresh_probability = min(0.1, count / 100000)
    
    if random.random() < refresh_probability:
        spawn_background_refresh(key, compute_fn, ttl)
        cache.set(rate_key, 0)  # Reset counter
    
    return entry["value"]

The Comparison

Solution	Complexity	Latency Impact	DB Load Reduction	Best For
Probabilistic early expiration	Low	None	99%+	Most hot keys
Stale-while-revalidate	Low	None (stale served)	95%+	HTTP caches, read-heavy
Distributed lock	Medium	50ms wait for waiters	99.9%	Critical keys (pricing, inventory)
Probabilistic refresh (rate-based)	Low	None	99%+	High-traffic, variable rate

The Protocol: Implement in Order

Week 1: Probabilistic Early Expiration

# Replace all cache.get() calls
def smart_get(key, compute_fn, ttl=300):
    entry = cache.get(key)
    now = time.time()
    
    if entry is None or now >= entry["expires"]:
        return compute_and_store(key, compute_fn, ttl)
    
    # Probabilistic refresh
    if random.random() < (1 - (entry["expires"] - now) / ttl):
        spawn_background_refresh(key, compute_fn, ttl)
    
    return entry["value"]

Week 2: Add Stale-While-Revalidate for HTTP Layer

# Nginx config
proxy_cache_valid 200 300s;
proxy_cache_use_stale updating;
proxy_cache_background_update on;

Week 3: Add Distributed Locks for Critical Keys Only

Pricing, inventory, user sessions
Use Redlock algorithm for multi-datacenter

The Counterpoint

Probabilistic = non-deterministic: Harder to test/debug
Stale data: Users may see slightly stale data (acceptable for most)
Lock contention: Can create new bottleneck if lock_ttl too long
Monitoring essential: Track cache hit rate, refresh rate, lock contention

Practical Takeaway

Start with probabilistic early expiration — 5 lines of code, 99% herd reduction, zero coordination. Add stale-while-revalidate at HTTP layer. Reserve distributed locks for truly critical keys (pricing, inventory). Monitor: cache_hit_rate, refresh_rate, lock_wait_time.

Sources: Facebook Engineering “Scaling Memcache” (2013); Twitter Engineering “Cache Invalidation” (2016); AWS ElastiCache “Best Practices”; RFC 5861 (stale-while-revalidate); Redis “Redlock Algorithm”; Netflix Tech Blog “Cache Invalidation Strategies” (2018).