Serving the Same Bytes a Million Times

Someone posts a video and it takes off. This is not Courtyard’s scale but the video’s: a few hundred kilobytes, watched a million times in an hour. Every watch is a read from the photo-and-video store, the third machine of Chapter 2. The same few hundred kilobytes, fetched from the same disk, a million times over. The disk is doing nothing but serving one file, again and again, and it is buckling. The resource that has run out is the origin, the one place where the true bytes live.

Look at the waste before looking for the fix. A million reads of one unchanging file. Chapter 2 established that this file never changes; a video is written once and never edited. So a million times the store does identical work to produce identical bytes, and nine hundred and ninety-nine thousand nine hundred and ninety-nine of those reads could have been answered from a copy of the first one.

That is the whole idea. Keep a copy of the answer somewhere faster and closer than recomputing it, and serve the copy. You did this with the ARP table in Part I Chapter 6 and with names in Part II Chapter 4, and now you do it for content. It is the single most powerful tool in this part, because most systems read the same small set of things vastly more often than they read everything else. And there are many places to keep the copy, each one closer to the user than the last.

The copy can sit in front of the store. A fast in-memory cache, the shared store from Chapter 7 doing double duty, stands between the servers and the video store. The first request for the video reads it from disk and puts a copy in memory; the next million read it from memory, which serves it far faster and at far higher volume than a disk can. The disk goes back to sleep.

The copy can sit in the application. The feed server, having built a user’s feed, keeps the result for a few seconds, and if the user refreshes it serves the copy instead of rebuilding. This has to be done with care. Chapter 7 warned that a cache in one server’s memory is fine as an optimisation and never as a source of truth, because four-fifths of requests arrive at a different server and miss it. It is a speedup, not a store.

The copy can sit in the browser. The user’s own machine keeps the video after watching it, so a second view fetches nothing at all. And copies can sit in between, in a dozen places you will meet properly in the next chapter, on machines whose entire job is to hold copies close to users.

The number that matters for any of these is the fraction of requests the cache answers from its copy without going deeper, which is its hit rate. A cache with a hit rate of ninety-nine percent turns a million reads into ten thousand that reach the store, a hundredfold reduction, from one copy. That is why caching is the first thing reached for, and it is the reason the origin can be small: it only ever serves the misses.

The reason any of this is safe is Part I Chapter 20. A GET was defined there as having no side effects and an answer that may be kept. That property is cacheability, and it is what lets any of these layers hold a copy without changing the meaning of anything. A POST cannot be cached, and the verb says so, in a form every layer can read. The discipline you learned as declaring what a retry would do turns out also to declare what a cache may keep, and this chapter is where that pays off.

Caching is easy to add and hard to get right, and there are two hard parts. The first is that the copy can be wrong. A video never changes, so its cached copy is never wrong, which is why videos are the easy case and this chapter began with them. But most of what Courtyard caches does change. A user’s display name, cached across the feed. A like count. A profile. You cache it, and it is fast, and then the underlying truth changes, because Mira renames herself, and every cache still holds the old name and shows it for as long as the copy lives.

This is staleness, the antagonist of Part III, in its self-inflicted form. In Chapters 3 and 5 staleness was forced on you by replication. Here you chose it, by keeping a copy, and now you owe a decision about how long the copy is allowed to be wrong. There are two ways to make that decision, and real systems use both.

One is expiry. Give each copy a lifetime, the TTL from Part II Chapter 4, and after it the copy is discarded and the next request rebuilds it fresh. This is simple, it bounds staleness to the lifetime, and it means Mira’s new name appears everywhere within, say, sixty seconds, with no coordination at all. The cost is that you are either serving stale data, with a long lifetime, or rebuilding constantly, with a short one. It is the same dial and the same trade as every cache in this book.

The other is invalidation. When the truth changes, tell the caches to drop their copies. Mira renames herself, and the application, having written the new name, sends a message to the caches to forget the old one. Now the change appears at once, and copies otherwise live for as long as they are useful. The cost is that you have to find every copy in order to invalidate it, and copies are scattered across layers and machines, and a copy you forget is stale forever. Naming everything that might hold a copy of a thing is famously one of the two hard problems in computing. Invalidation is precise and fragile; expiry is sloppy and robust. Most systems invalidate what they can and set a lifetime as the backstop for what they miss.

The second hard part is the one that surprises people, and it is the one that takes systems down. The viral video’s copy has a lifetime, say sixty seconds, as a backstop. At some instant, sixty seconds after it was cached, the copy expires and is discarded. In that same instant the video is being requested ten thousand times a second. Ten thousand requests arrive, each checks the cache, each finds nothing, since the copy has just expired, and each concludes that it must rebuild the copy from the store. Ten thousand simultaneous reads land on the disk that the cache existed to protect, all at once, for the same file, because they all missed at the same moment.

The cache did not reduce the load. It concentrated it, holding it back for sixty seconds and then releasing all of it in one spike. The store, which handles ten thousand requests a second comfortably when they are spread out, receives them in a single millisecond and falls over. And when it falls over, none of the ten thousand rebuilds succeed, so the cache stays empty, so the next ten thousand requests also miss, and the store never recovers.

This is a cache stampede, also called a thundering herd, and it is caused by many copies expiring in unison, or by one hot copy expiring under concurrency. The defences follow from the cause. The first is to jitter the expiry. Do not give every copy sixty seconds; give each one sixty seconds plus or minus a random few. Now they do not all expire together, and the load spreads instead of spiking. You saw this fix in Part II Chapter 4, in DNS, and you will see it again in Chapter 16. Jitter breaks synchronised behaviour, and synchronised behaviour is what turns many small events into one catastrophe.

The second is to coalesce the rebuilds. When ten thousand requests miss at once, do not allow ten thousand rebuilds. Let the first miss start the rebuild, and make the other nine thousand nine hundred and ninety-nine wait for it rather than each starting its own. One read reaches the store and everyone receives its result. This is the idempotency thinking of Part I Chapter 20, the recognition that these are all the same operation and it need be done only once, applied to cache rebuilds, and it is the most important of the three.

The third is to serve stale while you rebuild. When a copy expires, do not discard it. Mark it stale, keep serving it, and rebuild in the background. Users receive a copy a few seconds out of date for the moment it takes to refresh, which for a video or a like count is invisible, and the store sees one gentle rebuild instead of a stampede. It is staleness deliberately extended a little to avoid a spike, the same bargain as everywhere else in this part.

Every cache is a copy, so every cache is a source of staleness, and now there are copies at five depths, each with its own lifetime, each potentially wrong, and a change to the truth has to propagate through or expire out of all of them. The question of why a user is seeing an old name now has five possible answers stacked one above another, and debugging it means knowing which layer served the request.

A cache also changes the shape of failure for the thing behind it. The store now runs comfortably only because the cache absorbs ninety-nine percent of its load, which means the store is sized for one percent of the real traffic, which means that if the cache fails the store receives a hundred times its normal load and dies at once. You have made the system faster and cheaper and also more fragile. It now depends on the cache being up, and a cache failure is no longer a slowdown but an outage. The cache became load-bearing the moment you sized the origin behind it for the hit rate.

So the origin ran out, and you cached the hot content at several layers. Every layer is a source of staleness that needs invalidation or expiry; expiries must be jittered and rebuilds coalesced to avoid stampedes; and the origin is now sized behind the cache’s hit rate, so that a failure of the cache is an outage rather than a slowdown. The cache in the datacentre is doing its work, and the datacentre is in London, which is about to matter.