Evolution of Buffer Management in Database Systems: From Classical Algorithms to Machine Learning and Disaggregated Memory
Prudhvi Gadupudi, Suman Saha · 2025
Read Evolution of Buffer Management in Database Systems: From Classical Algorithms to Machine Learning and Disaggregated Memory by Prudhvi Gadupudi, Suman Saha (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-22995.txt.
Introduction
Prudhvi Gadupudi and Suman Saha survey forty years of buffer management, the database component that decides which data pages stay in fast memory. That cache is the main bridge across the latency gap between processors and storage, so its replacement policy shapes overall system speed. The survey follows the field from classical algorithms to learning-based and memory-disaggregated designs.
Early landmarks such as LRU-K, 2Q, LIRS, and ARC are traced into modern machine-learning-augmented policies and architectures that pool memory across machines. The authors also examine how operating systems and databases diverged architecturally. They review buffering in production systems including PostgreSQL, Oracle, and Linux. Newer trends covered include eBPF-based kernel extensibility, nonvolatile-memory tiering, and RDMA-enabled disaggregation. Drawing on more than fifty papers, they map recurring design patterns and trade-offs, then propose adaptive cross-layer management that joins learning with kernel extensibility.
Catalog record
| CREATOR | Prudhvi Gadupudi, Suman Saha |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-22995
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Evolution of Buffer Management in Database Systems: From Classical Algorithms to Machine Learning and Disaggregated Memory Prudhvi Gadupudi, Suman Saha Abstract Buffer management remains a critical component of database and operating system performance, serving as the primary mechanism for bridging the persistent latency gap between CPU processing speeds and storage access times. This paper provides a comprehensive survey of buffer management evolution spanning four decades of research. We systematically analyze the progression from foundational algorithms like LRU-K, 2Q, LIRS, and ARC to contemporary machine learning-augmented policies and disaggregated memory architectures. Our survey examines the historical OS-DBMS architectural divergence, production system implementations in PostgreSQL, Oracle, and Linux, and emerging trends including eBPF-based kernel extensibility, NVM-aware tiering strategies, and RDMA-enabled memory disaggregation. Through analysis of over 50 seminal papers from leading conferences (SIGMOD, VLDB, OSDI, FAST), we identify key architectural patterns, performance trade-offs, and open research challenges. We conclude by outlining a research direction that integrates machine learning with kernel extensibility mechanisms to enable adaptive, cross-layer buffer management for heterogeneous memory hierarchies in modern database systems. I Introduction The memory hierarchy has been a fundamental aspect of computer system design for over half a century. The persistent disparity between CPU processing speeds and storage access latencies necessitates intelligent buffer management: maintaining a carefully selected subset of data in fast, volatile memory to service repeated accesses efficiently. In both Database Management Systems (DBMS) and Operating Systems (OS), buffer management transcends simple caching—it is the primary determinant of overall system throughput and response latency. The landscape of buffer management has undergone significant transformation. Early systems relied on simple heuristics like LRU (Least Recently Used), which assumed uniform access costs and homogeneous storage media [ 1 ] . Contemporary systems must navigate a complex multi-tiered memory hierarchy encompassing processor caches, DRAM, CXL-attached memory, persistent memory (NVM), and various storage technologies (NVMe SSD, HDD), each with distinct latency, bandwidth, and cost characteristics [ 19 , 30 ] . This paper presents a comprehensive survey of buffer management research, organized chronologically and thematically. Our survey makes the following contributions: 1. Historical Analysis: We trace the evolution from Stonebraker’s 1981 critique of OS support for databases through the development of sophisticated replacement algorithms (LRU-K, LIRS, ARC) to modern learned policies. 2. Systematic Taxonomy: We classify buffer management approaches across multiple dimensions: algorithmic complexity, scan resistance, self-tuning capability, hardware awareness, and deployment context (Tables I-III). 3. Implementation Study: We examine how production systems (PostgreSQL, Oracle, MySQL, Linux) implement buffer management, analyzing their concurrency mechanisms, scalability characteristics, and practical trade-offs. 4. Emerging Trends: We survey recent advances in machine learning-based policies, eBPF kernel extensibility, NVM-aware algorithms, and disaggregated memory architectures from 2020-2025 literature. 5. Research Directions: We identify open challenges and outline promising directions for future work, including cross-layer optimization through eBPF and ML-based adaptation. The remainder of this paper is organized as follows: Section II examines foundational work establishing the OS-DBMS architectural divide and economic models. Section III surveys classical replacement algorithms. Section IV analyzes production system implementations. Section V reviews cost-aware policies for modern storage media. Section VI examines machine learning approaches. Section VII explores eBPF-based kernel extensibility. Section VIII discusses disaggregated memory systems. Section IX presents research directions, and Section X concludes. II Historical Foundation and Economic Models II-A The OS-DBMS Architectural Divergence The architecture of modern database buffer management was profoundly influenced by Stonebraker’s 1981 paper ”Operating System Support for Database Management” [ 1 ] . Stonebraker argued that general-purpose operating systems make fundamentally suboptimal decisions for database workloads. The OS manages memory with ”blind” global policies, typically LRU variants, designed for fairness across diverse processes without application-specific semantic knowledge. In contrast, a DBMS possesses rich semantic information about its access patterns. Consider a sequential scan of a multi-gigabyte table: the DBMS understands that each page will be accessed exactly once and never revisited, yet a naive OS policy would cache these pages, potentially evicting highly valuable B-tree index nodes in a phenomenon known as cache pollution. This fundamental mismatch led to the ”double buffering” problem—data residing redundantly in both the OS page cache and the DBMS user-space buffer pool, wasting memory and introducing synchronization overhead. This insight drove modern database systems (PostgreSQL, Oracle, MySQL) to bypass OS caching mechanisms using flags like O_DIRECT on Linux or FILE_FLAG_NO_BUFFERING on Windows. By managing their own memory pools, databases can implement sophisticated, workload-aware eviction policies, but at the cost of reimplementing memory management logic and losing potential OS-level optimizations [ 11 ] . II-B Economic Foundations: The Five-Minute Rule While Stonebraker established the architectural principles, Gray and Putzolu provided the economic framework. Their 1987 ”Five-Minute Rule” offered a quantitative method for buffer sizing decisions [ 2 ] . The rule states that for a page of size P accessed with frequency f , it should be kept in memory if: f>\frac{C_{memory}}{C_{disk\_access}} (1) where C_{memory} is the cost of storing one page in RAM and C_{disk\_access} is the cost of one disk I/O operation. For the technology of 1987, this threshold occurred at approximately one access every five minutes for a 1KB page. The rule has proven remarkably durable. Gray and Graefe revisited it in 1997, finding the five-minute threshold still held despite a decade of hardware evolution [ 3 ] . Graefe updated the rule in 2008 for Flash memory, establishing a two-tier hierarchy: pages accessed every 5 minutes should stay in DRAM, while those accessed every 2 hours could reside on Flash rather than HDD [ 4 ] . In today’s landscape with tiered memory (DRAM at $5/GB, CXL at $2/GB, NVMe at $0.10/GB), the Five-Minute Rule’s underlying principle remains relevant, though the economics have shifted toward bandwidth costs and latency-sensitive workloads rather than mechanical seek times [ 30 ] . TABLE I: Comparative Analysis of Classical Buffer Replacement Algorithms Algorithm Core Metric Complexity Scan Resistant Self-Tuning Key Innovation Primary Use LRU Recency O(1) No No Simple stack discipline Legacy systems LFU Frequency O(log N) Yes No Access count tracking Static workloads LRU-K [ 5 ] K-distance O(log N) Yes No Correlated reference period Commercial DBMS 2Q [ 6 ] Queue membership O(1) Yes No Probationary queue PostgreSQL (influenced) LIRS [ 7 ] Inter-reference recency O(1) Yes No IRR vs. recency distinction MySQL 8.0 ARC [ 8 ] Adaptive recency/frequency O(1) Yes Yes Ghost cache adaptation ZFS, storage arrays CLOCK-Pro [ 9 ] LIRS approximation O(1) Yes No Hardware-friendly CLOCK Linux kernel (influenced) CAR [ 10 ] ARC variant O(1) Yes Yes Patent-free ARC alternative Open-source systems III Classical Replacement Algorithms This section surveys the ”golden age” of buffer replacement algorithms (1990-2005), which produced the foundational policies still powering most production systems today. III-A LRU-K: Temporal Pattern Recognition O’Neil et al.’s 1993 LRU-K algorithm marked a significant advancement beyond simple LRU [ 5 ] . Rather than using only the most recent access timestamp ( K=1 ), LRU-K tracks the last K access times for each page. The eviction criterion is the ”backward K-distance”—the time elapsed since the K^{th} most recent access. The key insight is the concept of ”Correlated Reference Period”: multiple accesses occurring within a short temporal window should be treated as a single utilization event. For K=2 (LRU-2), pages accessed only once (e.g., during