In this chapter
We'll go deep on the real algorithms a cache uses to choose what to evict — LRU (recency), LFU (frequency), FIFO, and random — see exactly where LRU and LFU genuinely disagree, and find that no single policy is universally correct, only a better or worse fit for a specific real access pattern.
The Problem in Real Life
Mike gets the general idea now — a full cache has to throw something away. "But which thing?" he asks. "Randomly? Whatever's been there longest?"
Sarah smiles. "There's real, worked-out thinking behind this. It's not a coin flip."
When the cache is full, how does it actually decide what to throw out?
Mike
A Coin Flip vs. A Real, Deliberate Policy
LRU bets on recency
Evicts whatever hasn't been touched in the longest time — a strong fit for recency-driven access patterns.
LFU bets on overall popularity
Evicts whatever has the lowest total access count — a strong fit for steady, long-term popularity patterns.
LRU, LFU & Other Eviction Strategies
An eviction policy is the real, specific rule a cache follows to choose what to remove when it needs room. Different policies make genuinely different bets about which entries are least likely to be needed again soon — and picking the wrong one for a given real workload has a genuine, measurable cost.
- LRU — Least Recently Used. The cache tracks, for every entry, when it was last accessed, and evicts whichever entry has gone the longest without being touched. The real bet: something nobody's asked for in a while is probably not about to be asked for again soon — a reasonable, real assumption for a lot of genuinely common access patterns, like a customer browsing recently-viewed products.
- LFU — Least Frequently Used. The cache tracks, for every entry, how many times it's been accessed overall, and evicts whichever entry has the lowest real access count. The real bet is different from LRU's: something rarely asked for, period, is a better candidate to remove than something asked for constantly, even if that popular item hasn't been touched in the last few minutes specifically.
- Where LRU and LFU genuinely disagree. A product page that goes viral for one hour, then is never viewed again, looks completely different under each policy: LRU keeps it as long as it stays "recently used," then drops it fast the moment traffic stops. LFU, by contrast, might keep it around for a long time afterward, since its total access count stayed high, even though nobody's actually requesting it anymore — a real, concrete case where LFU's own bet can go stale in a way LRU's naturally self-corrects.
- FIFO and random — simpler, real alternatives. FIFO (first in, first out) evicts whatever entry has simply been in the cache longest, regardless of how often or recently it's been used — cheap to implement, but ignores real usage patterns entirely. Random eviction picks an entry to remove with no logic at all — surprisingly, in some real, specific workloads with no predictable access pattern, it performs close to more "intelligent" policies, at a genuinely lower bookkeeping cost.
- No single real policy is universally correct. GreenMart's own recently-viewed-products feature is a genuinely strong fit for LRU — recency is exactly the real signal that matters there. A catalog of evergreen bestsellers, accessed steadily over a long period, might fit LFU better. The right real choice always depends on the actual, observed shape of how that specific cached data gets accessed — not a universal best answer.
| Policy | Tracks | Evicts | Best real fit |
|---|---|---|---|
| LRU | Last access time | Least recently accessed entry | Access patterns driven by recency (recently viewed items) |
| LFU | Total access count | Least frequently accessed entry | Steady, long-term popularity (evergreen bestsellers) |
| FIFO | Insertion order | Oldest entry, regardless of use | Simple, low-overhead needs; unpredictable access patterns |
| Random | Nothing | A randomly chosen entry | Very low overhead; surprisingly competitive under unpredictable load |
GreenMart now has real, named language for a decision that was previously invisible — whatever eviction policy the proxy in front of GreenMart's storefront happened to ship with, by default, was making one of these real bets the whole time, without anyone at GreenMart choosing it deliberately.
Key Takeaway
An eviction policy is a real, deliberate bet about which cached entries are least likely to be needed again soon — LRU bets on recency, LFU bets on overall popularity, and the right one depends entirely on the real, observed shape of how that specific data actually gets accessed.
Why This Matters
As GreenMart builds real caching into more of its own infrastructure, the eviction policy behind each cache is a genuine, measurable performance lever — the wrong policy for a given access pattern means real, valuable data gets thrown away constantly, forcing repeated, expensive re-fetches for no good reason.
GreenMart now has the real, named vocabulary for how a cache chooses what to evict — LRU, LFU, FIFO, and random, each a different real bet. The next chapter shifts from reads to writes: what actually happens to a cache when the underlying data changes, not just when the cache runs out of room.