Cache Eviction: Deciding What to Forget

WHY IT EXISTS Caches are small, fast, and expensive memory stores used to avoid accessing larger, slower storage. Because they are small by design, they inevitably fill up. An eviction policy provides a deterministic algorithm for deciding which item to remove to make space for a new one, balancing the goal of keeping the most useful data.

THE MENTAL MODEL A cache eviction policy is like the rule you use to manage a small workbench. Your main tool chest is large but slow to search. You keep your most-used tools on the workbench for quick access. When you need a new tool from the chest but the bench is full, you must decide which tool to put back. Do you put back the one you used longest ago (Least Recently Used - LRU)? Or the one you use least often (Least Frequently Used - LFU)? The rule you choose is your eviction policy.

HOW IT WORKS When a request arrives for data not in the cache (a 'cache miss') and the cache is full, the eviction policy is triggered. It analyzes the metadata of the cached items, like access timestamps or usage counters, to select a victim for eviction. Common policies include: First-In, First-Out (FIFO), which discards the oldest item; Least Recently Used (LRU), which discards the item that hasn't been accessed for the longest time; and Least Frequently Used (LFU), which discards the item accessed the fewest times. The chosen item is removed, and the new item is stored in its place.

WHEN TO USE IT You must choose an eviction policy whenever you implement or configure a cache. LRU is a common, general-purpose default for workloads where recent access predicts future access, like user session data. LFU is better when some items are persistently more popular than others, regardless of recent access, such as a configuration file or a popular product's details. FIFO is simple but often inefficient, suitable only when access patterns are uniform.

WHEN NOT TO USE IT There is no 'when not to use it' for caching in general; if you have a cache, you need an eviction policy. The key is not to use the wrong policy. For example, do not use LRU for large data scans, like iterating over a massive dataset for a batch report. Each new item read will evict the previously read item, making the cache useless as it thrashes constantly. This is called cache pollution. In such cases, a more sophisticated policy or bypassing the cache might be necessary.

ONE CANONICAL EXAMPLE A web server caches rendered HTML pages and uses an LRU policy. When a user requests page A, it's cached. Then B, C, and D are requested, filling the cache. If a user then requests page E, the server must evict one page. Under LRU, it checks which page was accessed least recently. In this sequence, page A is the victim. It's removed, and page E is stored. If page A is requested again, it's a cache miss.