Caching basics: hit, miss, TTL, hit rate

Many apps read the same data far more often than they change it. Think of a product page on a sale day. Thousands of people read it every second, and its price changes once a day. A common answer is to keep a copy of the popular data in fast memory. Interviewers ask about this because many candidates say it without any numbers.

A weak answer names a tool and stops there. A strong answer gives numbers, for example: "Reads are 2,000 per second. The database can only do 1,000. If 9 of every 10 reads are answered from the copy, only 200 reads per second reach the database." A strong answer also says what can go wrong: the copy can be older than the real data.

At SDE-1 level you should explain how the copy works and when it is used. At SDE-2 level you should also estimate how many reads the copy answers, and say how old the data can get.

Think of a tea stall. The owner sells 50 kinds of snacks. The prices are written in a notebook in the back room. Walking to the back room for every customer is slow. So the owner writes the prices on a board near the counter. Most customers ask about the same few items, so the board answers almost every question. When a price changes, the owner rewrites that line on the board.

In a system, the notebook in the back room is the database. It holds the correct, latest data. The board is the cache: a small, fast store that keeps a copy of data you read often. A cache usually keeps its data in memory (RAM), so a read is very fast. In this lesson we assume a cache read takes 1 millisecond (ms) and a database read takes 20 ms.

Why the database is usually the slow part. Every read that needs data goes to the same database. Each query does real work. The database finds the rows with an index (lesson 20), it may read from disk, and it uses its CPU. So a database can answer only a fixed number of queries per second. When reads grow, the database usually reaches its limit before the other parts do. A bottleneck is the one part that limits how much work the whole system can do. For a system with many reads, the bottleneck is usually the database.

Here is how a read works with a cache:

1. The app asks the cache for the data, using a key. The key is the name of the data, for example product:4821.
2. If the cache has it, that is a hit. The app returns the data. The database is not touched.
3. If the cache does not have it, that is a miss. The app asks the database, returns the answer, and also stores the answer in the cache for next time. The stored copy of one key is called an entry.

The hit rate is the share of reads that are hits. A hit rate of 90% means 9 reads in 10 are answered by the cache. The miss rate is the rest: 1 minus the hit rate. Only the misses reach the database, so:

• database reads per second = all reads per second x miss rate

This is why a cache protects the database. It removes most of the work from the bottleneck.

A cached copy cannot stay forever, because the real data may change. So every entry gets a time to live (TTL). TTL is the number of seconds an entry may stay in the cache. After that time the entry expires (the cache removes it), the next read is a miss, and the app loads a fresh copy. Before it expires, the copy may be stale: old data that no longer matches the database. In the tea stall, the owner could wipe the whole board clean every morning and start again. That is a TTL of one day.

Reads do not come at fixed times. They arrive at random moments. So two reads of the same key sometimes come close together and sometimes far apart. Even a key that is read rarely sometimes gets a second read before its entry expires.

TTL is a trade-off in one number. A longer TTL means each stored copy serves more reads, so the hit rate rises. It also means the copy can be older than the real data. A shorter TTL gives fresher data and more misses.

Take a shopping app on a big sale day. Many people open the pages of a few popular phones, and a few people open products that are rarely viewed. We want to know how much a cache helps the database.

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

• The app serves 2,000 product-page reads per second at the peak.
• Each read that reaches the database costs 4 ms of database CPU time.
• The database has 4 CPU cores. One core gives 1,000 ms of work per second, so 4 cores give 4,000 ms per second.
• A cache read takes 1 ms. A database read takes 20 ms.
• The TTL is 60 seconds.

Step 1: the database without a cache.

• Work per second = 2,000 reads x 4 ms = 8,000 ms of CPU per second.
• That is 8,000 / 4,000 = 200% of what the database can do. The database has twice the work it can do. Requests wait longer and longer, and then fail.

Step 2: the hit rate of one key. Suppose one key is read r times per second and its TTL is L seconds. When the entry is stored, the read that stored it was a miss. After that, the entry serves about r x L reads before it expires. So in one life of an entry there is 1 miss and r x L hits:

• hit rate = (r x L) / (1 + r x L)

This formula assumes reads arrive at random moments and the cache never runs out of memory. Real systems differ a little, but the formula gives a good rough number.

Step 3: a popular page. Assumption: 30 popular phone pages get 1,500 of the 2,000 reads. That is 50 reads per second for each page (1,500 / 30 = 50).

• r x L = 50 x 60 = 3,000
• hit rate = 3,000 / 3,001 = 0.9997, which is 99.97%

Step 4: a rare page. Assumption: 50,000 rare pages share the other 500 reads per second. Each rare page is read 500 / 50,000 = 0.01 times per second, which is once every 100 seconds on average.

• r x L = 0.01 x 60 = 0.6
• hit rate = 0.6 / (1 + 0.6) = 0.6 / 1.6 = 0.375, which is 37.5%

Here is the answer to the predict box. A page read on average once every 100 seconds, with a 60-second TTL, has a hit rate of about 37.5%. Usually the entry expires before the next person comes. But because reads come at random moments, sometimes a second read arrives in time. So the cache helps a little, not a lot. A longer TTL would help this page, but it would also keep old data for longer.

Step 5: the overall hit rate. Add the hits from each group:

• Popular pages: 1,500 reads x 0.9997 = 1,499.5 hits per second (rounded from 1,499.55)
• Rare pages: 500 reads x 0.375 = 187.5 hits per second
• Total hits = 1,499.5 + 187.5 = 1,687 per second
• Overall hit rate = 1,687 / 2,000 = 0.8435, which is about 84%

Step 6: the database with the cache.

• Misses = 2,000 - 1,687 = 313 reads per second
• Work = 313 x 4 ms = 1,252 ms of CPU per second
• That is 1,252 / 4,000 = 31% of the database. The database went from 200% to 31%.

Step 7: speed. A hit takes 1 ms. A miss checks the cache first (1 ms) and then reads the database (20 ms), so it takes 21 ms.

• Average = 0.8435 x 1 ms + 0.1565 x 21 ms = 0.84 + 3.29 = 4.13 ms
• Without the cache every read takes 20 ms, if the database is not overloaded. The average is about 5 times better (20 / 4.13 = 4.8).

Now look at the slowest reads. An average can hide slow reads, so we also look at the p95: the time that 95 of every 100 reads beat. The miss rate is 15.65%, which is more than 5%. So the read at the 95% mark is a miss, and the p95 is 21 ms. That is slightly worse than the 20 ms without a cache. The cache made the average much better and left the p95 slow. To improve the p95 you need a hit rate above 95%.

• It solves: a database that cannot keep up with repeated reads, and slow reads. At 84% hits the database load fell from 200% to 31%.
• It costs memory. The cache must hold the entries. It also adds one more part that you must run and watch.
• It costs fresh data. For up to one TTL, a user can see stale data. Whether that is fine depends on the data. An old product description is fine. An old seat count may not be.
• It costs simplicity. Your system now has two copies of the data, and they can disagree.
• I would change the TTL when the data must be fresher: then shorten it, or do not cache that data. I would also change it when the database is still too busy: then lengthen it, or cache more keys.
• Good to cache: data that is read often, changes rarely, and is the same for many users, like a product page.
• Do not cache data that must always be exact, like a bank balance before a payment. Also skip data that is read only once, or that is cheap to compute.
• A cache helps most when a few keys get most of the reads. If every read asks for a different key, the hit rate is close to zero.

"A cache always makes the system faster." It does not. A miss is slower than having no cache, because it checks the cache first and then reads the database. If most reads are misses, you pay for both. In the example, the average improved, but the p95 did not.

"A longer TTL is always better, because the hit rate goes up." The hit rate does go up, but with limits. For a popular page the hit rate is already 99.97%, and doubling the TTL gives almost nothing. The cost is that the data stays old for longer. Raise the TTL only for keys that are rarely read and may be a little old.

"Going from a 90% to a 99% hit rate is a small improvement." It is a very large one. At 90% hits, 10% of reads reach the database. At 99% hits, 1% do. The database load is 10 times smaller. Always think in the miss rate, because the miss rate is the load on the database.

1. What is the hit rate? What happens to a read that is a miss?
2. A page is read on average 0.05 times per second (once every 20 seconds). The TTL is 60 seconds. (a) What is the hit rate? (b) What is the hit rate if the TTL is doubled to 120 seconds?
3. A teammate wants to cache each customer's bank balance for 10 minutes to reduce the load on the database. What is wrong with this plan, and what would you ask first?