Choosing what to forget
A Socratic walk-through of choosing what to forget — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #When memory runs out, how do you decide what to discard without knowing what you will need next?
A cache is full and something new has arrived. One resident must go. Which one?
Notice first that the question has a perfect answer, and that we cannot use it. Discard the item whose next use lies furthest in the future — that is provably the best possible choice, established by Belady in 1966. It is also useless, because it requires knowing the future. So the honest form of the question is not "what is the best thing to evict" but something stranger: what visible evidence about the past is the best available substitute for knowledge we cannot have?
Reasoning it through
REASONING #Let us take seriously that this is a prediction problem. We want to evict the item least likely to be needed soon, and we have only the access history. What signals does the history offer?
The first is recency. If something was touched a moment ago, is it more likely to be touched again? For most real workloads, yes — programs work in phases, users revisit what they just opened, loops re-read the same rows. That regularity has a name, temporal locality, and it is an empirical property of workloads rather than a law. Evicting the least recently used item is a bet that it holds.
The second signal is frequency. Something requested a thousand times is presumably popular in a way that a single request does not establish. Evicting the least frequently used item is a bet on stable popularity.
Now, which is right? The productive move is to notice they fail in different places, and that the failures are what tell you what each is really measuring.
Where does recency fail? Consider a scan — a query reading a large table once, straight through. Every page is maximally recent the instant it arrives, so recency ranks all of them above your genuinely hot data, and the scan evicts the entire working set on its way past. Worse, consider a loop over a region just slightly larger than the cache: every item is evicted precisely one step before it is wanted again, and the hit rate is zero. Not poor — zero. Recency is not merely imperfect there; it is systematically inverted.
Where does frequency fail? On change. An item that was hugely popular last week accumulates a count that a currently rising item cannot beat, so the cache clogs with stale winners. Pure frequency has no way to forget, which is an odd flaw in a mechanism whose entire job is forgetting.
So each proxy encodes an assumption: recency assumes the near past predicts the near future; frequency assumes popularity is stable. Neither assumption is always true, and each one's failure mode is exactly the workload the other handles well. Does that suggest the fix?
It does, and it is what modern caches do. Keep both signals and let the workload decide the weighting. Adaptive replacement maintains one list for items seen once and another for items seen repeatedly, plus ghost entries — keys remembered without their data — so that a miss on a ghost is evidence about which list was starved, and the boundary between them shifts accordingly. Others admit a new item only if a compact frequency sketch says it looks more valuable than the victim it would displace, which makes a one-off scan cheap to reject.
There is one more thing worth knowing, because it bounds how good any of this can get. No deterministic online policy can stay within a constant factor of the clairvoyant optimum: with a cache of k items, the best guarantee available is a factor of k, and least-recently-used achieves it. Randomisation improves the bound to about the logarithm of k. In other words, the gap between us and Belady is not a failure of ingenuity — it is the price of not knowing the future, and it has been measured.
The analogy
THE ANALOGY #Think of clearing a desk you must work at tomorrow, with no diary of tomorrow's meetings. You cannot know which papers you will need, so you reach for what the papers themselves reveal: this one you read an hour ago, that one you have consulted every day for a month, this pile arrived this morning from a mailing you will never open again. You are not deciding what matters — you are reading the traces of your own past behaviour as evidence about it.
a desk is cleared occasionally and with your full attention, whereas a cache decides on every single miss and must do it in a few nanoseconds, which is why real policies use crude approximations — a single reference bit swept by a clock hand — rather than the careful ordering the desk image suggests.
Clarifying the model
THE MODEL #The refinement that ties this together: recency and frequency are not two competing answers to the eviction question. They are two different proxies for the same unobservable quantity, the time until next use. Once you see them that way, "which is better" is revealed as the wrong question — the right one is which proxy your workload makes reliable, and whether you can detect that at runtime.
A misconception worth correcting is that a bigger cache always helps. Under first-in-first-out replacement it need not: adding capacity can strictly increase the number of misses, an effect known as Belady's anomaly. Policies like least-recently-used are immune, because they have a structural property — the contents at size k are always a subset of the contents at size k+1 — that first-in-first-out lacks. If you are ever tempted to treat eviction policy as an interchangeable detail, that anomaly is the counter-example.
And a practical note. Textbook least-recently-used requires reordering a list on every hit, which is real work on a hot path and a contention point across threads. Production systems almost always use an approximation — a reference bit and a sweeping hand, or a sampled subset of candidates. The cost of choosing is part of the design, not a footnote to it.
A picture of it
THE PICTURE #How to readThe two axes are the two proxies, laid out as what they actually are — independent evidence. Both policies agree about the top right and the bottom left, which is why any policy looks fine on an easy workload. The disagreements are the other two corners, and each one is a named failure. Bottom right is the scan page: recency would keep it, and doing so is what flushes your working set. Top left is the faded favourite: frequency would keep it long after anyone stopped asking. A policy that consults only one axis is blind to one of those corners by construction.
What became clearer
WHAT CLEARED #Eviction is a forecasting problem wearing the costume of a bookkeeping problem. Since the optimal rule needs the future, every real policy substitutes an observable proxy — recency, frequency, or some negotiated blend — and each proxy is a bet on a property of the workload. Knowing a policy therefore means knowing which bet it makes and which access pattern collects on that bet against you.
Where to go next
ONWARD #- How adaptive replacement uses ghost entries to detect which proxy the current workload favours.
- Why a compact frequency sketch makes a good admission filter, and what it costs in accuracy.
- How eviction interacts with write-back and dirty data, where the victim is not free to discard.
Key terms
TERMS #| Term | What it means |
|---|---|
| Belady's MIN | the clairvoyant policy evicting the item used furthest in the future; optimal, and unimplementable. |
| Temporal locality | the empirical tendency of recently used items to be used again soon. |
| Belady's anomaly | the effect where increasing cache size increases misses, possible under first-in-first-out. |
| Ghost entry | a remembered key whose data was evicted, used as evidence about a policy's recent mistakes. |
| CLOCK | an approximation of least-recently-used using one reference bit per item and a sweeping hand. |
Every term the collection defines is gathered in the glossary.