從寄存器、L1/L2高速緩存、內(nèi)存、閃存，到磁盤/光盤/磁帶/存儲(chǔ)網(wǎng)絡(luò)，計(jì)算機(jī)的各級(jí)存儲(chǔ)器硬件組成了一個(gè)金字塔結(jié)構(gòu)。越是底層存儲(chǔ)容量越大。然而訪問速度也越慢，具體表現(xiàn)為更小的帶寬和更大的延遲。因而這很自然的便成為一個(gè)金字塔形的逐層緩存結(jié)構(gòu)。由此產(chǎn)生了三類基本的緩存管理和優(yōu)化問題：
◆預(yù)取(prefetching)算法，從慢速存儲(chǔ)中加載數(shù)據(jù)到緩存;
◆替換(replacement)算法，從緩存中丟棄無用數(shù)據(jù);
◆寫回(writeback)算法，把臟數(shù)據(jù)從緩存中保存到慢速存儲(chǔ)。
其中的預(yù)取算法，在磁盤這一層次尤為重要。磁盤的機(jī)械臂+旋轉(zhuǎn)盤片的數(shù)據(jù)定位與讀取方式，決定了它最突出的性能特點(diǎn):擅長順序讀寫，不善于隨機(jī)I/O，I/O延遲非常大。由此而產(chǎn)生了兩個(gè)方面的預(yù)讀需求。
來自磁盤的需求
簡單的說，磁盤的一個(gè)典型I/O操作由兩個(gè)階段組成：
1.數(shù)據(jù)定位
平均定位時(shí)間主要由兩部分組成：平均尋道時(shí)間和平均轉(zhuǎn)動(dòng)延遲。尋道時(shí)間的典型值是4.6ms。轉(zhuǎn)動(dòng)延遲則取決于磁盤的轉(zhuǎn)速：普通7200RPM桌面硬盤的轉(zhuǎn)動(dòng)延遲是4.2ms，而高端10000RPM的是3ms。這些數(shù)字多年來一直徘徊不前，大概今后也無法有大的改善了。在下文中，我們不妨使用8ms作為典型定位時(shí)間。
2.數(shù)據(jù)傳輸
持續(xù)傳輸率主要取決于盤片的轉(zhuǎn)速（線速度）和存儲(chǔ)密度，最新的典型值為80MB/s。雖然磁盤轉(zhuǎn)速難以提高，但是存儲(chǔ)密度卻在逐年改善。巨磁阻、垂直磁記錄等一系列新技術(shù)的采用，不但大大提高了磁盤容量，也同時(shí)帶來了更高的持續(xù)傳輸率。
顯然，I/O的粒度越大，傳輸時(shí)間在總時(shí)間中的比重就會(huì)越大，因而磁盤利用率和吞吐量就會(huì)越大。簡單的估算結(jié)果如表1所示。如果進(jìn)行大量4KB的隨機(jī)I/O，那么磁盤在99%以上的時(shí)間內(nèi)都在忙著定位，單個(gè)磁盤的吞吐量不到500KB/s。但是當(dāng)I/O大小達(dá)到1MB的時(shí)候，吞吐量可接近50MB/s。由此可見，采用更大的I/O粒度，可以把磁盤的利用效率和吞吐量提高整整100倍。因而必須盡一切可能避免小尺寸I/O，這正是預(yù)讀算法所要做的。
來自程序的需求
應(yīng)用程序處理數(shù)據(jù)的一個(gè)典型流程是這樣的:while(!done) { read(); compute(); }。假設(shè)這個(gè)循環(huán)要重復(fù)5次，總共處理5批數(shù)據(jù)，則程序運(yùn)行的時(shí)序圖可能如圖1所示。
不難看出，磁盤和CPU是在交替忙碌：當(dāng)進(jìn)行磁盤I/O的時(shí)候，CPU在等待；當(dāng)CPU在計(jì)算和處理數(shù)據(jù)時(shí)，磁盤是空閑的。那么是不是可以讓兩者流水線作業(yè)，以便加快程序的執(zhí)行速度？預(yù)讀可以幫助達(dá)成這一目標(biāo)?；镜姆椒ㄊ?，當(dāng)CPU開始處理第1批數(shù)據(jù)的時(shí)候，由內(nèi)核的預(yù)讀機(jī)制預(yù)加載下一批數(shù)據(jù)。這時(shí)候的預(yù)讀是在后臺(tái)異步進(jìn)行的，如圖2所示。
注意，在這里我們并沒有改變應(yīng)用程序的行為：程序的下一個(gè)讀請(qǐng)求仍然是在處理完當(dāng)前的數(shù)據(jù)之后才發(fā)出的。只是這時(shí)候的被請(qǐng)求的數(shù)據(jù)可能已經(jīng)在內(nèi)核緩存中了，無須等待，直接就能復(fù)制過來用。在這里，異步預(yù)讀的功能是對(duì)上層應(yīng)用程序“隱藏”磁盤I/O的大延遲。雖然延遲事實(shí)上仍然存在，但是應(yīng)用程序看不到了，因而運(yùn)行的更流暢。
預(yù)讀的概念
預(yù)取算法的涵義和應(yīng)用非常廣泛。它存在于CPU、硬盤、內(nèi)核、應(yīng)用程序以及網(wǎng)絡(luò)的各個(gè)層次。預(yù)取有兩種方案：啟發(fā)性的(heuristic prefetching)和知情的(informed prefetching)。前者自動(dòng)自發(fā)的進(jìn)行預(yù)讀決策，對(duì)上層應(yīng)用是透明的，但是對(duì)算法的要求較高，存在命中率的問題；后者則簡單的提供API接口，而由上層程序給予明確的預(yù)讀指示。在磁盤這個(gè)層次，Linux為我們提供了三個(gè)API接口：posix_fadvise(2), readahead(2), madvise(2)。
不過真正使用上述預(yù)讀API的應(yīng)用程序并不多見：因?yàn)橐话闱闆r下，內(nèi)核中的啟發(fā)式算法工作的很好。預(yù)讀(readahead)算法預(yù)測(cè)即將訪問的頁面，并提前把它們批量的讀入緩存。
它的主要功能和任務(wù)可以用三個(gè)關(guān)鍵詞來概括：
◆批量，也就是把小I/O聚集為大I/O，以改善磁盤的利用率，提升系統(tǒng)的吞吐量。
◆提前，也就是對(duì)應(yīng)用程序隱藏磁盤的I/O延遲，以加快程序運(yùn)行。
◆預(yù)測(cè)，這是預(yù)讀算法的核心任務(wù)。前兩個(gè)功能的達(dá)成都有賴于準(zhǔn)確的預(yù)測(cè)能力。當(dāng)前包括Linux、FreeBSD和Solaris等主流操作系統(tǒng)都遵循了一個(gè)簡單有效的原則：把讀模式分為隨機(jī)讀和順序讀兩大類，并只對(duì)順序讀進(jìn)行預(yù)讀。這一原則相對(duì)保守，但是可以保證很高的預(yù)讀命中率，同時(shí)有效率/覆蓋率也很好。因?yàn)轫樞蜃x是最簡單而普遍的，而隨機(jī)讀在內(nèi)核來說也確實(shí)是難以預(yù)測(cè)的。
Linux的預(yù)讀架構(gòu)
Linux內(nèi)核的一大特色就是支持最多的文件系統(tǒng)，并擁有一個(gè)虛擬文件系統(tǒng)(VFS)層。早在2002年，也就是2.5內(nèi)核的開發(fā)過程中，Andrew Morton在VFS層引入了文件預(yù)讀的基本框架，以統(tǒng)一支持各個(gè)文件系統(tǒng)。如圖所示，Linux內(nèi)核會(huì)將它最近訪問過的文件頁面緩存在內(nèi)存中一段時(shí)間，這個(gè)文件緩存被稱為pagecache。如圖3所示。一般的read()操作發(fā)生在應(yīng)用程序提供的緩沖區(qū)與pagecache之間。而預(yù)讀算法則負(fù)責(zé)填充這個(gè)pagecache。應(yīng)用程序的讀緩存一般都比較小，比如文件拷貝命令cp的讀寫粒度就是4KB；內(nèi)核的預(yù)讀算法則會(huì)以它認(rèn)為更合適的大小進(jìn)行預(yù)讀I/O，比比如16-128KB。
大約一年之后，Linus Torvalds把mmap缺頁I/O的預(yù)取算法單獨(dú)列出，從而形成了read-around/read-ahead兩個(gè)獨(dú)立算法（圖4）。read-around算法適用于那些以mmap方式訪問的程序代碼和數(shù)據(jù)，它們具有很強(qiáng)的局域性(locality of reference)特征。當(dāng)有缺頁事件發(fā)生時(shí)，它以當(dāng)前頁面為中心，往前往后預(yù)取共計(jì)128KB頁面。而readahead算法主要針對(duì)read()系統(tǒng)調(diào)用，它們一般都具有很好的順序特性。但是隨機(jī)和非典型的讀取模式也大量存在，因而readahead算法必須具有很好的智能和適應(yīng)性。
圖4 Linux中的read-around, read-ahead和direct read
又過了一年，通過Steven Pratt、Ram Pai等人的大量工作，readahead算法進(jìn)一步完善。其中最重要的一點(diǎn)是實(shí)現(xiàn)了對(duì)隨機(jī)讀的完好支持。隨機(jī)讀在數(shù)據(jù)庫應(yīng)用中處于非常突出的地位。在此之前，預(yù)讀算法以離散的讀頁面位置作為輸入，一個(gè)多頁面的隨機(jī)讀會(huì)觸發(fā)“順序預(yù)讀”。這導(dǎo)致了預(yù)讀I/O數(shù)的增加和命中率的下降。改進(jìn)后的算法通過監(jiān)控所有完整的read()調(diào)用，同時(shí)得到讀請(qǐng)求的頁面偏移量和數(shù)量，因而能夠更好的區(qū)分順序讀和隨機(jī)讀。
預(yù)讀算法概要
這一節(jié)以linux 2.6.22為例，來剖析預(yù)讀算法的幾個(gè)要點(diǎn)。
1.順序性檢測(cè)
為了保證預(yù)讀命中率，Linux只對(duì)順序讀(sequential read)進(jìn)行預(yù)讀。內(nèi)核通過驗(yàn)證如下兩個(gè)條件來判定一個(gè)read()是否順序讀：
◆這是文件被打開后的第一次讀，并且讀的是文件首部；
◆當(dāng)前的讀請(qǐng)求與前一（記錄的）讀請(qǐng)求在文件內(nèi)的位置是連續(xù)的。
如果不滿足上述順序性條件，就判定為隨機(jī)讀。任何一個(gè)隨機(jī)讀都將終止當(dāng)前的順序序列，從而終止預(yù)讀行為（而不是縮減預(yù)讀大?。?。注意這里的空間順序性說的是文件內(nèi)的偏移量，而不是指物理磁盤扇區(qū)的連續(xù)性。在這里L(fēng)inux作了一種簡化，它行之有效的基本前提是文件在磁盤上是基本連續(xù)存儲(chǔ)的，沒有嚴(yán)重的碎片化。
2.流水線預(yù)讀
當(dāng)程序在處理一批數(shù)據(jù)時(shí)，我們希望內(nèi)核能在后臺(tái)把下一批數(shù)據(jù)事先準(zhǔn)備好，以便CPU和硬盤能流水線作業(yè)。Linux用兩個(gè)預(yù)讀窗口來跟蹤當(dāng)前順序流的預(yù)讀狀態(tài)：current窗口和ahead窗口。其中的ahead窗口便是為流水線準(zhǔn)備的：當(dāng)應(yīng)用程序工作在current窗口時(shí)，內(nèi)核可能正在ahead窗口進(jìn)行異步預(yù)讀；一旦程序進(jìn)入當(dāng)前的ahead窗口，內(nèi)核就會(huì)立即往前推進(jìn)兩個(gè)窗口，并在新的ahead窗口中啟動(dòng)預(yù)讀I/O。
3.預(yù)讀的大小
當(dāng)確定了要進(jìn)行順序預(yù)讀(sequential readahead)時(shí)，就需要決定合適的預(yù)讀大小。預(yù)讀粒度太小的話，達(dá)不到應(yīng)有的性能提升效果；預(yù)讀太多，又有可能載入太多程序不需要的頁面，造成資源浪費(fèi)。為此，Linux采用了一個(gè)快速的窗口擴(kuò)張過程：
◆首次預(yù)讀： readahead_size = read_size * 2; // or *4
預(yù)讀窗口的初始值是讀大小的二到四倍。這意味著在您的程序中使用較大的讀粒度（比如32KB）可以稍稍提升I/O效率。
◆后續(xù)預(yù)讀： readahead_size *= 2;
后續(xù)的預(yù)讀窗口將逐次倍增，直到達(dá)到系統(tǒng)設(shè)定的最大預(yù)讀大小，其缺省值是128KB。這個(gè)缺省值已經(jīng)沿用至少五年了，在當(dāng)前更快的硬盤和大容量內(nèi)存面前，顯得太過保守。比如西部數(shù)據(jù)公司近年推出的WD Raptor 猛禽 10000RPM SATA 硬盤，在進(jìn)行128KB隨機(jī)讀的時(shí)候，只能達(dá)到16%的磁盤利用率（圖5）。所以如果您運(yùn)行著Linux服務(wù)器或者桌面系統(tǒng)，不妨試著用如下命令把最大預(yù)讀值提升到1MB看看，或許會(huì)有驚喜：
# blockdev –setra 2048 /dev/sda
當(dāng)然預(yù)讀大小不是越大越好，在很多情況下，也需要同時(shí)考慮I/O延遲問題。
圖5 128KB I/O的數(shù)據(jù)定位時(shí)間和傳輸時(shí)間比重
重新發(fā)現(xiàn)順序讀
上一節(jié)我們解決了是否／何時(shí)進(jìn)行預(yù)讀，以及讀多少的基本問題。由于現(xiàn)實(shí)的復(fù)雜性，上述算法并不總能奏效，即使是對(duì)于順序讀的情況。例如最近發(fā)現(xiàn)的重試讀(retried read)的問題。
重試讀在異步I/O和非阻塞I/O中比較常見。它們?cè)试S內(nèi)核中斷一個(gè)讀請(qǐng)求。這樣一來，程序提交的后續(xù)讀請(qǐng)求看起來會(huì)與前面被中斷的讀請(qǐng)求相重疊。如圖6所示。
Linux 2.6.22無法理解這種情況，于是把它誤判為隨機(jī)讀。這里的問題在于“讀請(qǐng)求”并不代表讀取操作實(shí)實(shí)在在的發(fā)生了。預(yù)讀的決策依據(jù)應(yīng)為后者而非前者。最新發(fā)布的2.6.23對(duì)此作了改進(jìn)。新的算法以當(dāng)前讀取的頁面狀態(tài)為主要決策依據(jù)，并為此新增了一個(gè)頁面標(biāo)志位：PG_readahead，它是“請(qǐng)作異步預(yù)讀”的一個(gè)提示。在每次進(jìn)行新預(yù)讀時(shí)，算法都會(huì)選擇其中的一個(gè)新頁面并標(biāo)記之。預(yù)讀規(guī)則相應(yīng)的改為：
◆當(dāng)讀到缺失頁面(missing page)，進(jìn)行同步預(yù)讀；
◆當(dāng)讀到預(yù)讀頁面(PG_readahead page)，進(jìn)行異步預(yù)讀。
這樣一來，ahead預(yù)讀窗口就不需要了：它實(shí)際上是把預(yù)讀大小和提前量兩者作了不必要的綁定。新的標(biāo)記機(jī)制允許我們靈活而精確地控制預(yù)讀的提前量，這有助于將來引入對(duì)筆記本省電模式的支持。
另一個(gè)越來越突出的問題來自于交織讀(interleaved read)。這一讀模式常見于多媒體／多線程應(yīng)用。當(dāng)在一個(gè)打開的文件中同時(shí)進(jìn)行多個(gè)流(stream)的讀取時(shí)，它們的讀取請(qǐng)求會(huì)相互交織在一起，在內(nèi)核看來好像是很多的隨機(jī)讀。更嚴(yán)重的是，目前的內(nèi)核只能在一個(gè)打開的文件描述符中跟蹤一個(gè)流的預(yù)讀狀態(tài)。因而即使內(nèi)核對(duì)兩個(gè)流進(jìn)行預(yù)讀，它們會(huì)相互覆蓋和破壞對(duì)方的預(yù)讀狀態(tài)信息。對(duì)此，我們將在即將發(fā)布的2.6.24中作一定改進(jìn)，利用頁面和pagecache所提供的狀態(tài)信息來支持多個(gè)流的交織讀。
預(yù)讀建議
聯(lián)系客服
