ACM SIGMOD Record · 1993 · 358 citations · 14 references
ComputingComputer ScienceComputer SystemsDatabasesOperating SystemsStorage SystemsBuffer ManagementCachingData Storage SystemsMemory HierarchyPerformance TuningStorage ManagementAdaptive BufferingBuffer Pool ManagementBufferingInterarrival Time DistributionsInterarrival TimesPage ReplacementPage Replacement AlgorithmsWorkload
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.
14
The Art of Computer Programming, Volume 3, Sorting and Searching
Matthew Wilkes · The Computer Journal · 1974 · 716 citations · Full text
The working set model for program behavior
Peter J. Denning · Communications of the ACM · 1968 · 652 citations · Full text
Operating system support for database management
Michael Stonebraker · Communications of the ACM · 1981 · 384 citations · Full text