Caching

The problem: a database that can't keep up

Picture an online shop at its busy hour. Twenty app servers handle 20,000 product page views a second, and every page reads its product from the database. Say one database server answers about 5,000 simple lookups a second: it is being asked four times what it can do.

More app servers don't help: the lookups follow the page views, not the servers, so 40 app servers handling 20,000 page views a second still send 20,000 lookups to the same database. A second database with a copy of the data helps a little, but at about 5,000 lookups a second each you would need four of them, all doing the same work.

The clue is in the lookups: shoppers look at the same few products over and over, so the database keeps finding the same rows. Reading memory takes about 100 nanoseconds, while a database has to find the row, often on an SSD (about 100 microseconds per read) or a disk. Keeping copies of popular rows in memory is the fix: a cache. One cache server answers about 100,000 lookups a second.

How cache-aside works

The most common way to use a cache is cache-aside (also called lazy loading). For each lookup, the app server:

1. Asks the cache for the product.
2. If the cache has it, that's a hit: it uses the copy, and the database isn't asked at all.
3. If not, that's a miss: it reads the product from the database and stores a copy in the cache.

The cache never talks to the database; the app server does both. In code it's a few lines:

def get_product(product_id):
    product = cache.get(product_id)
    if product is None:                      # a miss
        product = db.find_product(product_id)
        cache.set(product_id, product, ttl=60)
    return product

Here is a cache that starts empty, given six lookups:

lookup  product  in the cache before  result
1       p1       (empty)              miss: read the database, store p1
2       p2       p1                   miss: read the database, store p2
3       p1       p1 p2                hit
4       p3       p1 p2                miss: read the database, store p3
5       p1       p1 p2 p3             hit
6       p2       p1 p2 p3             hit

3 hits, 3 misses: the database was read 3 times instead of 6

Every miss here is the first lookup of a product: a new cache starts cold and warms up as products are read.

Hit rate: what reaches the database

The hit rate is the share of lookups the cache answers: hits ÷ all lookups. In the six lookups above it's 3 ÷ 6 = 50%. On ten lookups such as p1 p2 p1 p1 p3 p1 p2 p1 p4 p1, only the first lookup of each of the four products misses, so the hit rate is 6 ÷ 10 = 60%.

For the database, what matters is the other side: only the misses reach it. At the busy hour's 20,000 lookups a second:

• 50% hits: 10,000 lookups a second still reach the database, twice what it answers. The cache isn't enough.
• 90% hits: 2,000 a second, well under its 5,000.
• 99% hits: 200 a second, ten times fewer than at 90%.

Going from 90% to 99% sounds like a small step, but it cuts the misses from 10% of the lookups to 1%: the last few percent of hits matter most.

High hit rates are realistic because popularity is uneven: in most shops a small share of products gets most of the views. Say the 1,000 most viewed of 100,000 products get 90% of the views. A cache holding just that 1% of the products answers about 90% of the lookups. The hit rate counts lookups, not products.

Stale copies: TTL and delete on write

A cached copy doesn't change when the database does. Say the mug (p1) is in the cache at $20, and the shop drops its price to $15 in the database. Every lookup of p1 is still a hit, so shoppers keep seeing $20, possibly forever. Two fixes, usually used together:

• A TTL (time to live): every copy expires a fixed time after it's stored, say 60 seconds. No copy is ever more than a minute old: the first lookup after it expires misses and reads the new price. A shorter TTL means fresher copies but more misses; a longer one means more hits but older copies.
• Delete on write: the code that writes a new price also deletes the cached copy, so the very next lookup misses and loads $15. Deleting is usually safer than writing the new value into the cache, because two updates racing each other can leave the older value there. The TTL stays as a safety net for a delete that never happens.

Two topics have lessons of their own: what to drop when the cache is full (eviction: LRU, LFU), and how caches go wrong, from write-through versus write-back to a stampede when a popular copy expires.

What to cache, and what not

A cache trades freshness for speed, and memory is smaller than disk, so choose what goes in:

• Cache it: data that's read often, changes rarely and is fine a few seconds old. Product names, photos and descriptions, the menu of categories, today's best sellers.
• Read it from the database: data that must be exact at that moment, such as a bank balance before a payment or the stock count at checkout (a stale count lets two shoppers buy the last one), and data that's rarely read, like orders from years ago.

Where caching shows up in design interviews

Almost every read-heavy design needs a cache: the redirects of a URL shortener, product pages, user profiles, a news feed. Put it in front of the database on the busy path, the reads that carry most of the traffic, and say the numbers out loud:

1. Name the reads: "product lookups, about 20,000 a second at the busy hour."
2. Place the cache: "cache-aside in front of the products database."
3. State the hit rate you assume: "say 90%, since a small share of products gets most of the views."
4. Say what reaches the database: "about 2,000 a second, under the 5,000 one server answers."
5. Say how copies stay fresh: "a TTL of a minute, and delete the copy when a product changes."

"Add a cache" without numbers tells the interviewer little; the hit rate and what's left for the database show the design works.

Common interview questions on caching

What happens on a cache miss?

With cache-aside, the app server reads the data from the database, stores a copy in the cache and returns it; the next lookup of the same key is a hit. Misses are all the database sees, so the miss rate decides whether it keeps up.

How do you keep the cache from serving stale data?

Delete the cached copy when the data is written, so the next read loads the new value, and give every copy a TTL as a safety net. The TTL is the longest a copy can be out of date, so pick it by asking how old the data is allowed to be.

What happens if the cache goes down?

Every lookup falls through to the database: at the busy hour, 20,000 a second on a server that answers about 5,000. So spread the copies over several cache servers: losing one sends only its share of the lookups to the database.

Cache-aside or read-through?

In cache-aside the app server loads the data on a miss; in read-through the cache loads it itself, through a loader it's given. Cache-aside works with any key-value cache, which is why it's the usual default.

Summary

• A cache keeps copies of popular data in memory, in front of the database.
• Cache-aside: check the cache first; on a miss, read the database and store a copy.
• Hit rate = hits ÷ lookups; only the misses reach the database. At 20,000 lookups a second, 90% hits leave 2,000, 99% leave 200.
• Fresh copies: delete the copy on write, and give every copy a TTL.
• What to cache: read often, changes rarely, fine a few seconds old.