Cache Eviction Techniques
Cache Eviction Techniques
When your cache is full and a new item needs space, something must go — the eviction policy you choose determines whether you keep the most valuable items or throw them away randomly.
Cache Eviction Policies - When the Cache Gets Full
🎯 Challenge 3: The Parking Lot Problem
Scenario: You manage a parking lot with 10 spaces (cache). All spaces are full. A new car arrives (new data). Which car do you remove to make space?
Option A: Remove the car that's been parked longest (first in, first out)
Option B: Remove the car that hasn't moved in the longest time (least recently used)
Option C: Remove the car that moves least frequently (least frequently used)
Option D: Remove a random car
Question: Which strategy makes the most sense for keeping the lot efficient?
The Answer: Cache Eviction Policies!
When cache is full, we need rules for what to remove. Let's explore each!
🥇 LRU (Least Recently Used) - Most Popular!
Rule: Remove the item that hasn't been accessed in the longest time.
Mental model: If you haven't used it recently, you probably won't need it soon.
Visual example:
LRU Implementation:
When LFU works best:
✅ Content popularity matters (viral videos)
✅ Long-term access patterns
✅ Identifying "hot" data
✅ Media streaming platforms
Examples:
-
YouTube video cache (popular videos stay)
-
Spotify song cache
-
News article cache (trending stories)
LFU Problem: The "Aging" Issue
Problem: Old item: 1000 accesses (from 2 years ago) New item: 5 accesses (from today, trending!)
LFU keeps old item, evicts new trending item! ❌
Solution: Use "Time-aware LFU" with decay
-
Reduce frequency counts over time
- Or use LRU + LFU hybrid
🎯 FIFO (First In, First Out) - Simple Queue
Rule: Remove the oldest item (first added), regardless of usage.
Mental model: Like a queue at a store - first person in line leaves first.
Visual example:
FIFO Implementation:
When FIFO works best:
✅ Simple requirements
✅ Time-based expiration matters
✅ All data equally likely to be accessed
✅ Predictable access patterns
Examples:
- Log file rotation
- Message queues
- Simple rate limiting
FIFO Problems:
❌ Doesn't consider access patterns
❌ May evict frequently used items
❌ No locality optimization
❌ Generally worse hit ratio than LRU/LFU
🎪 Comparison: Which Policy Wins?
📊 Real-World Performance Comparison
General performance (typical workloads):
LRU wins most scenarios! ✓
Complexity:
| Policy | Get Complexity | Set Complexity | Implementation |
|---|---|---|---|
| LRU | O(1) | O(1) | Moderate (doubly-linked list + hash map) |
| LFU | O(1)* | O(log n)* | Complex (multiple data structures) |
| FIFO | O(1) | O(1) | Simple (queue + hash map) |
💡 Choosing the Right Policy
Choose LRU when:
✓ General-purpose caching
✓ Temporal locality important
✓ Simple to implement
✓ Good performance for most workloads
Choose LFU when:
✓ Popularity matters (hot content)
✓ Long-term patterns
✓ Willing to handle complexity
✓ Media/content streaming
Choose FIFO when:
✓ Simplicity is critical
✓ Time-based expiration
✓ All items equally likely to be accessed
✓ Learning/prototyping
Most common choice: LRU (best balance of performance and simplicity!)
Key Takeaways
- LRU (Least Recently Used) is the most common eviction policy — removes the item that hasn't been accessed for the longest time
- LFU (Least Frequently Used) is better for skewed access patterns — keeps items that are accessed often, even if not recently
- TTL-based expiration removes stale data automatically — essential for correctness when source data changes
- The choice of eviction policy depends on your access pattern — LRU for general use, LFU for popularity-based caching, TTL for freshness requirements
- Redis supports multiple eviction policies configurable at runtime — allkeys-lru is the safest default for most applications