What Are Cache Eviction Policies?
Learn how cache eviction policies like LRU, LFU, and FIFO work, their trade-offs, and how real systems like Redis approximate them.
Expected Interview Answer
A cache eviction policy is the rule a fixed-size cache uses to decide which entry to remove once it is full and a new item needs to be stored, and the choice of policy directly determines the cache hit rate for a given access pattern.
The most common policies are LRU (Least Recently Used), which evicts the entry that has gone longest without being accessed and works well for temporal locality; LFU (Least Frequently Used), which evicts the entry with the lowest access count and favors items that are popular over time rather than just recently touched; and FIFO, which evicts in strict insertion order regardless of usage and is simple but ignores access patterns entirely. Real systems like Redis also offer randomized approximations (approximated LRU) because tracking exact recency at scale is expensive, and modern caches like Caffeine use hybrid policies such as W-TinyLFU that combine frequency and recency to resist scan-based pollution. Choosing the wrong policy for the workload — for example plain LRU on a workload with a one-time large sequential scan — can evict genuinely hot data and tank the hit rate.
- Keeps the cache bounded in memory while maximizing hit rate for the access pattern
- LRU adapts well to workloads with strong temporal locality
- LFU protects long-term popular items from being evicted by a burst of one-off accesses
- Hybrid policies like W-TinyLFU resist cache pollution from large sequential scans
AI Mentor Explanation
A cache eviction policy is like a coach deciding which player to drop from a limited squad when a new signing arrives. Under an LRU-style rule, the coach drops whoever has sat out the longest since their last match, assuming recent form predicts future selection. Under an LFU-style rule, the coach instead drops whoever has played the fewest matches overall, protecting a veteran who is reliably selected even if they rested last week. The squad-size cap forces this trade-off every single time a new player needs a spot.
Step-by-Step Explanation
Step 1
Cache reaches capacity
A new item needs to be inserted but the fixed-size cache has no free slot remaining.
Step 2
Policy identifies a victim
The eviction policy consults its tracked metadata (recency for LRU, frequency for LFU, insertion order for FIFO) to pick an entry to remove.
Step 3
Victim entry is evicted
The chosen entry is removed from the cache, freeing a slot and, for write-back caches, potentially flushing dirty data first.
Step 4
New item is inserted and tracked
The new entry takes the freed slot and its recency/frequency metadata is initialized for future eviction decisions.
What Interviewer Expects
- Names at least LRU and LFU by mechanism, not just by name
- Explains the trade-off: recency (LRU) vs frequency (LFU) vs simplicity (FIFO)
- Mentions that the wrong policy can pollute the cache on scan-heavy workloads
- Aware of real implementations: Redis approximated LRU, Caffeine W-TinyLFU
Common Mistakes
- Assuming LRU is always the best default regardless of access pattern
- Confusing eviction policy with cache invalidation (staleness) — they solve different problems
- Not knowing that exact LRU is expensive at scale, hence approximated variants
- Forgetting FIFO ignores usage entirely, which can be a real weakness
Best Answer (HR Friendly)
“A cache eviction policy is the rule a cache uses to decide what to throw out when it is full and needs room for something new. The most common one, LRU, throws out whatever has not been used in the longest time, while others like LFU throw out whatever has been used the least often overall, and picking the right one depends heavily on how the data is actually accessed.”
Code Example
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.store = OrderedDict()
def get(self, key):
if key not in self.store:
return None
self.store.move_to_end(key) # mark as most recently used
return self.store[key]
def put(self, key, value):
if key in self.store:
self.store.move_to_end(key)
self.store[key] = value
if len(self.store) > self.capacity:
self.store.popitem(last=False) # evict least recently usedFollow-up Questions
- How does Redis approximate LRU without tracking exact access order for every key?
- What is cache pollution and how does W-TinyLFU protect against it?
- When would FIFO eviction actually outperform LRU?
- How would you evict entries in a distributed cache shared across multiple nodes?
MCQ Practice
1. Which entry does a strict LRU policy evict first?
LRU tracks recency of access and evicts whichever entry has gone longest without being touched.
2. What is the key difference between LRU and LFU eviction?
LRU evicts based on how recently an item was used; LFU evicts based on how many total times it has been used.
3. Why do production caches like Redis often use approximated LRU instead of exact LRU?
Maintaining exact recency order for millions of keys is expensive, so Redis samples a subset of keys to approximate LRU cheaply.
Flash Cards
What is a cache eviction policy? — The rule a full cache uses to decide which entry to remove when inserting a new one.
LRU eviction? — Evicts the entry that has gone longest without being accessed.
LFU eviction? — Evicts the entry with the lowest total access count.
Why does eviction policy choice matter? — The wrong policy for a workload can evict hot data and reduce the cache hit rate.