Caching • Eviction PoliciesEasy⏱️ ~3 min

Eviction Policy Fundamentals: Why Pure LRU and LFU Are Rarely Enough

Definition
Eviction policies determine which cached entries to remove when capacity is reached. The goal is maximizing utility by retaining entries that provide the most value: hit ratio, cost savings, or latency reduction.
The Multi Factor Decision
Eviction must balance: recency (recently accessed items likely reused), frequency (often accessed items valuable), size (1MB consumes 100x space of 10KB), and miss penalty (fetch cost varies). Pure LRU considers only recency; pure LFU only frequency. Real workloads require balancing all four.
Three Layered Architecture
Effective caching combines three layers. Admission decides whether to cache at all, filtering one hit wonders (items accessed once then never again). Eviction chooses which resident to remove. TTL (Time To Live) expiration handles staleness regardless of capacity. Example: TinyLFU admission filters scans, segmented LRU for eviction, TTL for freshness.
Production Constraints
Operations must run O(1). Metadata overhead 24-50 bytes/entry; 10M entries at 50 bytes = 500MB bookkeeping. Lock contention minimized via sharding. At 100,000 QPS with 10ms miss penalty, reducing miss rate from 20% to 16% saves 4,000 backend requests per second.
Key Insight: Eviction is a multi layered decision: admission, eviction, and expiration policies working together. No single policy handles all workload patterns.

💡 Key Takeaways

✓Eviction balances four factors: recency, frequency, size, and miss penalty. Pure LRU/LFU consider only one.

✓Three layers: admission (should we cache this), eviction (what to remove), TTL expiration (when data becomes invalid).

✓Operations must be O(1); metadata 24-50 bytes/entry; 10M entries at 50 bytes = 500MB bookkeeping.

✓At 100K QPS with 10ms miss penalty, reducing miss rate from 20% to 16% saves 4,000 backend requests per second.

📌 Interview Tips

1Explain four factors: recency, frequency, size, miss penalty. Pure LRU/LFU each consider only one.

2Describe layered approach: TinyLFU admission, segmented LRU eviction, TTL freshness.

3Why not pure LRU: sequential scan evicts entire working set. Need admission filter or segmented design.

← Back to Eviction Policies Overview