Cache Stampede

Thundering Herd Problem

Cache stampede (thundering herd) occurs when many concurrent requests try to populate the same cache entry simultaneously.

The Problem

Cache Stampede Scenario:

1. Popular key expires
2. 1000 concurrent requests check cache
3. All see cache miss
4. All query database simultaneously
5. Database overwhelmed, slow response
6. All 1000 responses write to cache

Timeline:
Request 1: Cache miss → DB query ────────────────→ Cache set
Request 2: Cache miss → DB query ────────────────→ Cache set
Request 3: Cache miss → DB query ────────────────→ Cache set
...
Request 1000: Cache miss → DB query ─────────────→ Cache set

Result: 1000 duplicate DB queries!

Real-World Example

# Problematic code
def get_popular_product(product_id):
    cache_key = f"product:{product_id}"
    
    # Race condition here!
    product = cache.get(cache_key)
    if product is None:
        # Multiple threads enter here simultaneously
        product = db.query_product(product_id)  # 1000x DB queries!
        cache.set(cache_key, product, ttl=3600)
    
    return product

Impact

Prevention Strategies

1. Mutex/Lock Pattern

import threading
import time

class CacheStampedePrevention:
    def __init__(self, cache_client):
        self.cache = cache_client
        self.locks = {}
        self.lock_mutex = threading.Lock()
    
    def get_with_lock(self, key, loader, ttl=3600, lock_timeout=5):
        """Prevent stampede with distributed lock"""
        # Try cache first
        value = self.cache.get(key)
        if value is not None:
            return value
        
        # Acquire lock
        lock_key = f"lock:{key}"
        if self._acquire_lock(lock_key, lock_timeout):
            try:
                # Double-check after acquiring lock
                value = self.cache.get(key)
                if value is not None:
                    return value
                
                # Load and cache
                value = loader()
                self.cache.set(key, value, ttl)
                return value
            finally:
                self._release_lock(lock_key)
        else:
            # Another thread is loading, wait and retry
            time.sleep(0.1)
            return self.cache.get(key)
    
    def _acquire_lock(self, lock_key, timeout):
        deadline = time.time() + timeout
        while time.time() < deadline:
            if self.cache.set(lock_key, '1', nx=True, ex=timeout):
                return True
            time.sleep(0.01)
        return False
    
    def _release_lock(self, lock_key):
        self.cache.delete(lock_key)

2. Early Expiration

def get_with_early_expiration(key, loader, ttl=3600, early_pct=0.1):
    """Refresh cache before it expires"""
    data = cache.get(key)
    
    if data:
        data = json.loads(data)
        age = time.time() - data['created_at']
        
        # If close to expiration, refresh in background
        if age > ttl * (1 - early_pct):
            background_refresh(key, loader, ttl)
        
        return data['value']
    
    # No data, must load synchronously
    value = loader()
    cache.setex(key, ttl, json.dumps({
        'value': value,
        'created_at': time.time()
    }))
    return value

3. Probabilistic Early Expiration

import random

def get_probabilistic(key, loader, ttl=3600, beta=1.0):
    """XFetch algorithm - probabilistic refresh"""
    data = cache.get(key)
    
    if data:
        data = json.loads(data)
        delta = time.time() - data['created_at']
        
        # Calculate refresh probability
        # Higher delta = higher chance of refresh
        p = (beta * delta) / ttl
        
        if random.random() < p:
            # Probabilistically refresh
            try:
                value = loader()
                cache.setex(key, ttl, json.dumps({
                    'value': value,
                    'created_at': time.time()
                }))
                return value
            except:
                pass  # Use cached value on failure
        
        return data['value']
    
    # No data, load synchronously
    value = loader()
    cache.setex(key, ttl, json.dumps({
        'value': value,
        'created_at': time.time()
    }))
    return value

Locking Patterns

Distributed Lock with Redis

class DistributedLock:
    def __init__(self, redis_client):
        self.redis = redis_client
    
    def acquire(self, key, timeout=10, retry_count=3, retry_delay=0.1):
        """Acquire distributed lock with retry"""
        for i in range(retry_count):
            if self.redis.set(key, '1', nx=True, ex=timeout):
                return True
            time.sleep(retry_delay)
        return False
    
    def release(self, key):
        """Release distributed lock"""
        self.redis.delete(key)

# Usage
lock = DistributedLock(redis)
lock_key = f"lock:product:{product_id}"

if lock.acquire(lock_key):
    try:
        # Only one process loads data
        product = db.query(product_id)
        cache.set(f"product:{product_id}", product)
    finally:
        lock.release(lock_key)

Read-Write Lock Pattern

class ReadWriteLock:
    def __init__(self, redis_client):
        self.redis = redis_client
    
    def acquire_read(self, key):
        read_key = f"read:{key}"
        return self.redis.incr(read_key) == 1
    
    def release_read(self, key):
        self.redis.decr(f"read:{key}")
    
    def acquire_write(self, key, timeout=5):
        write_key = f"write:{key}"
        return self.redis.set(write_key, '1', nx=True, ex=timeout)
    
    def release_write(self, key):
        self.redis.delete(f"write:{key}")

# Multiple readers, single writer
def get_with_read_write_lock(key, loader):
    rw_lock = ReadWriteLock(redis)
    
    # Try read lock first
    if rw_lock.acquire_read(key):
        try:
            value = cache.get(key)
            if value:
                return value
        finally:
            rw_lock.release_read(key)
    
    # Acquire write lock
    if rw_lock.acquire_write(key):
        try:
            # Double-check
            value = cache.get(key)
            if value:
                return value
            
            value = loader()
            cache.set(key, value)
            return value
        finally:
            rw_lock.release_write(key)

Best Practices

1. Always use timeouts on locks to prevent deadlocks
2. Implement retry with backoff for lock acquisition
3. Use unique lock values for safe release
4. Consider lock-free approaches when possible
5. Monitor lock contention metrics