Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Cache Eviction Policy

This site has two caches, and they close with the same admission. LRU Cache evicts whoever's gone longest without being touched; LFU Cache evicts whoever's been touched the fewest times overall. Both are O(1) on get and put. Neither page's own Complexity section settles which one actually keeps more of the right things cached — LFU Cache's own words are "picking between them is a bet about the real workload, not something either page's own complexity bound can settle." This guide takes that bet literally: it runs both pages' own shipped reference implementations, unmodified, against two small synthetic workloads — one built to expose each policy's real weakness — and measures the real hit rates rather than reasoning about them in the abstract.

The question neither page's complexity bound answers

A cache's complexity bound says how fast one get or put runs. It says nothing about how often a get is a hit in the first place — that depends entirely on which entries the policy chose to keep, which depends entirely on the sequence of keys a real caller actually sends it. Two workloads below are built to disagree about that sequence as sharply as possible: one where a small set of entries is genuinely, persistently more valuable than everything else (LFU's bet pays off), and one where the entries that used to be valuable aren't anymore (LRU's bet pays off, and LFU's can fail completely).

Periodic floods: LFU protects a small hot core, LRU doesn't

Picture a cache sitting in front of something that gets hit constantly by a small set of hot keys — plus, periodically, a much larger flood of keys that are each touched exactly once and never again: a nightly batch report, a backup job walking every row once, a log tailer scanning a day's worth of entries. Each flood alone is bigger than the cache. The question is whether the flood is allowed to evict the hot core it otherwise never competes with.

Under LRU, yes: recency is the only thing that matters, and every key in the flood is, for one moment, more recent than the hot core. By the time the flood ends, the hot core has been completely pushed out — it has to be re-faulted in from scratch after every single flood, no matter how many times it was touched before the flood started. Under LFU, the hot core's frequency count survives the flood untouched: each flood key arrives at frequency 1, which is already the lowest frequency in the cache the moment it arrives (a brand-new key's frequency can't be lower than 1), so flood keys evict each other, never the hot core, as long as the hot core's own frequency is already above 1 when the flood starts.

Press "Run race" to measure hot-core hit rate for both policies across 20 flood cycles, each flood 3× the cache capacity.

At capacity = 1,000 — a 100-key hot core touched 10 times per cycle, then a flood of 3,000 brand-new one-time keys, repeated for 20 cycles — LRU's hot-core hit rate is exactly 90.00% (9 hits out of every 10 touches: the first touch after each flood is always a forced re-fault, and nothing else ever evicts the hot core mid-cycle). LFU's hot-core hit rate is 99.50% — the only misses are the very first touch of each hot key, ever; once a hot key has been touched twice, no flood dislodges it again. That gap holds at every capacity tested (200 through 5,000, same ratios throughout, since every workload parameter scales with capacity) and widens the more times a key is touched per cycle before the flood arrives — at 50 touches per cycle LRU's floor rises to 98.00%, a fixed (touches−1)/touches, while LFU stays within a hair of 100% regardless.

Popularity reversal: LFU can get stuck forever, LRU adapts

Now the opposite shape: a set of keys is genuinely hot for a long stretch, then popularity shifts entirely to a different, equally-sized set that was never touched before — a trending topic cooling off while a new one takes over, a feature flag's old cohort being retired in favor of a new one, the start of a new business day's working set. The old set's keys don't come back. The question is how fast each policy adapts.

LRU adapts almost immediately: a new key is, by definition, the most recent thing touched, so it only has to wait for the single oldest entry to cycle out, which happens on the very next miss. LFU can do far worse than "slow to adapt" — it can get stuck permanently. The old set spent a long stretch building up a high frequency count. When the new set's keys start arriving, each one lands at frequency 1 — the global minimum — so the next new key to arrive evicts the previous new key (also frequency 1), never the old, stale, but much-higher-frequency set sitting untouched. The new keys evict each other in an endless round-robin while the genuinely cold old keys squat in the cache indefinitely, simply because their frequency count was earned a long time ago and LFU — as built on this site, with no aging or decay — never forgets it.

Press "Run race" to fill the cache exactly full with one hot set, then switch entirely to a second, equally-sized hot set for 30 rounds, and measure each policy's hit rate on the new set only.

At capacity = 1,000 — 1,000 keys fill the cache exactly, each touched 30 times, then a second, disjoint set of 1,000 keys is touched 30 times each — LRU's hit rate on the new set is 96.67% (29 hits out of every 30 touches, the standard "one forced miss, then it sticks" shape). LFU's hit rate on the new set is a literal 0.00% — not a small number, not a slow convergence that would improve given more rounds: it stays exactly 0.00% at 30 rounds, 100 rounds, 1,000 rounds, even 10,000 rounds. The new keys never stop evicting each other, because nothing in this page's reference implementation (or the real LFU algorithm it implements) ever lowers a frequency once it's been earned. This is precisely the "aging problem" LFU Cache's own page names in passing — real production systems that use frequency at all almost always decay it over time for exactly this reason — measured here at its most extreme, not just asserted.

So which one

If the hot set can shift entirely over the cache's lifetime — and most real caches eventually see this, even if rarely — plain LFU's failure mode above is not a rounding error, it's a permanent correctness-shaped problem: popular-once keys can squat forever. LRU degrades gracefully in exactly the situation LFU degrades catastrophically in. If the hot set is genuinely stable and the real threat is periodic one-time floods — batch jobs, scans, backups, anything that touches a huge number of keys exactly once — LFU's frequency memory is a real, measured win, and LRU pays for it every single flood. Most production systems that care about this trade-off don't pick one pure policy; they blend recency and frequency (or decay frequency over time) specifically to get the flood-resistance above without the permanent-lock-in risk — a combination neither pure policy on this site implements.

Side by side

WorkloadLRU CacheLFU CacheWinner
Stable hot core + periodic one-time floods 90.00% hot-core hit rate (10 touches/cycle) 99.50% hot-core hit rate LFU, and it widens with more touches/cycle
Popularity reversal (hot set changes entirely) 96.67% hit rate on the new set 0.00% hit rate on the new set, permanently LRU, decisively