編者按：Linux檔案預讀算法磁盤I/O性能的發展遠遠滞後于CPU和記憶體，因而成為現代計算機系統的一個主要瓶頸。預讀可以有效的減少磁盤的尋道次數和應用程式的I/O等待時間，是改進磁盤讀I/O性能的重要優化手段之一。本文作者是中國科學技術大學自動化系的博士生，他在1998年開始學習Linux，為了優化伺服器的性能，他開始嘗試改進Linux kernel，并最終重寫了核心的檔案預讀部分，這些改進被收錄到Linux Kernel 2.6.23及其後續版本中。
從寄存器、L1/L2高速緩存、記憶體、閃存，到磁盤/CD光牒/錄音帶/存儲網絡，計算機的各級存儲器硬體組成了一個金字塔結構。越是底層存儲容量越大。然而通路速度也越慢，具體表現為更小的帶寬和更大的延遲。因而這很自然的便成為一個金字塔形的逐層緩存結構。由此産生了三類基本的緩存管理和優化問題：
◆預取(prefetching)算法，從慢速存儲中加載資料到緩存;
◆替換(replacement)算法，從緩存中丢棄無用資料;
◆寫回(writeback)算法，把髒資料從緩存中儲存到慢速存儲。
其中的預取算法，在磁盤這一層次尤為重要。磁盤的機械臂+旋轉盤片的資料定位與讀取方式，決定了它最突出的性能特點:擅長順序讀寫，不善于随機I/O，I/O延遲非常大。由此而産生了兩個方面的預讀需求。
來自磁盤的需求
簡單的說，磁盤的一個典型I/O操作由兩個階段組成：
1.資料定位
平均定位時間主要由兩部分組成：平均尋道時間和平均轉動延遲。尋道時間的典型值是4.6ms。轉動延遲則取決于磁盤的轉速：普通7200RPM桌面硬碟的轉動延遲是4.2ms，而高端10000RPM的是3ms。這些數字多年來一直徘徊不前，大概今後也無法有大的改善了。在下文中，我們不妨使用 8ms作為典型定位時間。
2.資料傳輸
持續傳輸率主要取決于盤片的轉速（線速度）和存儲密度，最新的典型值為80MB/s。雖然磁盤轉速難以提高，但是存儲密度卻在逐年改善。巨磁阻、垂直磁記錄等一系列新技術的采用，不但大大提高了磁盤容量，也同時帶來了更高的持續傳輸率。
顯然，I/O的粒度越大，傳輸時間在總時間中的比重就會越大，因而磁盤使用率和吞吐量就會越大。簡單的估算結果如表1所示。如果進行大量4KB的随機I/O，那麼磁盤在99%以上的時間内都在忙着定位，單個磁盤的吞吐量不到500KB/s。但是當I/O大小達到1MB的時候，吞吐量可接近50MB /s。由此可見，采用更大的I/O粒度，可以把磁盤的利用效率和吞吐量提高整整100倍。因而必須盡一切可能避免小尺寸I/O，這正是預讀算法所要做的。
表1 随機讀大小與磁盤性能的關系
來自程式的需求
應用程式處理資料的一個典型流程是這樣的:while(!done) { read(); compute(); }。假設這個循環要重複5次，總共處理5批資料，則程式運作的時序圖可能如圖1所示。
圖1 典型的I/O時序圖
不難看出，磁盤和CPU是在交替忙碌：當進行磁盤I/O的時候，CPU在等待；當CPU在計算和處理資料時，磁盤是空閑的。那麼是不是可以讓兩者流水線作業，以便加快程式的執行速度？預讀可以幫助達成這一目标。基本的方法是，當CPU開始處理第1批資料的時候，由核心的預讀機制預加載下一批資料。這時候的預讀是在背景異步進行的，如圖2所示。
圖2 預讀的流水線作業
注意，在這裡我們并沒有改變應用程式的行為：程式的下一個讀請求仍然是在處理完目前的資料之後才發出的。隻是這時候的被請求的資料可能已經在核心緩存中了，無須等待，直接就能複制過來用。在這裡，異步預讀的功能是對上層應用程式“隐藏”磁盤I/O的大延遲。雖然延遲事實上仍然存在，但是應用程式看不到了，因而運作的更流暢。
預讀的概念
預取算法的涵義和應用非常廣泛。它存在于CPU、硬碟、核心、應用程式以及網絡的各個層次。預取有兩種方案：啟發性的(heuristic prefetching)和知情的(informed prefetching)。前者自動自發的進行預讀決策，對上層應用是透明的，但是對算法的要求較高，存在命中率的問題；後者則簡單的提供API接口，而由上層程式給予明确的預讀訓示。在磁盤這個層次，Linux為我們提供了三個API接口：posix_fadvise(2), readahead(2), madvise(2)。
不過真正使用上述預讀API的應用程式并不多見：因為一般情況下，核心中的啟發式算法工作的很好。預讀(readahead)算法預測即将通路的頁面，并提前把它們批量的讀入緩存。
它的主要功能和任務可以用三個關鍵詞來概括：
◆批量，也就是把小I/O聚集為大I/O，以改善磁盤的使用率，提升系統的吞吐量。
◆提前，也就是對應用程式隐藏磁盤的I/O延遲，以加快程式運作。
◆ 預測，這是預讀算法的核心任務。前兩個功能的達成都有賴于準确的預測能力。目前包括Linux、FreeBSD和Solaris等主流作業系統都遵循了一個簡單有效的原則：把讀模式分為随機讀和順序讀兩大類，并隻對順序讀進行預讀。這一原則相對保守，但是可以保證很高的預讀命中率，同時有效率/覆寫率也很好。因為順序讀是最簡單而普遍的，而随機讀在核心來說也确實是難以預測的。
Linux的預讀架構
Linux核心的一大特色就是支援最多的檔案系統，并擁有一個虛拟檔案系統(VFS)層。早在2002年，也就是2.5核心的開發過程中，Andrew Morton在VFS層引入了檔案預讀的基本架構，以統一支援各個檔案系統。如圖所示，Linux核心會将它最近通路過的檔案頁面緩存在記憶體中一段時間，這個檔案緩存被稱為pagecache。如圖3所示。一般的read()操作發生在應用程式提供的緩沖區與pagecache之間。而預讀算法則負責填充這個pagecache。應用程式的讀緩存一般都比較小，比如檔案拷貝指令cp的讀寫粒度就是4KB；核心的預讀算法則會以它認為更合适的大小進行預讀 I/O，比比如16-128KB。
圖3 以pagecache為中心的讀和預讀
大約一年之後，Linus Torvalds把mmap缺頁I/O的預取算法單獨列出，進而形成了read-around/read-ahead兩個獨立算法（圖4）。read- around算法适用于那些以mmap方式通路的程式代碼和資料，它們具有很強的局域性(locality of reference)特征。當有缺頁事件發生時，它以目前頁面為中心，往前往後預取共計128KB頁面。而readahead算法主要針對read()系統調用，它們一般都具有很好的順序特性。但是随機和非典型的讀取模式也大量存在，因而readahead算法必須具有很好的智能和适應性。
圖4 Linux中的read-around, read-ahead和direct read
又過了一年，通過Steven Pratt、Ram Pai等人的大量工作，readahead算法進一步完善。其中最重要的一點是實作了對随機讀的完好支援。随機讀在資料庫應用中處于非常突出的地位。在此之前，預讀算法以離散的讀頁面位置作為輸入，一個多頁面的随機讀會觸發“順序預讀”。這導緻了預讀I/O數的增加和命中率的下降。改進後的算法通過監控所有完整的read()調用，同時得到讀請求的頁面偏移量和數量，因而能夠更好的區分順序讀和随機讀。
預讀算法概要
這一節以linux 2.6.22為例，來剖析預讀算法的幾個要點。
1.順序性檢測
為了保證預讀命中率，Linux隻對順序讀(sequential read)進行預讀。核心通過驗證如下兩個條件來判定一個read()是否順序讀：
◆這是檔案被打開後的第一次讀，并且讀的是檔案首部；
◆目前的讀請求與前一（記錄的）讀請求在檔案内的位置是連續的。
如果不滿足上述順序性條件，就判定為随機讀。任何一個随機讀都将終止目前的順序序列，進而終止預讀行為（而不是縮減預讀大小）。注意這裡的空間順序性說的是檔案内的偏移量，而不是指實體磁盤扇區的連續性。在這裡Linux作了一種簡化，它行之有效的基本前提是檔案在磁盤上是基本連續存儲的，沒有嚴重的碎片化。
2.流水線預讀
當程式在處理一批資料時，我們希望核心能在背景把下一批資料事先準備好，以便CPU和硬碟能流水線作業。Linux用兩個預讀視窗來跟蹤目前順序流的預讀狀态：current視窗和ahead視窗。其中的ahead視窗便是為流水線準備的：當應用程式工作在current視窗時，核心可能正在 ahead視窗進行異步預讀；一旦程式進入目前的ahead視窗，核心就會立即往前推進兩個視窗，并在新的ahead視窗中啟動預讀I/O。
3.預讀的大小
當确定了要進行順序預讀(sequential readahead)時，就需要決定合适的預讀大小。預讀粒度太小的話，達不到應有的性能提升效果；預讀太多，又有可能載入太多程式不需要的頁面，造成資源浪費。為此，Linux采用了一個快速的視窗擴張過程：
◆首次預讀： readahead_size = read_size * 2; // or *4
預讀視窗的初始值是讀大小的二到四倍。這意味着在您的程式中使用較大的讀粒度（比如32KB）可以稍稍提升I/O效率。
◆後續預讀： readahead_size *= 2;
後續的預讀視窗将逐次倍增，直到達到系統設定的最大預讀大小，其預設值是128KB。這個預設值已經沿用至少五年了，在目前更快的硬碟和大容量記憶體面前，顯得太過保守。比如西部資料公司近年推出的WD Raptor 猛禽 10000RPM SATA 硬碟，在進行128KB随機讀的時候，隻能達到16%的磁盤使用率（圖5）。是以如果您運作着Linux伺服器或者桌面系統，不妨試着用如下指令把最大預讀值提升到1MB看看，或許會有驚喜：
# blockdev –setra 2048 /dev/sda
當然預讀大小不是越大越好，在很多情況下，也需要同時考慮I/O延遲問題。
圖5 128KB I/O的資料定位時間和傳輸時間比重
重新發現順序讀
上一節我們解決了是否／何時進行預讀，以及讀多少的基本問題。由于現實的複雜性，上述算法并不總能奏效，即使是對于順序讀的情況。例如最近發現的重試讀(retried read)的問題。
重試讀在異步I/O和非阻塞I/O中比較常見。它們允許核心中斷一個讀請求。這樣一來，程式送出的後續讀請求看起來會與前面被中斷的讀請求相重疊。如圖6所示。
圖6 重試讀(retried reads)
Linux 2.6.22無法了解這種情況，于是把它誤判為随機讀。這裡的問題在于“讀請求”并不代表讀取操作實實在在的發生了。預讀的決策依據應為後者而非前者。最新釋出的2.6.23對此作了改進。新的算法以目前讀取的頁面狀态為主要決策依據，并為此新增了一個頁面标志位：PG_readahead，它是“請作異步預讀”的一個提示。在每次進行新預讀時，算法都會選擇其中的一個新頁面并标記之。預讀規則相應的改為：
◆當讀到缺失頁面(missing page)，進行同步預讀；
◆當讀到預讀頁面(PG_readahead page)，進行異步預讀。
這樣一來，ahead預讀視窗就不需要了：它實際上是把預讀大小和提前量兩者作了不必要的綁定。新的标記機制允許我們靈活而精确地控制預讀的提前量，這有助于将來引入對筆記本省電模式的支援。
圖7 Linux 2.6.23預讀算法的工作動态
另一個越來越突出的問題來自于交織讀(interleaved read)。這一讀模式常見于多媒體／多線程應用。當在一個打開的檔案中同時進行多個流(stream)的讀取時，它們的讀取請求會互相交織在一起，在核心看來好像是很多的随機讀。更嚴重的是，目前的核心隻能在一個打開的檔案描述符中跟蹤一個流的預讀狀态。因而即使核心對兩個流進行預讀，它們會互相覆寫和破壞對方的預讀狀态資訊。對此，我們将在即将釋出的2.6.24中作一定改進，利用頁面和pagecache所提供的狀态資訊來支援多個流的交織讀