DiskSeen: Exploiting Disk Layout and Access History to Enhance I/O Prefetch

当前主流操作系统的磁盘预取策略追踪文件抽象级别的访问模式。虽然这对于利用应用程序级的访问模十分有效，但文件级预取无法实现预取可达到的完整性能提升。这有两个原因。一是某些预取机会只能通过了解磁盘上的数据布局得到，例如元数据或多个文件的数据的连续布局。其次，磁盘数据的非顺序访问（需要磁头移动）比顺序访问慢得多，所以对于误预取一个“随机”块相对于顺序块来说代价更大。
为了克服在逻辑文件级别预取的固有限制，本文提出一种直接在磁盘布局级别进行预取的便捷方式。我们的技术称为 Diskseen，旨在补足文件级预取策略（如果有）并与之协同。Diskseen 跟踪磁盘块的位置和访问时间，并根据分析它们的时间和空间关系，以求提高磁盘访问的顺序和整体预取性能。
我们在 Linux 2.6 内核中的 Diskseen 方案的实现表明，对于微基准测试和 grep、CVS、TPC-H 等真实应用程序，它可以显着提高预取的有效性，减少20％至53％的执行时间。
Current disk prefetch policies in major operating systems track access patterns at the level of the file abstraction. While this is useful for exploiting application-level access patterns, file-level prefetching cannot realize the full performance improvements achievable by prefetching. There are two reasons for this. First, certain prefetch opportunities can only be detected by knowing the data layout on disk, such as the contiguous layout of file metadata or data from multiple files. Second, nonsequential access of disk data (requiring disk head movement) is much slower than sequential access, and the penalty for mis-prefetching a 'random' block, relative to that of a sequential block, is correspondingly more costly.
To overcome the inherent limitations of prefetching at the logical file level, we propose to perform prefetching directly at the level of disk layout, and in a portable way. Our technique, called DiskSeen, is intended to be supplementary to, and to work synergistically with, file-level prefetch policies, if present. DiskSeen tracks the locations and access times of disk blocks, and based on analysis of their temporal and spatial relationships, seeks to improve the sequentiality of disk accesses and overall prefetching performance.
Our implementation of the DiskSeen scheme in the Linux 2.6 kernel shows that it can significantly improve the effectiveness of prefetching, reducing execution times by 20%-53% for micro-benchmarks and real applications such as grep, CVS, and TPC-H.