Storage · 14 min

Caching

Keep recent answers in memory so the database only does each piece of work once. Then deal with the three ways that goes wrong: stale data, a full cache, and a stampede.

At 9:02 on a Tuesday, a pop star posts a photo of her new running shoes with a link to your shop. The page is product:7, the Kumo runners. Ten minutes later it is getting 2,000 views a second, up from 3.

Every view runs the same database query: name, price, photos, stock and reviews. Within a minute the database is at 100% CPU. Queries queue up, and checkout, the one page that makes money, starts timing out too.

The shop is down, and almost every query was asking the identical question. This article builds the fix one piece at a time, then shows the way the fix itself breaks.

Why one page can sink the database

The product query takes 120 ms. Disks are not the reason. The query does a lot of work: it joins five tables, sorts the reviews and adds up stock across warehouses.

Say the database can work on 16 queries at the same time. Each query takes 0.12 s, so one worker finishes 1 ÷ 0.12 ≈ 8.3 queries a second, and 16 workers finish about 16 × 8.3 ≈ 133. The viral page asks for 2,000. The other 1,867 each second join a queue that only grows, and soon every request times out.

You could buy a bigger database. But look at what it is doing: the price at 9:12 is the same as at 9:02, so it is working out the same answer 2,000 times a second.

Keep the answer close

Where an answer lives decides how long it takes to fetch. These are rough times for one read:

Even an SSD read is about 800 times faster than our query, which is why the 120 ms is the query’s work, not the disk. And even a cache on another machine answers in about 1 ms, 120 times faster than the query. So keep the finished answer in memory and hand it out again.

Put a cache between your web servers and the database. Give each answer a key: product:7 is the key, and all the page’s data is the value. Every request now follows the same steps:

1. Look up product:7 in the cache.
2. If it is there, use it. That is a hit, and it takes about 1 ms.
3. If it is not there, that is a miss. Ask the database (120 ms), store the answer in the cache, then use it.

This pattern is called cache-aside. The cache sits to one side: your code checks it before the database, and your code fills it after a miss.

What a 90% hit rate really buys

Suppose 9 reads in 10 are hits. Out of every 10 reads, 9 take 1 ms and 1 takes 120 ms. The total is 9 × 1 + 1 × 120 = 129 ms, so the average is 129 ÷ 10 = 12.9 ms. That is nearly ten times faster than no cache.

The general rule, where miss rate is simply 1 − hit rate: average time = hit rate × hit time + miss rate × miss time. With our numbers, 0.9 × 1 + 0.1 × 120 = 12.9 ms.

For product:7 the hit rate can be far above 99%. It is one key read 2,000 times a second, so after one miss fills it, thousands of hits follow.

What deserves a place in the cache

The best things to cache are read far more often than they change, and look the same to everyone who asks. The product page fits: thousands of reads a second, a price change now and then.

• Good: product details, a celebrity’s profile, the home page’s best sellers, the result of an expensive search.
• Careful: anything personal, like a cart. Put the user in the key (cart:alice), or one shopper sees another shopper’s cart.
• Not as the final word: the price you charge. Show the cached price on the page, but read the real price from the database at checkout.
• Not worth it: things read once. They take up room and push out entries that would have been read again.

Every copy goes stale

Once the price is in the cache, there are two copies. When the shop changes the price in the database, the cached copy is stale: an old answer that looks just as confident as a fresh one.

The simplest guard is a time limit. Store each entry with a TTL, short for time to live: “keep this for 60 seconds, then throw it away”. When the TTL runs out, the entry expires. The next read is a miss, and the fresh price comes back from the database.

TTL is a dial. A long TTL gives more hits but older data. A short one gives fresher data but more misses. For product:7 even a 10-second TTL costs just one database query per 10 seconds, against 20,000 reads served from memory. Or so it seems; the section on the second outage comes back to this.

When the cache is full, something has to go

Memory is limited. Your shop has 50,000 products and the cache has room for, say, 5,000. When a miss needs to store a new product and every slot is taken, the cache throws one entry out. That is eviction. Which one should go?

The usual answer is LRU, least recently used: evict the entry nobody has asked for in the longest time. The bet is that what was read recently will be read again soon. product:7 is read every half a millisecond, so it is never the least recent and never leaves.

The other common answer is LFU, least frequently used: evict the entry with the fewest reads. It protects a page that is popular all day from a sudden run of one-off reads. The cost is that read counts pile up, so a page with a million reads yesterday and none today still looks valuable and stays.

Redis lets you pick either one with a single setting (maxmemory-policy), so this is a choice you make, not code you write.

When the price changes

Waiting for the TTL means some shoppers see the old price for up to a whole TTL. Usually you also act at the moment you write. There are two choices, and the demo’s On price change buttons let you try each.

• Delete the key. Update the database, then delete product:7 from the cache. The next read misses and fetches the new price. Removing a cached entry like this is called invalidation.
• Update the key. Write the new value into the cache as well. The next read is a hit. The risk: two price changes, to $115 and then $120, run on two servers at once. The database ends at $120, but if the first server is a few milliseconds slow, its cache write of $115 lands last. The cache now says $115 until the TTL ends.

Deleting is the safer default, because a delete can’t put a wrong value in; the worst it costs is one extra miss. Facebook’s memcache, which serves billions of requests a second, works this way: a web server changes the database, then deletes the key, and the next read refills it.

Keep a TTL even when you delete on write. If a delete is ever lost, say a server crashes between the two steps, the TTL still limits how long the wrong price lives.

The second outage: the hot key expires

The shop is back. product:7 sits in the cache with a 60-second TTL and the database is quiet. Then, once a minute, the database spikes to 100% for a moment and some shoppers get errors.

This is a cache stampede, also called a thundering herd: many requests miss the same key at once and all rush the database. The fix is to let one request refill the key while the others wait for its answer.

• Share one refill. The web server remembers that a query for product:7 is already on its way, and later misses wait for that result instead of starting their own. Go’s singleflight package and NGINX’s proxy_cache_lock work this way. This happens inside each web server, so each one still sends one query: a shop running 20 web servers sends 20, not 240.
• Take a short lock. The first request to miss sets a lock key in Redis that only one request can win: SET lock:product:7 1 NX PX 200 (“set it only if it doesn’t exist, and drop it after 200 ms”). 200 ms is a bit longer than the 120 ms query, so the lock can’t get stuck if the winner crashes. The winner refills; the rest keep checking the cache every few milliseconds until the value appears. This works across all web servers, so the database gets 1 query.
• Refresh early. Store the expiry time with the value. The first request that sees less than, say, 5 s left starts a fresh query in the background, while everyone keeps getting the current copy. Nobody ever misses the hot key.

In the demo above, press Stampede. product:7 was cached at 0 s with your TTL; 2 s after it expires, 50 reads arrive within 0.1 s. All 50 are MISS. Database reads jumps to 51 (the first fill at 0 s plus these 50), and its busiest second is 50. Now tick Stampede protection. The same reads replay: 1 MISS, 49 WAIT, and a busiest second of 1. A WAIT is not a hit, so the hit rate stays at 0%.

The waiters still take up to 120 ms, because they wait for the refill. The database, though, does one query instead of 50.

The whole fix in one function

Here is cache-aside with a TTL, delete-on-write and one shared refill per web server. With the Redis lock instead, refill_in_progress would check the lock key. Look for the three outcomes: a hit, a wait for someone else’s refill, or doing the refill yourself.

get_product(id):
    key = "product:" + id
    value = cache.get(key)
    if value != null:
        return value                    # hit: about 1 ms
    if refill_in_progress(key):
        return wait_for_refill(key)     # someone else is asking the database
    start_refill(key)
    value = db.query_product(id)        # miss: about 120 ms
    cache.set(key, value, ttl = 60)
    finish_refill(key, value)           # hand the value to everyone waiting
    return value

change_price(id, new_price):
    db.update_price(id, new_price)
    cache.delete("product:" + id)       # after the database, never before

Ready for the next viral post

Now you can plan for the next launch instead of reacting to it. The numbers: 2,000 views a second on one product, and a database that handles about 133 queries a second.

• Hit rate: aim for 99% or better, so misses stay near 20 a second.
• Memory: a product page’s data (text, prices, a dozen image links, the top five reviews) is around 10 KB, so 5,000 popular products × 10 KB = 50 MB. That fits easily in one small Redis server.
• Freshness and stampedes: delete on write, a 60 s TTL as a backstop, and the Redis lock so each expiry of product:7 costs 1 query instead of 240.

One last warning. The cache now hides how slow the database is. If the cache restarts empty, every read is a miss at once, and you are back where you started: the database down, ten minutes after the pop star’s post. Before sending traffic to a fresh cache, fill it with your most popular products.