Theory
Cache Eviction Policies
📋 Overview
Cache Eviction is the strategic process of removing items from a cache to make room for new data when memory limits are reached. Since cache storage (RAM) is expensive and finite, choosing the correct eviction policy is critical to maintaining a high Cache Hit Ratio. A poor policy can lead to "Cache Thrashing," where the system spends more time moving data in and out of the cache than actually serving it.
🏗️ Core Principles & Characteristics
- LRU (Least Recently Used): Discards the item that hasn't been accessed for the longest time. It operates on the principle of Temporal Locality (data used recently is likely to be used again soon).
- LFU (Least Frequently Used): Discards the item with the lowest total access count. It is ideal for data with static or long-term popularity.
- FIFO (First-In, First-Out): Discards the oldest item in the cache, regardless of how often or recently it was accessed. Simple but often inefficient.
- TTL (Time-To-Live): An expiration-based approach where data is automatically evicted after a fixed duration (e.g., 60 seconds).
- W-TinyLFU: A modern hybrid policy (used in the Caffeine library) that balances recency and frequency to achieve near-optimal hit rates for diverse workloads.
⚖️ Trade-offs: Pros & Cons
- Pros:
- Optimized Performance: Ensures that the most valuable ("hot") data remains in the fastest storage tier.
- Stability: Prevents "Out of Memory" crashes by strictly enforcing a memory cap on the cache.
- Cons:
- Computation Overhead: Policies like LFU require maintaining counters, while LRU requires updating a linked list on every read.
- The "Scan" Problem: Sequential scans (like a DB backup) can "pollute" an LRU cache, evicting all hot data in favor of data that will never be read again.
- Staleness: LFU can suffer from "frequency accumulation" where an item that was popular last week stays in the cache forever.
🌍 Real-World Implementation
- Redis: Uses an Approximate LRU algorithm. Instead of a perfect linked list, it samples a small set of keys and evicts the oldest one to save memory.
- Web Browsers: Use LRU to manage the local storage of images, scripts, and stylesheets.
- CDN (Content Delivery Networks): Use advanced variations of LFU/LRU to cache popular static assets at the network edge.
- CPU Caches: Use hardware-level pseudo-LRU policies to manage L1/L2/L3 cache lines.
💡 Interview "Gotchas" & Tips
- LRU Implementation: Be ready to explain how to build an LRU cache in $O(1)$ time using a HashMap (for lookups) combined with a Doubly Linked List (for tracking access order).
- Segmented LRU: Mention this as a solution to the "Scan" problem—new items go into a "probationary" segment and only move to the "protected" segment after their second hit.
- Counter Decay: For LFU, explain that you must periodically "decay" (e.g., divide by 2) the frequency counters so the cache can adapt to changing trends.
- Distributed Eviction: In a cluster (like Redis Cluster), remember that eviction happens locally on each node.
📐 Suggested Architecture Primitives
- Distributed Cache: Redis (Approximate LRU/LFU) or Memcached (LRU).
- In-App Cache: Caffeine (Java), Ristretto (Go), or Guava.
- Monitoring: Track Cache Hit Ratio and Eviction Rate; a high eviction rate with a low hit ratio usually means your cache is too small or your policy is wrong.
Canvas