Cache Invalidation and the Cost of Being Wrong

Marlow Books is a four person online bookshop that exists only in this course, and on a Thursday in April it sold forty copies of a novel it had twelve of.

Nothing was down. Nothing was slow. Lesson 003 recorded the shape of it in one line: every request a clean 200 in eight milliseconds, the uptime monitor delighted, and a week of apology emails afterwards. Twenty eight customers got a note saying the book they had already paid for did not exist.

The novel was that month's radio book club pick, which is the only reason a four person shop sells forty of anything in a day.

At 06:00 that Thursday the distributor's overnight file landed, the way it had every morning for three years. The distributor had sent part of Marlow's order somewhere else, so the file corrected the shop's stock for that title from sixty down to twelve. The import script did what it always did: one UPDATE across about eight thousand rows, finished by 06:00:04.

Two months earlier, in February, the book page cache had moved out of each box's own memory and into a small managed Redis, which lesson 008 counted as two points of hit rate. With one shared cache instead of a private one per box, changing an entry finally became possible, so the founder did the obvious thing. They added a second key alongside the rendered page, book: plus the ISBN, holding a small JSON record with the title, the price and the stock count, which both the page renderer and the checkout's in stock guard read. Four lines: a price change deletes that title's entries, and an order commit decrements the stock in the record.

It worked beautifully. A sale showed up on the page inside a second instead of inside ten minutes.

And because it worked, the founder did the other thing. If every change reaches the entry, then the TTL is only a backstop, and a backstop that fires every ten minutes is throwing away perfectly good pages for no reason. The TTL went from ten minutes to twenty four hours.

The import script was written in year one, before the shop had a cache at all. It writes rows. It has never called Redis, nobody has ever thought about it, and it has run without error every morning for three years.

So at 06:00 the row said twelve, the cache said sixty, and there was nothing left in the system that would ever notice the difference.

Forty checkouts that day read the cached record, saw plenty in stock, said yes and decremented the row. Twelve, eleven, ten, down through zero and on to minus twenty eight, with no constraint in Postgres to stop it. The cached record came down too, politely, from sixty to twenty, which is why the page said the book was available all day, right up until somebody in the packing room reached for the thirteenth copy on Friday morning.

The invalidation code was not broken. It ran correctly on every write path it knew about, all day, for two months. It was simply not in the one place that mattered, and the ten minute TTL that used to cover for exactly that had been traded away for a couple of points of hit rate.

Expiry answers when. Invalidation answers why.

Invalidation is retiring a cached entry because the thing it was copied from changed, rather than because a clock ran out.

Lesson 008 dealt entirely in clocks. A TTL, an expiry, a cache that stops believing itself on a schedule you picked. It never once asked what the underlying row was doing, which is why it could treat staleness as a price paid knowingly.

The difference between the two is bigger than it looks from the code. A TTL is a decision you make once, in one place, and nothing has to arrive for it to work. It keeps working when the network is down, when the writer has crashed, when the writer is a script somebody wrote three years ago and forgot.

An invalidation is a message. Something has to notice the write, work out which entries that write makes wrong, and get a delete to every place holding a copy, in the right order, before anybody reads. Every one of those clauses is a place it fails, and they fail differently.

That is why the joke everybody quotes, usually credited to Phil Karlton at Netscape, has survived thirty years: two hard things in computer science, cache invalidation and naming things. The joke lasts because the hard part has nothing to do with storage. The hard part is being sure that a fact you copied earlier is still true, without going back to the place you copied it from. That is a distributed systems problem, and it arrives disguised as a one line fix.

Three ways to retire an entry

They fail in different places.

Delete the key. One line after the write: cache.delete("book:" + isbn). The next reader misses and rebuilds from the source. This is what Marlow did, and it is what you should reach for first: it is the only one of the three that a person reading the write path six months later understands instantly.

It has a bill. Every invalidation is a manufactured miss, and lesson 008 priced Marlow's miss at about six milliseconds against a hit at two. Worse, if the key is hot and the rebuild is slow, a delete is a stampede with a human hand on it. Deleting the /gifts key from lesson 008 during Christmas week, with its nine hundred millisecond aggregation and twenty requests a second, would summon the same herd the founder spent eleven minutes fighting in December.

Write through it. The writer updates the row and writes the new value into the cache in the same breath, so no reader ever takes a miss and a hot key never goes cold. Lesson 046 owns the pattern; the word is here because you cannot reason about invalidation without it.

Two things stop it being the default. The writer has to be able to build the cached value, and Marlow's cached value is twelve kilobytes of rendered HTML with related titles and an average rating pulled from other tables. You do not want your order processing path rendering web pages. And two writers of the same key can land in the cache in the opposite order to the database, leaving the cache holding the older value with nothing left to correct it: both writers believe they already have. Write through is at its best when the cached value is the row, unchanged.

Version the key. Do not delete anything. Read book:9780140449136:v7 instead of book:9780140449136, where the version comes off the row, a counter or its last modified timestamp. When the row changes, readers compute a different key, miss, and rebuild. The old entry becomes garbage nobody will ever ask for, and it dies quietly of eviction.

Nothing has to be delivered anywhere, which is why this is the only one of the three that works on copies you cannot reach. It is also atomic: a reader computes either the old key or the new one, and there is no instant where an entry is half retired.

The catch is that something has to tell the reader which version to ask for, and that something has to be fresh. If the reader must query Postgres for the row's timestamp before every cache lookup, it has just performed the read the cache existed to avoid. Versioning pays when the version rides along for free, already in a URL or a page the browser is holding.

Marlow's covers are the clean case. Lesson 001 counted 1.2 million cover images at 180 kilobytes each, and nginx serves them as /covers/9780140449136.jpg with a one year expires header. When a publisher sends a new cover, there is no purge on earth that reaches the copies sitting in customers' browsers. Rename the file to /covers/9780140449136-b41f9c.jpg, change the reference on the page, and every browser fetches it immediately, because it has never heard of that URL. That is why every asset bundler you have ever used puts a hash in the filename. Lesson 022 owns the same trick at the edge.

One row, how many keys?

Delete the key looks like one line because the example in every article has one key.

Marlow's stock change on one ISBN has to retire the JSON record the checkout reads and the twelve kilobyte rendered page, which are two keys with two prefixes, written by two different pieces of code. Add a category listing that filters on in stock and it is three. Add a "recently viewed" strip built per customer and it is one key per customer who ever looked at that book, which is a set nobody is holding.

Nobody keeps an accurate list of the keys derived from a row. Any list you keep goes stale the first time a colleague adds a cache in a hurry, which is how caches are always added.

There are two honest ways out and one of them is boring.

The boring one: keep the derivation shallow. Cache things keyed by exactly the identity of the thing that changes, so one row means one key, and the delete is obvious to anybody reading the write path. Most caches that work in production work because somebody quietly enforced this.

The other one is a generation counter. Keep a number, put it in every key in a class, raise it when anything in that class changes: catalogue:v41:book:9780.... It costs almost nothing to maintain and it retires everything at once, which is exactly right for a rare broad change like a template edit, and useless for stock, because one sale would retire the entire catalogue.

That "retires everything at once" has a price lesson 008 already worked out. At 04:10 on a March morning, wiping the cache costs nothing: forty requests a second all miss and the pair absorbs it. At 11:00 in Christmas week the shop is offered 384 pages a second against an origin that can serve 260, and lesson 001's queueing arithmetic says there is no steady state at all above that line. A flush button in an admin panel is a load bearing decision wearing a friendly label.

The message that never arrives

April generalises into a rule. Every write path has to invalidate, and you cannot find the write paths by reading the code that calls the cache. You find them by reading the code that writes the row. Grep for the table name, not for the cache client.

Marlow's real list that April was five long. The checkout, the price import and the admin form all touched the cache. The distributor CSV script did not, because it predates the cache. The fifth is the founder's own psql session at eleven at night, which no amount of code review reaches.

A delete can also simply fail. It is a network call to a managed Redis that has already restarted once this year, and you have three choices when it errors, none of them free. Ignore it and you are wrong until the TTL. Retry inline and you have made every write slower and it can still fail. Fail the write and you have put your cache into your database's availability chain, which lesson 003 showed multiplies downward: two things that have to work now, where one did before.

Almost everybody logs it and lets the TTL clean up. That is the correct answer exactly when the TTL is a bound you can live with, which is the sentence the founder's twenty four hour change quietly turned false.

The real fix is to stop asking writers to remember. Let the database emit the event: a trigger, or better, a change stream read off the database's own write log, so anything that touches a row produces an invalidation whether or not the writer has heard of the cache. Lessons 037 and 040 own that machinery. It costs a component and removes the failure mode where a script from year one silently disagrees with production every morning at six.

One variant deserves its own warning. Negative caching is storing the fact that something was not found, so a flood of requests for a missing key does not reach the database every time. It is worth having and it has a trap in it: who invalidates the entry for a row that does not exist yet? The insert path, which is the one piece of code with no reason at all to know your cache exists. Keep negative TTLs in seconds.

The message that arrives too early

Here is the failure that outlives every code review, because the code looks correct and the ordering is not.

writer   BEGIN; UPDATE books SET stock = 12 ...
writer   cache.delete("book:9780...")   entry gone
reader   cache.get                      miss
reader   SELECT                         stock 60, not committed yet
reader   cache.set                      stock 60, ttl 86400
writer   COMMIT                         the row now says 12

The cache now holds a value that was never true after the commit, with a fresh twenty four hour lease, and no future event will retire it, because the write that would have has already happened. You invalidated before there was anything to invalidate, and then you cached the old answer with a full life.

So: delete after the commit, never before. Free, and it removes the worst version of this.

It does not close the window, it narrows it. Move the reader a few milliseconds earlier and the same thing happens with everybody behaving correctly:

reader   SELECT         stock 60, correct at this instant
writer   COMMIT         the row now says 12
writer   cache.delete   deletes nothing, entry not written yet
reader   cache.set      stock 60, ttl 86400

The reader is slow between reading and writing, because rebuilding took five milliseconds, or nine hundred if it is the gift ranking, and the writer commits inside that gap. Nobody made a mistake. The cache is stale until the TTL.

Four things people actually do about it. Delete a second time, a second or so after the commit, comfortably past the slowest rebuild you have; it looks embarrassing in a diff, and it works. Let only the writer populate the cache, so there is no racing reader to lose to. Keep the TTL short enough that the window costs you a bounded amount, which is the same answer as always. Or version the key, where the race evaporates: the slow reader computed the old version's key, so its stale write lands under a name nobody will ever ask for again, and everybody after the commit computes the new key and misses.

None of these is a lock, and none gives you a cache and a row that agree at an instant. If you need that, you need the row. Lesson 008 drew the line as a suggestion against a decision; lesson 015 owns the transaction that enforces it, and lesson 023 owns the vocabulary for what "agree" even means when two copies exist.

The copies you cannot reach

From September to February, Marlow's cache lived in each box's own memory, and lesson 008 counted that as the invisible fourth thing that broke when the second server arrived.

It has a consequence nobody wrote down at the time: box A cannot delete box B's dictionary entry. Nobody in that period decided against invalidation. The shape of the cache had taken it off the menu before anyone got the chance. You could add a broadcast between the boxes, which is one more message that can fail to arrive, layered on top of the message you already could not guarantee. So the TTLs stayed short, which was the right call for the wrong reason.

February's move to Redis usually gets described by its hit rate: 94% to 96%, worth about a third of the database's page load at Christmas volume. The larger thing it bought was the ability to change your mind. One copy, one place, one command.

Lesson 008 called it staleness being the price of distance, and invalidation is what that price is actually made of. In the process, you delete a dictionary entry. In a shared store, you send a command. At the edge, you make a purge request and then hope about it. In a stranger's browser, you have no mechanism at all and never will. Past the second row, deleting stops being available at all and versioning takes over.

Galewatch, which collects readings from nine hundred wind turbines, sits at the happy end of this. Its year long report covers last March, and nothing that happens today can make last March wrong, so the report needs no invalidation at any distance and can be cached in a browser until the machine is thrown away. The cheapest invalidation strategy is caching only things that cannot change.

Split the key by how fast it changes

An entry's useful life is set by its fastest changing ingredient.

Marlow's twelve kilobyte page holds a title, an author, a description and a cover reference that change roughly never, a price that changes a few times a year, and a stock count that changes on every sale. One customer buying one copy retires all twelve kilobytes, along with the description that has not changed since the day the title was listed.

Price that before deciding it is a scandal. At the Christmas peak Marlow serves 384 page requests a second, and lesson 008 measured a 96% hit rate after February, which is about 15 misses a second. The shop's four people plus two temporary staff pack an order every five seconds or so at that peak, a bit under two titles each, so the writes generate well under half an invalidation a second. Against 15 misses that is a rounding error. Delete the whole page on every write and never think about it again.

That ratio is the number to check before you copy anybody's caching design. A catalogue is read three or four orders of magnitude more often than it is written, which is why delete on write is the right default and why almost every article about caching quietly assumes it.

Turn the ratio over and you get Stagefront, this course's stadium ticketing service, where two hundred thousand people load the same seat map in the same minute at 10:00. Lesson 008 established the map is cached with a ten second TTL, so the database builds it six times a minute rather than two hundred thousand times. A stadium seats tens of thousands, most of them are claimed in the first few minutes, and every hold and every purchase changes a seat row, so the underlying data changes well over a hundred times a second while the on-sale runs. Invalidate on write there and the map is retired a hundred times a second, the cache serves almost nothing, and the database is asked to build the expensive thing continuously, which is the exact load the cache was installed to remove. Stagefront's ten seconds is a correct engineering answer for a value that changes faster than anybody can read it and that nobody is allowed to decide from.

Marlow's real fix was the split. Cache the page shell for a day, and read the volatile fields fresh: a stock count by primary key costs about a fifth of a millisecond on a row already in memory, which is what lesson 007 measured for the session lookup. A page then costs a two millisecond cache hit plus that, the twelve kilobytes stops being retired by sales at all, and a description nobody has touched in years stops being rebuilt because somebody in Pune bought a paperback.

It also removes the number the checkout was believing, which was April's actual bug. The fix was not a better invalidation. It was to stop keeping the number that mattered in the same object as the numbers that did not.

What being wrong costs

Being wrong has a price, and it multiplies out.

cost of being wrong = chance the invalidation is missed
                    x how long you stay wrong
                    x what a wrong answer costs per minute

You cannot drive the first term to zero. It is a message crossing a network between systems that fail independently, and every technique above moves it without closing it. The third term is not yours either; it belongs to the business, and it is the difference between a slightly old star rating and a book sold twice.

The middle term is the TTL, and it is the only one you control outright. Which is why the TTL stays after invalidation works, and why raising it is a statement about how wrong you are willing to be rather than a knob for hit rate.

Marlow's twenty four hours deserves one more pass, because it did not mean what the founder thought even before the CSV arrived. Lesson 008's sizing says live entries are the miss rate times the TTL. April is an ordinary month at forty requests a second, so call it two misses a second. Two a second for twenty four hours wants 173,000 entries and two gigabytes, and the cache has 256 megabytes, which holds about twenty one thousand pages at twelve kilobytes each. Twenty one thousand slots refilling at two a second means an ordinary entry gets evicted in under three hours, whatever the TTL says.

That is not what happened to the book club novel. LRU keeps whatever is being read. The most viewed page in the shop is the one that holds its stale copy the longest, and it is also the page where being wrong is most expensive. Popularity protects your worst lie.

Run the same setting at Christmas and it is a different system again. Fifteen misses a second for twenty four hours would want 1.3 million entries and a bit over fifteen gigabytes, against a cache holding 256 megabytes, so an ordinary December entry lives about twenty four minutes. Same number in the config file, three different real lifetimes in one year, and nothing writes that down. A TTL you cannot afford in memory is not a TTL.

For every value you cache, answer three things in one line each: what event makes this wrong, which code path emits that event, and what happens when somebody adds another write path next year without asking you. The answer to the third is always the TTL. That is what it is for.

Recap

Expiry answers when, invalidation answers why. A TTL is local and needs nothing to arrive. An invalidation is a message that has to be noticed, addressed correctly and delivered in order, and each of those is a separate way to be wrong.

The TTL is the backstop, and a backstop set to a day is a day of being wrong. Marlow raised it from ten minutes to twenty four hours because invalidation worked, which is exactly the moment the backstop became the only thing standing between a forgotten write path and twenty eight apology emails.

Three ways to retire an entry, and only one of them has to be delivered. Delete the key, write through it, or version it. Versioning is the one that works on copies you cannot reach, and its price is that something fresh has to tell the reader the version.

One row, many keys. The delete is one line in the example and a set nobody is holding in production. Either keep the derivation shallow enough that one row means one key, or bump a generation and accept that you have just gone cold.

Delete after the commit, and know the race you still have. Deleting before the commit lets a reader cache the old value with a fresh full lease that no future event will retire. Deleting after leaves a narrower window where a slow rebuild writes a value that was true when it read it.

An entry lives at the rate of its fastest changing ingredient. Twelve kilobytes of book page retired by a paperback sale means a description nobody has touched in years is rebuilt at the speed of stock. Split the key and the volatile field costs a fifth of a millisecond from the row.

Popularity protects your worst lie. LRU keeps whatever is being read, so the most viewed page in the shop is the one that holds a stale copy longest, and it is the page where a wrong answer costs most.

The cost of being wrong is three terms and you own one. Chance the message is missed, times how long you stay wrong, times what wrongness costs per minute. Only the middle term has your name on it.

Check your understanding

1. Marlow splits the book page: a shell cached for twenty four hours and stock read from the row on every request. List the write paths that still have to invalidate anything, and say what the worst stale value on that page is now and how long it can last.

2. Take the delete after commit race with the /gifts ranking from lesson 008, which takes nine hundred milliseconds to rebuild. Work out how wide the window actually is, then say what delay you would set on a second delete and what that delay costs you.

3. Argue for adding invalidation to Stagefront's seat map during an on-sale, as strongly as you can. Then give the one number that kills the idea, and say how you would measure it before the next one.

4. A service caches "not found" for an hour to stop a bot hammering the database with bad ids. Say what breaks, who has to fix it, and what you would set the negative TTL to instead.

5. An engineer proposes a "flush the cache" button in the admin panel, because clearing it fixed a bug last week. Say what you would need to know before shipping it, and what you would put next to it in the interface.

Next lesson

010 Databases Under Load: Indexes, Slow Queries and the First Bottleneck. Today's answer to almost every hard question was "then read the row", and lessons 005 and 006 left Marlow's Postgres alone on box A as the ceiling every other tier keeps relocating work onto; next lesson opens that box and asks what actually makes a query cost what it costs.