Posted inDatabase

Prevent Redis Cache Stampede: Mutex Locking vs Probabilistic Early Expiration (XFetch)

Database tutorial - IT technology blog
Database tutorial - IT technology blog

Quick Start: Simulating the Stampede

Your web service handles 15,000 requests per second. The homepage aggregates product metrics, cached in Redis with a 10-minute TTL. At 12:00:00, that key expires. One second later, 1,500 worker threads query Redis, hit a cache miss, and immediately flood your database with identical, expensive analytical queries.

Engineers call this a cache stampede, or the dogpiling effect. Connection pools exhaust within milliseconds. Database CPU spikes to 100%, and downstream services begin timing out.

Here is what that vulnerability looks like in standard Python caching code:

import redis
import time

r = redis.Redis(host='localhost', port=6379, db=0)

def get_expensive_product_data(product_id):
    cache_key = f"product:{product_id}"
    cached_val = r.get(cache_key)
    
    if cached_val is not None:
        return cached_val
    
    # Danger zone: Hundreds of threads reach this line at once upon TTL expiry
    computed_data = execute_heavy_database_query(product_id)
    r.setex(cache_key, 600, computed_data)
    return computed_data

def execute_heavy_database_query(product_id):
    time.sleep(0.3)  # Simulates 300ms complex DB aggregation
    return f"data_for_{product_id}"

Simulate this in k6 or Locust across 2,000 virtual users. The instant the key expires, Postgres connection pool limits (like default max_connections=100) collapse under FATAL: remaining connection slots are reserved errors. To fix this, you must either restrict regeneration to one worker or refresh data before it actually dies.

Root Cause and Resolution Strategies

Whether you run PostgreSQL, MySQL, or MongoDB, relational engines struggle when thousands of threads execute the exact same aggregation at once. Standard cache patterns decouple reads from refresh routines, leaving a dangerous gap between eviction and repopulation.

Two battle-tested architectures prevent dogpiling:

  1. Distributed Mutex Lock: Serializes regeneration. Only one worker acquires the lock to query the database, while remaining threads pause, poll, or serve stale data.
  2. Probabilistic Early Expiration (XFetch): Refreshes entries proactively. As the expiration window nears, reads calculate an escalating probability to recompute in the background.

Strategy 1: Distributed Mutex Locking with Redis

Distributed locks guarantee single-worker rebuilds. When a cache miss lands, the thread attempts to secure an exclusive key via Redis’s atomic SET key value NX PX operation.

import uuid
import time

def get_with_mutex(product_id):
    cache_key = f"product:{product_id}"
    lock_key = f"lock:{cache_key}"
    
    val = r.get(cache_key)
    if val is not None:
        return val
    
    # Acquire a 5-second distributed lock
    lock_token = str(uuid.uuid4())
    acquired = r.set(lock_key, lock_token, nx=True, px=5000)
    
    if acquired:
        try:
            # Winner thread computes and sets the value
            data = execute_heavy_database_query(product_id)
            r.setex(cache_key, 600, data)
            return data
        finally:
            # Release safely via Lua script to avoid deleting newer locks
            lua_release = """
            if redis.call('get', KEYS[1]) == ARGV[1] then
                return redis.call('del', KEYS[1])
            else
                return 0
            end
            """
            r.eval(lua_release, 1, lock_key, lock_token)
    else:
        # Back off 50ms and retry cache read
        time.sleep(0.05)
        return get_with_mutex(product_id)

Mutex locks act like turnstiles. They protect your database reliably, yet waiting threads suffer latency spikes. If the lock-holder dies mid-query, others wait out the full lock timeout.

Strategy 2: Probabilistic Early Expiration (XFetch)

Tail latency matters at 50,000 QPS. Waiting 50ms on a lock poll wastes client response time. In 2015, researchers Vattani, Chierichetti, and Lowenstein proved a cleaner solution: the XFetch algorithm.

Instead of waiting for eviction, readers evaluate whether to recompute early. The decision balances remaining TTL against past database query duration. As time runs down, the likelihood of a proactive background update approaches 100%.

The mathematical condition is:

-(compute_time * beta * ln(random())) > remaining_ttl

  • compute_time (delta): Seconds spent generating the cached record during its last run.
  • beta: Aggressiveness multiplier. Setting 1.0 mirrors optimal theoretical probability. Values above 1.0 trigger refreshes earlier.
  • random(): Uniform random float between 0.0 and 1.0 (exclusive of 0).

Here is an end-to-end Python implementation:

import math
import random
import time
import json

def xfetch_read(key, beta=1.0):
    raw = r.get(key)
    if not raw:
        return None, True  # Cold start cache miss
        
    entry = json.loads(raw)
    value = entry["value"]
    delta = entry["delta"]         # Compute duration in seconds (e.g., 0.28)
    ttl = r.ttl(key)              # Seconds left before Redis drops the key
    
    if ttl <= 0:
        return value, True
    
    # Core XFetch probability trigger
    should_refresh = -(delta * beta * math.log(random.random())) > ttl
    return value, should_refresh

def get_product_data_xfetch(product_id):
    key = f"product:{product_id}"
    value, needs_refresh = xfetch_read(key, beta=1.0)
    
    if value is not None and not needs_refresh:
        return value
        
    # Recompute: triggered either by cold miss or probabilistic roll
    start_time = time.time()
    fresh_data = execute_heavy_database_query(product_id)
    compute_duration = time.time() - start_time
    
    payload = json.dumps({
        "value": fresh_data,
        "delta": compute_duration
    })
    
    # Persist with a 600-second TTL
    r.setex(key, 600, payload)
    return fresh_data

Under steady traffic, the key never actually expires. Readers bypass lock overhead entirely, and the primary database sees one background refresh smoothed over the end of the TTL window.

Production Considerations

  • Apply Jitter to Fixed TTLs: If you keep standard expiration, spread key lifespans using pseudo-random offset jitter: ttl = 600 + random.randint(-45, 45). This stops keys populated during bulk deployments from dying in the same second.
  • Decouple XFetch with Background Workers: Do not block HTTP threads when needs_refresh evaluates to true. Serve the current cached value immediately, then push an asynchronous task to Celery or RQ to write the new data.
  • Tune Lock TTL Above p99 Latency: When using mutexes, set lock expiration to at least 3x your database p99 duration. If a query runs 400ms and the lock expires at 300ms, redundant workers charge in anyway.
  • Calibrate the Beta Factor: If heavy traffic bursts outpace refreshes, increase beta to 1.3 or 1.5. When database capacity is constrained, lock it at 1.0 to prevent duplicate background rebuilds.
Share:
Tags: