2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm
📜 Abstract
In a path-breaking paper last year Pat and Betty O'Neil and Gerhard Weikum proposed a self-tuning improvement to the Least Recently Used (LRU) buffer management algorithm[15]. Their improvement is called LRU/k and advocates giving priority to buffer pages based on the kth most recent access. (The standard LRU algorithm is denoted LRU/1 according to this terminology.) If P1's kth most recent access is more recent than P2's, then P1 will be replaced after P2. Intuitively, LRU/k for k > 1 is a good strategy, because it gives low priority to pages that have been scanned or to pages that belong to a big randomly accessed file (e.g., the account file in TPC/A). They found that LRU/2 achieves most of the advantage of their method. The one problem of LRU/2 is the processor overhead to implement it. In contrast to LRU, each page access requires log N work to manipulate a priority queue where N is the number of pages in the buffer. Question: is there a low overhead way (constant overhead per access as in LRU) to achieve similar page replacement performance to LRU/2? Answer: Yes. Our "Two Queue" algorithm (hereafter 2Q) has constant time overhead, performs as well as LRU/2, and requires no tuning. These results hold for real (DB2 commercial, Swiss bank) traces as well as simulated ones. Based on these experiments, we estimate that 2Q will provide a few percent improvement over LRU without increasing the overhead by more than a constant additive factor.
✨ Summary
Summary
The paper introduces 2Q, a buffer-replacement algorithm intended to obtain the performance benefits of LRU/2 without its priority-queue overhead. It separates recently accessed pages from pages that have demonstrated sustained reuse: A1in is a FIFO queue for newly referenced pages, Am is an LRU queue for pages admitted after evidence of reuse, and A1out is a metadata-only history queue for recently evicted pages. The resulting operations use constant-time list manipulation. Experiments with Zipfian workloads, scans, index/data access patterns, and traces from DB2, a windowing application, and an OLTP system report higher hit rates than LRU and performance generally comparable to LRU/2. The authors recommend allocating approximately 25% of the buffer to A1in and retaining identifiers for roughly 50% of the buffer size in A1out.
Influence
Subsequent research treated 2Q as a reference cache policy and reused its central ideas. A 2002 USENIX study incorporated 2Q into a fingerprinting tool for identifying operating-system buffer-cache policies and explicitly described its FIFO short-term queue, LRU main queue, and historical metadata queue. (usenix.org) The Multi-Queue algorithm adopted a history buffer similar to 2Q’s A1out while extending the design to multiple frequency-sensitive LRU queues for second-level caches. (usenix.org) Later work on energy-efficient buffer caches used 2Q as a baseline and developed variants including chip 2Q, inode 2Q, and hotCold 2Q. (web.eece.maine.edu) A separate study proposed 2Q* for mail-service storage workloads, directly extending the algorithm for that application domain. (tandfonline.com) Bibliographic records also list later research applying or comparing against 2Q in self-tuning memory management, query evaluation, distributed databases, multimedia databases, and broadcast-disk systems. (sigmod.org) These sources establish continued research influence and adaptation; they do not, by themselves, establish broad production deployment of the original algorithm.