張 劍

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

1 引言

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

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

2 相關(guān)研究

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

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

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

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

2.2 緩存算法

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

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

圖2 CFLRU緩存算法示意圖

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

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

3 算法設(shè)計(jì)

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

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

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

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

圖4 O值D值示意圖

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

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

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

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

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

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

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

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

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

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

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

4.3 測(cè)試環(huán)境

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

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

4.4 測(cè)試對(duì)象與數(shù)據(jù)集

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

表3 blktrace測(cè)試配置

表4 測(cè)試trace基本情況

4.5 測(cè)試結(jié)果分析

4.5.1 每小時(shí)平均IOPS性能測(cè)試

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

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

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

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

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

4.5.2 總請(qǐng)求IOPS性能測(cè)試

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

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

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

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

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

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

4.5.3 測(cè)試結(jié)果分析

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

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

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

5 結(jié)語(yǔ)

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