Cache Eviction Policies (LRU/LFU)

Overview

A cache eviction policy is the rule a cache uses to decide which entry to remove when it is full and a new entry needs space. The three policies you must know are least recently used (LRU), least frequently used (LFU), and first in first out (FIFO), and each answers the same question differently: which entry is the least valuable to keep?

🧠 Mental model: Your desk is full of papers. LRU = toss the paper you haven't touched in the longest time. LFU = toss the paper you barely ever use. FIFO = toss the oldest paper, no matter how useful it is.

Key Concepts

Every policy tracks some metadata per entry and evicts the entry that scores worst by its rule. The cost of a wrong eviction is a future cache miss, so the goal is to keep entries most likely to be read again. Eviction pairs naturally with a caching strategy, which decides how entries enter the cache in the first place.

Least recently used (LRU)

LRU evicts the entry that has gone the longest without being accessed, betting that recently used items will be used again soon (temporal locality). Each access moves an entry to the "most recent" end, and eviction takes from the "least recent" end.

Least frequently used (LFU)

LFU evicts the entry with the lowest access count, betting that popular items stay popular. It protects a heavily requested entry even if it was not touched in the last few operations, but it can cling to items that were hot in the past and have since gone cold.

First in first out (FIFO)

FIFO evicts the oldest inserted entry regardless of how often or how recently it was used, like a queue. It is the cheapest to implement because it ignores access patterns entirely, but that also makes it the most likely to evict a hot entry.

Policy	Evicts	Tracks	Strength	Weakness
LRU	Longest-unused entry	Recency of access	Captures temporal locality	Evicts a rare-but-important reuse
LFU	Lowest-count entry	Access frequency	Keeps steadily popular items	Slow to release once-hot items
FIFO	Oldest-inserted entry	Insertion order	Simplest and cheapest	Ignores actual usage

Trade-offs

The trade-off is prediction accuracy versus bookkeeping cost. FIFO is nearly free but blind to usage, so it usually yields the lowest hit rate. LRU tracks recency with a linked list plus a hash map and is the pragmatic default for most workloads. LFU can beat LRU when popularity is stable, but counters must be aged or decayed, otherwise stale favorites are never evicted; that extra machinery makes LFU the most expensive of the three.

Interview Tips

Default to LRU unless the workload gives you a reason not to, and be ready to justify it with temporal locality.
Reach for LFU only when you can argue that popularity is stable over time, and mention counter aging so the interviewer knows you have seen its failure mode.
Note that real systems often use approximations, such as sampled LRU, because exact ordering is too costly at scale.

Summary

An eviction policy chooses which entry to drop when a full cache needs space.
LRU evicts the longest-unused entry and captures temporal locality.
LFU evicts the least-accessed entry and rewards stable popularity.
FIFO evicts the oldest-inserted entry and is cheapest but usage-blind.
The choice trades prediction accuracy against per-entry bookkeeping cost.