吳峰光：應用Linux學會預讀算法
Linux發(fā)展迅速，現(xiàn)在已經(jīng)趕上了微軟，怎樣才能更好的應用Linux呢？本文教會你預讀算法，讓Linux更易用。大家好，我將在報告里面簡單的回顧一下，在之前一兩年里面對預讀算法的改進，和I/O性能的影響。
眾所周知磁盤是非常不善于尋道的，尋道的開銷很大，所以要盡量減少小的IO，一般的應用程序會進行小的IO，它會進行一個小的緩沖區(qū)，然后進行度，比如說4K，4K，8K這樣的讀，然后內(nèi)核里面會進行優(yōu)化，把小的轉(zhuǎn)化成大的預讀。
這個預讀在下面這個圖里面可以看到，上面是應用程序進行的4K的讀，下面是內(nèi)核進行的16K大小的，或者更大的預讀。這個預讀的兩個主要的改進性能，一個是能夠改進吞吐量，通過把小的讀轉(zhuǎn)換成大的預讀實現(xiàn)的。
它通過把同步的讀轉(zhuǎn)換成異步的預讀，來實現(xiàn)對IO的等待。這個預讀的算法呢基本的原理是對應用程序的讀請求序列進行檢測，如果應用程序進行順序的讀，那就可以對它進行預讀。但是實際在實現(xiàn)中會有很多的IO的訪問模式，不僅是非常簡單的順序讀，還有可能有其他的變化形式，這樣就會對變化形式進行檢測。還有對抖動進行一些處理。
在接下來的PPT里面我主要介紹兩個預讀的算法。首先這些改進是對順序讀的檢測開始的，最簡單的順序讀就是一頁一頁的往前讀，所以它的判斷條件非常的簡單。后來有人發(fā)現(xiàn)有些情況下某些頁面會被重復讀取，這種情況呢發(fā)生在讀的請求跟也面的邊界不是對齊的情況下，這樣同一個頁面會被讀取多次，這種情況實際上仍然是順序讀，所以把判斷條件改進一下，加一個條件該可以應付了。后面的重次讀是更復雜的情況，這種情況發(fā)生在很多的網(wǎng)絡(luò)應用程序里面，像FTP，HTTP程序的應用。還有就是內(nèi)核的AIO，在這些IO里面他們會經(jīng)常提交一個比較大的讀請求，這個請求會只完成一部分之后就反回，在老的內(nèi)核里面，是以應用程序請求的頁面作為預讀的判斷條件，所以這個就會被搞迷糊了，在新的2.6.23里面做了改進，它以實際讀取的頁面，作為預讀算法的輸入，這樣下面這個圖就是一個非常好的順序的讀。
通過這個改進呢有些用戶就反映一些非常好的性能提升。像這里面是一個16級內(nèi)存的服務器，它用HTTP服務了1200個客戶端，這個在老的內(nèi)核里面和新的內(nèi)核里面，CPU的IO，IO降低了17％，網(wǎng)絡(luò)的帶寬，就是實際服務量反而提高了17％，同時對于磁盤來說，磁盤的利用率降低了26％，磁盤的帶寬增加的29％。
下面是另外一個HTTP的用戶報告，它說IO viter從80％降低到了20％。下面一個問題是預讀抖動，這會發(fā)生在當一個預讀的頁面，被讀者實際使用到之前就被換出了緩存，避免說有三個時間，一個讀者在進行一個頁面一個頁面的讀，然后發(fā)生了預讀抖動，發(fā)生預讀抖動之后所有頁面就完全被從緩沖里面拿出去了，老的內(nèi)核里面就會進行一個頁面一個頁面的IO，這里面紅色的就表示發(fā)生了磁盤IO，這個效率非常低，新的版本的情況就是新的窗口會被重新建立，一個IO是4K，這樣依次的遞增，馬上效率就恢復了。這個圖是發(fā)生預讀抖動之后的性能比較。
我們這個電腦用了128兆的內(nèi)存，在每一秒新開一個讀者，這個讀者讀的速度是100K每秒，逐漸逐漸的到了大概二三十秒鐘的時候，這個就發(fā)生了，這個時候網(wǎng)絡(luò)的流量在老的內(nèi)核是5兆每秒，新的流量是15兆每秒，提升了3倍的性能，IO的性能也提升了8倍。
這個圖是另外一種不太明顯的順序讀。由于Linux那些文件結(jié)構(gòu)的限制，只能處理一個文件一個流，它有兩個進程，分別打開兩個文件描述符進行讀的時候，這能夠被正確的檢測出來是順利讀，但是整個文件是被兩個流共享的，這樣就會發(fā)生相互干擾，下面這個圖大家就會看到，在內(nèi)核看來發(fā)生了很多的變化。這樣的話預讀就會被關(guān)閉，這會導致嚴重的性能下降。這個是內(nèi)部的文件結(jié)構(gòu)，每一個對應一個打開的FD。
在這種時候呢老的算法只有一個，他們就會向兩個不同的流，他們之間就沒有任何相關(guān)性，順序性就不能被檢測，改進的方法是利用一個特性，就是說任何一個頁面一旦被讀進內(nèi)存，就會被緩存一段時間，所以我們就可以去檢測之前的那個頁面，那個頁面是不是在緩存里面，如果是的話，就是一個順序的讀。我們知道是順序讀之后就會進行預讀了，然后就要解決一個進行多大預讀的問題。這個預讀大小就應該是安全的，預讀太大了就會發(fā)生預讀抖動，所以就有一些公式的推導來進行估計，這個估計是準確的，它的前提只有一個條件，就是流的數(shù)保持平穩(wěn)就可以了。前面兩個主要的問題解決之后，就可以得到預讀的算法了。
我們看下面這個圖，首先開始狀況是前面一系列的等候，就表示讀者已經(jīng)讀過了頁面，這個井號表示讀者正在讀的頁面，前面的下劃線表示預讀窗口，第一步我們先判斷這個地方有沒有頁面存在，如果這個頁面被緩存了，就說明這是一個順序的流，我們就可以進行預讀。為了進行預讀我們就需要知道從哪里開始從哪里結(jié)束。往前收收歷史的頁面，確定歷史頁面的數(shù)目，得到一個H，這個H把它反向的影射過來，在第四步就得到了END標志，那么有了開始和結(jié)束標準，我們就可以預讀了。
下面是三種預讀算法的比較。在老的內(nèi)核里面是只能進行一個FD，進行一個順序讀。一個文件差不多可以支持32個流，這32個流是可以改大的，但是改大了效率會比較低。根據(jù)上下文的預讀是基于區(qū)域的實現(xiàn)，所以效率并不受流數(shù)量的影響，所以可以支持流的數(shù)目是無窮多的。這種特性非常適合對于順序和隨機讀混合在一起的情況預讀，這種情況下每種隨機讀相當于新開了一個，所以在這個圖里面相當于有很多個，這種情況下是無法應付的。因為只內(nèi)處理32個缺省的。那么這個上下文預讀還可應用在科學計算里面。科學計算里面經(jīng)常對一個大的矩陣進行裂變力。它的間隔是相等的，但是不能改進讀的大小，IO的大小不能改進的話，這個性能還是受影響的，根據(jù)上小文的預讀是非常多的流。這些流在進行第一次裂變力還不知道，但是是存在的，首先會進行4頁面的預讀，然后進行8頁面的預讀，這個效率就提上去了。
再下面是FNS服務器的讀，這個客戶端一般會進行比較大的預讀，但是這個預讀會被拆分成比較小的請求，這個請求到達服務器的時間可能是混亂的，這服務器可能是SMP服務器，有多個CPU，這個運行很多個FNSD，這實際接收了某一個請求的話，會使混亂加劇，這樣也相當于讀請求是亂序的被執(zhí)行，或者是被并發(fā)的執(zhí)行的。在這種情況下在6.2.23里面新的預讀算法對這種混亂的讀更加不敏感，有比較好的適應性，所以對NFS讀性能提升是1.8倍，如果采用上下文預讀的話會達到2倍，會更好一點。
接下來是稀疏讀，稀疏讀是當一個文件里面一部分文件，可能是1/2被應用程序讀了，這樣可以改變順序性檢測條件，使稀疏讀得到支持。
這個是一個用戶服務器，它的特點就是跳8K的讀，然后再跳8K，然后再進行備份，這種就不能被老的內(nèi)核檢測出來，所以沒有預讀，在上下文預讀里面性能會很好，會有40到50倍的性能提升。
最后一般認為隨機讀是不能常用的，但是在現(xiàn)實生活中會有很熱門的區(qū)域，這些區(qū)域被隨機讀的次數(shù)非常多，也就是說它非常的密集，這樣預讀的命重率非常的高，這種情況下是可以進行預讀的，而前面講的基于上下文和稀疏的預讀的算法，在這里面可以使用。這個另外有一個用戶測試。在負載中呢，用戶是隨機的把一個大的文件加載到內(nèi)存里面去，從這兩條曲線里面可以看到，當前面部分比較稀疏讀的時候，性能經(jīng)常是持平的，沒有太大的明顯的變差，也沒有明顯的變好，但是當讀的密度增加的時候呢，會有3倍的性能的提升。
這種密集的算法可以在其他的數(shù)據(jù)庫當中應用，像播放曲目數(shù)據(jù)庫等等都有不同程度的提升。希望你能學會預讀算法。
【編輯推薦】
