Eviction Policies: LRU, LFU, ARC, TinyLFU

Every cache has a finite size, and when it is full, adding a new entry requires evicting an existing one. The eviction policy -- the algorithm that decides which entry to remove -- has a profound impact on cache hit rate and, by extension, system performance. A poorly chosen eviction policy can reduce hit rates by 10-30% compared to the optimal policy for a given workload, translating directly into increased database load, higher latency, and reduced throughput.

LRU (Least Recently Used) is the most widely deployed eviction policy. It evicts the entry that has not been accessed for the longest time, betting that recently accessed data is more likely to be accessed again (temporal locality). LRU can be implemented in O(1) using a doubly-linked list (for ordering) combined with a hash map (for lookup). Every access moves the entry to the head of the list; eviction removes from the tail. The clock algorithm is an efficient LRU approximation used in operating system page replacement, using a circular buffer with reference bits instead of a linked list. Redis implements several LRU variants: allkeys-lru (evict any key), volatile-lru (evict only keys with TTL), and an approximate LRU that samples a subset of keys to reduce overhead.

LFU (Least Frequently Used) evicts the entry with the fewest accesses, making it ideal for workloads with skewed access patterns where a small set of keys receives the vast majority of requests. However, naive LFU has a significant problem: entries that were popular in the past but are no longer accessed accumulate high frequency counts and resist eviction, polluting the cache with stale hot data. Solutions include frequency decay (halving counts periodically) and windowed LFU (counting accesses within a recent time window). ARC (Adaptive Replacement Cache), developed by IBM Research, solves the LRU-vs-LFU choice by maintaining two LRU lists -- one for recently accessed entries and one for frequently accessed entries -- and dynamically adjusting the balance between them based on observed access patterns.

TinyLFU, the algorithm behind the Caffeine caching library (the standard JVM cache), represents the state of the art. It uses a Count-Min Sketch -- a probabilistic data structure -- as an admission filter that estimates access frequency with minimal memory overhead. When a new entry arrives, TinyLFU compares its estimated frequency against the entry it would evict; the new entry is admitted only if it is predicted to be accessed more often. Window-TinyLFU (W-TinyLFU) adds a small admission window that uses LRU to handle burst access patterns, combining the strengths of both LRU and LFU. Benchmarks consistently show Caffeine's W-TinyLFU achieving near-optimal hit rates across diverse workloads, outperforming pure LRU by 5-15% and pure LFU by similar margins.

You have a small bookshelf (cache) that holds 10 books, but you own 100 books stored in a closet (database). When the shelf is full and you want to add a new book, you need an eviction policy. LRU: remove the book you have not touched in the longest time. LFU: remove the book you have read the fewest times total. ARC: keep track of which strategy would have been better recently and adjust. TinyLFU: before putting a new book on the shelf, check if you are likely to read it more often than the book it would replace -- if not, leave the shelf as is.