Cache Invalidation: The Second-Hardest Problem

Remember that viral sneaker listing. You cached it, the hit rate soared, the database relaxed. Then the seller drops the price — $220 becomes$180 for a flash sale. You update the database. Done?

Not even close. Somewhere in RAM sits a cached copy that still says **$220**, and it will keep telling fifty thousand shoppers$220 until it happens to expire. Your database is correct. Your users are seeing a lie. That gap — between the moment the truth changes and the moment every copy of it catches up — is cache invalidation, and it has earned the most quoted joke in our field:

"There are only two hard things in computer science: cache invalidation and naming things." — Phil Karlton

This lesson is why that joke is true, and the handful of cures that make caching survivable in spite of it. We'll build up from the humblest fix to the industrial one — and in the middle you'll break a perfectly correct invalidation with your own hands, because that surprise is the whole reason this problem is hard.

Scope: this is about keeping copies honest when the truth changes — a question of freshness. Making room when the cache fills up was the last lesson, Eviction — and they are not the same: a perfectly fresh key can be evicted for space, and a stale key can sit resident forever. Different problem, different cure.

Updating a database is easy. Keeping every copy of that data in sync is where it turns brutal — for four reasons that shape every cure below.

• Copies are everywhere, and an update chases none of them. The same price can live in your app's memory, a Redis tier, a CDN edge in Tokyo, and a user's browser tab. Writing the database updates exactly zero of them. You have to hunt down and fix each copy yourself.
• You can't update two systems atomically — the dual-write problem. "Write the database, then delete the cache" is two operations with no shared transaction. If the second one fails — the process crashes, the network hiccups — the database and cache now disagree, and nothing rolls it back.
• Concurrency can defeat a correct invalidation. This is the cruel one. You can delete the cache at exactly the right moment and still end up stale, because a slow reader repopulates the old value a millisecond later. It isn't a bug in your code; it's the nature of the problem. (You'll trigger it yourself shortly.)
• There is no free lunch. Every cure trades freshness against complexity against performance. You either accept some staleness and bound it, or you take on machinery and races to chase zero. Perfect, fast, simple — pick two.

Hold those four in mind. Every technique that follows is just a different bargain among them.

The humblest cure — and the one you should almost always have on: give every entry a time-to-live. Cache the price for 60 seconds; after that, the next read is forced to refetch from the database. That's the entire mechanism. No coordination, no changes to your write path, no races. If a value goes stale, it self-heals within the TTL. This is why TTL is the floor under every other strategy in this lesson: even when a fancier cure fails, a short TTL caps how long you can possibly serve a lie.

The whole game is tuning one number, because TTL is literally "how much staleness can I live with?" — seconds for a price, minutes for a profile, a day for a config that barely moves. Short TTL means fresher data but more database load; long TTL means cheaper but staler. A few refinements worth carrying:

• Hard vs. soft TTL. Hard: at expiry the entry is gone and the next reader waits for a refetch. Soft (stale-while-revalidate): serve the slightly-stale copy instantly and refresh it in the background — lovely UX, freshness lags by a hair.
• Jitter. If a thousand keys all get a 60-second TTL at the same instant, they all expire at the same instant and stampede the database together. Add a little randomness (60s ± a few) so expirations spread out. (That stampede is a lesson of its own — the next one.)
• Negative caching. Briefly cache "not found" too, so a flood of requests for a missing key doesn't hammer the database.

TTL's honest limit: for the whole window between the change and the expiry, you are serving stale data. When that window is too big to accept, you stop waiting for a clock and start actively killing the copy.

If you can't wait for a TTL, invalidate the copy the instant the data changes — on the write path itself. When you update the database, immediately reach over and remove the cached copy, so the next read is forced to reload the truth. This is the workhorse of active invalidation, and it comes with two rules that nearly everyone gets wrong the first time.

Rule 1 — DELETE the key; do not UPDATE it. It is tempting to just write the new value straight into the cache. Don't. If two writers both try to update the cache, their writes can land in the wrong order — an older value arriving after a newer one — and leave the cache permanently stale. Deleting is idempotent and safe: it only says "this is no longer valid," and the next read pulls whatever the database currently holds. Delete throws a copy away; update tries to author one — and authoring races.

Rule 2 — write the DATABASE first, THEN delete the cache. Order matters. If you delete the cache first and then write the database, there's a window where a reader misses, reads the old database value (your write hasn't landed yet), and cheerfully repopulates the cache with it — stale again, until the TTL saves you. Database first; then delete.

Get both rules right and you have the standard, solid pattern: cache-aside reads, delete-on-write invalidation. And yet — it still has a race. Even with perfect ordering, concurrency can quietly undo your delete. That is not a mistake in your code; it is the shape of the problem — and it is worth seeing with your own hands.

Here's a shared cache and database, a Reader, and a Writer. The Reader does the normal cache-aside dance: check the cache, and on a miss, read the database and write what it found back into the cache. The Writer does textbook delete-on-write: update the database, then delete the cache key. Both are correct. You control the interleaving — advance the Reader or the Writer one step at a time — and your job is to find the order that poisons the cache.

Do this: let the Reader miss and read the database, so it grabs the old $220**. Now, *before the Reader writes that back*, run the Writer all the way through — it sets the database to **$180 and deletes the cache. Finally, let the Reader finish: it writes **$220** into the cache, the value it read a moment ago. The database says$180. The cache says $220. And the delete already happened. You did everything right, and the cache is a liar.

Now flip on the stale-write guard and replay the exact same order. This time the Reader's stale write is rejected, and the cache heals — the next read reloads $180. That little guard, in one form or another, is the whole idea behind every real fix.

What just beat you has a name: a stale set — a slow reader repopulating a value that a writer already invalidated. You can't prevent the interleaving; two independent actors will sometimes run in that order. So every real fix does the same thing by a different route: it lets the cache reject a write that's based on stale information.

• Leases (Facebook's memcache). On a miss, the cache hands the reader a short-lived token bound to that key. The reader may only write its value back if the token is still valid — and a delete invalidates every outstanding token. So the slow reader's stale write is simply refused. (The same famous paper reuses that token to throttle thundering herds and adds a brief hold-off on writes right after a delete.)
• Versioning / compare-and-set. Tag each value with the database version it came from. The cache accepts a write only if its version is newer than what's already there (or newer than the last invalidation). The stale reader is carrying an old version number, so its write loses.
• Delayed double-delete. Delete the cache, write the database, then delete the cache one more time after a short delay — sweeping away anything a slow reader repopulated in the gap. Crude, but genuinely common.
• And always, a short TTL underneath. Even if every guard somehow fails, a small TTL gives the lie a deadline.

Notice the shape of all four: you cannot stop the race, so you make the stale write detectable and throw it away.

Delete-on-write couples your cache to your write path, and it still carries the dual-write problem — two writes, no shared transaction, either one can fail. The most robust cure removes the second write entirely: instead of your code telling the cache what changed, let the database tell it.

Every committed change to a database is already recorded in its change log — MySQL's binlog, Postgres's WAL. A tool like Debezium tails that log and streams every insert, update, and delete as an event (usually onto Kafka), and a small consumer invalidates the matching cache key. This is the grown-up answer, and the reason is subtle but important: the invalidation is derived from a change the database already committed — so there is no second write to fail and no dual-write inconsistency. If it's in the log, it happened, and the cache will hear about it, in order. It's also decoupled: your write path doesn't even know the cache exists, and any number of services can subscribe to the same stream. The cost is real infrastructure and eventual consistency — the event lands milliseconds to seconds after the commit, not instantly. (Its cousin, the transactional outbox, earns the same guarantee by writing the change and an "outbox" row in one transaction, then relaying the outbox.)

And one more move, for invalidating a whole group at once: versioned or generational keys. Put a version in the key — user:42:v7 — or a shared generation number across a namespace — feed:g5. To invalidate everything under it, you don't delete a thousand keys and risk a delete storm; you bump one number. v7 becomes v8, g5 becomes g6, and every old key is instantly unreachable and ages out on its own. An O(1) increment instead of an O(N) sweep — paid for with a brief hit-rate dip while the new generation warms up.

The invalidation bugs that reach production almost always trace back to one of these — each sounds obviously correct, and each is wrong:

• "Just write the new value into the cache on update." → Two writers race and one leaves it permanently stale. Delete, don't update — deleting is idempotent; authoring isn't.
• "Delete the cache, then update the database." → A reader repopulates the old value in the gap. Database first, then delete.
• "Delete-on-write means my cache is always fresh." → No — the stale-set race can repopulate an old value after your delete. You need a guard (lease / version), or you're leaning entirely on the TTL.
• "I'll write the database and the cache in one atomic step." → You can't; there is no transaction across two systems. That's the dual-write problem, and it's the reason CDC and the outbox exist.
• "More freshness is always better — so use TTL 0 / no cache." → Then you don't have a cache. Pick a TTL that matches your real tolerance; chasing zero staleness rarely pays for itself.
• "Invalidation is just eviction." → Eviction frees space; invalidation preserves truth. A key can be evicted while perfectly fresh, and stale while still resident.

• A cache is a copy, and the instant the truth changes, that copy is a potential lie. Invalidation keeps copies honest — and it's hard because copies are everywhere, you can't update two systems atomically, concurrency races defeat correct code, and every cure trades freshness for complexity.
• The cures, lazy to eager: TTL (accept bounded staleness — the floor everyone keeps); delete-on-write (database first, then delete — never update); event-driven / CDC (let the database's change log drive invalidation — no dual-write); versioned keys (bump one number to invalidate a whole group).
• Even correct delete-on-write races — the stale set, where a slow reader repopulates an old value. Kill it with leases, version / CAS, or a delayed double-delete — and always keep a short TTL as the floor.
• Choosing: tolerate N seconds stale? → TTL. Fresh-on-write in one app? → delete-on-write + a TTL. Many services, strict freshness, no dual-write? → CDC. Invalidate a whole group? → versioned keys. High concurrency you can't let race? → leases or versioning. Under all of it: there is no perfect invalidation — only the trade-off you chose on purpose.

Next — Stampedes, Thundering Herds & Cache Warming. We kept saying "the next read just reloads from the database." But what happens when a blazing-hot key expires and ten thousand reads miss at the very same instant and all stampede the database at once? That's the failure mode that actually takes systems down — and it's next.