Keeping cached data fresh (invalidation)

A cache holds a copy of data. When the real data changes, the copy is wrong until someone fixes it. A user saves a new price or a new profile photo, reloads the page, and sees the old one. Interviewers ask: "How do you keep the cache correct?"

A weak answer says "I will update the cache when the data changes". It does not say what happens when that step fails, or when the same data sits in many places. A strong answer first asks how old the data may be. Then it chooses a way, gives a number for how wrong the cache can be, and says what the way costs.

At SDE-1 level you should name two ways to keep a cache fresh. At SDE-2 level you should estimate how many reads are old for each way. At SDE-3 level you should also explain what breaks when one change touches many cached entries, or when the step that removes the entry fails.

Go back to the tea stall (lesson 31). The owner changes a price in the notebook. The board near the counter still shows the old price. A customer who reads the board pays the old price, or argues. In lesson 31 you met this: the copy is stale when it no longer matches the database.

The owner has three ways to fix the board.

1. Wipe the whole board every hour. Nobody needs to remember anything, but a wrong price can stay for up to an hour.
2. Wipe the one line at the moment the price changes. The board is almost always right, but the owner must remember every change, and every board that shows that price.
3. Number the boards. When a price changes, the owner hangs a new board with a new number. Customers always read the board with the highest number. The old board stays on the wall, and nobody reads it.

In a system, these are three ways to keep a cache fresh. To invalidate an entry means to make the cache stop using it because the data changed. The ways are: time to live (TTL), deleting the entry when data changes, and changing the key.

Way 1: wait for the TTL

Every entry has a TTL (lesson 31). When it ends, the cache removes the entry. The next read loads fresh data. With this way, the app does nothing when data changes. It is simple, and it fixes itself. The cost: an entry can be stale for up to one TTL.

A change lands at a random moment of an entry's life. So on average the entry is stale for half a TTL after the change. If the data changes rarely, compared with the TTL:

• share of reads that are stale = changes per second x TTL / 2

This is a rough estimate. It works only when the number of changes during one TTL is much smaller than 1. If the data changes every few seconds, the copy is stale for most of its life.

How to choose the TTL: ask "how old may this data be?" This is a business question. A product description can be an hour old. A price can be a minute old on a listing. A stock count that decides if you can buy should not come from the cache at all (lesson 22).

Way 2: delete the entry when the data changes

This is cache-aside from lesson 32. The app writes the database, then deletes the cache entry. The next read is a miss and loads the new value. Order matters: database first, then delete. Writing the new value into the cache instead is riskier when two changes arrive together (lesson 32).

The copy is now stale only for the short time between the database write and the delete. Assumption: 5 ms. The cost:

• One extra miss after each change.
• Every entry that holds the data must be found. One price may be in the product page, in three category lists, and in search results. One change then needs several deletes. If the code forgets one key, that page shows the old price until its TTL ends. The customer can see two prices for one product.
• A delete can fail. The app may crash after the database write, or the network to the cache may fail. The entry stays stale. Nobody retries.
• Changes that do not pass through your code. If an admin tool or a script changes the database directly, nobody deletes the entry.

So always keep a TTL as well. The delete makes the cache fresh in the usual case. The TTL ends the problem when a delete is lost, or when a slow reader stores an old value after the delete (lesson 32). It is a safety net.

Way 3: change the key

Put a version number in the key: product:4821:v7. When the data changes, the version becomes 8. Readers build the key from the current version, so they never read v7 again. The old entry is not deleted. It is never read. The cache removes it when its TTL ends or when the cache is full and needs space.

This is useful when one change would need many deletes: change the version of a list, and every old page of the list is ignored. The costs:

• A reader must first find the current version. That is one more cache read, about 1 ms more.
• The version number must come from a place that every server trusts. If the cache loses it, a new version could reuse an old key. Start again from a number that has never been used.
• Old entries use memory until they are removed.

Count the stale reads

Do not say "the cache is fresh". Say how many reads are stale. A stale read is a read that returns data different from the database at that moment. Then compare with what the business accepts. Simulator Level 3 does this. It counts a read as stale if it misses a change older than 5 seconds. A design passes only if less than 3% of reads are stale.

We use the shopping app from lessons 31 and 32.

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

• The shop has 50,030 products. In total, 20 prices change every second (both from lesson 32). So one product changes 20 / 50,030 = 0.0004 times per second, which is once every 2,500 seconds (rounded).
• One popular phone page is read 50 times per second (lesson 31).
• During a sale, the stock count shown on the page of one item changes every 10 seconds on average. (The real check at buying time reads the database, as in lesson 22.)
• The three category lists have a TTL of 300 seconds.
• The time between the database write and the delete is 5 ms (0.005 seconds).
• The cache does 100,000 simple operations per second.

Step 1: the price, with the TTL only.

• TTL 60 seconds: stale share = 0.0004 x 60 / 2 = 0.012 = 1.2%. Of 50 reads per second, 50 x 0.012 = 0.6 read per second shows an old price. This answers the predict box.
• TTL 300 seconds: stale share = 0.0004 x 300 / 2 = 0.06 = 6%, or 3 reads per second.

Step 2: the price, with a delete. Stale share = changes per second x the window = 0.0004 x 0.005 = 0.000002 = 0.0002%. That is 1.2 / 0.0002 = 6,000 times better than the TTL of 60 seconds.

Step 3: the stock count. It changes every 10 seconds. Changes come faster than the TTL, so the half-TTL formula does not work here, and the TTL way does badly.

• With a TTL of 60 seconds, the first change comes after about 10 seconds. The copy is stale for the other 60 - 10 = 50 seconds. That is 50 / 60 = 83% of the time, so about 83% of reads are stale. This is also rough.
• With a delete, stale share = 0.1 x 0.005 = 0.0005 = 0.05%.
• Does the hit rate suffer? With the delete, an entry lives about 10 seconds. It serves 50 x 10 = 500 reads. Hit rate = 500 / (1 + 500) = 99.8%. With the TTL only, 50 x 60 = 3,000 reads, and 3,000 / 3,001 = 99.97%. Misses per second: 50 x 0.002 = 0.1 with the delete, 0.017 with the TTL only. The cost of fresh data is very small for a popular page.

Step 4: many keys. The price is in 1 product page and 3 category lists, which is 4 keys.

• Deletes = 20 changes per second x 4 keys = 80 per second. That is 80 / 100,000 = 0.08% of the cache.
• If the code forgets the 3 lists, they show the old price for up to the TTL of 300 seconds. The product page shows the new price.

Step 5: a lost delete. Assumption: 1 delete in 10,000 fails.

• Changes per day = 20 x 86,400 = 1,728,000. Failed deletes = 1,728,000 / 10,000 = 172.8, about 173 per day.
• With a TTL of 300 seconds, each wrong entry lives at most 300 seconds.
• With no TTL, a wrong entry stays until the next change of the same product deletes it. A price that changes every 2,500 seconds heals in about 2,500 seconds, which is 42 minutes. A product description that changes once in 30 days stays wrong for about 30 days (30 x 86,400 = 2,592,000 seconds).

• The TTL way solves the problem with no work at change time. It costs stale data for up to one TTL: 1.2% of reads at 60 seconds, and 83% for a fast-changing count. I would use it for data that changes rarely, or when a little old data is fine.
• Delete on change solves staleness: 0.0002% for the price. It costs one extra miss for each change and a delete for every key that holds the data (80 per second here). A delete can also be missed or lost. I would use it when users notice a wrong value. I would keep a TTL as well.
• A changed key solves many deletes with one step. It costs one more cache read for each read, a trusted version number, and memory for old entries. I would use it when one change touches many entries.
• Do not cache data that must be exact when money decides (lesson 31).

"If I delete the entry on every change, the cache is never stale." There is still a window (5 ms here). A delete can also be lost. Another tool can change the database without telling the cache. The share is small, not zero.

"A short TTL solves staleness." It lowers it, but it does not remove it, and it costs hits. Take a rare page read once every 100 seconds (0.01 per second). At a TTL of 60 seconds, its hit rate is 0.6 / 1.6 = 37.5% (lesson 31). At 5 seconds it is 0.05 / 1.05 = 4.8%. The cache then helps almost nothing.

"With invalidation I do not need a TTL." A lost delete leaves the entry wrong until the next change of the same data deletes it. In the example, a description that changes once in 30 days can stay wrong for about 30 days. A TTL of 300 seconds turns that into 5 minutes at most.

1. What is a stale read? Name the three ways to keep a cache fresh. Why keep a TTL when you also delete entries?
2. A page changes on average once every 1,000 seconds and is read 20 times per second. The TTL is 100 seconds, with no delete. (a) What share of reads is stale? How many stale reads per second? (b) With a delete and a window of 10 ms (0.01 seconds), what share is stale?
3. A seller changes a product title. The product page shows the new title at once. Search results show the old title for up to 10 minutes. The search entries have a TTL of 600 seconds. Why, and what could you do?