Cache eviction policies: LRU, LFU, and when each one wins

A TTL (time-to-live, already covered in System Design's caching lesson) controls how long an entry is allowed to live — it says nothing about what happens when the cache is full of entries that haven't expired yet but a new one needs room. Eviction is the separate mechanism that kicks in specifically at that moment: picking an existing, still-valid entry to remove to make space, using a policy that tries to remove the entry least likely to be needed again soon.

Least Recently Used tracks, for every entry, when it was last read or written, and evicts whichever entry has gone the longest without being accessed. The intuition: data that was actively used recently is statistically more likely to be used again soon than data nobody has touched in a while — "recency predicts future use."

LRU is the default in most real caches (including Redis's allkeys-lru policy) because this intuition holds for a genuinely wide range of real access patterns — a user's profile they just viewed is more likely to be viewed again soon than one nobody's touched all day.

Least Frequently Used tracks an access count per entry instead of a last-access time, and evicts whichever entry has the lowest count. The difference from LRU matters for a specific, real pattern: an item accessed constantly for a long stretch, then not touched for the last few minutes, stays protected under LFU (its count is still high) but would get evicted under LRU (its last access is now relatively old) — LFU better fits access patterns with a stable set of genuinely "hot" items that occasionally go briefly quiet, while LRU better fits patterns where recent activity really is the best predictor.

FIFO evicts whatever entry was inserted first, regardless of how often or recently it's been accessed — cheaper to implement than tracking per-entry access recency or frequency, and a reasonable choice when access patterns are close to uniform (no entry is meaningfully "hotter" than another, so recency/frequency tracking buys nothing). Random eviction is even simpler still, and — counterintuitively — performs surprisingly close to LRU for some uniform-ish workloads, at a fraction of the bookkeeping cost.

There's no policy that dominates in every case — LRU can actually perform worse than random under a specific, real pathological pattern: a one-time full table scan touching every entry exactly once floods an LRU cache with entries that will never be accessed again, evicting genuinely hot data to make room for data that's now "most recently used" but will never be read again. Recognizing this failure mode (and the scan-resistant variants, like LRU-K, some real caches add specifically to guard against it) is what separates choosing a policy deliberately from assuming LRU is always the safe default.