Cache replacement policies

Cache replacement policies are essential algorithms used to manage a computer's cache memory. A cache is a small, high-speed storage area that keeps recent or frequently used data. Accessing a cache is much faster and computationally cheaper than accessing main memory. However, because a cache has limited space, it eventually becomes full. When new data must be stored, the system must use a replacement policy to decide which existing item to discard.

To understand how well a cache works, engineers look at two main figures of merit: latency and hit ratio. The hit ratio describes how often the system finds the requested item in the cache. A higher hit ratio means the cache is working effectively. Latency is the time it takes for the cache to return an item after it is requested. There is a constant trade-off between these two factors. More efficient strategies track more usage information to improve the hit ratio. However, tracking this extra information can increase latency, making the system slower.

Computer scientists have developed several different types of policies to handle these decisions. One theoretical ideal is Bélády's algorithm, also called the optimal replacement policy or the clairvoyant algorithm. This policy would always discard the item that will not be needed for the longest time in the future. Because a computer cannot actually predict the future, this algorithm is unfeasible for real-world use. Instead, it serves as a benchmark. Engineers use it to calculate the practical minimum for error and compare it to real algorithms.

Simple queue-based policies are another common category. First In, First Out (FIFO) treats the cache like a queue. It evicts blocks in the exact order they were added, regardless of how often they are used. Conversely, Last In, First Out (LIFO) behaves like a stack. In LIFO, the most recently added block is the first one to be evicted. Some systems use Random Replacement (RR), which simply selects an item to discard by chance. This method requires no access history and is used in ARM processors due to its simplicity.

Recency-based policies are more complex but often more effective. The Least Recently Used (LRU) algorithm discards items that have not been accessed for the longest time. This requires tracking "age bits" for cache lines to monitor usage. Because full LRU can be expensive to implement in hardware, many designers use Pseudo-LRU (PLRU). PLRU uses a binary tree of one-bit pointers to approximate the LRU decision. This reduces hardware costs and power usage while maintaining a similar hit ratio.

Other specialized policies address specific data patterns. Most Recently Used (MRU) discards the item that was used most recently. While this sounds counterintuitive, researchers like Chou and DeWitt noted in 1985 that MRU is best for repeated scans of large datasets. In these cyclic patterns, MRU often achieves more hits than LRU. Another variant is Segmented LRU (SLRU), which divides the cache into probationary and protected segments. This helps ensure that only data accessed at least twice reaches the protected area.

Modern networking and web caching also require unique approaches. The SIEVE algorithm was designed for web caches like Content Delivery Networks. It uses a single FIFO queue with a moving hand to select objects for eviction. It employs "lazy promotion" to avoid updating the data structure during every cache hit. For network applications, Time-Aware, Least Recently Used (TLRU) is used. TLRU uses a timestamp called Time to Use (TTU) to regulate content based on its lifetime. This ensures that short-lived or unpopular content is replaced quickly to make room for new data.