The LRU-K page replacement algorithm for database disk buffering

TLDR

This paper introduces a new database disk buffering approach called the LRU‑K method. LRU‑K tracks the last K references to each page to estimate interarrival times and uses that statistical estimate to guide replacement decisions. Simulation experiments show that LRU‑K, while simple and low‑overhead, outperforms conventional buffering algorithms, closely mimics manually tuned schemes, and self‑tunes in real time without external workload hints.

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.