Cache Invalidation: Keeping a Cache Honest

We have a cache: a fast copy of an answer, kept close (caching), that forgets things when it fills (eviction). This piece is about the other hard half. A cache holds a copy, and the original can change underneath it. Keeping the copy honest is cache invalidation, and it has a reputation.

There is an old programmer's joke: there are only two hard things in computer science, cache invalidation and naming things. It is funny because it is true. Here is why invalidation earns its place.

Picture a price tag on a shop shelf. Somewhere in the back office, the real price of the item lives in a system, and that system just changed it from 10 to 12. But the little printed tag on the shelf still says 10. The tag is a cache: a fast, local copy of a number that really lives somewhere else. And right now it is lying. A customer reads the tag, believes it, and takes the item to the till expecting to pay 10. Nobody is confused about where the truth is; the truth is in the back office. The problem is that the copy on the shelf did not get the memo. Invalidation is the whole job of making sure that when the real price changes, the tag stops showing the old one.

The problem: a fast, confident, wrong answer

Here is the thing that makes stale data dangerous. A cache miss is not a disaster; it is just slow. The request goes to the database, gets the right answer, and everyone is a little annoyed at the latency but nobody is misled. A stale hit is the opposite: it is instant, it looks healthy, every dashboard is green, and it is wrong. Fast and wrong is worse than slow and right, because nothing warns you.

Worked example. You cache a product price, v1 = 10. A write updates the database to v2 = 12. If nothing tells the cache, then for as long as that entry lives, every reader gets 10. Not an error, not a timeout, just a confident wrong number handed back in a millisecond. The fix is to invalidate: when the write lands, make the cache stop serving the old copy. There are four common ways to do that, and the rest of this piece is one for each, everyday version first.

Four ways to keep it honest

The four strategies trade the same two things against each other: how much staleness you can tolerate, and how much you are willing to pay on every write. Here is each in turn.

Expire it (TTL)

Think of a newspaper. This morning's edition is fine to trust today, but by tomorrow you want a fresh one; the date on the masthead tells you when to stop believing it. A TTL is that date stamped on a cached answer: hold it for a set time, then throw it out and fetch again.

TTL does not stop staleness, it bounds it. With a 60-second TTL, the price tag can be wrong for at most 60 seconds, then it self-corrects. That is often completely fine (a follower count, a weather reading) and it costs you nothing to reason about. The tradeoff is blunt: a short TTL keeps data fresh but hurts your hit rate; a long TTL is efficient but serves staler data. We met the timers themselves in eviction; here the job they do is bound how long a lie can live.

Update on write (write-through)

Think of carbon paper. You write a note once and the same stroke makes two identical copies at the same instant, one for your desk and one for the file room. They cannot disagree, because they were written together.

Write-through is that: when you change the database, you change the cache in the same motion, so the two never diverge. There is no stale window at all, which is its whole appeal. The cost is that every write now does double work and recomputes the cached value, even for data that may never be read again. We met this in the caching piece; here it is the invalidation strategy with no window, paid for up front on every write.

Invalidate on write (delete the key)

Back to the shelf. The instant the price changes, you walk over and rip the old tag off. A blank spot where a tag should be is annoying, someone has to look up the price, but nobody gets charged the wrong number. That is the whole idea.

Invalidate-on-write is the workhorse. On a write you do not bother updating the cached value; you simply delete it. The next read misses, fetches the fresh value, and refills the cache on its way back, exactly the cache-aside flow. Compared to update-on-write, it is lazy in the good way: you only pay to recompute the value if someone actually asks for it again. The visualizer walks the full cycle, from in-sync, to the stale lie, to the delete, to the refill.

Versioned (immutable) keys

Instead of correcting the tag on the shelf, print a whole new tag with a new barcode and put it up; the old barcode is simply never scanned again. That is the cleverest option: never edit a cached value at all. Bake a version into the key, and when the data changes, bump the version so readers start asking for a brand-new key.

Worked example: a website ships its code as app.js?v=1. Every browser and CDN caches that file hard, maybe for a year, because it is safe to: that exact URL will never have different contents. When the code changes, the site references app.js?v=2. That is a different key, so it misses everywhere and fetches fresh, while app.js?v=1 sits untouched in caches, orphaned and harmless, until it ages out. This is the trick behind cache busting on almost every website you use. There is no stale window, because there is no moment when the old key holds the new data; the new data always arrives under a new name.

Why it is genuinely hard

If the strategies are this tidy, why the reputation? Because the moment more than one thing is happening at once, the timing bites. Delete the key on a write, and a slower read that started just before your write can refill the cache with the old value a hair after you deleted it, quietly re-poisoning it. Run more than one cache node, or one per region, and now a write has to reach every copy, and until it does, different users see different truths. None of this is exotic; it is the normal state of a busy system, and it is why "just delete the key" turns out to have footnotes.

There is one race common enough to earn its own piece. When a single popular key is invalidated or expires, it is not one read that misses and refills, it is thousands, all at the same instant, all stampeding the database for the same value at once. That is the cache stampede, or thundering herd.

Next: the stampede. What happens when a hot key expires and the whole crowd rushes the database at the same moment, and the handful of ways to keep that from taking the system down. That is the next piece.