Cache-aside, write-through, write-back

A cache holds a copy of data. After some time the real data changes. A seller changes a price. A buyer adds a like. What happens to the copy? Interviewers ask this because an old copy shows wrong data, and a copy that is updated badly can show wrong data too.

A weak answer says "update the cache" and stops. It does not say who does it, in which order, or what happens when one step fails. A strong answer picks one way, says what it costs, and uses numbers: how often the data is read, how often it changes, and how much old data or lost data is fine.

At SDE-1 level you should explain how one way works. At SDE-2 level you should compare three ways with numbers. At SDE-3 level you should also explain what breaks when two requests change the same data at the same time, or when the cache fails.

Go back to the tea stall from the last lesson. The prices are in the notebook in the back room. That is the database. The board near the counter is the cache. Now one price changes. The owner has three choices:

1. Change the notebook, then erase that line on the board. The next customer asks, the owner walks to the notebook, and writes the new price on the board.
2. Change the notebook and the board together, before serving anyone.
3. Change only the board. Stick a note on it: "copy to the notebook tonight". In the evening the owner copies all the changes at once.

Each choice answers one question: who writes the cache, and when? In a system, the owner is your app, or a library between the app and the database. The three choices have names.

Cache-aside

The cache sits beside the database, and the app talks to both. A read works as in the last lesson: check the cache, and on a miss read the database and store the answer. A write has two steps:

1. Write the new value to the database.
2. Delete the entry from the cache.

The next read of that key is a miss, so it loads the new value from the database. Only data that someone reads ever enters the cache.

What can go wrong:

• Wrong order. If you delete first and write the database second, a reader can arrive in between. It misses, reads the old value from the database, and stores it. The cache now keeps the old value until the TTL ends. So write the database first.
• A failure between the steps. The app crashes after the database write and before the delete. The cache keeps the old value until the TTL ends. The TTL puts a limit on this problem.
• Updating instead of deleting. Some teams write the new value into the cache instead of deleting the entry. Two requests change one price at the same time: write A sets 100 and write B sets 120. The database gets A, then B, and holds 120. The cache writes can arrive as B, then A, and the cache holds 100. That is wrong until the TTL ends. A delete cannot do this, because the next read always loads from the database. The cost of deleting is one extra miss after each write.
• A slow reader. A reader misses and reads 100 from the database. Then write B saves 120 and deletes the entry. Then the slow reader stores 100. This is rare, because the reader must be slower than a whole write. The TTL ends it.

Write-through

Every write goes to the database and to the cache, and the app says "done" only after both are written. A read of a written key is a hit and shows the new value, until the entry expires. A read of a key that was never written is a miss, and works as in cache-aside.

What can go wrong:

• Slower writes. Each write now has two steps.
• Data that nobody reads. The cache stores every written item, even items that no one will read.
• A failure between the steps. Write the database first. If the cache write then fails, the cache is old, and the TTL ends that. If you write the cache first and the database write fails, the cache shows data that the database never had. That is worse.
• Two writers at once. The same order problem as above can leave the older value in the cache, even when both writers write the database first. The fix is to make the writes for one key happen one after another.

Write-back

The app writes only to the cache, and the cache says "done" at once. A short time after that, without making the user wait, the cache saves the changes to the database. It often saves many changes together. Write-back is also called write-behind.

Two good things follow. A write is as fast as a cache write (1 millisecond). And many changes to one key become one database write. For example, 10 changes to one counter can become one save.

What can go wrong:

• Lost writes. If the cache fails before it saves, those changes are lost. The database never had them.
• A database that is behind. Until the save, the cache has newer data than the database. Anyone who reads the database directly sees old data.

So use write-back only for data where losing a few seconds of changes is fine.

We use the shopping app from the last lesson, on a sale day.

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

• The app serves 2,000 product-page reads per second, as before.
• 20 prices or stock counts change every second.
• The app counts 2,000 page views per second, spread over 1,000 products.
• A database write uses 4 ms of CPU time, like a read in the last lesson. The database has 4 cores, which give 4,000 ms of CPU per second. So it can take 4,000 / 4 = 1,000 writes per second.
• A database write takes 20 ms. A cache read or write takes 1 ms.
• One cache entry uses 2 kilobytes (KB) of memory.

Step 1: price changes with cache-aside. One change is a database write (20 ms) plus a delete (1 ms), which is 21 ms. After each delete, the next read of that product is a miss. There are 20 changes per second, so there are at most 20 extra misses per second.

• Extra database work = 20 x 4 ms = 80 ms of CPU per second.
• That is 80 / 4,000 = 2% of the database. It is 20 of 2,000 reads, which is 1%.

Step 2: the same changes with write-through. One change is a database write (20 ms) plus a cache write (1 ms), which is 21 ms. The same as cache-aside. There are no extra misses, so the 2% is saved. The cost is memory. Assumption: 18 of the 20 changes per second are for products that nobody reads soon.

• With a TTL of 60 seconds, those entries live 60 seconds: 18 x 60 = 1,080 unread entries x 2 KB = 2,160 KB, about 2 MB. Small.
• With no TTL, a change to a product that is already in the cache replaces its entry. So the cache cannot grow past the whole product list. Assumption: the shop has 50,030 products (the 30 popular and 50,000 rare pages of the last lesson). 50,030 x 2 KB = 100,060 KB, about 100 MB. Small too.
• The cost is large when each write makes a new key, for example a new review. With no TTL, after one day: 18 x 86,400 seconds = 1,555,200 new entries x 2 KB = 3,110,400 KB, about 3.1 GB. The cache keeps growing.

So for prices, write-through saves at most 2% of the database and costs little memory. For a list of products that is read far more than it changes, cache-aside is simpler and caches only what is read. Always set a TTL.

Step 3: the page-view counter. With cache-aside or write-through, each view is one database write.

• 2,000 writes per second x 4 ms = 8,000 ms of CPU per second.
• That is 8,000 / 4,000 = 200% of the database. It cannot keep up.

With write-back, the cache adds up the views in memory, one number per product. Every few seconds it saves one write per product. Assumption: every product gets at least one view in each period, so these are upper limits.

Saving every 1 second leaves no room for other work. Saving every 5 seconds uses 20% of the database. The price is that a cache failure loses up to 5 seconds of counts, which is 10,000 views.

Here is the answer to the predict box. Only write-back can keep up: 200 writes per second instead of 2,000. What you could lose is the changes not yet saved, up to 10,000 views. For a view count that is fine. For a payment it is not.

• It solves: old copies in the cache (all three ways), and, for write-back, a database that cannot take every write.
• It costs: extra misses, slower writes, or lost writes. Each way pays in a different place.
• I would change the way when the number of reads for each write changes. I would also change it when the business cannot accept the old data or the loss that the current way allows.
• How to choose: start with cache-aside. Use write-back only when the database cannot take the writes and a small loss is fine.
• Money and stock: read from the database when the answer decides a payment. A cache may be a little old on a page. It must not be old when you charge.

"Write-through keeps the cache and the database always the same." It does not. There are two steps, and one can fail. Two writers at the same time can leave the older value in the cache.

"Write-back is just a faster write-through." No. Write-through waits for the database before it says "done". Write-back does not wait. The speed comes from not waiting, and the price is that unsaved writes are lost if the cache fails.

"On a write, update the cache with the new value. Deleting wastes a read." Updating can leave the older value in the cache when two writes happen together. Deleting is safer. It costs one extra miss, and in the example that was only 1% of reads.

1. Name the three ways. For each, say where a write goes first.
2. A counter gets 3,000 writes per second over 1,500 products. A database write uses 4 ms of CPU, and the database has 4 cores (4,000 ms per second). (a) How busy is the database if every write goes to it? (b) With write-back, saving every 4 seconds, what is the most it must write per second, and how busy is it? (c) What is the most you can lose?
3. A teammate changes a price like this: first delete the cache entry, then write the database. What can go wrong, and what do you change?