Cache Eviction: LRU, LFU, TTL, FIFO

Your cache has been humming. The hot products sit in memory, the hit rate is up around 90%, the database is practically napping — exactly the win from the last two lessons. Then, at 2 a.m., a nightly analytics job kicks off a full-table scan: it reads every single product once, in order, top to bottom. Your cache does what a cache does — it tries to remember each one as it flies past. But there's no room. So for every cold product the scan touches, the cache throws out a resident to make space. Product by product, your carefully-earned hot set gets evicted to hold keys the job will read exactly once and never again.

By sunrise the scan is done and your cache is full of garbage. Morning traffic arrives to a cold cache: the hit rate has cratered from 90% to 20%, and the database you spent two lessons protecting is suddenly slammed. Nothing crashed. No bug shipped. The cache simply made the wrong choices about what to forget.

That is this lesson. A cache is a small, fixed box in front of a big store, and it will fill up. The moment it is full and a new key arrives, exactly one resident has to be thrown out — and which one you pick is the whole difference between a cache that flies and one that thrashes. Remember the core truth from Why Caching Wins: hit rate is the entire game. Eviction is where hit rate is won or lost.

Scope: here we're deciding what to forget when the box is full — a question of space. Keeping a cached copy from going stale when the database changes underneath it is a different question — freshness — and it's the next lesson, Cache Invalidation. Don't conflate them; we'll draw the line sharply at the end.

Before the real policies, meet the perfect one — because you need a yardstick to judge the others against.

If you could see the future, the best possible eviction is obvious: when you must throw something out, throw out the key whose next use is furthest away — or that will never be used again at all. That's it. This is Bélády's OPT (also called MIN, or the clairvoyant algorithm), and it is provably optimal: no policy, however clever, can achieve fewer misses on a given sequence of requests. It is the ceiling.

It is also completely impossible to build, because it requires knowing the future — which requests are coming and in what order. So why should you care about an algorithm you can never run?

Two reasons, and they shape the whole lesson:

• It's the measuring stick. Replay your real traffic against OPT offline and you learn the ceiling: "our LRU gets 71%; OPT would get 79% — so there are eight points sitting on the table." Without OPT you have no idea whether your policy is great or terrible.
• It reframes everything else. Since none of us can see the future, every practical policy is a guess at "furthest future use," built from the only thing we actually have: the past. LRU guesses using recency. LFU guesses using frequency. FIFO guesses using age. Hold OPT in your mind as the thing they are all clumsily imitating — it turns five unrelated-looking algorithms into five answers to the same question.

Five policies you'll actually meet — each one a different bet on "which resident won't be needed soon."

FIFO — evict the oldest inserted. The proxy is age: whoever has been here longest goes first, like a queue. It's the simplest thing that could work — no per-access bookkeeping at all. It's also blind to how the data is actually used: a key that's been hit ten thousand times gets evicted before a newcomer that's never been touched, purely because it arrived earlier. FIFO is what you pick when you genuinely can't afford to track anything else.

LRU — evict the least recently used. The proxy is recency, and it rests on temporal locality: if you touched something recently, you'll probably touch it again soon. This is the default — the one you reach for when you're not sure — and on bursty, session-shaped traffic it's near-perfect. It's cheap, too: a hash map plus a doubly-linked list, move-to-front on every access, evict the tail, all O(1) (it's the classic interview problem for a reason). Its fatal flaw is the story we opened with: LRU is not scan-resistant. A sequential sweep bigger than the cache marks every key it touches as "recently used" and flushes your hot set — the morning disaster, in one policy.

LFU — evict the least frequently used. The proxy is popularity: keep a count per key, and the rarely-wanted go first. On stable, skewed traffic — a handful of forever-hot keys — it beats LRU, and it shrugs off scans: a scanned key has a count of one, so it's the first thing evicted and the hot set stays safe. Its flaw is the mirror image of LRU's: it's sticky. Counts pile up over a key's entire lifetime, so yesterday's viral hit keeps its huge count and squats in the cache long after everyone stopped caring — while a genuinely hot newcomer can't build a count fast enough to survive. The cure is aging: periodically decay the counts so "frequent" means "frequent lately."

Random — evict a random resident. The proxy is nothing, and that's the point. It keeps zero metadata, never takes a lock to reorder a list, and — surprisingly — lands within a few points of LRU on a lot of real workloads. When memory or CPU for bookkeeping is precious, random is not a joke; it's a serious, respectable choice (Redis ships it as allkeys-random).

TTL — evict on expiry. Every key gets a lifespan; when its clock runs out it's gone, used or not. Strictly this isn't a "who to kick when the box is full" rule — it's time-based — but it earns its seat because so much cached data has a natural shelf life: a login session, a one-minute rate-limit window, a rendered page that's fine for thirty seconds. In practice you layer TTL on top of a capacity policy — in Redis, the volatile-* family evicts by LRU, LFU, or soonest-to-expire, but only among keys that were given a TTL. (Using TTL to bound how stale a copy may get is a freshness decision — that's the next lesson, not this one.)

You can read those five descriptions and still not feel the difference. The only way is to watch the same requests hit different policies at the same time and see them pull apart.

Below, one request stream feeds four caches — FIFO, LRU, LFU, and OPT (the crystal ball) — all the same size. Each one lights up hit or miss, shows you exactly who it evicts, and runs a live hit-rate bar so you can watch the gap open.

Do this in order:

1. Start on skewed traffic (a few hot keys). LRU and LFU both track OPT closely — on friendly traffic, most reasonable policies are fine.
2. Hit inject a scan and watch LRU's bar fall off a cliff while LFU and OPT barely flinch. That drop is cache pollution — the 2 a.m. story, happening live.
3. Switch to shifting popularity (the hot set changes halfway) and watch LFU go stubborn, clinging to yesterday's favorites and missing the new ones, while LRU adapts within a few requests.

Two things to notice. Nobody ever beats OPT — it's the ceiling, and it's unreachable. And nobody wins every workload. That second point is the entire lesson: there is no best eviction policy, only a best-for-this-traffic one.

Since the race has no permanent champion, choosing a policy means reading your traffic, not ranking the algorithms. The chooser:

• General read-heavy, popularity roughly power-law, and you're honestly not sure → LRU. It's the safe default for a reason; Redis's own advice is literally "if in doubt, allkeys-lru."
• Strongly skewed and stable — a fixed set of hot keys that stays hot → LFU with aging. It guards that set and ignores scans.
• Bursty or session-shaped, with strong recent reuse → LRU again — recency is exactly the right signal.
• Data with a natural lifespan, or you need a staleness ceiling → TTL, layered on a capacity policy.
• Metadata or CPU is scarce, or the workload is adversarial → Random — cheap, and hard to fool on purpose.
• You want the best possible hit rate and can afford the machinery → a modern hybrid (next section).

Underneath all six is a single question: does my future look more like "recently used" or "frequently used" — and is there a scan waiting to pollute recency? Answer that and the policy almost picks itself. And then measure: the whole reason OPT exists as a yardstick is that the "obviously smart" policy sometimes loses, and only your real traffic knows which one.

Here's a thing the textbook won't tell you: almost nobody runs the LRU you learned in class. Exact LRU keeps a perfect global ordering of every key, and at scale the memory for that ordering — and the lock contention from reordering it on every read — is too expensive. So real caches cheat, cleverly.

• Redis doesn't do exact LRU — it samples. When it needs to evict, it grabs a small handful of random keys (five by default) and evicts the best victim among them. Bump the sample to ten and you're within a whisker of true LRU for a fraction of the cost. Its LFU is approximate too: an 8-bit probabilistic (Morris) counter with a built-in decay, so frequency is cheap to store and ages on its own. And Redis hands you the whole family as one config knob, maxmemory-policy: allkeys-lru / -lfu / -random, the volatile-* variants for keys-with-a-TTL, and noeviction — refuse new writes with an error — for when Redis is being used as a database, not a cache.

• Memcached splits its LRU into HOT / WARM / COLD segments per size class, so a burst of new items can't flush the frequently-hit ones, and threads don't all fight over a single list.

• The state of the art is W-TinyLFU (Caffeine, and many CDNs). It fronts the cache with a tiny admission filter: using a compact frequency sketch, it decides whether a newcomer even deserves to be cached — it must out-score the key it would evict — behind a small recency window. The result is scan-resistant and adaptive — the best of LRU and LFU — which is how a modern cache sits just a few points under OPT. (ARC reaches the same goal differently: it keeps ghost lists of recently-evicted keys and self-tunes the balance between recency and frequency, no knob required.)

The point isn't to memorize these. It's that the five policies from earlier are the vocabulary; production systems blend and approximate them to get near-optimal hit rates on a real budget.

A few things about eviction feel obviously true and simply aren't — and each one has bitten someone in production:

• "A bigger cache always means fewer misses." Not always. Under FIFO, there are access patterns where adding memory causes more misses — Bélády's anomaly. The textbook string 1 2 3 4 1 2 5 1 2 3 4 5 faults 9 times with three slots but 10 with four. It happens because FIFO isn't a stack algorithm — a bigger cache's contents aren't guaranteed to contain the smaller one's. LRU, LFU, and OPT are stack algorithms and can never do this — a genuine, concrete reason to prefer them over FIFO.
• "LRU is the smart choice, always." Only until a scan walks through. Recency is a wonderful signal right up to the moment a batch job floods the cache with keys it touches exactly once.
• "Production runs the LRU I learned in class." It runs an approximation — Redis samples, W-TinyLFU sketches. Exact LRU is a teaching model, not a production one.
• "Eviction and invalidation are the same thing." They're orthogonal, and mixing them up causes real bugs. Eviction is about ROOM: a perfectly fresh, correct key gets thrown out because the cache is full. Invalidation is about HONESTY: a key stays happily cached, but its value went stale because the database changed underneath it. You can be evicted while correct; you can be stale while resident. Making room is this lesson. Staying honest is the next one — and it's the harder problem of the two.

• When the cache fills, one resident must go — and that choice is your hit rate. Evict a hot key and it misses, reloads, and shoves out the next hot key: that's thrashing. Eviction is where the whole caching win is kept or thrown away.
• The perfect choice is OPT — evict the key used furthest in the future — but it needs a crystal ball, so every real policy guesses it from the past: FIFO by age, LRU by recency, LFU by frequency, Random by nothing.
• No policy wins everywhere. LRU dies on scans; LFU goes sticky on shifts (fix: aging); FIFO ignores heat (and can even fault more with more memory); Random is cheap and shockingly okay. The access pattern picks the policy — so read your traffic, then measure against OPT.
• Production approximates and blends — Redis's sampled LRU and decaying-counter LFU, Memcached's segmented LRU, W-TinyLFU's admission sketch — to get near-OPT hit rates on a real budget.

Next — Cache Invalidation: The Second-Hardest Problem. Eviction decided what to forget to save space. Now the harder question: when the source of truth changes, how do you stop the cache from confidently serving a lie? There's an old joke that there are only two hard problems in computer science — cache invalidation, naming things, and off-by-one errors — and we're about to see why the first one earns its spot.