LRU and LFU Cache Eviction

LRU and LFU Cache Eviction

Caching is a fundamental technique in computer science used to store copies of frequently accessed data in a fast, intermediate storage layer. Because high-speed storage hardware, such as Static Random Access Memory (SRAM) or Dynamic Random Access Memory (DRAM), is expensive and limited in capacity compared to bulk storage, a cache can only hold a fraction of the total data available in a system.^[28] When a cache reaches its maximum capacity and a new item must be inserted, the system must decide which existing item to remove. The algorithm dictating this decision is known as a cache eviction policy.^[29]

The primary goal of an eviction policy is to maximize the cache hit rate, which is the percentage of requests successfully served from the cache rather than the slower underlying storage. The performance of a memory hierarchy is often measured by its Average Memory Access Time (AMAT), calculated as the cache hit time plus the product of the miss rate and the miss penalty. Because the miss penalty (fetching from a hard drive or a remote network) can be orders of magnitude slower than a cache hit, even a fractional percentage improvement in the hit rate can yield dramatic system-wide performance gains. To achieve this, the policy must predict which data items are least likely to be requested in the future. Because predicting the future with absolute certainty is impossible, eviction algorithms rely on historical access patterns as heuristics.

Least Recently Used (LRU) and Least Frequently Used (LFU) are the two foundational algorithms in cache management.^[30] LRU operates on the principle of temporal locality, assuming that data accessed recently will likely be accessed again soon. It evicts the item that has remained unaccessed for the longest period. LFU operates on the principle of popularity, assuming that data accessed many times in the past will continue to be requested. It evicts the item that has been accessed the fewest times overall.^[28] These two algorithms form the basis for decades of research into memory management and are implemented in nearly every modern computing system.

The Cache Eviction Problem

Modern computing architectures rely on a memory hierarchy characterized by varying speeds and capacities ^[1]. At the top of the hierarchy are CPU registers and L1 caches, which operate at nanosecond latencies but hold only kilobytes of data. At the bottom are magnetic hard drives or solid-state drives, which hold terabytes of data but require milliseconds or microseconds to access. Main memory (RAM) sits between these extremes. Moving data up the hierarchy is computationally expensive. A cache hit occurs when requested data is found in the fast storage layer, while a cache miss requires fetching the data from the slower layer, incurring a significant latency penalty.

The theoretical upper bound for cache performance was defined by Laszlo Belady in 1966 with his optimal replacement algorithm, often referred to as MIN or OPT ^[2]. Belady proved that the optimal strategy is to evict the item that will be needed furthest in the future. If an item will never be needed again, it should be evicted immediately. Because operating systems and databases cannot look ahead into future instruction streams or user queries, Belady's MIN algorithm cannot be implemented in practice. It is used exclusively as an analytical tool to measure the efficiency of practical algorithms.

Without knowledge of the future, practical algorithms must track past behavior to avoid a catastrophic performance degradation known as thrashing. Thrashing occurs when a system's active working set exceeds the capacity of the cache, causing the system to spend more resources swapping data in and out of the cache than executing actual computational work. The challenge lies in balancing the accuracy of these historical heuristics against the computational overhead required to maintain them. An eviction policy that requires complex calculations or locks the entire cache data structure during updates can introduce latency that negates the benefits of caching in the first place. Therefore, the cache eviction problem is not merely about selecting the right item to evict, but doing so with minimal time and space complexity.

Least Recently Used (LRU) Mechanism

The Least Recently Used algorithm evicts the item that has not been accessed for the longest time. To accomplish this, the system must maintain a strict ordering of all items in the cache based on their most recent access time.

The standard implementation of an LRU cache combines two data structures: a hash map (or hash table) and a doubly linked list ^[3]. The hash map stores the cache keys and provides pointers directly to the corresponding nodes in the linked list. This allows the system to locate any item in O(1) time. The doubly linked list maintains the recency order. The head of the list represents the most recently used item, while the tail represents the least recently used item.

When a system requests an item, the cache checks the hash map. If the item exists (a cache hit), the system uses the pointer to locate the node in the doubly linked list, unlinks it from its current position, and moves it to the head of the list. If the item does not exist (a cache miss), the system fetches the data from the slower storage and creates a new node at the head of the linked list. If the cache is already at its maximum capacity, the system identifies the node at the tail of the linked list, removes it from the list, deletes its corresponding entry from the hash map, and then inserts the new node at the head.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache_map = {}
        self.list = DoublyLinkedList()

    def get(self, key):
        if key in self.cache_map:
            node = self.cache_map[key]
            self.list.move_to_head(node)
            return node.value
        return -1

    def put(self, key, value):
        if key in self.cache_map:
            node = self.cache_map[key]
            node.value = value
            self.list.move_to_head(node)
        else:
            if len(self.cache_map) >= self.capacity:
                tail_node = self.list.remove_tail()
                del self.cache_map[tail_node.key]
            new_node = Node(key, value)
            self.list.add_to_head(new_node)
            self.cache_map[key] = new_node

This implementation ensures that both read and write operations execute in O(1) time complexity. The space complexity is O(N), where N is the maximum capacity of the cache, because the system must store a hash map entry and two pointers (previous and next) for every cached item.

Despite its theoretical efficiency, strict LRU introduces a severe concurrency bottleneck in multi-threaded environments. Because every read operation requires updating the doubly linked list to move the accessed node to the head, the operation is effectively a write. In a highly concurrent system, threads must acquire an exclusive write lock on the linked list to prevent pointer corruption. This lock contention forces threads to serialize, destroying read throughput and making strict LRU impractical for modern, multi-core software architectures.

Least Frequently Used (LFU) Mechanism

The Least Frequently Used algorithm evicts the item that has been accessed the fewest times since it was inserted into the cache. This requires the system to maintain a frequency counter for every item. When the cache reaches capacity, the item with the lowest counter is removed. If multiple items share the lowest frequency, the system typically applies a secondary tie-breaker policy, most commonly LRU, to choose among them.

A naive implementation of LFU uses a min-heap (a priority queue) to keep the items sorted by their access frequency. While this allows the system to find the least frequently used item in O(1) time, updating the frequency of an item after a cache hit requires rebalancing the heap, which takes O(log N) time ^[4]. In high-throughput systems, this logarithmic time complexity creates a performance bottleneck.

To achieve O(1) time complexity for LFU, researchers Ketan Shah, Anirban Mitra, and Dhruv Matani published an algorithm in 2010 that utilizes nested data structures ^[5]. This O(1) LFU implementation relies on two hash maps. The first hash map links keys to their specific values and their current frequency count. The second hash map links frequency counts to doubly linked lists of items that share that exact frequency. The system also maintains an integer tracking the current minimum frequency in the cache.

When an item is accessed, its frequency counter is incremented. The system locates the item in the doubly linked list corresponding to its old frequency, removes it, and appends it to the doubly linked list corresponding to its new frequency. If the old frequency list becomes empty and it was the minimum frequency, the minimum frequency integer is incremented. When eviction is necessary, the system looks up the doubly linked list for the minimum frequency and removes the item at the tail of that list.

A fundamental mechanical flaw in pure LFU is cache pollution. Items that receive a massive burst of accesses over a short period accumulate very high frequency counts. Even if those items are never requested again, their high counts prevent them from being evicted, wasting valuable cache space. To mitigate this, practical LFU implementations introduce an aging mechanism. A common aging strategy involves periodically dividing all frequency counters by two, or applying a logarithmic decay function, ensuring that historical popularity degrades over time if not sustained by new accesses. Another approach is a sliding window, where only accesses within a recent timeframe contribute to the frequency count, naturally phasing out obsolete data.

History and Development

The conceptual origins of cache eviction algorithms trace back to the development of virtual memory and paging systems in the early 1960s. The Atlas computer, developed at the University of Manchester and operational by 1962, was the first system to implement paging ^[6]. The Atlas supervisor program had to decide which pages of memory to transfer to magnetic drum storage when core memory was full. It used a learning algorithm to estimate the time a page would next be required, representing the earliest attempt at predicting access patterns for eviction.

The formalization of replacement algorithms occurred in the mid-1960s, driven by the development of the IBM System/360 Model 67 and its TSS/360 operating system . In 1966, Laszlo Belady, a researcher at the IBM Thomas J. Watson Research Center, published "A study of replacement algorithms for a virtual-storage computer" in the IBM Systems Journal ^[2]. This paper was a landmark in computer science. It introduced the MIN algorithm and evaluated several practical policies. Belady's research also uncovered a counterintuitive phenomenon now known as Belady's anomaly. He demonstrated that for certain algorithms, specifically First-In-First-Out (FIFO), increasing the size of the cache could actually cause the hit rate to decrease under specific access patterns ^[7].^[31] For example, a system with three page frames processing a specific sequence of memory requests might experience nine page faults, but expanding the memory to four page frames could cause the same sequence to trigger ten page faults.

In 1968, Peter Denning at the Massachusetts Institute of Technology published "The Working Set Model for Program Behavior" in the Communications of the ACM ^[8]. Denning provided the theoretical justification for LRU by formalizing the concept of temporal locality. He observed that programs do not access memory uniformly; instead, they execute within localized "working sets" of memory pages. Denning defined the working set mathematically using a sliding window of time. Because working sets change slowly over time, the pages accessed in the immediate past are highly predictive of the pages that will be accessed in the immediate future.

In 1970, Richard Mattson, Jan Gecsei, Donald Slutz, and Irving Traiger published "Evaluation techniques for storage hierarchies," which introduced the concept of stack algorithms ^[9]. They proved mathematically that any algorithm satisfying the inclusion property (where the contents of a cache of size N are always a subset of the contents of a cache of size N+1) is immune to Belady's anomaly. Both LRU and LFU were proven to be stack algorithms, cementing their reliability for system designers.

While LRU became the standard for operating system page replacement, LFU was explored primarily in early database research. However, pure LFU was frequently dismissed in the 1970s and 1980s due to the high memory overhead of maintaining integer counters for every page and the severe impact of cache pollution, leading researchers to focus on approximating LRU instead.

Variants and Refinements

Because pure LRU and pure LFU possess specific vulnerabilities, researchers have developed numerous variants to address edge cases, reduce memory overhead, and improve scan resistance. Scan resistance refers to an algorithm's ability to withstand a full table scan (a sequential read of a massive dataset) without evicting the frequently accessed items in the working set.

The Clock Algorithm: Invented by Fernando Corbató for the Multics operating system in the late 1960s, the Clock algorithm approximates LRU with significantly less overhead ^[10]. Instead of a doubly linked list, it uses a circular buffer and a single "reference bit" for each page. When a page is accessed, its bit is set to 1. When eviction is needed, a pointer (the "clock hand") sweeps through the buffer. If it encounters a 1, it resets the bit to 0 and moves to the next page. If it encounters a 0, that page is evicted. This eliminates the need to update pointers on every read operation, drastically reducing lock contention.

LRU-K: Introduced by Elizabeth J. O'Neil, Patrick E. O'Neil, and Gerhard Weikum in 1993, LRU-K was designed to solve the scan resistance problem in database disk buffering ^[11]. Standard LRU evaluates recency based on the last access (K=1). LRU-K evaluates recency based on the time of the K-th most recent access. A sequential scan only accesses items once, meaning their K-th access time remains infinitely far in the past, preventing them from displacing the true working set. LRU-2 is the most widely implemented variant.

2Q: Developed by Theodore Johnson and Dennis Shasha in 1994, the 2Q algorithm achieves the scan resistance of LRU-2 but with O(1) overhead ^[12]. It maintains two separate queues. Newly accessed items are placed in a FIFO queue. If an item in the FIFO queue is accessed a second time, it is promoted to a standard LRU queue. Items that are only accessed once during a scan pass through the FIFO queue and are evicted without ever polluting the main LRU cache.

Adaptive Replacement Cache (ARC): Invented by Nimrod Megiddo and Dharmendra S. Modha at IBM Research in 2003, ARC dynamically balances between recency and frequency ^[13]. ARC maintains two lists: L1 for items accessed once (recency) and L2 for items accessed at least twice (frequency). Each list is divided into a physical cache portion and a "ghost directory" that tracks the keys of recently evicted items.^[30] By monitoring hit rates in the ghost directories, ARC continuously adjusts a parameter that dictates the physical space allocated to L1 versus L2. IBM patented ARC ^[14], which historically limited its use in open-source software.

CLOCK with Adaptive Replacement (CAR): Developed by Sorav Bansal and Dharmendra S. Modha in 2004, CAR combines the adaptive tuning of ARC with the low-overhead mechanics of the Clock algorithm ^[15]. By replacing ARC's strict LRU lists with Clock circular buffers, CAR achieves similar hit rates to ARC but eliminates the need for lock-heavy pointer updates on every read, making it highly suitable for concurrent storage systems.

Low Inter-reference Recency Set (LIRS): Proposed by Song Jiang and Xiaodong Zhang in 2002, LIRS addresses LRU's weaknesses by using the distance between the last two accesses (Inter-Reference Recency) to make eviction decisions ^[16]. It categorizes blocks into high Inter-Reference Recency (HIR) and low Inter-Reference Recency (LIR), dynamically protecting LIR blocks from being evicted by sequential scans.

Window TinyLFU (W-TinyLFU): Created by Gil Einziger, Roy Friedman, and Ben Manes in 2015, W-TinyLFU provides a highly memory-efficient frequency-based cache ^[17].^[32] It uses a Count-Min Sketch ^[18] (a probabilistic data structure) to approximate frequency counts using very few bits per item.^[33] To handle bursts of new items that have not yet built up frequency, W-TinyLFU places new arrivals into a small LRU "window" cache. Items evicted from the window cache are only admitted to the main TinyLFU cache if their estimated frequency is higher than the item they would displace.

Learning Cache Replacement (LeCaR): Introduced by Giuseppe Vietri and colleagues in 2018, LeCaR applies machine learning to the eviction problem ^[19]. It uses a regret minimization algorithm to dynamically shift weights between a pure LRU policy and a pure LFU policy based on real-time workload analysis. By treating eviction as a multi-armed bandit problem, LeCaR adapts to changing access patterns without requiring manual tuning or complex ghost directories.

Real-World Applications

The theoretical principles of LRU and LFU are applied across the entire computing stack, though pure implementations are rare due to performance constraints. Systems typically employ modified versions tailored to their specific architectural needs.

Operating Systems: The Linux kernel relies heavily on a modified LRU algorithm for page replacement to manage physical memory ^[20]. Linux maintains two separate lists for memory pages: an active list and an inactive list. Pages are initially placed on the inactive list. If they are accessed again, they are promoted to the active list. The kernel periodically scans the active list and demotes pages that have not been accessed recently back to the inactive list. Evictions only occur from the tail of the inactive list. This dual-list approach approximates LRU while minimizing the lock contention that would occur if a single list were updated on every memory reference.

Relational Databases: Database management systems require strict control over memory to ensure query performance. PostgreSQL manages its shared buffer cache using a variation of the Clock sweep algorithm rather than strict LRU ^[21]. This avoids the overhead of manipulating linked list pointers during high-concurrency read operations. MySQL's InnoDB storage engine utilizes a modified LRU list for its buffer pool ^[22]. To prevent full table scans from wiping out the working set, InnoDB inserts newly read pages at a midpoint in the list (typically 3/8ths of the way from the tail) rather than at the head. A page is only moved to the head of the list if it is accessed a second time after a specific delay.

In-Memory Data Stores: Redis, a widely used in-memory data structure store, supports multiple eviction policies, including allkeys-lru and allkeys-lfu ^[23]. Because Redis is designed to handle millions of keys, maintaining strict LRU or LFU data structures would consume too much memory. Instead, Redis uses a randomized approximation. It samples a small number of keys (defaulting to 5) and evicts the best candidate among the sample based on the chosen policy. For its LFU implementation, Redis uses a highly optimized 24-bit field per object, allocating 16 bits for the last decrement time and 8 bits for a logarithmic frequency counter, which naturally handles aging and prevents cache pollution. Memcached, another popular caching system, transitioned from a strict LRU to a segmented LRU approach to better handle varied access patterns and reduce lock contention ^[24].

Web Caching and Content Delivery Networks (CDNs): Eviction in web caching introduces additional complexity because cached objects (images, videos, HTML files) vary wildly in size and retrieval cost ^[25]. A CDN cannot simply evict the least recently used item if that item is a massive video file that costs significant bandwidth to re-fetch. Consequently, web caches often employ size-aware variants of LRU and LFU, such as GreedyDual-Size, which factor in the byte size and download latency of an object alongside its recency and frequency.^[32]

Application-Level Caching: Software libraries used by developers to cache data within application memory also rely on these algorithms. Caffeine, a high-performance caching library for Java, implements the W-TinyLFU algorithm ^[26]. This allows Caffeine to achieve near-optimal hit rates by combining the burst-handling capabilities of an LRU window with the long-term historical accuracy of LFU, all while maintaining a minimal memory footprint.

Hardware Caches: At the hardware level, CPU caches (L1, L2, L3) operate at speeds where updating a doubly linked list is impossible. For caches with high associativity, hardware designers implement Pseudo-LRU (PLRU) ^[27].^[34] Tree-PLRU uses a binary tree of single bits to track the access history of cache lines, requiring only N-1 bits to approximate the LRU item among N cache lines. This provides a sufficiently accurate eviction decision using simple, fast hardware logic.

Significance and Tradeoffs

The choice between LRU and LFU, or their variants, involves fundamental tradeoffs regarding workload characteristics, computational overhead, and memory consumption. No single eviction policy is optimal for all scenarios.

The primary tradeoff centers on the nature of the data access pattern. LRU excels in environments with strong temporal locality, where the data accessed most recently is highly likely to be needed again. It adapts rapidly to phase changes in a workload. If an application stops querying one dataset and begins querying another, LRU quickly flushes the old data. However, LRU is highly susceptible to sequential scans. A backup process or a large analytical query that reads a massive number of records once will push all the frequently accessed data out of an LRU cache, severely degrading system performance.

LFU is designed to identify and protect the core working set over the long term. It excels in environments where certain items are consistently popular, such as a content delivery network serving viral images or a database storing static configuration tables. LFU is inherently scan-resistant because items read only once during a scan will have a frequency of 1 and will be evicted before items with established high frequencies. The tradeoff is that LFU adapts very slowly to phase changes. If a previously popular item falls out of favor, its high frequency count ensures it will occupy cache space for an extended period until an aging mechanism eventually reduces its count.

Computational overhead is a critical factor in highly concurrent systems. Strict LRU requires a write operation (updating pointers) even when a read occurs. In a multi-threaded environment, this necessitates acquiring a write lock on the cache data structure, transforming a fast read operation into a serialization bottleneck. This is why high-performance databases and operating systems rely on Clock algorithms, segmented lists, or probabilistic sampling. These approximations sacrifice a small degree of eviction accuracy to eliminate lock contention and maintain high throughput.

Memory overhead also dictates implementation choices. Strict LRU requires two pointers per cached item. On a 64-bit system, this adds 16 bytes of overhead per item. If the cache stores millions of very small objects, the pointer overhead can consume a substantial percentage of the total allocated memory. LFU requires integer counters, which also add overhead. Modern hybrid algorithms like W-TinyLFU address this by using probabilistic data structures like the Count-Min Sketch, reducing the tracking overhead to a fraction of a byte per item while maintaining the scan resistance of LFU and the adaptability of LRU.

As storage technologies evolve, the parameters governing cache eviction continue to shift. The introduction of Non-Volatile Memory Express (NVMe) solid-state drives and persistent memory modules has narrowed the latency gap between main memory and secondary storage. While this reduces the absolute penalty of a cache miss, the massive scale of modern cloud workloads ensures that intelligent cache eviction remains a critical discipline in system design, driving ongoing research into machine learning and adaptive heuristics.