The goal of sequential read-ahead is to keep the cache pre-loaded and ready with data for upcoming I/O operations, thus preventing potential misses. We outline a state-of-the-art sequential prefetching scheme whose variants are used in many commercial systems, for example, DB2 [29], Oracle [30], and Shark [32]. We also point out an anomaly akin to Belady's anomaly [3] that plagues such sequential prefetching schemes when used in conjunction with LRU-based caching. We also offer a simple and elegant remedy.
We manage the lists in the cache in terms of tracks, where a track is a set of up to eight 4K pages.
Before a sequential prefetching policy can be deployed, sequential access must be detected somehow. In many mainframe type applications, the client often indicates sequential accesses. In the absence of such hints, a necessary first step is to effectively detect sequences. Next, we discuss one such detection scheme; if desired, other schemes can be readily substituted without changing the essence of our analysis.