The LRU-K page replacement algorithm for database disk buffering
- 1 June 1993
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 22 (2), 297-306
- https://doi.org/10.1145/170036.170081
Abstract
This paper introduces a new approach to database disk buffering, called the LRU-K method. The basic idea of LRU-K is to keep track of the times of the last K references to popular database pages, using this information to statistically estimate the interarrival times of references on a page by page basis. Although the LRU-K approach performs optimal statistical inference under relatively standard assumptions, it is fairly simple and incurs little bookkeeping overhead. As we demonstrate with simulation experiments, the LRU-K algorithm surpasses conventional buffering algorithms in discriminating between frequently and infrequently referenced pages. In fact, LRU-K can approach the behavior of buffering algorithms in which page sets with known access frequencies are manually assigned to different buffer pools of specifically tuned sizes. Unlike such customized buffering algorithms however, the LRU-K method is self-tuning, and does not rely on external hints about workload characteristics. Furthermore, the LRU-K algorithm adapts in real time to changing patterns of access.Keywords
This publication has 12 references indexed in Scilit:
- Flexible buffer allocation based on marginal gainsPublished by Association for Computing Machinery (ACM) ,1991
- Data caching issues in an information retrieval systemACM Transactions on Database Systems, 1990
- An approximate analysis of the LRU and FIFO buffer replacement schemesACM SIGMETRICS Performance Evaluation Review, 1990
- Data cache management using frequency-based replacementACM SIGMETRICS Performance Evaluation Review, 1990
- Starburst mid-flight: as the dust clears (database project)IEEE Transactions on Knowledge and Data Engineering, 1990
- Buffer management in relational database systemsACM Transactions on Database Systems, 1986
- Principles of database buffer managementACM Transactions on Database Systems, 1984
- Operating system support for database managementCommunications of the ACM, 1981
- Principles of Optimal Page ReplacementJournal of the ACM, 1971
- The working set model for program behaviorCommunications of the ACM, 1968