In our previous exploration of large-scale architectures in System Design: The Architecture That Scales , we walked through how an application scales from a single machine to an architecture serving millions of users. And in Design a Rate Limiter , we focused on putting boundaries in place to protect the system from aggressive traffic spikes.
Across both of those systems, there was one component sitting on the critical path of almost every user interaction: the caching layer .
In heavily read-intensive systems, designing an effective caching strategy is critical to maintaining low response times.
The initial goal was straightforward: deliver data instantly from the cache whenever possible. If the data had been sitting in cache for longer than its configured TTL, re-fetch fresh data from the origin.
It sounded trivial.
Until you look at what actually happens to the unlucky user whose request arrives the moment a cache entry expires.
Why should a random user pay the entire latency penalty of a database query just because the cache expired a second ago?
If an endpoint normally responds in 4ms, that user suddenly waits 400ms or 800ms while the backend fetches from the database, transforms the data, repopulates the cache, and finally returns the response.
User Request → Cache Expired → Blocked (400ms) → Origin Query → Response
This latency penalty on cache expiration is the exact problem stale-while-revalidate is designed to eliminate.
The First Solution: Stale-While-Revalidate
A standard pattern designed to tackle this is stale-while-revalidate (SWR).
The concept is deceptively elegant: serve the stale data to the user immediately, and simultaneously spawn a background asynchronous process to re-fetch fresh data from the origin.
In this model, the user gets their data in milliseconds without waiting for origin revalidation. And when the next request arrives in the near future, the cache is already fresh.
The revalidation is triggered based on the configured max-age:
Cache-Control: max-age=60, stale-while-revalidate=300
For 60 seconds, the response is fresh. For the next 300 seconds, the cache returns stale data instantly while refreshing in the background.
It felt like a solved problem. Users were happy, latency was flat, and origin load was minimized.
However, naive stale-while-revalidate implementations introduce a critical concurrency challenge under heavy load.
The Concurrency Problem: The 100-User Stampede
What happens when a popular cache item reaches its max-age, and 100 different users make the exact same API request at the same time?
Every single request arrives, checks the cache, sees that the data is stale, and spawns its own asynchronous revalidation task.
Suddenly, 100 duplicate queries hit the origin database simultaneously for the exact same resource.
This is the classic Cache Stampede (or Thundering Herd ) problem.
Instead of protecting the database, the caching tier unintentionally generated a coordinated spike of redundant work. Database connections spiked, query response times slowed, and latency cascaded across the system.
Why In-Memory State Failed at Scale
An initial approach to prevent duplicate fetches is tracking the revalidation state using an enum or in-memory flag.
enum CacheStatus { IDLE, FETCHING, FRESH }
When a request triggers revalidation, mark the status as FETCHING. Any subsequent requests that arrive while it is fetching simply return the stale data and skip triggering another fetch.
On a single standalone server instance, this pattern works as expected.
Then came the real question: where does this state live?
If the state is kept in server memory, what happens when you scale up horizontally to 10 or 20 application servers behind a load balancer?
Server A has no idea that Server B is already fetching the data. Each server still spawns its own revalidation query.
In-memory process state simply does not scale in a distributed architecture.
The Distributed Lock Workaround
To coordinate across multiple instances, the synchronization state can be moved to a shared key-value store using a distributed lock.
When a server detects that a cache item is stale, it attempts to acquire an atomic lock for that key (with a short lease TTL):
1. Try acquire lock: SET lock:item_id worker_id NX EX 5 2. If acquired: re-fetch from origin, update cache, release lock 3. If NOT acquired: another server is fetching → serve stale cache immediately
This coordinates access across instances: even with dozens of horizontally scaled servers, only one server acquires the lock to query the database, while all other servers serve stale data safely.
The Latency Cost of Synchronization
While distributed locking solved the duplicate query problem, it introduced new trade-offs:
- Critical Path Overhead: Every cache check now required an extra network roundtrip to the central lock coordinator.
- Lock Contention & Deadlocks: If a worker crashed while holding the lock, revalidation was blocked until the lease TTL expired.
- Operational Complexity: The lock store became another coordination dependency under heavy traffic surges.
While distributed locking prevents duplicate queries, acquiring locks on the hot read path adds network latency and coordination overhead. Eliminating stampedes without locking requires a different architectural approach.
A Different Paradigm: Rolling the Dice
To avoid coordination locks altogether, high-throughput distributed systems often use a different paradigm: probabilistic early revalidation .
The core intuition is fascinating: on every read request, you roll a dice .
If the dice rolls a six, the server initiates an asynchronous background revalidation. Otherwise, it simply serves the cached data and moves on.
The clever part is that the dice roll is dynamically weighted based on how close the cache item is to its max-age .
When the data is brand new, the probability of rolling a trigger is virtually zero. But as the item approaches its expiration timestamp, the chances steadily climb.
Because real-world applications receive a continuous stream of requests, one of the incoming reads will naturally hit the probability threshold and refresh the cache in the background before the hard expiration is ever reached.
How the Probabilistic Decision Works
In optimal early expiration algorithms (such as XFetch), each server evaluates the revalidation decision locally using a logarithmic probability formula:
should_revalidate = (current_time - (β * delta * ln(random(0, 1)))) > expiry_time
Where:
- delta (Δ): The time (in seconds) it took the origin to compute and return the data when it was last generated.
- β (Beta): A tuning parameter (> 0). Increasing β starts revalidating earlier to protect heavier, slower queries.
- random(0, 1): A uniform random number between 0 and 1.
As current_time nears expiry_time, the probability of this condition evaluating to true rises exponentially.
Evaluating the Trade-Offs
This probabilistic approach eliminates the need to acquire locks across servers:
- Zero Lock Latency: Every node evaluates the decision locally in nanoseconds without any network calls.
- Pre-Emptive Refresh: The cache is refreshed before it expires, meaning users almost never encounter cold stale data.
- The Trade-Off: In rare instances, two requests arriving at the same millisecond might both trigger a background fetch. But handling two background queries is a minor trade-off compared to the 100+ query stampede of an unprotected system.
Comparing Cache Strategies
Different caching challenges require different trade-offs:
- Synchronous Cache: Simple, but causes latency spikes whenever cache misses occur.
- SWR with Distributed Locks: Ideal when origin queries are massive or expensive and duplicate fetches must be strictly avoided at all costs.
- SWR with Probabilistic Expiration: The best choice for high-throughput, latency-critical read paths where lock-free scalability and smooth response times are top priority.
Conclusion
When building caching layers, the simplest solution often hides distributed concurrency traps.
By combining stale-while-revalidate with probabilistic early revalidation , we can completely eliminate cache stampedes, protect our origin databases, and deliver consistently fast response times to every single user.