Caching

Caching is taught as an optimisation and it is not one. An optimisation makes the same thing faster. A cache makes a different thing faster: an older thing.

Every cache in this book, from the L1 line on your processor to the CDN edge node in São Paulo, works the same way. It answers a question using data that was correct at some point in the past, and it is faster precisely because it did not go and check. The speed is not free and it is not paid for in money. It is paid for in correctness, in a currency of seconds.

The lecture behind this book is Caching, the secret behind it all (youtube.com/watch?v=estH64OkwxU, 64 minutes). Its examples are good and its coverage of where caches live is the right map. It spends almost no time on the half of the subject that is hard, which is what happens when the cached answer is wrong and someone notices.

The one question

Every decision in caching is an answer to it. A TTL is a numeric answer. An eviction policy is an answer about what you are willing to lose. An invalidation strategy is an attempt to put a bound on the answer. A hit ratio is how often you got away with it.

If you can state the staleness window for every cache in your system, you understand your system. Most engineers cannot state it for any of them, which is why the second half of this book exists.

What is in the lecture and what is not

Parts I and II are the lecture, expanded, with the numbers filled in. Parts III to VII are mostly outside it. The lecture covers two caching strategies; there are five, and the two it omits are the ones that fail interestingly. It covers eviction and never covers invalidation, which is the harder of the two by a wide margin. It never mentions the thundering herd, cache stampede, penetration, or Cache-Control, and it makes one claim about write-through freshness that is not true in any system with more than one server.

There are three direct corrections, each in a trap block.

The five block types

The four highlighters

A suggested route

1. Do the arithmetic in section 3 with a pen. It is the argument for everything else, and it has a result most people find surprising.
2. Part II is a map. Read it once and refer back.
3. Parts IV and V are the book. They are where interviews go and where production incidents come from.

One request for one user's profile, and every cache it passes through.

   BROWSER                                              staleness window
     │
     ├─ memory + disk cache ─────────────────────────    minutes to days
     │      obeys Cache-Control. you do not control
     │      when it is cleared                     ← section 31
     │
     ├─ OS + browser DNS cache ─────────────────────    seconds to hours
     │      name to address                        ← section 10
     ▼
   CDN EDGE (nearest PoP)
     │
     ├─ edge cache ─────────────────────────────────    your s-maxage
     │      hit: never reaches you at all          ← section 11
     ▼
   LOAD BALANCER
     ▼
   APPLICATION
     │
     ├─ in-process memory ──────────────────────────    seconds
     │      per instance, so N instances = N        ← section 29
     │      different answers
     │
     ├─ REDIS ──────────────────────────────────────    your TTL
     │      shared, so all instances agree          ← sections 12, 36
     ▼
   POSTGRES
     │
     ├─ shared buffers ─────────────────────────────    none: coherent
     │      the only cache here that cannot be stale
     ▼
   DISK

Five of those caches can be serving a different answer to the same question at the same moment. A profile edit that updates Postgres and deletes the Redis key has changed two of the seven boxes. The browser, the edge and the in-process memory of three other instances are all still confidently wrong.

Four rules are encoded in that picture, and they are the whole book.

• Every layer has a staleness window, and you own the number or you inherited it. A default TTL is still a decision, made by someone who did not know your system.
• A cache you cannot invalidate is a cache with a TTL, whatever you call it. The browser cache is the clearest case: once the response has left, the only bound on its wrongness is the number you already sent.
• Caching moves load, it does not remove it. Every miss still costs the full path plus the cache lookup you added.
• The cache is a new dependency and a new failure mode. Section 29 is about the day it is not there, and it is the part most systems have never tested.

You have a dashboard. It shows each organisation its project count, its most active members, and a chart of tasks completed per week. The query behind it joins four tables, aggregates over a few million rows, and takes 400ms.

That is acceptable. One user, once, is fine.

Then the product succeeds. Ten thousand users open the dashboard each morning within the same twenty minutes, and the arithmetic changes:

   10,000 users  ×  400ms of database work
   ────────────────────────────────────────
   =  4,000 seconds of query time, in a 20 minute window
 
   20 minutes = 1,200 seconds of wall clock
   so you need  4,000 / 1,200  ≈  3.3 cores of pure database CPU
   doing nothing but this one query

And almost every one of those ten thousand answers is identical. The underlying tasks changed a handful of times during the window. You computed the same aggregate ten thousand times because nobody told the system it had already done it.

This is the shape the lecture identifies correctly across all three of its examples. Google recomputing rankings for the same query, Netflix streaming the same film from Oregon to Mumbai, Twitter recalculating trends for every viewer of the trending page. Expensive work, repeated, with the same answer.

But notice what makes it cacheable, because it is not "it is expensive". It is that the answer changes far more slowly than it is requested. Trending topics shift over hours and are read every second. A film does not change at all. A dashboard aggregate moves a few times an hour and is read ten thousand times.

That ratio is the whole decision:

   read rate                 how often the answer is requested
   ─────────────      the higher this is, the more a cache buys
   change rate               how often the answer is different

A value read a thousand times a second and written a thousand times a second is a terrible caching candidate no matter how expensive it is to compute, because every cached copy is wrong almost immediately.

The lecture's definition is good and worth keeping: a subset of some data, held somewhere faster to reach. Three words in that sentence carry the weight.

Subset, because if it held everything it would be a replica and would need the capacity and the durability of the original. The lecture makes this point well with Netflix: no edge node holds the catalogue, and choosing what each one holds is itself a machine learning problem.

Faster, which is always a trade against something. Every layer of the hierarchy in section 7 buys speed with capacity, cost, or durability, and usually all three.

A copy, and this is the word the lecture does not press on. The moment the copy exists, there are two answers to the same question and no mechanism keeping them equal. Everything difficult about caching descends from that sentence, and it is why Parts IV and V are longer than Parts II and III.

The vocabulary, once, so the rest of the book can use it:

   cache hit        the data was there. you paid the cache lookup only
   cache miss       it was not. you paid the lookup AND the full path
   hit ratio        hits / (hits + misses). the number that matters
   eviction         removing something because you are out of room
   invalidation     removing something because it is WRONG
   TTL              time to live: how long a copy may be used
   stale            still present, no longer correct

Eviction and invalidation are different problems and people conflate them constantly. Eviction is a capacity question: what do I drop to make room? Invalidation is a correctness question: what is no longer true? The lecture covers eviction thoroughly and invalidation not at all, which is the single largest gap in it, and Part IV is the answer.