When the Cache Is Full
A cache has bounded size. When a new entry arrives and there is no room, an eviction policy picks a victim to remove. The right policy depends on how your access pattern behaves over time.
The Classic Policies
- LRU least recently used evicts whatever has gone longest without access. It assumes recent use predicts future use and handles most workloads well.
- LFU least frequently used evicts the entry with the fewest accesses. It protects items that are popular over the long run but can keep stale once hot entries.
- FIFO first in first out evicts the oldest inserted entry regardless of use. It is cheap to implement but ignores access patterns entirely.
Tradeoffs
LRU needs recency tracking, LFU needs a frequency counter, and FIFO needs only a queue. Real systems often use approximations like a sampled LRU or a frequency sketch because exact tracking is costly at scale. A pure LFU also suffers from cache pollution when an old burst of hits keeps an entry that is now cold.
Key idea
LRU bets on recency, LFU bets on long run popularity, and FIFO ignores access entirely, so match the policy to how your data is reused.