The I/O Bottleneck and the Quest for Perfect Caching: A Deep Dive into Buffer Pools, Replacement Policies, and Prefetching

Introduction: The I/O Bottleneck and the Quest for Perfect Caching

Every computer scientist knows the fundamental law of storage: latency is the enemy. While CPU clock speeds and memory bandwidth have advanced at a breathtaking pace over the past few decades, the mechanical seek times of hard drives and even the solid-state access latencies of SSDs remain stubbornly slow relative to the core processing units they serve. The gap between processor speed and I/O latency—often measured in microseconds for SSDs and milliseconds for HDDs—has become the single greatest performance bottleneck in virtually every data-d31dd264 system, from relational databases to NoSQL stores, from file systems to key-value caches, from stream processing engines to scientific computing clusters.

Consider the arithmetic: a modern CPU can execute billions of instructions per second, but a single random read from a spinning hard disk takes about 10 milliseconds. In that time, the CPU could have executed tens of millions of instructions. Even a fast NVMe SSD, with latencies around 10–20 microseconds, still leaves a gap of tens of thousands of processor cycles. The only way to bridge this chasm is to keep the most frequently or recently accessed data in main memory—but main memory is finite and expensive. This fundamental tension between capacity and speed defines the art and science of caching.

At the heart of any system that manages large volumes of persistent data lies a simple but critical abstraction: the buffer pool. A buffer pool is a fixed-size region of main memory that acts as a cache for disk-resident pages, blocks, or objects. When a read request arrives, the system first checks if the required page is already in the buffer pool. If it is (a cache hit), the data is served instantly from memory. If not (a cache miss), the page must be fetched from the slower storage layer, incurring the full I/O latency. The performance of the entire system—throughput, response time, and overall resource utilization—hinges on the ability of the buffer pool’s replacement policy to maximize the hit rate while minimizing the overhead of managing the cache.

But a buffer pool is not merely a passive cache. It can be augmented with prefetching—a speculative mechanism that anticipates future accesses and brings pages into memory before they are actually requested. Prefetching, when done correctly, can dramatically reduce miss penalties and smooth out I/O bursts. When done incorrectly, it can pollute the cache with useless data, evict useful pages, and degrade performance. The synergy between replacement and prefetching is delicate; they must be designed together, not in isolation.

This blog post is an exhaustive exploration of that synergy. We will begin by formalizing the buffer pool abstraction and its role in modern systems. Then we will dissect the classic replacement policies—LRU, LFU, Clock, ARC—with rigorous analysis of their strengths and weaknesses under different workloads. Next, we will dive into prefetching: sequential, stride-based, pattern-based, and learned approaches. We will examine how replacement and prefetching interact, and how advanced systems like IBM’s ARC and Intel’s IAA have attempted to harmonize them. Finally, we will look ahead to emerging trends: machine-learning-driven caching, tiered storage, and persistent memory. By the end, you will have a deep understanding of why caching remains one of the most active and challenging areas of systems research—and how you can apply these principles to your own projects.

The Buffer Pool Abstraction

What Is a Buffer Pool?

A buffer pool is a software-managed cache that sits between the application (or the operating system’s virtual memory manager) and persistent storage. In a database management system (DBMS), for example, the buffer pool is the mechanism by which disk pages are brought into memory for reading or writing. The pool consists of a fixed number of frames, each capable of holding a single page (typically 4KB, 8KB, or 16KB). Pages are identified by a page ID, often consisting of a file ID and an offset within that file.

When a transaction requests a page, the buffer manager looks up the page ID in a hash table or a page table. If the page is in the pool, the manager returns a pointer to the frame. If not, the manager selects a frame to evict (using the replacement policy), writes the page back to disk if it is dirty, reads the requested page from disk into that frame, and then returns the frame. This operation is atomic from the perspective of the requesting transaction, though concurrency control mechanisms (latches, mutexes) are needed to protect the data structures.

Why Not Just Use the OS Page Cache?

Many operating systems provide a generic page cache (e.g., the Linux page cache) that caches file blocks in memory. So why do most databases and specialized storage engines implement their own buffer pool? The reasons are multifaceted:

1. Control over eviction policy: The OS uses its own heuristics (typically a variant of LRU or a two-list algorithm) that may not match the access patterns of a database workload. For example, a B-tree index scan produces a sequential scan pattern that the OS might misinterpret as random if the file is large.
2. Dirty page management: Databases must ensure write-ahead logging (WAL) and crash recovery. They need precise control over when dirty pages are flushed to disk, and in what order. The OS page cache is unaware of transaction semantics.
3. Prefetching coordination: Databases can issue explicit prefetch requests (e.g., read-ahead of index pages) that the OS cannot predict.
4. Memory allocation: A DBMS may want to reserve a portion of memory for its own buffer pool and keep the rest for sorting, hash tables, etc. The OS page cache competes for memory with other processes.
5. Page-level metadata: The buffer pool often stores additional per-page information—dirty flag, pin count, last access time, reference count—that the OS does not maintain.

Thus, while the OS page cache is a good general-purpose solution, high-performance storage systems almost always manage their own buffer pool.

The Fixed-Size Pool and Its Implications

Buffer pools are typically fixed in size at startup. This is by design: pre-allocating a large chunk of pinned memory avoids the overhead of dynamic memory allocation and ensures that the pool does not compete with other system processes in unpredictable ways. The downside is that the pool size must be chosen carefully. Too small, and the cache miss rate will be high, causing excessive I/O. Too large, and memory is wasted (and might cause swapping, which is even worse). Modern systems often allow dynamic resizing (e.g., MySQL’s innodb_buffer_pool_size can be changed online) but with careful constraints.

Within the pool, frames are organized as a set of slots. Each slot has a page ID, a pointer to the actual memory region, a dirty flag, a pin count (number of concurrent users), and metadata for the replacement policy. The pin count is crucial: a page that is being written or read must not be evicted until its pin count drops to zero. This introduces a complication for replacement policies: they can only consider unpinned pages for eviction.

Replacement Policies: The Heart of the Buffer Pool

The replacement policy decides which page to evict when a new page must be read into the pool. The goal is to minimize the number of future cache misses. This is an online decision problem: we have no knowledge of future access patterns, only past observations. The theoretically optimal policy, known as Belady’s algorithm (MIN), evicts the page that will be used furthest in the future. But this requires knowledge of the entire reference string, which is impossible in practice. Real-world policies are heuristics that attempt to approximate MIN.

LRU: The Gold Standard and Its Pitfalls

The Least Recently Used (LRU) policy evicts the page that has not been accessed for the longest time. It assumes that pages that have been used recently will be used again soon (temporal locality). LRU is simple to implement: maintain a doubly linked list of pages in order of access. On each hit, move the page to the head of the list. On a miss, evict the page at the tail. This yields O(1) hit and eviction operations.

LRU works well for workloads with strong temporal locality, such as OLTP systems where a single record is repeatedly updated or queried. However, LRU has well-known failure modes:

• Sequential scans: A large scan of a table will bring a stream of new pages into the buffer pool, each evicting the most recently used pages. This pollutes the cache with pages that will never be accessed again (since the scan moves forward) and evicts pages from other queries that have high reuse. This is called “cache pollution” or “scan thrashing.” Databases often have special handling for scans (e.g., MySQL’s InnoDB uses a “young” and “old” list, akin to the Clock algorithm).
• LRU thrashing under low locality: If the working set is slightly larger than the buffer pool, pages are constantly evicted and re-fetched, leading to near-zero hit rate. LRU cannot distinguish between a page that is part of a large, frequently accessed set and a page that was accessed once.
• Poor handling of loops: Consider a loop over a set of pages that fits entirely in the pool but the loop’s size is just below the pool capacity. LRU will evict the first page of the loop when the second pass begins, causing a miss on every iteration. A more effective policy would keep all pages in the loop resident if the loop fits.

LFU: Frequency Counts, But At a Cost

The Least Frequently Used (LFU) policy evicts the page with the smallest access frequency count. It is based on the assumption that pages accessed many times in the past will be accessed many times in the future. Pure LFU suffers from two problems:

1. Cold start: A new page with a low frequency count will be evicted quickly even if it is about to become popular.
2. Frequency inflation: A page that was very popular in the past but is no longer accessed will retain a high frequency count and never be evicted, causing cache “cache pollution.”

To address these issues, many systems use a sliding window or decaying frequency variant. For example, the LFU-Aging algorithm periodically divides all frequency counters by 2 (or decrements them). Another variant is Window-LFU (used in the HTTP proxy cache Squid), which only counts accesses within the last N requests.

Clock (Second Chance): The Practical Compromise

The Clock algorithm (also known as the Second Chance algorithm) is a simple approximation of LRU that avoids the overhead of a linked list. It organizes frames in a circular buffer and maintains a reference bit per frame. The clock hand sweeps around the buffer; if the reference bit is 1, it clears it and moves on (giving the page a second chance). If the bit is 0, that page is evicted. On a hit, the reference bit is set to 1.

Clock is the basis for the Linux page cache replacement algorithm (improved versions like CLOCK-Pro and CLOCK-E). It performs nearly as well as LRU in practice but with less overhead and better cache locality for the replacement data structures.

ARC: Adaptive Replacement Cache

Adaptive Replacement Cache (ARC), introduced by Megiddo and Modha at IBM Research in 2003, is a landmark algorithm that dynamically balances between recency and frequency. ARC maintains two lists: one for recently accessed pages (LRU list) and one for frequently accessed pages (LFU list). The sizes of these lists are dynamically adjusted based on the workload. Specifically, ARC uses “ghost entries” (metadata for pages that have been evicted) to learn whether the workload favors recency or frequency.

ARC’s design is elegant: it tracks two “target” sizes for its LRU and LFU lists, and adapts them online by observing whether a miss would have been a hit had a different list been larger. This allows ARC to handle scans gracefully (by shrinking the LFU list) while still capturing hot pages in the LFU list.

ARC is used in the ZFS file system and in many high-end storage arrays. It has been shown to outperform LRU and LFU on a wide variety of workloads. However, ARC is not without its complexities: implementation requires careful handling of ghost lists and adaptive tuning of the target sizes.

Other Notable Policies

• LIRS (Low Inter-reference Recency Set): Developed to overcome the weakness of LRU for loops. LIRS classifies pages as “hot” (accessed repeatedly) or “cold” based on the distance between consecutive accesses. It keeps hot pages in a separate list and uses an LIR (Low Inter-reference Recency) stack to evict only cold pages. LIRS is used in the LSM tree based database RocksDB for its block cache.
• 2Q (Two Queue algorithm): Maintains two FIFO queues—a small “A1” queue for first-time accessed pages, and a large “A2” queue for pages accessed at least twice. Pages in A1 are moved to A2 on a second access. Eviction is from A1 first, then from A2. This prevents scans from polluting the main cache.
• LRU-K (e.g., LRU-2): Maintains the time of the K most recent accesses. Evicts the page with the largest K-th access time. This generalizes LRU (which is LRU-1) and gives better resistance to scans. However, the overhead of tracking multiple timestamps can be high.
• CAR (Clock with Adaptive Replacement): Combines the ideas of ARC and Clock, providing low overhead and adaptivity. Used in some academic prototypes.

Theoretical Performance Bounds

The effectiveness of a replacement policy can be measured by its competitive ratio: the ratio of the number of misses incurred by the online policy to the number of misses incurred by the optimal offline algorithm (Belady) in the worst case. It is known that any deterministic online algorithm for caching has a competitive ratio of at least (k/k+1) where k is the cache size. LRU and FIFO achieve a competitive ratio of k, meaning they can be k times worse than optimal in the worst case. However, randomized algorithms (e.g., the random eviction policy) have better competitive ratios in expectation. ARC and LIRS do not have known competitive bounds but are empirically close to optimal on many workloads.

Prefetching: Looking Ahead

Replacement policies react to misses; prefetching proactively anticipates them. The core idea is simple: if we can predict which pages will be accessed soon, we can fetch them into the buffer pool before they are requested, overlapping the I/O latency with computation. Prefetching is especially effective in two scenarios: sequential scans (e.g., full table scans) and pointer-chasing (e.g., index traversals where the next child page can be predicted from the current leaf page).

Sequential Prefetching

The simplest form is sequential prefetching (also called read-ahead). When a page is accessed, the system speculatively reads the next N pages into the buffer pool. N is the prefetch depth, often tuned dynamically. For example, the Linux page cache uses a read-ahead mechanism that doubles the window size on each successful sequential access, up to a maximum.

Challenges: If the access pattern is not truly sequential, prefetching can cause cache pollution. Moreover, if the sequential scan is only partial (e.g., a range query that aborts halfway), prefetched pages are wasted. Adaptive schemes adjust the prefetch aggressiveness based on the observed pattern.

Stride and Pattern Prefetching

Many data structures exhibit strided access patterns: e.g., array traversal by a step of 64 bytes. Hardware prefetchers in modern CPUs can detect such strides and fetch cache lines ahead. In a buffer pool, a similar idea can be implemented: maintain a history of recent miss offsets, detect a repeating stride, and issue prefetches accordingly.

More complex pattern-based prefetching uses techniques like Markov prediction or context-based prefetching. For each page access, the system records the next page accessed; if the same “next page” is seen repeatedly from the current page, that next page is prefetched. This is effective for file system workloads where files are read sequentially or where directory traversals follow predictable paths.

Group Prefetching and I/O Merging

Prefetching is often done in batches—multiple pages are read in a single I/O request. This reduces the per-page overhead and leverages the higher throughput of large I/Os. For example, a sequential prefetch of 256KB can be amortized over thousands of 4KB pages. The buffer pool must allocate space for the prefetched pages, which may require evicting other pages. This is where replacement and prefetching interact: aggressive prefetching can fill the buffer with many pages that are not yet referenced, potentially causing useful pages to be evicted before they have a chance to be re-used.

Software Prefetch Hints

Many databases allow the application to issue explicit prefetch hints. For example, PostgreSQL’s BufferAccessStrategy can be set to BAS_BULKREAD for a sequential scan, which uses a circular buffer and avoids polluting the main buffer. Similarly, system administrators can configure the kernel’s read_ahead_kb parameter per block device.

The Delicate Dance: Synergy Between Replacement and Prefetching

The combination of replacement and prefetching is not a simple superposition. The two mechanisms can either complement or counteract each other. Let’s examine the key interactions.

Prefetch Pollution

When prefetched pages enter the buffer pool, they are initially not accessed. If the replacement policy treats them the same as any other page, they may evict useful pages. For example, consider an LRU cache where a prefetched page is inserted at the head. Then, even before it is accessed, it pushes all existing pages down one spot. If a page at the tail is a hot page that was about to be re-accessed, it might be evicted prematurely. This phenomenon is known as prefetch pollution.

To mitigate pollution, many systems assign a lower initial priority to prefetched pages. For example, in the Linux page cache, prefetched pages are inserted at the tail of the LRU list (or in a separate “prefetch” list) so that they are evicted quickly if not accessed soon. In a Clock algorithm, the reference bit for a prefetched page might be cleared initially, ensuring it is a candidate for early eviction. ARC can be extended with a separate ghost list for prefetched pages.

The Prefetch Timing Problem

Even if prefetched pages are not evicted, they must be present in the pool at the time of the actual access. If the prefetch is issued too early, the page may sit in the pool for a long time before use, occupying space that could serve other pages. If issued too late, the I/O may not complete before the request arrives, defeating the purpose. Optimal prefetch timing requires estimating the arrival time of the next access and the latency of the storage device. Adaptive algorithms adjust the prefetch distance (number of pages ahead) based on recent miss rate and latency.

Coordinated Solutions: ARC with Prefetching

IBM’s ARC has been extended to handle prefetching gracefully. The original ARC paper describes how to integrate “prefetch hits” and “prefetch misses” into the ghost list mechanism. When a prefetched page is accessed, it is treated as a hit in the regular LRU or LFU list. When a prefetched page is evicted without being accessed, a prefetch miss is recorded, which causes the algorithm to reduce the prefetch depth. This feedback loop prevents the pool from being overwhelmed with useless prefetches.

Another approach is to separate the buffer pool into a demand cache and a prefetch cache. Pages requested by the application go into the demand cache, while prefetched pages go into a separate, smaller cache. Pages from the prefetch cache are moved into the demand cache only when accessed. This prevents prefetched pages from evicting valuable demand-paged pages. The tradeoff is more memory overhead for managing two pools.

Prefetch-Aware Replacement Policies

Some replacement policies are explicitly designed with prefetching in mind. LIRS has a variant called LIRS-P (prefetch-aware) that distinguishes between demand and prefetch accesses. The inter-reference distance for prefetched pages is measured from the time they are prefetched, not from the time they are accessed. This allows the policy to evict stale prefetches more aggressively.

Similarly, CART (Clock with Adaptive Replacement and Prefetching) combines Clock, ARC, and separate handling of prefetched pages. It maintains two ghost lists per list to track both demand and prefetch misses.

Practical Implementations in Real Systems

Let’s examine how these concepts are implemented in widely used systems.

MySQL InnoDB Buffer Pool

InnoDB uses a hybrid LRU list with a midpoint insertion strategy. The buffer pool is divided into a “young” sublist (front) and an “old” sublist (tail). A page is initially inserted at the midpoint (between young and old) and, upon the first access, is moved to the head of the young sublist. This is equivalent to a two-queue algorithm that protects against scans: a sequential scan only populates the old sublist and quickly gets evicted without affecting the young (hot) pages. InnoDB also has a configurable innodb_old_blocks_time parameter that defines how long a page must remain in the old sublist before being promoted. This prevents a single access (e.g., by a scan) from moving a page to the young list.

InnoDB does not incorporate prefetching in the traditional sense, but it does support read-ahead for sequential access patterns. The read-ahead thread monitors the pattern of page requests and, when it detects a sequential pattern, reads a block of pages in one I/O. These pages are inserted at the tail of the old sublist, making them easily evictable.

PostgreSQL Shared Buffers

PostgreSQL uses a Clock-sweep replacement algorithm for its shared buffer pool. Each buffer descriptor has a usage count (0–5). On each access, the usage count is incremented (up to 5). The clock hand sweeps through buffers; if the usage count is 0, the buffer is evicted; otherwise, it is decremented and the hand moves on. This is a “second-chance” variant with multi-bit counters, which is more robust than a single reference bit.

PostgreSQL also implements prefetching via the effective_io_concurrency parameter and the pg_prewarm extension. The kernel’s read-ahead is often relied upon for sequential scans, but PostgreSQL can also issue posix_fadvise hints. For B-tree index scans, PostgreSQL uses a “prefetch” strategy that issues asynchronous I/O requests for index pages that are predicted to be needed soon, based on the current scan direction.

Linux Page Cache

The Linux kernel’s page cache uses a two-list LRU approach: active and inactive lists. Pages are initially placed on the inactive list. On first access, they are promoted to the active list. The system tries to keep a certain ratio between the sizes of the two lists (default 2:1 active to inactive). The kernel also implements a CPU-intensive adaptive replacement algorithm called CLOCK-Pro (or more recent variants like LIRS-based). For prefetching, the kernel maintains a separate per-file read-ahead state that tracks the window size and the number of pages to read ahead. The read-ahead algorithm doubles the window on each successful sequential detection and halves it on a miss.

RocksDB Block Cache

RocksDB, the LSM-tree-based key-value store, uses the LRU policy for its block cache but has added support for LIRS and Hybrid policies in recent versions. The block cache is partitioned into shards to reduce contention. Prefetching in RocksDB is primarily done at the file level: when reading a SSTable, RocksDB may prefetch the index and filter blocks along with the data block.

Advanced Topics and Future Directions

Machine Learning for Caching

Recent research has explored using machine learning (ML) to predict future accesses and optimize both replacement and prefetching. One prominent approach is DeepCache (or CACHE using neural networks). The idea is to train a model that takes as input the recent access history (e.g., the last 10 accessed page IDs) and outputs a probability distribution over the next page to be accessed. The replacement policy then evicts the page with the lowest predicted probability of future access. Similarly, prefetching decisions are based on the top-k predicted pages.

These ML-based caches have demonstrated hit rates close to Belady’s optimal on traces from production workloads (e.g., Facebook’s Memcached). However, the overhead of running a neural network on every I/O is non-trivial. To reduce overhead, researchers have proposed learned Bloom filters and decision trees that are lightweight enough for online use. Another approach is offline training with periodic retraining, where the model is used as a hint to a classical policy. For example, ROCA (Reinforcement Online Cache Algorithm) uses Q-learning to adjust the weights of LRU and LFU.

Tiered Storage and Multi-Level Caching

Modern storage systems often use a hierarchy: DRAM, fast NVMe, slower SATA SSD, and HDD. A single buffer pool is insufficient because pages may be stored on different tiers. Multi-level caches (e.g., L2 cache on SSD, L3 cache in DRAM) require coordinated replacement and prefetching. An optimal policy for a two-level cache is more complex: the miss penalty at the first level depends on the hit rate of the second. Partitioning memory between levels is often done via static allocation, but dynamic splitting using ghost entries (like in ARC for multi-level caches) has been explored.

Persistent Memory (PMem)

The advent of Intel Optane DC Persistent Memory (now discontinued) and other byte-addressable non-volatile memory blurs the line between memory and storage. In a PMem-aware buffer pool, pages can be placed directly on PMem and accessed with near-DRAM latency (but still slower than DRAM). Replacement policies may need to consider the cost of moving pages between DRAM and PMem, as well as the persistent nature of the data. The Persistent Memory Buffer Pool (e.g., in Oracle’s PMem-aware database) uses a variant of LRU with writeback optimization.

Caching in Distributed Systems

In large-scale distributed caching systems like Memcached or Redis Cluster, replacement and prefetching are complicated by consistency, replication, and network latency. Each node runs its own buffer pool (or cache), and a global miss might be satisfied from another node. Cache sharding uses hash-based partitioning, but hot spots can occur. Consistent hashing reduces rehashing when nodes are added. Some systems use dynamic replication of hot keys across multiple nodes, which is a form of prefetching across nodes. Twemproxy is an example of a proxy that can perform consistent hashing and limited prefetching.

Putting It All Together: Designing a Buffer Pool with Prefetching

Imagine you are building a storage engine for a next-generation database. How would you design the buffer pool and prefetcher? Here is a possible architecture:

1. Buffer Pool Structure: Use a Clock-based algorithm with multi-bit usage counters (like PostgreSQL) to reduce lock contention. Split the pool into a “demand” section and a “prefetch” section with a configurable ratio (e.g., 80/20). Prefetched pages are placed into the prefetch section with a usage counter of 0. When a prefetched page is accessed, it is moved to the demand section with an elevated usage counter.

2. Replacement Policy: Use an adaptive approach similar to ARC, but for the demand section only. Maintain ghost lists that track recent evictions from both demand and prefetch sections. The target sizes of the ghost lists are adjusted based on the miss rate. In the prefetch section, use a simple FIFO or Clock that evicts pages that have not been accessed after a certain time.

3. Prefetching: Implement a multi-level prefetcher:

   • Sequential detector: Monitors page access offsets for each file. If three consecutive accesses are at increasing offsets, trigger a prefetch of the next 8 pages.
   • Stride detector: For workloads like pointer-chasing in a B-tree, keep a per-session history of the last two accessed page IDs. If the stride matches the offset between the two pages, prefetch the next page in that stride.
   • Pattern-based detector: Use a limited hash table that records pairs (current_page, next_page); if the same pair appears twice, prefetch next_page when current_page is accessed.

4. Coordination: Prefetch requests are batched into a single I/O. The prefetcher maintains a feedback loop: if a prefetched page is evicted before being accessed, decrease the prefetch depth. If a prefetch hit is high, increase the depth. Also, if the prefetch section is full, throttle prefetching until space frees up.

5. Persistence: For recovery, the buffer pool state (page IDs of dirty pages) is logged to ensure the write-ahead log is consistent. Prefetch section is not persistent; it is re-populated on restart.

Conclusion

The buffer pool is the unsung hero of every data-d31dd264 system. Its replacement policy and prefetching mechanism are the result of decades of research and engineering, spanning from simple FIFO to complex adaptive algorithms like ARC and LIRS, and now into the realm of machine learning. Yet, the quest for perfect caching is far from over. As storage devices evolve (PMem, flash with asymmetric read/write costs), as memory capacities grow, and as workloads become more unpredictable, new challenges emerge.

What we have learned is that no single algorithm dominates all workloads. The best buffer pool is one that can adapt: adapt to the access pattern, adapt to the storage medium, adapt to the interactions between replacement and prefetching. This adaptability is the key insight behind modern algorithms like ARC and its descendants. By understanding the trade-offs and the synergy between caching and prefetching, system designers can build storage engines that squeeze every ounce of performance out of the hardware.

For the engineer reading this, I encourage you to not just rely on default settings. Profile your workloads, understand your access patterns, and tune your buffer pool accordingly. Perhaps you need to disable read-ahead for random access, or increase the prefetch depth for sequential scans. Perhaps you need to adopt a different replacement policy (e.g., LIRS for a LSM-tree). The tools are there—the art is in applying them wisely.

The I/O bottleneck may never disappear, but with a well-designed buffer pool and a judicious prefetcher, we can come remarkably close to making it invisible. And that, in the end, is the closest we can get to perfect caching.