Linux文件預(yù)讀算法磁盤I/O性能的發(fā)展遠(yuǎn)遠(yuǎn)滯后于CPU和內(nèi)存，因而成為現(xiàn)代計(jì)算機(jī)系統(tǒng)的一個主要瓶頸。預(yù)讀可以有效的減少磁盤的尋道次數(shù)和應(yīng)用程序的I/O等待時間，是改進(jìn)磁盤讀I/O性能的重要優(yōu)化手段之一。本文作者是中國科學(xué)技術(shù)大學(xué)自動化系的博士生，他在1998年開始學(xué)習(xí)Linux，為了優(yōu)化服務(wù)器的性能，他開始嘗試改進(jìn)Linux kernel，并最終重寫了內(nèi)核的文件預(yù)讀部分，這些改進(jìn)被收錄到Linux Kernel 2.6.23及其后續(xù)版本中。
從寄存器、L1/L2高速緩存、內(nèi)存、閃存，到磁盤/光盤/磁帶/存儲網(wǎng)絡(luò)，計(jì)算機(jī)的各級存儲器硬件組成了一個金字塔結(jié)構(gòu)。越是底層存儲容量越大。然而訪問速度也越慢，具體表現(xiàn)為更小的帶寬和更大的延遲。因而這很自然的便成為一個金字塔形的逐層緩存結(jié)構(gòu)。由此產(chǎn)生了三類基本的緩存管理和優(yōu)化問題：
◆預(yù)取(prefetching)算法，從慢速存儲中加載數(shù)據(jù)到緩存;
◆替換(replacement)算法，從緩存中丟棄無用數(shù)據(jù);
◆寫回(writeback)算法，把臟數(shù)據(jù)從緩存中保存到慢速存儲。
其中的預(yù)取算法，在磁盤這一層次尤為重要。磁盤的機(jī)械臂+旋轉(zhuǎn)盤片的數(shù)據(jù)定位與讀取方式，決定了它最突出的性能特點(diǎn):擅長順序讀寫，不善于隨機(jī)I/O，I/O延遲非常大。由此而產(chǎn)生了兩個方面的預(yù)讀需求。
來自磁盤的需求
簡單的說，磁盤的一個典型I/O操作由兩個階段組成：
1.數(shù)據(jù)定位
平均定位時間主要由兩部分組成：平均尋道時間和平均轉(zhuǎn)動延遲。尋道時間的典型值是4.6ms。轉(zhuǎn)動延遲則取決于磁盤的轉(zhuǎn)速：普通7200RPM桌面硬盤的轉(zhuǎn)動延遲是4.2ms，而高端10000RPM的是3ms。這些數(shù)字多年來一直徘徊不前，大概今后也無法有大的改善了。在下文中，我們不妨使用 8ms作為典型定位時間。
2.數(shù)據(jù)傳輸
持續(xù)傳輸率主要取決于盤片的轉(zhuǎn)速(線速度)和存儲密度，最新的典型值為80MB/s。雖然磁盤轉(zhuǎn)速難以提高，但是存儲密度卻在逐年改善。巨磁阻、垂直磁記錄等一系列新技術(shù)的采用，不但大大提高了磁盤容量，也同時帶來了更高的持續(xù)傳輸率。
顯然，I/O的粒度越大，傳輸時間在總時間中的比重就會越大，因而磁盤利用率和吞吐量就會越大。簡單的估算結(jié)果如表1所示。如果進(jìn)行大量4KB的隨機(jī)I/O，那么磁盤在99%以上的時間內(nèi)都在忙著定位，單個磁盤的吞吐量不到500KB/s。但是當(dāng)I/O大小達(dá)到1MB的時候，吞吐量可接近50MB /s。由此可見，采用更大的I/O粒度，可以把磁盤的利用效率和吞吐量提高整整100倍。因而必須盡一切可能避免小尺寸I/O，這正是預(yù)讀算法所要做的。
表1隨機(jī)讀大小與磁盤性能的關(guān)系
來自程序的需求
應(yīng)用程序處理數(shù)據(jù)的一個典型流程是這樣的:while(!done) { read(); compute(); }。假設(shè)這個循環(huán)要重復(fù)5次，總共處理5批數(shù)據(jù)，則程序運(yùn)行的時序圖可能如圖1所示。
圖1典型的I/O時序圖
不難看出，磁盤和CPU是在交替忙碌：當(dāng)進(jìn)行磁盤I/O的時候，CPU在等待;當(dāng)CPU在計(jì)算和處理數(shù)據(jù)時，磁盤是空閑的。那么是不是可以讓兩者流水線作業(yè)，以便加快程序的執(zhí)行速度?預(yù)讀可以幫助達(dá)成這一目標(biāo)?；镜姆椒ㄊ?，當(dāng)CPU開始處理第1批數(shù)據(jù)的時候，由內(nèi)核的預(yù)讀機(jī)制預(yù)加載下一批數(shù)據(jù)。這時候的預(yù)讀是在后臺異步進(jìn)行的，如圖2所示。
圖2預(yù)讀的流水線作業(yè)
注意，在這里我們并沒有改變應(yīng)用程序的行為：程序的下一個讀請求仍然是在處理完當(dāng)前的數(shù)據(jù)之后才發(fā)出的。只是這時候的被請求的數(shù)據(jù)可能已經(jīng)在內(nèi)核緩存中了，無須等待，直接就能復(fù)制過來用。在這里，異步預(yù)讀的功能是對上層應(yīng)用程序“隱藏”磁盤I/O的大延遲。雖然延遲事實(shí)上仍然存在，但是應(yīng)用程序看不到了，因而運(yùn)行的更流暢。
預(yù)讀的概念
預(yù)取算法的涵義和應(yīng)用非常廣泛。它存在于CPU、硬盤、內(nèi)核、應(yīng)用程序以及網(wǎng)絡(luò)的各個層次。預(yù)取有兩種方案：啟發(fā)性的(heuristic prefetching)和知情的(informed prefetching)。前者自動自發(fā)的進(jìn)行預(yù)讀決策，對上層應(yīng)用是透明的，但是對算法的要求較高，存在命中率的問題;后者則簡單的提供API接口，而由上層程序給予明確的預(yù)讀指示。在磁盤這個層次，Linux為我們提供了三個API接口：posix_fadvise(2), readahead(2), madvise(2)。