An O(1) algorithm for implementing the LFU cache eviction scheme
📜 Abstract
Cache eviction algorithms are used widely in operating systems, databases and other systems that use caches to speed up execution by caching data that is used by the application. There are many policies such as MRU (Most Recently Used), MFU (Most Frequently Used), LRU (Least Recently Used) and LFU (Least Frequently Used) which each have their advantages and drawbacks and are hence used in specific scenarios. By far, the most widely used algorithm is LRU, both for its O(1) speed of operation as well as its close resemblance to the kind of behaviour that is expected by most applications. The LFU algorithm also has behaviour desirable by many real world workloads. However, in many places, the LRU algorithm is is preferred over the LFU algorithm because of its lower run time complexity of O(1) versus O(log n). We present here an LFU cache eviction algorithm that has a runtime complexity of O(1) for all of its operations, which include insertion, access and deletion(eviction).
✨ Summary
Summary
The paper presents an LFU cache implementation with constant-time insertion, lookup, and eviction. Its design combines a hash table for key-based access with two levels of linked-list organization: an ordered list of frequency buckets and a per-frequency list of items. Each cached item stores a pointer to its current frequency bucket, allowing accesses to move an item to the next frequency in constant time. Eviction selects an item from the first frequency bucket, also in constant time.
The paper’s algorithm has been used as a reference implementation pattern in subsequent software projects. For example, Go implementations explicitly describe themselves as based on the paper, while Python documentation states that its frequency-list implementation follows the paper’s algorithm. A TypeScript implementation likewise identifies the paper as the basis for its O(1) cache operations. (pkg.go.dev)
The work has also been cited in later systems research, including storage and cache-management papers. A USENIX FAST paper lists it as a reference, and a later study of delayed-eviction caching cites it when discussing constant-time LFU candidate selection. (usenix.org)
These references indicate concrete influence as a commonly reused data-structure design for LFU caches, particularly in educational and open-source implementations. The available evidence does not establish broad adoption of this exact algorithm in major commercial caching systems.