Two Kinds of Cached Thing
Cache invalidation is famous for being hard, and the reason is specific rather than general. It depends entirely on what kind of thing you cached.
A write tells you which row it changed. It does not tell you which cached aggregates, lists, counts or rendered pages were built from that row, and nothing in the write knows.
Every technique here is a different way of solving one problem: given a write, find the derived entries that are now wrong.
Four Strategies, Counted
The script is at scripts/labs/invalidation/strategies.py. It runs one stream of 120,000 reads and writes through four strategies and counts two things: stale reads served, and delete operations performed.
Deleting the exact key on every write performed 5,779 deletes and served 249.1 stale reads per thousand, against 104.4 for doing no write-side work at all.
This is the result the descriptions cannot give you. Delete on write sounds strictly better than a , costs real work on every write, and on this workload produced more than twice the staleness.
Both strategies were equally blind to derived entries. The one that kept more entries alive served more of them, and every one it served was wrong. A TTL is an invalidation mechanism that works on things you have not thought about.
Read this against the previous chart. Freshness is bought with write-side work, and the price rises with how broadly your derived entries are defined. Versioned keys reached zero staleness with zero deletes, which needs explaining.
How Each One Works
Nothing is ever removed, which is why it reaches zero staleness with zero deletes. The orphaned entries remain until the eviction policy reclaims them, so versioning converts an invalidation problem into an eviction problem.
Correctness is not the axis that separates the useful ones. Tag based charges write-side work, versioned keys charge memory, and flushing charges your entire hit rate.
Why It Stops Working
Invalidation works by every writer participating, and the set of writers grows: a migration, an admin tool, a bulk import, another service writing directly. Nothing fails visibly, so the decay is silent.
Invalidation is a property of a whole chain, not of one cache. A design where every layer is invalidated except the last has a worst case equal to the max-age you set on the layer you cannot reach.
What to Build, and How to Test It
An entry defined by a predicate can be invalidated by a row that was never part of it. This is why cache invalidation is called hard: for those entries, the information needed to do the bookkeeping does not exist in the write.
What you name a key decides how you can invalidate it, and it is chosen before any of the difficulty appears. Nearly every impossible invalidation problem was created by a key that could have carried a parent and a version and instead carried a hash.
Quick Check
Knowledge Check
4 questions - Score 80% to pass
You add per-row delete-on-write invalidation to a cache that previously used only a TTL. Measured, what happened to stale reads?
A cached entry is defined by a filter, such as all orders over £100. Which invalidation strategy can catch a newly inserted matching row?
Should you delete the cache key before or after the database write?
Your invalidation tests all pass. What do they most likely fail to cover?
