A cache is one of those tools that look magical as long as you keep them at arm’s length. You store a piece of data that’s expensive to produce, you serve it instantly to subsequent requests, and performance takes off. Except that, on closer inspection, this apparent simplicity hides a trap: how do you guarantee that the data you serve is still valid, and how do you keep the cache from overflowing? That’s precisely what makes caching hard to master.
This third and final installment of the caching series tackles that complexity. In the first episode, we saw why a cache speeds up a web application; in the second, where that performance gain concretely comes from. That leaves the trickiest question of all: once the data is cached, how do you make sure it stays reliable over time?
The two hard things in computer science
You may know this quote attributed to Phil Karlton:
“There are only two hard things in Computer Science: cache invalidation and naming things.”
We’ll set naming aside for today. Let’s focus on the first difficulty: cache invalidation. Because behind that quip lies a very real operational truth. A cache that serves stale data can be more dangerous than no cache at all: it gives the illusion of freshness while silently propagating outdated information.
And as we’re about to see, this quote, famous as it is, is incomplete. It names one problem, invalidation, without mentioning its inseparable corollary: eviction.
Cache invalidation: flagging what’s stale
Cache invalidation refers to the process that marks cached data as outdated, and therefore “invalid.” The goal is to stop serving it to subsequent incoming requests. Without this mechanism, there’s no way to guarantee the integrity and consistency of the data persisted in the cache: you’d keep returning a frozen version of reality indefinitely.
Several strategies enable automatic invalidation. The most widespread is to associate a lifetime, a Time-to-Live (TTL), with each piece of data. The TTL specifies the period during which the data can legitimately be used. Once that window passes, it’s considered invalid and must no longer be served.
There’s nothing abstract about this principle: it’s exactly what the max-age directive of the Cache-Control HTTP header implements, mentioned in the first episode of this series.
Cache-Control: max-age=3600With a simple duration setting (here, 3600 seconds, or one hour), you control the data’s refresh rate precisely. On expiry, the cache knows it must go fetch a fresh version from the source.
One thing to watch out for, though: tuning the TTL is a permanent trade-off between performance and freshness. A TTL that’s too long exposes you to the risk of serving stale data; a TTL that’s too short cancels out part of the cache’s benefit by multiplying refreshes. When in doubt, it’s better to err on the side of caution and pick a shorter duration than planned: you lose a bit of cache hit rate, but you gain consistency, a trade-off that’s almost always preferable.
Cache eviction: making room for the fresh
Let’s go back to Karlton’s quote. It suffers from an important omission: it conflates, or at least lumps together, two distinct operations. Flagging a piece of data as invalid is one thing. Freeing the space it occupies to replace it with fresh data is another.
That’s the whole point of eviction, or expelling data from the cache. Where invalidation merely marks a piece of data as stale, eviction takes over by automating its actual removal. The two phases are complementary: invalidation identifies, eviction cleans up.
The TTL, for example, invalidates data based on an expiry duration. But other mechanisms go further by combining invalidation and removal in one stroke. They become indispensable the moment you hit a constraint the TTL alone ignores: the cache’s finite capacity.
Because a cache isn’t infinitely extensible. Its value lies precisely in the fact that it resides in a fast but limited space: RAM, for instance. When that space fills up, you have to decide which data to sacrifice to make room for the new. That’s where eviction algorithms come in, triggered at regular intervals or when the cache’s maximum size is reached, or dangerously approached.
Least Recently Used (LRU)
The LRU algorithm removes the least recently used data first. The underlying logic is intuitive: if a piece of data hasn’t been accessed in a while, it’s likely it won’t be anytime soon. You thereby preserve what’s been touched recently, betting on the temporal locality of accesses. It’s the most common default strategy, because it adapts well to the majority of usage profiles.
Least Frequently Used (LFU)
The LFU algorithm reasons not about recency but about frequency: it evicts the data that’s been used least often. A piece of data accessed hundreds of times stays in the cache even if its last access is old, while rarely requested data goes first. LFU shines when certain data is durably popular, but it can conversely penalize recent arrivals, which haven’t yet had time to build up a high access counter.
First-In First-Out (FIFO)
The FIFO algorithm completely ignores access patterns and simply relies on arrival order: the first piece of data in is the first out, as in a queue. It’s the simplest to implement, but also the most naive: it accounts for neither popularity nor recency of use. Reserve it for cases where simplicity outweighs optimizing the cache hit rate.
A parallel with garbage collection
There’s an illuminating analogy for anyone familiar with memory management in garbage-collected languages: invalidation and eviction are to caching what mark and sweep is to garbage collection.
In both cases, you find the same two-step structure. A first phase identifies what’s no longer useful: you mark unreachable objects in GC, you invalidate stale data in the cache. A second phase actually reclaims the resources: you sweep memory in GC, you evict entries in the cache. Understanding this parallel helps grasp why these two steps are inseparable: marking without cleaning frees no resource, and cleaning without having marked would amount to deleting data that’s still valid.
Conclusion
While caching looks simple on the surface, its real difficulty lies in managing the data lifecycle. Invalidation guarantees you never serve stale information; eviction guarantees you always have room for the fresh. One protects integrity, the other capacity, and you need both for a cache to stay reliable over time.
Phil Karlton’s quote was therefore right at its core: invalidation really is one of computer science’s hard problems. But it’s better off completed by eviction, its indispensable corollary. Mastering these two mechanisms (and choosing the right TTL strategy and the right eviction algorithm according to your access profiles) is what turns a cache from a fragile optimization into a robust component of your architecture.
And so this caching series comes to a close: from the benefits (part 1) to their technical origin (part 2), all the way to the complexity you have to accept to make lasting use of it.