The LRU-K page replacement algorithm for database disk buffering
Elizabeth J. O'Neil, Patrick Eugene O'Neil, Gerhard Weikum · ACM SIGMOD Record · 1993
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.
Cited by 369 works. doi:10.1145/170036.170081
Authors
References
- The working set model for program behavior
- The Art of Computer Programming, Volume 3, Sorting and Searching
- Operating system support for database management
- Principles of Optimal Page Replacement
- Data caching issues in an information retrieval system
- Principles of database buffer management
- Starburst mid-flight: as the dust clears (database project)
- The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time
- Buffer management in relational database systems
- Flexible buffer allocation based on marginal gains