Cache Invalidation Is Not the Hard Part

There is a famous joke about the two hardest problems in computer science, and cache invalidation is one of them. It is repeated in interviews constantly, usually as a way of ending a conversation rather than starting one, and I think it does real damage — because invalidating a cache entry is not hard. It is a single delete. Any junior engineer can write it correctly on the first attempt.

What is hard is everything the joke leaves out.

Nobody has one cache

Ask where the cached copy lives and count honestly. There is a shared cache such as Redis. There is a local in-process map in each of your twelve application instances, added by someone who profiled a hot path. There is a CDN edge, with its own TTL, in dozens of locations. There is the browser, holding whatever your Cache-Control header told it to hold. There is the database's own buffer pool, and possibly a materialised view, and possibly a search index that was populated from a change stream.

Now delete the key. You have invalidated exactly one of those.

The instant you have more than one copy you are running a cache coherence protocol, whether or not you designed one. Processors solve this problem with hardware, a bus everyone listens to, and decades of formal work. You solve it with a pub/sub message that might be dropped, delivered twice, or delivered to eleven of your twelve instances because the twelfth was mid-deploy. There is no atomic delete-everywhere, and no amount of care at the call site creates one.

The practical consequence is that a local in-process cache with a sixty-second TTL is a sixty-second commitment to being wrong, and it is invisible in code review because the line that adds it is three characters longer than the line that does not.

The race nobody writes on the whiteboard

Even with a single shared cache, the standard cache-aside pattern has an ordering hazard that most candidates have never traced.

A reader misses, and fetches version 1 from the database. Before it writes that value back, a writer commits version 2 and deletes the cache key — correctly, in the right order. Then the reader, still holding the value it fetched a moment ago, populates the cache with version 1.

The cache now serves stale data until the TTL expires, or forever if there isn't one, and every log line in the system says the invalidation worked. It did. The bug is a concurrency bug wearing an invalidation costume, and the fixes come from concurrency: a versioned compare-and-set, a short delete-again after the write, or simply never letting readers populate a key that a writer has recently touched.

Expiry is a synchronising event

The other thing a TTL quietly does is schedule work.

Set a one-hour TTL on your most popular key and you have not decided how fresh the data is. You have decided that once an hour, every request in flight for that key at that instant will miss simultaneously and go to the origin together. A key is popular precisely because a lot of traffic wants it, so the hottest keys produce the worst stampedes, and the intuitive reaction — shorten the TTL to reduce staleness — schedules the same event more often.

Shortening TTLs is the wrong dial. The useful ones are: let a single request rebuild while everyone else is served the stale value, refresh probabilistically as expiry approaches so the misses spread out instead of arriving together, and jitter your TTLs so keys written in the same batch do not expire in the same batch. Notice that none of these are about invalidation. They are about scheduling, which is a different discipline entirely.

The question that actually decides the design

Here is the part that gets skipped, and it is the part that determines every technical choice above.

How wrong is this data allowed to be, and for how long?

A follower count that lags thirty seconds is fine, and nobody will ever notice. A product price that lags thirty seconds is usually fine and occasionally a refund, a complaint, or in some jurisdictions a regulatory matter — and it depends entirely on whether the customer is browsing or checking out. A permission that lags thirty seconds after being revoked is a security incident with a timestamp. Same cache, same TTL, three completely different answers.

Notice that the tolerance is a property of the field, not of the cache. One Redis instance holding all three of those values needs three different policies, and a single global TTL — which is what almost every system actually ships — is a bet that the strictest field can live with the loosest setting.

Record the tolerance where the code is

The practical fix is unglamorous: give every cached field a named constant whose name says what it protects, and put it beside the definition rather than in a design document nobody opens again.

PERMISSION_CACHE_TTL   = 5s    // revocation must be near-immediate
PRICE_CACHE_TTL        = 30s   // stale at checkout is a refund
FOLLOWER_COUNT_TTL     = 5m    // nobody will ever notice

That file is worth more than the architecture diagram. It turns TTL length, invalidate-versus-update, and whether a local per-instance copy is allowed at all from matters of preference into consequences of a number someone chose deliberately. It also gives the next engineer a reason to change it, instead of guessing why it was five seconds and rounding up.

The joke has it backwards. Invalidation is the easy step at the end. The hard parts are the three copies you did not know you had, the race you cannot see in the logs, and the moment ten thousand clients discover the same key expired — none of which a delete statement touches.