Answers · The systems around the model

What's the difference between LRU and LFU, and which one should I use?

In shortLRU drops the item unused for longest; LFU drops the item requested least often. Both guess at future use, and the cheap win is refusing one-off arrivals rather than counting requests.

LRU discards the item that has gone longest without a request. LFU discards the item that has collected the fewest requests over its whole stay in the cache. The two rules are guessing at the same quantity, which held item will next be wanted furthest in the future, and they differ only in which evidence they consult. Start from recency, and spend your effort on refusing bad arrivals rather than on a cleverer eviction order.

What the sweep costs

Take a cache of three items. Normal traffic has made six requests, the three popular items are held, and four of the six hit: $4/6 = 0.67$ . Then a nightly report walks a table touching each row once. Every row is new, every row misses, every row is admitted, and each admission evicts the popular item that has gone longest untouched. By request 9 only one popular item survives and the running rate is $4/9 = 0.44$ . By request 12 the cache holds nothing real traffic wants: $4/12 = 0.33$ . Real traffic resumes and pays a miss for each popular item before it is held again, so by request 18 the rate reads $5/18 = 0.28$ . Nothing failed and no component misbehaved. The rule did exactly what it was told.

i^{\star} = \arg\max_{i \in C}\, t_{\mathrm{next}}(i), \qquad \mathrm{LRU}: \arg\min_{i \in C} t_{\mathrm{last}}(i), \qquad \mathrm{LFU}: \arg\min_{i \in C} n_i

Frequency repairs the sweep immediately. A row touched once by a crawler has $n=1$ and loses every comparison, so the popular items keep their places. The failure then arrives from the other side: a count is a record of the whole past, and the past includes a week when something was briefly enormous. Long after the interest has gone, that item still outscores everything current, and the cache fills with champions of a finished period. The usual remedy is to give the evidence a shelf life, halving every count periodically or counting over a recent window. The ageing schedule then matters as much as the cache size.

FIG 1

rule	hit rate on skewed traffic (%)	hit rate during a sweep (%)	extra bytes per item	relative cost
discard the least recently used	86	12	8	1
discard the least frequently used	89	88	40	4
discard one at random	72	71	0	1
filter arrivals, then use recency	91	89	12	3

Where the natural guess goes wrong

It is tempting to read LRU as claiming that what was used recently will be used again. The claim is narrower: reuse is concentrated in time, so an item asked for once tends to be asked for again within a short window, and an item idle for a long stretch is likelier to stay idle. Recent use and likely-to-be-used-again are not the same statement, and they come apart on exactly one pattern, a single pass through more items than the cache can hold. That pattern is not exotic: a backup, a migration, a crawler, a full-table scan, a nightly report. Recency sees a stream of newly used items and, obeying the only rule it has, throws away everything the real traffic depends on. The loss is not gradual. Once the pass is longer than the cache, nothing valuable is left, and the working set has to be reloaded one miss at a time.

Refuse the arrival instead

On a miss the expensive work is already done, so there is a moment to ask a different question: is this item worth displacing anything at all? Keep a small approximate record of what has been requested recently. If the arriving item's count is below the count of the resident it would evict, serve the answer and keep nothing. The valuable item keeps its place, the one-off visitor is served and forgotten, and the sweep has nothing to displace. The record can be tiny, since approximate counters with ageing hold usable estimates in a few bytes per item: the last row of the table above costs 12 bytes against 40 for full counting, which is $12/40 = 0.3$ of the memory for a hit rate during the sweep of 89 against 88.

FIG 2Hit rate against cache size, for three rules

recency alonefrequency without ageingthe clairvoyant rule

The top curve cannot be built. The useful reading is the vertical gap between it and your real policy at your real size, because that gap is the whole of what changing the rule can win.

Measure the ceiling before tuning anything. At a thousand items, recency sits at $0.93 - 0.55e^{-1000/400} = 0.885$ , and the rule that always discards the item wanted furthest away sits at $0.97 - 0.5e^{-1000/300} = 0.952$ . The gap is $0.952 - 0.885 = 0.067$ , about seven points. That is the entire prize available from eviction at that size. If your policy is already at 88 percent and the ceiling is 95, no amount of cleverness in the eviction rule can win more than seven points, and the effort belongs in admission, or in not caching that request at all.

Where both rules stop being the right question

Both rules count requests and ignore size, so both mislead as soon as items differ in size. A hit rate counts hits, not bytes saved, and a 10 MB item that hits as often as a 1 KB item is spending $10\,000\,000/1\,000 = 10\,000$ times the room for the same reward. What matters is hits expected per unit of space per unit of time, $h/(s\tau)$ : $h$ hits before discard, over the space $s$ the item occupies times the time $\tau$ it is expected to stay. If a miss costs almost nothing, or if the cache is so small that it only holds the handful of items everybody asks for, then every rule behaves alike and the choice between them is noise.

The clairvoyant rule is not an option, only a measuring stick. Replay a recorded hour against it at your own cache size before writing anything: if the gap to your current policy is two points, the next eviction rule is not where the work is.

Worth keeping

LRU and LFU are both predictions about which held item will be wanted furthest in the future; they differ only in the evidence they use.
A pass through more items than the cache holds empties an LRU cache of everything valuable, and hit rate stays low until the working set is reloaded one miss at a time.
Refusing a low-count arrival entry is usually cheaper and more effective than improving the rule that picks what to evict.

Where this goes next

This question is one step of Keeping the Answer Nearby, a course that works through its subject from the beginning. The page that teaches this part of it is Deciding What to Throw Away, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course