ASEP: An Adaptive Sequential Prefetching Scheme for Second-level Storage System

Abstract—In model storage systems, the multilevel buffer caches hierarchy is widely used to improve the I/O performance of disks. In the hierarchy, the referenced pages in second-level buffer cache have larger reuse distance that is the number of accesses between two references to the same block in a reference sequence. These reuse distances have close value with their lifetime- the time they are conserved in buffer cache. Therefore, this tiny difference can be more easily eliminated by the prefetched (not yet accessed) data that reduces the lifetime of referenced pages. This leads more pages than those replaced by prefetching to lose their re-access opportunity. This anomaly influence can significantly reduce the overall hit ratio of buffer cache and, unfortunately, it is ignored by traditional sequential prefetching algorithms. To address this problem, we propose an Adaptive SEquential Prefetching (named ASEP) that uncovers this anomaly influence and adaptively adjusts the prefetching depth by considering the access characteristics in second-level buffer cache. We extensively evaluate ASEP by conducting trace driven experiments with a prototype implements in Linux (software RAID-MD). The experiments ’ results, under varied workloads from transaction processing applications to Web searching applications, show that ASEP outperforms the default sequential prefetching scheme in Linux kernel and other heuristic schemes, with the response time improvement by up to 49.7 % and the cache hit ratio improvement ranging from 0.2 ~ 8.5%