Cache Stampede

The core mechanism of a cache stampede is the thundering herd problem. When a popular cache item expires, numerous concurrent requests—often from parallel processes or distributed application instances—find the cache empty simultaneously. This triggers a synchronized, overwhelming surge of requests to the primary database or backend API, which can lead to:

• Resource exhaustion (database connections, CPU)
• Significant latency spikes for all dependent requests
• Cascading failures if the backend cannot handle the load This problem is exacerbated in distributed systems where many nodes share a common cache but have independent execution timelines.

The primary trigger for a stampede is the coordinated expiration of cache entries. This most commonly occurs due to:

• Identical Time-To-Live (TTL) values: A batch of items cached at the same time with the same TTL will expire simultaneously.
• Cache server restart or failure: A full cache flush causes all items to become "misses" at once.
• Global cache invalidation events: A business logic event (e.g., a major data update) that purges a large segment of the cache. Without mitigation, this creates a predictable point of failure where system load shifts catastrophically from the fast cache layer to the slower primary data store.

A fundamental defense is to ensure only one request regenerates the cache value. This is implemented via distributed locks or deduplication mechanisms.

• Process: The first request to encounter a miss acquires a lock (e.g., in Redis). Subsequent requests block or wait, then reuse the result generated by the first request.
• Cache-aside with lock: Application logic explicitly manages the lock around the data-fetching routine.
• Read-through cache with built-in coalescing: The caching layer itself (e.g., a read-through memcached plugin) handles request coalescing transparently. This pattern prevents redundant work but requires careful lock timeout handling to avoid deadlocks if the regenerating request fails.

Instead of waiting for full expiration, this strategy refreshes cache items probabilistically before their TTL ends. A common implementation is "Cache Refresh-Ahead" or using the stale-while-revalidate pattern.

• Mechanism: When a request is made for an item near its expiry (e.g., within the last 20% of its TTL), the system may:
  1. Immediately return the stale cached value.
  2. Asynchronously trigger a background refresh to update the cache with new data.
• Benefit: Smooths out load by spreading regeneration over time, preventing a synchronized stampede at the expiry boundary. It trades minor data staleness for massive reliability gains.

Introducing randomness is a key technique for decoupling simultaneous processes. Jitter adds a random delay to cache regeneration attempts.

• Application: When a cache miss occurs, instead of immediately querying the backend, the process waits for a random duration (e.g., 0-100ms). This spreads the herd of requests over a small time window.
• Exponential Backoff: If the backend is already under load or returns an error, subsequent retry attempts use an exponentially increasing delay, preventing aggressive retries from worsening the stampede. This is a simple, client-side strategy that requires no coordination but does not eliminate duplicate work.

In AI agent systems, cache stampedes are a critical risk for semantic caches and deterministic caches storing LLM responses or tool call results.

• Trigger: An agent workflow with many parallel sub-agents querying the same cached piece of knowledge or API result upon cache expiry.
• Impact: Can cause overwhelming load on:
  • LLM inference endpoints, incurring high cost and latency.
  • External APIs called via tool calling, potentially triggering rate limits.
• Mitigation: Agent orchestration layers must implement deduplication for identical tool calls and employ probabilistic early refresh for cached LLM completions, treating the model as a fragile backend resource.

A cache miss occurs when a requested data item is not found in the cache, forcing the system to retrieve it from the slower primary data source (e.g., a database or API). This is the fundamental event that, when multiplied across many concurrent requests for the same expired item, triggers a cache stampede. High rates of cache misses for popular keys are the primary symptom of an ongoing stampede.

• Latency Penalty: Each miss incurs the full latency of the backend query.
• Resource Amplification: Concurrent misses for the same key multiply the load on the primary source.

Time-To-Live (TTL) is a cache policy that defines the maximum duration a cached item is considered valid before it is automatically expired. Stampedes are directly caused by the simultaneous expiration of many items with identical or similar TTLs. Mitigation strategies often involve manipulating TTLs, such as:

• TTL Jitter / Staggering: Adding random offsets to expiration times to prevent synchronized expiration.
• Probabilistic Early Refresh: Refreshing items before their TTL expires based on a calculated probability, smoothing out load.

The cache-aside pattern is a caching strategy where the application code is directly responsible for loading data into the cache on a miss. This pattern is highly susceptible to stampedes because multiple application threads can simultaneously experience a miss for the same expired key and all proceed to recompute the value. Mitigations like locking or lease tokens must be implemented at the application layer to serialize these recomputation attempts when using this pattern.

A read-through cache is a caching pattern where the cache system itself (or a dedicated library) is responsible for loading data from the primary source on a miss. This centralizes the logic for managing concurrent misses, making it easier to implement built-in stampede protection. The cache can guarantee that only one request per key triggers a recomputation, while others wait for the result. This pattern shifts the complexity from the application to the caching infrastructure.

Stale-while-revalidate is a cache-control strategy that allows a system to serve stale (expired) data immediately to a user while asynchronously triggering a refresh in the background. This is a powerful defense against stampedes because it decouples user response time from data freshness. Users never wait for a recomputation, eliminating the "herd" behavior. The background refresh can be rate-limited or performed by a single worker, preventing a thundering herd on the backend.

Probabilistic early expiration, often paired with proactive refresh, is a technique to prevent stampedes by not letting items reach their natural TTL simultaneously. A background process or a subset of user requests triggers a recomputation before the item expires, based on factors like:

• Access frequency: Popular items are refreshed earlier.
• Random chance: A small percentage of requests trigger a refresh.
• Monotonic write timestamps: The system knows when the source data was last updated. This ensures the cache is "warm" with fresh data before a mass expiration event can occur.