Sequential prefetching is a well established technique for improving I/O performance. As Linux runs an increasing variety of workloads, its in-kernel prefetching algorithm has been challenged by many unexpected and subtle problems; As computer hardware evolves, the design goals should also be adapted. To meet the new challenges and demands, a prefetching algorithm that is aggressive yet safe, flexible yet simple, scalable yet efficient is desired. In this chapter, the author explores the principles of I/O prefetching and present a demand readahead algorithm for Linux. He demonstrates how it handles common readahead issues by a host of case studies. Both static, logic and dynamic behaviors of the readahead algorithm are covered, so as to help readers building both theoretical and practical views of sequential prefetching.
Principles Of I/O Prefetching
Bandwidth and latency are the two major aspects of I/O performance. For both metrics, there have been huge and growing performance gaps between disk, memory and processor. For example, the Intel(R) QuickPath(TM) Interconnect(QPI) can provide 12.8GB/s bandwidth per direction for processor-to-processor and processor-to-io data transfers. Today's DDR3-1333 memory has a theoretical bandwidth of 10666MB/s and response time of 12 nanoseconds, while a Seagate(R) 7200.11 SATA disk has a maximum sustained transfer rate of 105MB/s and average seek time of 8.5ms. Hence the performance gap as of 2009 is about 10 times for bandwidth and 7e5 times for latency. In this section, we demonstrate how I/O prefetching can help fill the performance gaps.
Complete Chapter List
Yair Wiseman, Song Jiang
Yair Wiseman, Joel Isaacson, Eliad Lubovsky, Pinchas Weisberg
Michael M. Swift
Arati Baliga, Pandurang Kamat, Vinod Ganapathy, Liviu Iftode
Moses Reuven, Yair Wiseman
Timothy R. Leschke
Daniel G. Waddington, Nilabja Roy, Douglas C. Schmidt
Feng Chen, Xiaoning Ding, Song Jiang
Wei Wu, Kian-Lee Tan
Yannis Smaragdakis, Scott Kaplan
Moshe Itshak, Yair Wiseman