Cache Eviction Policies (LRU, LFU, FIFO)
Concept
Every cache has a finite capacity, and once it's full, adding a new entry means something existing has to go. An eviction policy is the rule that decides which entry gets removed, and the choice of rule directly determines the cache's hit rate for a given workload — a poorly matched policy can evict data that was about to be requested again while keeping data nobody wants, turning an expensive-to-implement cache into one that barely helps.
Three baseline policies cover most of the design space:
- FIFO (First In, First Out) — evicts whichever entry was inserted earliest, regardless of how it's been accessed since. It requires no per-access bookkeeping at all — just an ordered queue of insertion order.
- LRU (Least Recently Used) — evicts the entry that hasn't been accessed for the longest time, on the theory that recent access predicts near-future access (temporal locality). Implementing true LRU requires updating an ordering structure (commonly a hash map plus a doubly linked list) on every single read, not just every write.
- LFU (Least Frequently Used) — evicts the entry with the lowest access count, on the theory that consistently popular items should stay cached regardless of exactly when they were last touched. This requires maintaining a counter per entry and reordering by frequency, which is more bookkeeping than LRU's simpler "move to front" update.
A more advanced hybrid, ARC (Adaptive Replacement Cache), developed at IBM, tracks both recency and frequency in two separate lists and dynamically adjusts how much weight each gets based on the actual observed request pattern, rather than committing to one signal (recency or frequency) up front. It generally beats both plain LRU and plain LFU across a wider range of workloads, at the cost of being meaningfully more complex to implement and reason about.
Tradeoffs
| Policy | Signal used | Bookkeeping cost | Best fit | Weak spot |
|---|---|---|---|---|
| FIFO | Insertion order only | Lowest — a simple queue | Cheap to implement; acceptable when access pattern is close to uniform | Evicts popular items just because they're old — ignores usage entirely |
| LRU | Recency of last access | Moderate — reorder on every read | Workloads with strong temporal locality (a burst of related requests cluster in time) | Vulnerable to a "scan" — one pass over a large range of cold data evicts the entire working set, even though none of it will be accessed again soon |
| LFU | Access frequency (count) | Higher — maintain and reorder by counters | A stable set of consistently popular keys (product catalog entries, common config, reference lookups) | Slow to adapt when popularity shifts — an item popular yesterday keeps a high count and resists eviction even after it stops being requested, unless counts are aged/decayed |
| ARC | Both recency and frequency, adaptively weighted | Highest — two lists, dynamic sizing logic | Mixed or unpredictable workloads where neither pure recency nor pure frequency is consistently the better signal | Implementation and tuning complexity; usually reached for only once a simpler policy has been measured and found wanting |
The core tension is prediction accuracy versus bookkeeping cost: the more information a policy tracks about actual usage, the better it can predict what to keep, but every additional bit of tracked state costs CPU and memory on the hot path of every cache access — an eviction policy that's expensive to maintain can erode the very performance gain the cache exists to provide.
When to use / when not to
- Use LRU as the default choice for general-purpose application caches — it handles the common case (recently touched data is likely to be touched again) well and is supported natively by most caching libraries and by Redis/Memcached's own eviction settings.
- Use LFU specifically when the access pattern has a stable long-tail shape — a small set of keys stay hot for a long time (popular product pages, frequently-looked-up reference data) — and confirm the library or implementation ages/decays counts over time, or a burst of one-time historical popularity will permanently protect a now-cold key.
- Use FIFO only when the cost of implementing or running LRU/LFU genuinely isn't justified by the workload — e.g., a cache where access pattern really is close to random, so tracking recency or frequency wouldn't improve the hit rate enough to pay for the bookkeeping.
- Watch specifically for scan-resistant behavior when the workload includes occasional large sequential scans (a backup job, a batch export) — plain LRU is the policy most vulnerable to having its entire working set evicted by one such scan; ARC or a scan-detecting variant handles this case explicitly where plain LRU does not.
- Don't reach for ARC as a default — its complexity is worth paying for once measurement shows plain LRU or LFU underperforming on the real workload, not as a speculative upgrade before that's been established.
Common pitfall
Picking an eviction policy based on textbook intuition rather than the actual measured access pattern, then never revisiting it once traffic shape changes. A cache tuned for LRU's recency assumption can silently degrade in hit rate if the real workload turns out to have a long-tail-popularity shape better served by LFU, or vice versa — and because the cache still "works" (it just serves fewer hits than it could), this kind of mismatch rarely triggers an alert on its own. It shows up only as a slowly rising origin/database load that gets attributed to traffic growth rather than to an eviction policy no longer matching the access pattern it was chosen for.
Engineering Lens
The strong answer in a design review isn't naming a favorite eviction policy — it's being able to describe the actual access-pattern shape of the data being cached (recency-dominated, frequency-dominated, or scan-prone) and showing the chosen policy matches that shape, ideally backed by a measured hit rate rather than an assumption. Most production caching libraries default to LRU because it's a reasonable prior for unknown workloads, but treating that default as permanent without ever measuring against the real traffic is the same category of mistake as never revisiting a database index against actual query patterns — a decision that was reasonable once and was never re-checked.