Cache Eviction Policies

Cache is a high-speed storage layer that sits between an application and its primary data store. It holds frequently accessed data to speed up reads. When a program needs to fetch data, it first checks the cache before going to the slower main storage.

Cache storage typically uses RAM which is costlier than the main storage on disc. Due to this cost constraint, cache size is usually limited. When this limited cache becomes full and we need to add new items, we must decide which existing items to remove. This is where cache eviction policies come into play.

The simplest approach to cache eviction is First-In-First-Out (FIFO). As the name suggests, FIFO removes the item that was added to the cache first. Think of it as maintaining a queue of cached items – when we need space, we remove the item at the front of the queue (the oldest one) and add the new item at the back. While FIFO is straightforward to implement, it has a significant drawback. Consider a scenario where a particular piece of data is accessed very frequently but happened to be cached first. Under FIFO, this frequently used item would be the first to be removed despite being the most useful item in the cache.

This limitation leads us to consider frequency of access as a metric for eviction, bringing us to the Least Frequently Used (LFU) policy. LFU keeps track of how many times each cached item has been accessed and removes the item with the lowest access count when space is needed. This works well for many scenarios, but LFU too has its shortcomings. Consider a situation where certain data was accessed many times in the past but hasn't been used recently. With LFU, this item would stay in cache due to its high historical access count, even though it's no longer needed.

This brings us to the Least Recently Used (LRU) policy, which focuses on recency rather than frequency. LRU tracks when each item was last accessed and removes the item that hasn't been accessed for the longest time. This policy works particularly well for workloads where items accessed recently are likely to be accessed again soon. LRU handles both the FIFO problem of evicting frequently used items and the LFU problem of holding onto items that were popular in the past but are no longer useful.