Cache Eviction Policies
When a cache reaches capacity, an eviction policy determines which entries to remove. Common policies: LRU (Least Recently Used), LFU (Least Frequently Used), FIFO, and TTL-based expiration.
LRU = a fridge with limited shelf space. Whatever you haven't touched in the longest time gets tossed when you bring home new groceries. LFU = toss what you RARELY eat, even if you bought it yesterday.
LRU evicts the entry that was accessed least recently. It works well for temporal locality (recently accessed items tend to be accessed again). LFU evicts the least frequently accessed entry — better for stable working sets where some items are persistently popular. FIFO is simple but ignores access patterns. TTL expiration evicts entries after a fixed time regardless of access frequency — appropriate for data with known staleness tolerance.
LRU is O(1) with a doubly-linked list + hash map: the map gives O(1) access to any node, the linked list maintains recency order. On access, move the node to the head; on eviction, remove from the tail. Redis uses an approximated LRU (sample 5 random keys, evict the oldest) to avoid the memory overhead of exact LRU tracking. LFU in Redis 4.0 uses a probabilistic counter (Morris counter) that increments logarithmically — avoids counter overflow while tracking relative frequency. For cache warming at startup, pre-populate with the highest-frequency keys from logs to avoid cold-start storms. Segment-aware caching (e.g., Caffeine's Window TinyLFU) splits the cache into a small admission filter and a main protected region, providing better hit rates than pure LRU or LFU for real workloads.
For a general web application cache, I'd use LRU — it handles temporal locality well and is simple to reason about. For a cache serving a catalog of items with stable but uneven popularity (e.g., product pages where top 1% of products get 80% of traffic), LFU is better — it keeps the persistent hot items in cache. I'd always combine an eviction policy with TTL: eviction handles capacity, TTL handles staleness.
Assuming LRU is universally optimal. For scan-heavy workloads (full table scans, batch jobs), LRU is catastrophic — the scan floods the cache with one-time entries, evicting the working set. Use a scan-resistant variant or bypass the cache entirely for batch reads.