Caching • Eviction PoliciesMedium⏱️ ~3 min
Recency vs Frequency: LRU, LFU, and Segmented Designs
Recency driven and frequency driven eviction policies represent two fundamental approaches to predicting future access patterns. Least Recently Used (LRU) maintains a recency ordering and evicts the item accessed longest ago, betting that recent access predicts near term reuse. LRU adapts quickly to workload shifts because a few accesses immediately promote an item to the most protected position. However, LRU is vulnerable to scan pollution: a sequential scan that touches a large keyset once will evict the entire working set, collapsing hit rate. The metadata cost for exact LRU is a hashmap plus doubly linked list, requiring approximately 24 to 48 bytes per entry in pointers and bookkeeping on 64 bit systems.
Least Frequently Used (LFU) tracks access counts and evicts the item with the lowest frequency, betting that long term popularity predicts future access. LFU retains popular items even through temporary access pauses, making it robust for workloads with stable hot sets. However, without counter decay, LFU adapts slowly to workload changes and stale once popular items can persist indefinitely. Implementing LFU requires counters (typically 1 byte per entry with periodic decay) and frequency buckets that map from count to a set of items. Periodic counter decay, such as halving all counts on a schedule, bounds stale history and prevents counter saturation in 8 bit implementations.
Segmented designs like Segmented LRU (SLRU) and 2Q combine recency and frequency to resist scan pollution while adapting to change. SLRU maintains two LRU queues: a probation segment for newly admitted items and a protected segment for items that received a second hit. Items enter probation on first access; a second hit promotes them to protected. Eviction takes from probation first, so a scan flows through probation without disturbing the protected working set. This simple modification dramatically improves hit rate under mixed workloads. The CLOCK algorithm approximates LRU using reference bits and a circular buffer with a sweeping hand, providing similar behavior with lower overhead and better concurrency, though tuning the sweep rate relative to insertion rate is critical to avoid FIFO like behavior under pressure.
💡 Key Takeaways
•LRU evicts the least recently accessed item and adapts quickly to workload shifts, but sequential scans evict the entire working set. Exact LRU requires 24 to 48 bytes metadata per entry for hashmap plus doubly linked list pointers on 64 bit systems.
•LFU evicts the least frequently accessed item and retains long term popular data, but without decay stale items persist. Implementation requires 1 byte counters with periodic halving to prevent saturation and adapt to change, plus frequency buckets for efficient eviction.
•Segmented LRU (SLRU/2Q) uses two queues: probation for new items and protected for items with multiple hits. Evicting from probation first allows scans to flow through without disturbing the working set in protected. Typical split is 20% probation and 80% protected.
•CLOCK approximates LRU using reference bits and a circular scan, offering lower overhead and better concurrency than exact LRU. However, tuning the hand sweep rate is critical; too slow mimics FIFO under pressure, too fast wastes CPU.
•W-TinyLFU (used in Caffeine) combines a small window LRU segment (1% to 2%) to absorb bursts with segmented LRU for the main cache and TinyLFU admission filtering. This design improves hit rate by 10% to 30% over plain LRU under heavy tailed workloads at the same memory budget.
•Choosing between policies depends on workload: use LRU or SLRU for small fixed size values with high churn and quick adaptation needs; use LFU with decay for stable working sets; use segmented designs with admission for scan heavy or mixed workloads.
📌 Examples
Redis supports multiple eviction policies including approximate LRU and LFU via sampling. To keep CPU cost low, Redis samples 5 to 10 random candidates and evicts the worst among them by policy. This yields hit ratios within a few percent of exact algorithms under typical power law workloads with a fraction of the overhead.
Caffeine (a Java caching library) implements W-TinyLFU with a window segment (1% LRU), probation segment (20%), and protected segment (79%), plus a Count Min Sketch for admission. Published evaluations show 10% to 30% hit rate improvement over LRU under production traces from search, social, and storage workloads.