When Caches Go Wrong

The problem: the old price comes back

An online shop caches its products the usual way: a write updates the database and then deletes the cached copy, and every copy has a TTL of 10 minutes. The shop drops the mug (product p1) from $20 to $15. The database says $15, the delete ran, and yet minutes later the cache says $20 again.

The cause is a race between a read and a write. In cache-aside only reads store copies: a page view that misses reads the database and stores what it read. If it reads just before the price change and stores just after the delete, it puts the old price back:

step  who           does                           cache     database
1     page view A   asks the cache: a miss         no p1     $20
2     page view A   reads the database, gets $20   no p1     $20
3     price change  writes $15                     no p1     $15
4     price change  deletes p1 from the cache      no p1     $15
5     page view A   stores the $20 it read         $20       $15

Nothing deletes the $20 again, and a hit never asks the database, so shoppers see $20 until the copy's TTL runs out, 10 minutes after step 5.

Keeping stale copies short

The race is rare: a read has to start before the write and store its copy after the delete. You can't rule it out, but three habits keep it harmless:

• Delete after the database write, not before. Delete first, and any page view between the delete and the write misses, reads the old price and stores it. Deleting after the write leaves only the rare race above.
• Keep a TTL on every copy. It's the safety net: whatever slips past the delete expires on its own. Without one, the $20 from the race would stay until the next price change.
• Use short TTLs for data that changes. With a 30-second TTL on products, the race shows the old price for 30 seconds at most, not 10 minutes.

Three ways to write: cache-aside, write-through, write-back

• Cache-aside: the app writes the database, then deletes the copy; the next read misses and loads the new value. It's simple, and only data that's read takes memory; its weak spot is the race above.
• Write-through: every write goes to the cache and the database together, and is done only once both have it. Reads right after a write find the new value, and nothing is lost if the cache dies. The price: each write waits for two stores, and the cache fills with everything written, read or not.
• Write-back (or write-behind): writes go to the cache only and are done at once; the cache writes them to the database later, often in batches. Writes are fast and the database sees far fewer, but anything not yet written is lost if the cache dies first.

A view counter at 10,000 views a second fits write-back: the +1s add up in the cache and the total goes to the database once a second, 1 write instead of 10,000, and a crash loses at most a second of views. A shopper's cart must never be lost, so never write-back: write-through says done only once the database has it. (A bank balance stays out of the cache, as in Caching.) A user's profile, read on every page and edited a few times a year, is the usual cache-aside case.

The cache stampede

A hot key is a copy that a huge share of requests read. Say the shop's home page gets 10,000 requests a second, all served by one cached copy with a 60-second TTL, and building the page takes the database about 0.2 seconds. The moment the copy expires, every request misses until a new copy is stored, and each miss starts its own build:

after the expiry   requests that missed   builds running
0 ms               1                      1
10 ms              100                    100
100 ms             1,000                  1,000
200 ms             2,000                  the first build is done

That's 10,000 a second × 0.2 seconds = 2,000 builds of the same page where 1 would do, arriving at 10,000 a second, twice the 5,000 simple lookups a second one database server answers. And 2,000 is the best case: so many builds slow the database down, the first one takes longer, and still more requests miss. This is a cache stampede, also called a thundering herd.

Stopping a stampede

• One build, under a lock. The first request to miss takes a lock on the key (in the cache: a key set only if nobody holds it, with a short expiry in case that server crashes) and builds the page. The others wait about 0.2 seconds for its copy, or better, get the old copy, kept a little past its TTL for this. One build instead of 2,000. Inside one server the same idea is request coalescing: many requests for one key share a single trip to the database.
• Refresh ahead. A job builds the home page every 50 seconds, so a fresh copy replaces the old one 10 seconds before its 60-second TTL ends. No request ever misses, for 72 builds an hour instead of 60.
• Jittered TTLs. Copies stored together expire together: if a job stores 6,000 products at 9:00 with a 10-minute TTL, all 6,000 expire at 9:10:00. With a TTL of 10 minutes plus a random 0 to 60 seconds, they expire over a minute: about 100 a second instead of 6,000 in one.

When the whole cache goes cold

A cache server that restarts comes back empty: a cold cache. At 20,000 product lookups a second, the 90% hit rate that left the database 2,000 a second is gone, and every lookup misses: 20,000 a second, four times what the database answers. Warm the cache up before it takes traffic, most viewed products first, or limit how many misses reach the database at once. Then give the warmed copies jittered TTLs, or they all expire together 10 minutes later.

Lookups for things that don't exist always miss: there's nothing to store. If a deleted product is still linked from an old blog post and opened 50 times a second, all 50 reach the database. Cache the "not found" answer too, with a short TTL such as 60 seconds, and the database sees about one of those lookups a minute.

Where it shows up in design interviews

Adding a cache is the easy part; the follow-up is "what can go wrong?" Answer before you're asked: how copies stay fresh (write the database, then delete the copy, with a short TTL as the safety net), which write strategy each kind of data gets, and what happens when your hottest key expires (a lock, refresh ahead, jittered TTLs). If a cache restart would flood the database, say how you warm it up.

Common interview questions

What is a cache stampede, and how do you prevent it?

When a popular copy expires, every request misses at once and rebuilds the same data, which can overload the database. Let one request rebuild under a lock while the others wait or get the old copy, refresh hot copies before they expire, and add jitter so many keys don't expire together.

Write-through or write-back?

Write-through waits for the database on every write: reads after it are fresh and nothing is lost, but writes are slower. Write-back answers at once and writes the database later: fast, but recent writes can be lost, so use it for counters and activity data, never for payments.

Why delete the cached copy on a write instead of updating it?

Two writes can reach the database in one order and the cache in the other, which leaves the older value in the cache. A delete is the same in either order: the next read loads the newest value from the database.

Summary

• Stale copies: a read racing a write can store the old value after the delete. Delete after the write; short TTLs are the safety net.
• Writes: cache-aside deletes the copy, write-through writes both, write-back writes the cache now and the database later.
• Stampede: when a hot key expires, every request misses: 2,000 builds where 1 would do. Use a lock, refresh ahead and jitter.
• Cold cache: after a restart every lookup misses; warm it up, and cache "not found" answers too.