一種針對混合存儲系統(tǒng)的高效緩存算法?

張 劍

（中國艦船研究設(shè)計中心 武漢 430064）

1 引言

隨著科技的發(fā)展，固態(tài)硬盤（Solid State Drive，SSD）［1～2］作為一種擁有高速I/O、低能耗等優(yōu)點的新型存儲介質(zhì)，在存儲系統(tǒng)中得到了廣泛應用。然而，固態(tài)硬盤相對機械硬盤（Hard Disk Drive，HDD）來說有著壽命相對較短以及小寫放大等問題，考慮到數(shù)據(jù)安全要素，一般不采用完全替代機械硬盤的方式使用固態(tài)硬盤，而采用固態(tài)硬盤作為緩存來構(gòu)建混合存儲系統(tǒng)，在提升性能的同時保證系統(tǒng)數(shù)據(jù)的持久安全性。

為了實現(xiàn)系統(tǒng)數(shù)據(jù)存儲的更好管理與I/O性能提升，本文針對內(nèi)存、固態(tài)硬盤、機械硬盤（實際使用中一般采用磁盤陣列）構(gòu)成的混合存儲系統(tǒng)，設(shè)計了一種兼顧時間局部性和空間局部性的緩存算法ODCA（Order Distance Cache Algorithm），并在特定的架構(gòu)下進行了該算法的性能測試。測試結(jié)果表明，ODCA算法可以顯著提高混合存儲系統(tǒng)的I/O效率，并且具有較強的穩(wěn)定性。

2 相關(guān)研究

2.1 混合緩存系統(tǒng)研究

國內(nèi)外有很多采用固態(tài)硬盤作為二級緩存構(gòu)建混合存儲系統(tǒng)的研究，典型的系統(tǒng)包括SieveS?tore系統(tǒng)［3］、OP-FCL系統(tǒng)［4］。

普渡大學的Pritchett等提出了SieveStore混合存儲系統(tǒng)，系統(tǒng)使用1個固態(tài)硬盤為多個機械硬盤服務器做緩存，并通過兩種不同的方案來識別服務器中的熱數(shù)據(jù)：離線、離散分配方法SieveStore-D，通過寫入日志的方式精確記錄一個時間段內(nèi)每個數(shù)據(jù)塊的訪問次數(shù)，當時間段結(jié)束后，在離線狀態(tài)下完成訪問次數(shù)的整合，把訪問次數(shù)超過門限的數(shù)據(jù)塊緩存到固態(tài)硬盤；在線、連續(xù)分配方法SieveS?tore-C，在一段時間內(nèi)，當對某個數(shù)據(jù)塊的訪問丟失連續(xù)達到一定次數(shù)后，則將它緩存到固態(tài)硬盤。

Yongseok Oh等提出了OP-FCL（Optimal Parti?tioning flash，最佳點閃存）混合存儲系統(tǒng)，系統(tǒng)使用固態(tài)硬盤作為機械硬盤的緩存，并根據(jù)系統(tǒng)的性能變化，合理劃分固態(tài)硬盤存儲空間，以達到性能最佳。該系統(tǒng)將固態(tài)硬盤存儲空間分為兩部分，一部分是數(shù)據(jù)緩存空間，用來存放數(shù)據(jù)，另一部分是預分配空間，用來垃圾回收。通過適當分配兩個空間的大小，提高系統(tǒng)的性能。預分配空間增大時，數(shù)據(jù)緩存空間減小，緩存性能下降，導致系統(tǒng)性能降低，但同時數(shù)據(jù)更新開銷減小，使得系統(tǒng)性能提升，如圖1所示，最終會存在一個最優(yōu)點使系統(tǒng)性能達到最優(yōu)。

2.2 緩存算法

內(nèi)存的緩存替換算法已經(jīng)相對成熟，例如LRU［5］、LFU［6］、MQ［7］等，但由于固態(tài)硬盤具有區(qū)別于內(nèi)存的特點，于是一些針對固態(tài)硬盤的緩存算法被提出。

Seon-yeong等提出一種 CFLRU［8］（Clean-First LRU）緩存算法。如圖2所示，算法將鏈表分為工作區(qū)和淘汰區(qū)兩個區(qū)域，工作區(qū)管理最近被訪問的頁，淘汰區(qū)管理即將被淘汰的頁。當發(fā)生替換操作時，算法會在淘汰區(qū)中優(yōu)先選擇干凈的頁進行淘汰，如果淘汰區(qū)不存在干凈的頁，那么就把LRU端的臟頁作為替換頁。

圖2 CFLRU緩存算法示意圖

Hoyoung Jung等基于CFLRU算法進行改進，設(shè)計了 LRU-WSR［9～10］（LRU-Write Sequence Reorder?ing）算法。如圖3所示，算法將緩存頁劃分為三種類型：干凈頁，冷臟頁和熱臟頁。臟頁通過一個冷熱標識進行冷熱劃分。發(fā)生淘汰時，判別LRU端的頁類型：若為干凈頁或冷臟頁，直接淘汰；若為熱臟頁，則將標記為冷臟頁，并把該頁插入MRU端，即多給熱臟頁一次被保留的機會。

圖3LRU-WSR緩存算法示意圖

3 算法設(shè)計

為了提高緩存的命中率，針對內(nèi)存和固態(tài)硬盤兩級緩存，ODCA緩存算法設(shè)計均采用盡可能滿的方式，以確保更多的數(shù)據(jù)留在緩存中，提高系統(tǒng)性能。ODCA緩存算法對時間局部性和空間局部性均進行考慮，并結(jié)合LRU和LFU的特性，采用一個熱度值來表示數(shù)據(jù)頁的熱度。系統(tǒng)從運行時開始記錄累計有多少數(shù)據(jù)頁提取到緩存中，該值命名為S值（Sum），并對緩存中的每個數(shù)據(jù)頁記錄如下信息：

1）O值（Order）：該頁最近一次被訪問時系統(tǒng)的S值。

2）D值（Distance）：該頁最近一次被訪問時系統(tǒng)的S值與該頁當前O值之差，若該頁剛被提取到緩存中，則D值為無窮大。

圖4為O值及D值的一個示例，假設(shè)初始狀態(tài)（S=0）下緩存中無數(shù)據(jù)，系統(tǒng)依次讀取1、2、3、4、3、1、5頁。

圖4 O值D值示意圖

顯然，對于數(shù)據(jù)頁來說，O值是反映數(shù)據(jù)最近是否被訪問的度量，數(shù)值越大，說明其越近被訪問；D值是反映數(shù)據(jù)訪問頻度的度量，數(shù)值越小，說明其越頻繁被訪問。ODCA算法將二者相結(jié)合，使用權(quán)值公式來對緩存數(shù)據(jù)的冷熱進行判斷，得出每一個數(shù)據(jù)頁的熱度值。熱度值的計算方式如式（1）所示。

其中k為系數(shù)，用于調(diào)整LFU和LRU之間的權(quán)重關(guān)系；udisk表示數(shù)據(jù)頁存儲設(shè)備在系統(tǒng)中所占的權(quán)值，通過這一值的設(shè)定，可以將熱數(shù)據(jù)緩存算法和多個固態(tài)硬盤之間的負載算法相結(jié)合，負載重的固態(tài)硬盤IO帶寬較小，存儲在其上的數(shù)據(jù)頁可以擁有較低的緩存權(quán)值，從而降低設(shè)備的I/O請求數(shù)量，提高系統(tǒng)整體性能。udisk值設(shè)定如表1所示。

表1 固態(tài)硬盤權(quán)重設(shè)定表

4 性能測試與結(jié)果分析

4.1 測試系統(tǒng)架構(gòu)

測試系統(tǒng)的緩存由內(nèi)存與固態(tài)硬盤組成，內(nèi)存進行一級緩存，固態(tài)硬盤進行二級緩存?？紤]到機械硬盤和固態(tài)硬盤具有不同的存儲特性，將內(nèi)存劃分成兩個區(qū)域（機械硬盤內(nèi)存區(qū)和固態(tài)硬盤內(nèi)存區(qū)）分別進行管理。測試系統(tǒng)的結(jié)構(gòu)及數(shù)據(jù)流向如圖5所示。整個系統(tǒng)中數(shù)據(jù)頁的熱度值均采用ODCA算法進行計算。

圖5 測試系統(tǒng)的架構(gòu)及數(shù)據(jù)流向

機械硬盤內(nèi)存區(qū)只緩存機械硬盤中的數(shù)據(jù)。數(shù)據(jù)在機械硬盤內(nèi)存區(qū)緩存期間，若其熱度值達到了事先定義好的閾值，則將其提升至固態(tài)硬盤內(nèi)存區(qū)；在機械硬盤內(nèi)存區(qū)空間不夠而發(fā)生數(shù)據(jù)淘汰時，選擇熱度值較低的數(shù)據(jù)，如果其為干凈數(shù)據(jù)，則直接淘汰，如果其為臟數(shù)據(jù)，則將數(shù)據(jù)同步到機械硬盤后淘汰。

固態(tài)硬盤內(nèi)存區(qū)緩存固態(tài)硬盤中的數(shù)據(jù)以及從機械硬盤內(nèi)存區(qū)提升上來的數(shù)據(jù)。數(shù)據(jù)塊在固態(tài)硬盤內(nèi)存區(qū)緩存期間，完成對數(shù)據(jù)塊的冷熱區(qū)分。發(fā)生數(shù)據(jù)淘汰時，固態(tài)硬盤內(nèi)存區(qū)將小寫合并成大寫后再一次性寫入固態(tài)硬盤，減少對固態(tài)硬盤的寫操作，從而延長固態(tài)硬盤的壽命。

4.2 系統(tǒng)實現(xiàn)

系統(tǒng)實現(xiàn)基于開源的 iSCSI［11～12］代碼。iSCSI是當前存儲界最熱門的技術(shù)之一，其使用TCP/IP協(xié)議，本質(zhì)上就是用廣域網(wǎng)仿真了一個常用的高性能本地存儲總線，從而創(chuàng)建了一個存儲局域網(wǎng)。系統(tǒng)實現(xiàn)主要包含以下模塊：固態(tài)盤內(nèi)存區(qū)緩存模塊、機械硬盤內(nèi)存區(qū)緩存模塊、固態(tài)盤緩存模塊、機械硬盤內(nèi)存區(qū)數(shù)據(jù)提升模塊、機械硬盤讀寫模塊。

4.3 測試環(huán)境

iSCSI的客戶端、服務端均在Linux服務器上進行部署。具體測試環(huán)境配置如表2所示。

表2 測試環(huán)境配置

4.4 測試對象與數(shù)據(jù)集

采用blktrace工具集進行測試。blktrace是一個針對Linux內(nèi)核中塊設(shè)備I/O層的跟蹤工具。具體測試時，采用blktrace工具集中的btreply回放工具對微軟公司服務器的一周實際請求trace進行回放測試。由于真實trace時間過長，測試過程中采用64倍加速的方式進行回放測試。blktrace測試配置如表3所示，測試trace的基本情況如表4所示。

表3 blktrace測試配置

表4 測試trace基本情況

4.5 測試結(jié)果分析

4.5.1 每小時平均IOPS性能測試

每小時平均IOPS測試結(jié)果如圖6、圖7、圖8所示。

圖6 性能測試結(jié)果（rsrch，每小時平均IOPS）

圖7 性能測試結(jié)果（usr，每小時平均IOPS）

圖8 性能測試結(jié)果（web，每小時平均IOPS）

可以看出，在擁有不同I/O訪問特點的多種trace下，混合存儲系統(tǒng)在ODCA緩存算法下每小時平均IOPS大部分時間都要高于LRU及LFU緩存算法，印證了ODCA緩存算法的高命中率和穩(wěn)定性。

4.5.2 總請求IOPS性能測試

總請求IPOS測試結(jié)果如圖9、圖10、圖11、圖12所示。其中圖9、圖10、圖11表示的值為從系統(tǒng)啟動運行到每一個測試時間點（每個小時一次）的總請求IOPS；圖12表示的值為總測試時間（168h）內(nèi)的總請求IOPS。

圖9 性能測試結(jié)果（rsrch，總請求IOPS）

圖10 性能測試結(jié)果（usr，總請求IOPS）

圖11 性能測試結(jié)果（web，總請求IOPS）

圖12 性能測試結(jié)果（總測試時間內(nèi)總請求IOPS）

從圖9、圖10、圖11可以看出，系統(tǒng)運行一段時間后混合緩存系統(tǒng)在ODCA緩存算法下總請求IOPS即優(yōu)于LRU和LFU緩存算法，而且隨著時間推移這種優(yōu)勢越發(fā)明顯。從圖18可以看出，對于rsrch、usr、web三種trace，混合緩存系統(tǒng)在ODCA緩存算法下總請求IOPS分別比LRU緩存算法提高了10.89%、27.27%、20.70%，分別比LFU緩存算法I/O性能提高了1.82%、21.74%、40%。

4.5.3 測試結(jié)果分析

rsrch的I/O訪問特點是對熱數(shù)據(jù)的短時間高頻次訪問，對于這類數(shù)據(jù)訪問，ODCA算法性能高于LRU算法，與LFU算法基本相同。

web的I/O訪問特點是熱數(shù)據(jù)的訪問間隔較長，對于這類數(shù)據(jù)訪問，ODCA性能大幅度高于LRU和LFU。

綜上所述，相對于經(jīng)典的LRU和LFU緩存算法，ODCA緩存算法能更大程度提高混合緩存系統(tǒng)I/O性能，且對不同特點的I/O請求都有較好的適應性。

5 結(jié)語

隨著大數(shù)據(jù)時代的發(fā)展，人們對存儲性能的要求越來越高，固態(tài)硬盤作為一種高性能緩存介質(zhì)，在各類存儲系統(tǒng)中得到越來越廣泛的應用。本文針對內(nèi)存、固態(tài)硬盤、機械硬盤構(gòu)成的混合存儲系統(tǒng)，提出了一種結(jié)合LRU和LFU算法優(yōu)點、綜合考慮數(shù)據(jù)時間局部性和空間局部性的ODCA緩存算法。通過測試發(fā)現(xiàn)，對于不同特點的I/O請求，ODCA緩存算法均優(yōu)于LRU和LFU算法。