When the cache is empty and everyone asks at once (stampede)

A cache protects the database only while it holds the data. An interviewer asks: "Your cache restarts at 8 pm on a sale day. What happens?" This question tests whether you know that the design must also work when the cache is empty.

A weak answer says "the cache will fill again" and moves on. A strong answer works out the load on the database with an empty cache, and says what makes it worse. Then it names ways to stop the problem and says what each one costs.

At SDE-1 level you should say that an empty cache sends all reads to the database. At SDE-2 level you should calculate that load and name two fixes. At SDE-3 level you should explain why the problem makes itself worse, and where each fix stops helping.

Think of the tea stall again. Every morning the owner wipes the board clean. At 9 am, 100 customers arrive and all ask the price of tea. The board is empty. The owner walks to the notebook for the first customer. But the other 99 have already asked, and each one starts another walk. That is 100 walks for one answer, and the crowd keeps growing. A better owner says to everyone: "Wait, I am checking." She walks once, writes the price on the board, and answers all 100.

A cache is cold when it has few or no entries, for example when it is new, restarted or cleared. A cache is warm when it holds the popular entries. The cold start is the time right after the cache starts empty. During a cold start the hit rate is close to 0%, so every read goes to the database.

How much more load is that? Before, only the misses reached the database. If the hit rate was 95%, the miss rate was 5%. With an empty cache the miss rate is 100%. The load grows by 100 / 5 = 20 times.

A cache stampede happens when many requests miss the same data at the same time and all go to the database. It starts in two common ways:

• A cold start. All keys are missing at once.
• One popular entry expires. Its TTL ends, and everyone who reads it misses together.

A stampede is worse than the plain arithmetic, for two reasons.

1. Duplicate misses. While one request loads a key, other requests for the same key also miss. These extra misses are duplicates. Their number is the reads per second of that key x the seconds the load takes. In cache-aside, each one asks the database for the same answer.
2. It makes itself worse. The extra load makes the database slower. A slower load means a longer wait, so more duplicates. Requests time out (the app gives up) and may never store the answer, so the cache stays empty. Users retry, which adds more reads.

There is also a third cause. Synchronised expiry means that many entries expire at the same moment, because they were filled at the same moment with the same TTL. After a cold start, or after a script that fills many keys at once, this is common. The stampede then comes back every TTL, like an echo.

Four fixes

1. Request coalescing. When many requests miss one key, only one request asks the database. The others wait for its answer and share it. To coalesce means to join many into one. This is the owner who says "wait, I am checking".
2. TTL jitter. Add a random amount to each TTL, for example plus or minus 25%. Entries filled together then expire at different times.
3. Warm-up. Before a new or restarted cache takes users, fill it with the most popular entries. Use a list of popular keys, or a copy saved on disk. Bring users back in small steps.
4. Protect the database. Limit how many queries run at the same time. Refuse some requests on purpose, with a "busy" answer. Or return old data when you have it. The database stays up, and a few users see an error or old data.

Here is request coalescing in code, inside one app server. A Future is a box that the first request fills with the answer. The other requests wait for the box.

inflight = {}   # key -> a Future (a box that the first request fills)
def get(key):
    value = cache.get(key)
    if value is not None:
        return value                          # hit
    box = Future()
    first = inflight.setdefault(key, box)     # one atomic step: the first caller wins
    if first is not box:
        return first.result(timeout=3)        # the others wait for the first one
    try:
        value = db.load(key)                  # only one request asks the database
        cache.set(key, value, ttl=600 * random.uniform(0.75, 1.25))  # jitter
        box.set_result(value)
        return value
    except Exception as err:
        box.set_exception(err)                # waiting requests fail at once
        raise
    finally:
        del inflight[key]

The call setdefault is atomic, as in lesson 22: check and write happen in one step, so two requests cannot both win. This holds in standard Python (CPython) when threads share one process and the key is text or a number. Python does not promise it, so a lock is safer. Each app server has its own inflight table, so a key is loaded at most once per server. To load it once in total, the first request writes a "loading" marker into the cache. The write works only if the marker is not there yet, in one atomic step. The other requests see the marker, wait a moment, and read the cache again. The marker gets a short TTL, so it disappears if the loader crashes.

We use the shopping app from lesson 31 on a sale day. Its numbers are repeated here.

Assumptions (made up to teach with, not real traffic):

• 2,000 product-page reads per second, as in lesson 31. A read that reaches the database uses 4 ms of CPU. The database has 4 cores, which give 4,000 ms of CPU per second. The product-page TTL is 60 seconds.
• 30 popular pages get 1,500 of the reads (50 per second each). 50,000 rare pages get the other 500 reads per second.
• The home page has a "Top deals" block. It takes 1,800 ms of database CPU to build, and 100 home-page reads per second need it. Its TTL is 600 seconds.
• When the database is overloaded, one product-page load takes 2 seconds. A Top deals build takes 1.8 seconds when the database has no other work.
• When several queries run together, the database shares its CPU equally between them.

Step 1: a normal day. In lesson 31, 313 reads per second reached the database: 313 x 4 = 1,252 ms, which is 31%. The Top deals block is built once every 600 seconds: 1,800 / 600 = 3 ms per second, which is 0.075%.

Step 2: the cold start. The cache restarts. All 2,000 reads go to the database: 2,000 x 4 = 8,000 ms per second, which is 200%. That is 2,000 / 313 = 6.4 times the normal load. Here is the answer to the predict box: the load grows 6.4 times. And the cache may not fill by itself. At 200% the waiting line keeps growing, loads take longer and longer, the app gives up (a timeout), and the answers are not stored.

Step 3: duplicate misses. Each popular page gets 50 reads per second. While one load takes 2 seconds, 50 x 2 = 100 more reads arrive. So each page costs 1 + 100 = 101 queries. For 30 pages that is 30 x 101 = 3,030 queries for 30 answers: 3,030 x 4 = 12,120 ms of CPU. With coalescing it is 30 queries: 30 x 4 = 120 ms.

Coalescing does not help the rare pages. They are 50,000 different keys, so their 500 reads per second all reach the database: 500 x 4 = 2,000 ms, which is 50%. With coalescing the database is at about 50% and can recover. Without it, the 3,030 queries land on top of this load, so loads get slower.

Step 4: warm-up. Before users come back, a script loads the 30 popular pages and the Top deals block: 30 x 4 + 1,800 = 1,920 ms of CPU. When users arrive, only the rare pages reach the database, which is 50%, not 200%. As the rare pages fill in, the load falls towards 31%, in about one TTL (rough).

Step 5: one popular entry expires. Top deals expires. For 1.8 seconds, 100 x 1.8 = 180 more reads miss. That makes 181 builds: 181 x 1,800 = 325,800 ms of CPU. The whole database does 4,000 ms per second, so this is 325,800 / 4,000 = 81.45 seconds of work, about 81 seconds. The 181 builds share the CPU equally, so each needs about 81 seconds to finish. In that time 100 x 81 = 8,100 more reads arrive and start more builds. The key may never be filled. With coalescing there is 1 build: 1,800 / 4,000 = 0.45 seconds of the whole database. The 180 other readers wait about 1.8 seconds and share the answer.

Step 6: the echo. Suppose the home page has 10 such blocks. A warm-up fills all 10 at one moment, so all 10 expire at one moment. Even with coalescing that is 10 builds: 10 x 1,800 = 18,000 ms, which is 18,000 / 4,000 = 4.5 seconds of the whole database when it does nothing else. With jitter of plus or minus 25%, each TTL is between 450 and 750 seconds. That is a range of 300 seconds. The same 18,000 ms of work now spreads over 300 seconds: 18,000 / 300 = 60 ms per second, which is 60 / 4,000 = 1.5% of the database.

• Request coalescing solves duplicate misses (181 builds became 1). It costs waiting: readers wait as long as the load takes, and if the loader fails, all of them fail. It does not help with many different keys.
• TTL jitter solves synchronised expiry (4.5 seconds of full load at one moment became 1.5% load over 300 seconds). It costs a data age that varies: the oldest entry is now 1.25 x the TTL.
• Warm-up solves the cold start (200% became 50%). It costs a list of popular keys or a saved copy to maintain, and database work before users arrive. Add jitter, because everything is filled at the same moment.
• Protecting the database solves overload. It costs some users an error or old data.
• I would change the design when the load at a hit rate of 0 is more than the database can take. Then I add these fixes, not a bigger database, because the problem exists only while the cache is empty.

"After a restart, just wait. The cache fills by itself." It fills only if the database can answer. At 200% load, requests time out, answers are not stored, and users retry. It can last as long as the traffic does.

"Request coalescing fixes a cold cache." It removes repeated asks for the same key. It does not reduce reads for different keys. In the example, the 500 reads per second for rare pages still reached the database (50%). Warm-up and protecting the database do that job.

"A longer TTL prevents stampedes." A longer TTL makes them rarer, not smaller. Without coalescing, when the key expires there are still 181 builds. Entries filled together also still expire together, unless you add jitter.

1. What is a cache stampede? Name the two common ways it starts, and one fix for each.
2. A block takes 2,000 ms of database CPU to build and 50 reads per second need it. The build takes 2 seconds when the database has no other work, and the database has 4 cores (4,000 ms per second). (a) When the entry expires, how many builds start if there is no coalescing? (b) How many seconds of the whole database is that? (c) How many with coalescing?
3. A cache has a hit rate of 90%, and the database is at 25% CPU. The cache restarts during a sale. What load do you expect, and what do you do?