Advanced System Design Fundamentals
Vote

0% completed

​

Stampede, Thundering Herd, Dogpile

Part 1: One Entry Expires

Part 2: Three Names, One General Case

Part 3: Two Shapes of the Problem

Part 4: Fix 1, Request Coalescing

Part 5: The Failure Coalescing Creates

Part 6: Fix 2, Probabilistic Early Refresh

Part 7: Fix 3, Jittered TTLs

Part 8: Using This in an Interview

Common Mistakes

Key Takeaways

Cache Stampede Explained: Thundering Herd and Dogpile, Request Coalescing, Probabilistic Early Refresh, and Jittered TTLs (Video)

Three names describe one family of failures: the cache stampede, the dogpile, and the more general thundering herd. In each of them, a popular result is missing for a moment, and every request that needs it tries to rebuild it at the same time.

The cause is often a normal event, not a bug. A cache entry expires on schedule, exactly as designed, and for a few seconds the database receives all the traffic that the cache used to answer. Part 2 separates the three names, and the rest of the lesson covers the three standard fixes and what each one leaves unsolved.

Part 1: One Entry Expires

A cache keeps copies of results that are slow to produce, so most requests never reach the database. Four terms describe it:

  • A cache entry is one stored result. Each entry is found by its key.
  • The time to live, or TTL, is how long an entry stays in the cache before it is removed.
  • A cache miss is a request that finds no entry. On a miss, the server recomputes the value from the database and writes it back.

Take a large online store during a sale. Its home page shows today's deals, and a heavy database query builds the deals list in about 2 seconds. The store caches the list for 5 minutes. About 1,000 requests a second read the list, spread across 20 application servers. These numbers are made-up examples.

The diagram below shows the first seconds after the entry expires.

One cache entry expires, about 2,000 requests miss in the next 2 seconds, and the slower database lets even more requests miss
One cache entry expires, about 2,000 requests miss in the next 2 seconds, and the slower database lets even more requests miss

Step 1: The entry expires. The next request misses and starts the 2-second query.

Step 2: Other requests keep arriving. They miss too, because the first query has not finished. In 2 seconds, about 2,000 requests miss.

Step 3: Each miss sends the same query. The database now runs about 2,000 copies of the heavy query at once.

Step 4: The database slows down. Under that load, each query takes longer than 2 seconds. The entry stays missing for longer, so even more requests miss.

Notice the loop in Step 4. The slow database keeps the entry missing, and the missing entry keeps the database busy, so the event makes itself worse. Nothing failed: one entry expired. This event is called a cache stampede.

Part 2: Three Names, One General Case

The three names in the opening are related in a simple way. A thundering herd is the general case. Many waiters are released at the same moment, and all of them reach for one resource. The resource does not have to be a cache.

A cache stampede is the caching case: the waiters are cache misses, and the resource is the database behind the cache. A dogpile is another name for a cache stampede, not a separate problem.

A herd can also reach a database as a burst of new connections, all opened at once. Later in the course, Connection Pooling and the Database Thundering Herd covers that side of it.

Part 3: Two Shapes of the Problem

The deals list is one shape of the problem. There is a second shape, and it needs different fixes.

The first shape is one hot key: a single entry that a large share of requests read. The deals list is a hot key.

The second shape is many keys at once. Each key has modest traffic, but thousands miss in the same second, because they were written at the same moment with the same TTL. In the store, these are the 50,000 product pages. Before the sale, a scheduled job writes all of them into the cache at once, which is called warming the cache.

The table below lists common events that write many keys at once.

EventWhy many keys expire together
A deploy or a cache restartThe cache is empty or uses new keys, so the popular keys are all written again within seconds
A scheduled job that warms the cacheIt writes many keys at once, all with one TTL
A traffic spike from a campaign or a popular linkThe spike fills many entries in the same minute

Notice that keys which miss together are also written back together, so they expire together again one TTL later. A warming job on a timer repeats its stampede on the same timer. Gradual growth in traffic is not a cause, because keys first written at different moments expire at different moments.

Part 4: Fix 1, Request Coalescing

The first fix deals with Step 3 of Part 1, where 2,000 requests send the same query. Request coalescing means that one request computes the missing value, and the other requests wait for its result.

A lock decides which request computes. A lock is a marker that only one request can hold at a time. The request that gets it, the winner, runs the query, writes the entry, and releases the lock. Every other request finds the lock taken, waits, and then reads the new entry.

How much coalescing helps depends on where the lock is kept. The diagram below compares three places for it.

With no lock, 2,000 requests run the query; a lock inside each of 20 servers cuts that to 20, and a shared lock cuts it to 1
With no lock, 2,000 requests run the query; a lock inside each of 20 servers cuts that to 20, and a shared lock cuts it to 1

Notice the three columns from left to right. With no lock, about 2,000 queries reach the database.

The simplest lock is inside the application process. Each of the 20 servers picks its own winner, so 2,000 queries become 20. That may already be enough, but it is not one.

To get down to one query, the lock must be somewhere all 20 servers can see it, which is usually the cache itself. The winner creates a lock key there, which the cache allows only if none exists yet. The lock key has its own short expiry, so a crashed winner cannot block the key forever. It costs one extra network call on every miss, so choose a shared lock when 20 queries would still be too many for the database.

Part 5: The Failure Coalescing Creates

Coalescing removes the duplicate queries, but it changes how requests fail. Every waiting request now depends on its winner. If the winner is slow, a slow query becomes 2,000 slow requests. To prevent that, every waiter needs two things:

  • A timeout. A waiter waits a little longer than a normal computation takes, then stops waiting.
  • A fallback. This is what the waiter returns after its timeout. The best fallback is often the old value.

To keep the old value available, the cache holds an expired entry for a short extra time, called a grace period. During it, one request refreshes the entry, and every other request gets the old copy at once.

This is called serving stale while revalidating, where stale means out of date. For the store, a deals list that is a few seconds old is better than a home page that does not load. If there is no old copy, the fallback can be a default response or a fast error.

Part 6: Fix 2, Probabilistic Early Refresh

Coalescing makes a miss cheaper, but the miss still happens. The second fix, probabilistic early refresh, tries to prevent it by refreshing the entry shortly before it expires. It works in four steps:

  1. Each value is stored with two extra facts: the time it expires and how long it took to compute.
  2. On every read, a random draw decides whether this reader refreshes the value now.
  3. The chance of refreshing is near zero while the entry is young, and it rises quickly as the expiry approaches. Common versions also start earlier for values that are slow to compute, like the 2-second deals query.
  4. The chosen reader writes the value with a full new TTL, so usually no reader finds the entry missing.

Notice why the chance has to rise. A constant chance would refresh a young entry as often as an old one, which wastes work. A fixed refresh time, such as 10 seconds before expiry, would send every reader to refresh at that same moment. That is the stampede again, only a little earlier. With a rising chance, one reader on a busy key usually acts first. On a very hot key, a few readers may be chosen close together, so teams often add coalescing as well.

Part 7: Fix 3, Jittered TTLs

The third fix is for the second shape from Part 3, many keys at once. Jitter is a small random amount added to each TTL when the entry is written. Instead of exactly 10 minutes, each key gets a TTL somewhere between 9 and 11 minutes.

Go back to the warming job from Part 3, which writes the 50,000 product pages at once, each with a 10-minute TTL. Without jitter, all 50,000 expire within seconds of each other. With jitter, their expiries spread across 2 minutes, which is about 420 a second. Jitter is applied on every write, so it still works after a restart. Its cost is small: a value can now be up to 11 minutes old, not 10.

Jitter spreads a group of keys apart. It does nothing for one hot key, because moving a single expiry time does not change what happens when that time arrives. The deals list would still expire, and about 2,000 requests would still miss. The diagram below shows which fix handles which shape.

Three fixes compared against the two shapes of a stampede, with the new risk that each fix brings
Three fixes compared against the two shapes of a stampede, with the new risk that each fix brings

Notice the coalescing row. Coalescing removes duplicate work for each key, but if 50,000 keys expire together, it still runs one query for each of them. Early refresh has the same limit, because keys written together come up for refresh together.

Part 8: Using This in an Interview

The stampede usually comes up in the deep dive, when one part of your design is examined in detail. The interviewer points at your cache and asks what happens when a popular entry expires. Name the shape first, then the fix, then what the fix costs.

"The deals list is one hot key, read 1,000 times a second and built in 2 seconds. If it simply expires, about 2,000 requests run the same query. A lock in each server turns that into 20, and meanwhile other requests get the previous list. For the product pages, I'd add jitter to every TTL, because the warming job writes them all at once."

Two follow-up questions are common. "Does your lock give you one query?" tests depth. Say it gives one per server, and when a shared lock is worth its network call. "What if the query takes 30 seconds?" tests judgment. The waiters time out and get the old value, and the slow query becomes a separate problem.

Common Mistakes

Mistake 1: Using jitter for a hot key. Jitter spreads many keys apart, but one key has only one expiry time. A single hot key needs coalescing or early refresh.

Mistake 2: Coalescing without a timeout for the waiters. Without a timeout, one slow recomputation stalls every request for that key.

Mistake 3: Claiming an in-process lock gives one recomputation. With 20 servers, it gives 20. Say so, and decide whether 20 is acceptable.

Key Takeaways

  • A thundering herd is the general case. A cache stampede is its caching case, and a dogpile is another name for a stampede.
  • Keys written together expire together. Deploys, cache restarts, warming jobs, and traffic spikes all write many keys at once.
  • Coalescing has two costs to name. An in-process lock leaves one recomputation per server, and a slow winner blocks every waiter.
  • Early refresh prevents the miss. Its chance of refreshing is near zero for a young entry and rises near expiry.
  • In a system design interview, name the shape before the fix. Use jitter for many keys, and coalescing or early refresh for one hot key.

The next lesson, Invalidation Strategies, covers how a cached value is removed or replaced when the data behind it changes.

Reading Progress

0%


Vote for new content

On This Page

Part 1: One Entry Expires

Part 2: Three Names, One General Case

Part 3: Two Shapes of the Problem

Part 4: Fix 1, Request Coalescing

Part 5: The Failure Coalescing Creates

Part 6: Fix 2, Probabilistic Early Refresh

Part 7: Fix 3, Jittered TTLs

Part 8: Using This in an Interview

Common Mistakes

Key Takeaways