The Cache Stampede Scenario
Imagine this: You're in a system design interview. The interviewer sketches a typical architecture: an API layer, a Redis cache, and a PostgreSQL database. Then comes the bombshell scenario: A highly popular cache key expires. In the same second, 40,000 requests arrive, all demanding that exact key. What happens? And more importantly, how do you prevent your database from collapsing under the load?
Many engineers jump straight to scaling the database or adding read replicas. While these are valid scaling strategies, they miss the core of the problem. The interviewer isn't just testing your knowledge of database capacity; they're assessing your understanding of distributed systems resilience and your ability to anticipate and mitigate cascading failures. This situation is a classic example of a Cache Stampede, also known as the Thundering Herd problem.
The core issue is that when a cache entry expires, multiple concurrent requests, instead of hitting the cache (which is now empty for that key), all proceed to hit the origin data store simultaneously. If the data retrieval and cache population process is slow, and the requests are numerous and come in a tight window, the origin can become overwhelmed. This leads to increased latency, potential timeouts, and in worst-case scenarios, a complete service outage.
The Arithmetic of Failure
Before jumping to solutions, let's do the math. The scenario posits 40,000 requests per second. If retrieving and regenerating the cache value takes just 200 milliseconds (0.2 seconds), then within that 0.2-second window, the database will be hit by all 40,000 requests. This isn't just a theoretical problem; it's a real-world stress test for any system. Even if your database can handle this peak load for a brief moment, the subsequent requests, while the cache is being repopulated, will continue to hammer the database, potentially leading to a sustained overload.
The critical insight is that the problem isn't just the number of requests, but the concurrency and the time window during which the database is unprotected. If cache regeneration takes longer than the time it takes for all 40,000 requests to arrive, you have a stampede.
Beyond Scaling: Proactive Prevention
The common, but flawed, first response is to scale the database. While increasing database capacity (e.g., through read replicas or a more powerful instance) can help absorb the shock, it's a reactive measure. It doesn't fundamentally solve the stampede problem. If the cache regeneration time is significant, even a scaled database can eventually buckle under sustained, unmitigated load. The real solution lies in modifying how the cache is managed and how requests are handled during cache misses.
Strategies to Mitigate Cache Stampedes
Several strategies can effectively prevent or mitigate cache stampedes:
1. Cache Lock/Mutex
This is often considered the most robust solution. When the first request for an expired key arrives, it acquires a lock (e.g., using Redis's SETNX command or a distributed locking mechanism). Only the request holding the lock is allowed to fetch data from the database and regenerate the cache. All other requests arriving while the lock is held will either:
- Wait: They block and wait for the lock to be released. A timeout should be implemented to prevent indefinite waiting.
- Return stale data: If acceptable, they can be served the existing (expired) cache value if it's still available, or an error if not.
- Return a specific error: Indicate that the data is temporarily unavailable.
Once the regenerating request successfully updates the cache, it releases the lock. Subsequent requests will then hit the newly populated cache. This serializes the cache regeneration process, ensuring only one request hits the database at a time for a specific key.
2. Cache Entry Pre-warming/Refresh-Ahead
Instead of waiting for a key to expire and then dealing with the surge, you can proactively refresh cache entries before their TTL is reached. This involves:
- Setting longer TTLs with background refresh: Set a TTL slightly longer than the expected data staleness tolerance. Then, use a background job or a scheduled task to periodically fetch and update the cache entry well before it expires.
- Event-driven updates: If your data changes infrequently but is critical, trigger cache updates from the data source itself. For example, when a record is updated in the database, asynchronously send a message to update the corresponding cache entry.
This approach requires more complex infrastructure but significantly reduces the likelihood of a cache miss at a critical moment. The challenge is determining the right TTL and refresh interval without overwhelming the database with refresh requests.
3. Stale-While-Revalidate
This pattern allows reads to continue while the cache is being rebuilt. When a request comes for an expired key:
- The first request immediately returns the stale (expired) data from the cache if available.
- In parallel, this request initiates the process of fetching fresh data from the database.
- Once the fresh data is retrieved, it updates the cache and then returns the fresh data to the client (or subsequent requests).
This pattern provides the best user experience as users rarely see an error or a long wait. However, it still sends a request to the database. To prevent a stampede, this pattern is often combined with the cache lock mechanism. The first request acquires the lock, serves stale data, and then regenerates the cache. Subsequent requests that arrive while regeneration is in progress might also be served stale data (if available) or wait for the lock to be released.
4. Increased Cache TTLs and Reduced Concurrency
While not a complete solution, simply increasing the TTL of popular keys can reduce the frequency of expiry events, thereby lowering the probability of a stampede. Additionally, implementing rate limiting or request queuing at the API gateway or application layer can smooth out traffic spikes, preventing 40,000 requests from hitting simultaneously. This is a simpler, less intrusive approach but may not be sufficient for extremely high-traffic scenarios or keys with very short TTLs.
The Interviewer's Signal
The key takeaway from this system design problem is that the interviewer is looking for more than just a quick fix. They want to see that you understand the underlying distributed systems problem (Cache Stampede), can quantify the risk (the arithmetic), and can propose architectural solutions that go beyond brute-force scaling. The best answer involves a combination of techniques, often starting with a cache lock to serialize regeneration, potentially combined with stale-while-revalidate for a better user experience, and considering background refresh for critical data.
The surprising detail here is not the 40,000 requests, but the implicit assumption that a simple database scale-up is the primary solution. It's not. It's about intelligent cache management and request handling to protect your origin servers from self-inflicted DDoS attacks.