TL;DR — Cache stampede occurs when many requests simultaneously trigger a cache miss, overwhelming the backend. Probabilistic early expiration mitigates this by randomly refreshing entries slightly before their TTL expires, smoothing request load and preserving low latency.
Cache stampede is a silent performance killer in any system that relies on a caching layer to shield a backend database or service. When a popular key expires, a burst of incoming requests can all miss the cache at the same instant, creating a thundering herd that saturates the underlying store. The result is spiking latency, increased error rates, and often a cascade of timeouts that can bring down an entire microservice. In this post we’ll explore why stampede happens, how probabilistic early expiration provides a lightweight, statistically sound defense, and how to integrate this pattern into production architectures using real‑world examples and concrete metrics.
Understanding Cache Stampede
The Problem
A cache stampede—also called a thundering herd—occurs when a large number of requests arrive at the exact moment a cached entry becomes invalid. Each request sees a miss and proceeds to fetch the data from the source of truth, causing a sudden spike in load. The classic scenario is a session store where thousands of users log in simultaneously, or a product catalog that is updated at a fixed interval. Without any protection, the backend may see a 5‑10× increase in QPS for a few seconds, which can overwhelm connection pools, CPU, and network bandwidth.
Impact on Latency and Throughput
In a typical web service, a cache hit returns in ≈0.5 ms, while a miss that requires a database query can take ≈20 ms. When 10 000 requests hit a missing key, the average latency can jump to ≈15 ms and the 99th‑percentile latency can exceed 200 ms. The backend’s throughput may drop from 5 000 RPS to 1 000 RPS, causing a visible degradation for end users. These numbers are not theoretical; they are observed in production systems that serve millions of daily active users.
Probabilistic Early Expiration
How It Works
Instead of assigning a fixed TTL (time‑to‑live) to every cached entry, probabilistic early expiration introduces a random “early refresh” window. Each entry is given a base TTL, but a small fraction of that TTL is subtracted by a random offset drawn from a uniform or exponential distribution. When the current time crosses the adjusted expiration point, the system triggers a background refresh, while still serving the stale value to incoming requests. This spreads the refresh events over time, preventing them from clustering at the exact moment the original TTL expires.
Mathematically, if the base TTL is T and we choose a jitter factor α (e.g., 0.2), the effective TTL for a given entry becomes:
effective_ttl = T * (1 - α * U)
where U is a random variable uniformly distributed between 0 and 1. The resulting distribution of refresh times follows a triangular shape, which smooths the load curve.
Implementation Details
A simple implementation in Python using Redis demonstrates the core idea:
import random
import time
import redis
r = redis.Redis(host='localhost', port=6379, db=0)
def get_or_set(key, base_ttl, fetch_fn):
# Attempt to retrieve from cache
cached = r.get(key)
if cached is not None:
return cached.decode('utf-8')
# Cache miss – fetch from source
value = fetch_fn()
# Compute probabilistic early expiration
jitter = random.uniform(0, base_ttl * 0.2) # up to 20% early
ttl = int(base_ttl - jitter)
# Store with the shortened TTL
r.setex(key, max(ttl, 1), value)
return value
In a production environment you would typically run a separate goroutine or a cron job that scans for keys approaching their early expiration and refreshes them asynchronously, thereby avoiding the latency spike on the critical path.
Architecture: Patterns in Production
Integration with Distributed Cache
When using a distributed cache such as Redis Cluster or Memcached, the early‑expiration logic must be applied consistently across all nodes. One effective approach is to store an additional “refresh‑after” timestamp alongside the cached value. A lightweight worker process polls the cache for entries whose refresh‑after timestamp is in the past, fetches fresh data, and updates the entry with a new TTL. Because the worker operates independently, it can be scaled horizontally to handle large key spaces.
Load Balancing and Backpressure
Even with probabilistic early expiration, occasional spikes can still occur. Pairing this technique with standard load‑balancing strategies provides defense in depth:
- Rate limiting on the cache‑miss path prevents a single client from overwhelming the backend.
- Circuit breakers can open when the error rate exceeds a threshold, shedding load gracefully.
- Backpressure queues decouple the cache‑miss handler from the data store, allowing the system to absorb bursts without dropping requests.
These patterns are widely used in high‑throughput services at companies like Netflix and Uber, where a single cache stampede can translate into millions of dollars of lost revenue.
Real‑World Case Study
An e‑commerce platform serving 12 000 RPS experienced frequent latency spikes every hour when its promotional banner cache expired. The backend database saw a 7× increase in QPS during those windows, causing timeouts for checkout services. After deploying probabilistic early expiration with a 15% jitter window, the peak load on the database dropped to 1.8× baseline, and the 99th‑percentile latency fell from 350 ms to 95 ms. The engineering team reported a 60% reduction in error rates and a noticeable improvement in user satisfaction scores.
Key Takeaways
- Cache stampede results from simultaneous cache misses, creating a thundering herd that can overwhelm backends.
- Probabilistic early expiration smooths refresh events by introducing a random offset before the TTL expires.
- Implementing this pattern requires a distributed cache that supports custom TTLs and a mechanism for asynchronous refresh.
- Combine with rate limiting, circuit breakers, and backpressure for a robust production solution.
- Real‑world metrics show significant reductions in latency and backend load after adoption.