Choosing What to Forget
Last timeWhat a Hit Is Actually Worth
A full cache cannot accept anything without discarding something. Every eviction rule is a guess about the future built from the only evidence available, which is the past.
A cache with infinite space would need no rules. Real caches fill up within
minutes of starting, and from then on every arrival is a trade: this new item, in
exchange for one of the ones already held. The rule that picks the one to drop is
the single most studied thing in this subject, and it is doing something it
cannot possibly do well.
What the rule is actually predicting
Rewrite the problem and the difficulty is clear. You are holding a
thousand items. You must name the one that will next be requested furthest in
the future. You have no information about the future. All you have is a record of
what has already been asked for.
So every rule is a theory about how the past predicts the future, and the two
theories in common use are the obvious ones. Recency says that what has not been
wanted lately will not be wanted soon. Frequency says that what has rarely been
wanted will rarely be wanted.
Recency, and the one thing that breaks it
Discarding the least recently used item is the default almost everywhere, and it
deserves to be. Reuse is concentrated in time, so the item untouched for longest
genuinely is the best available bet. It needs almost no bookkeeping and adapts
instantly when traffic changes.
It has one catastrophic failure, and it occurs constantly in practice. Suppose something sweeps through a collection larger than the cache,
touching each item once: a nightly report, a backup, a migration, a crawler, a
full-table scan. Recency sees a stream of recently used items and dutifully
discards everything the real traffic depends on. By the time the sweep finishes,
the cache holds nothing anybody wants, and it stays that way until the working
set has been reloaded one miss at a time.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents