李　勇　王　冉　馮　丹　施　展

1(中國電子科技集團公司第二十八研究所　南京　210007)2　　　(武漢光電國家實驗室(籌)(華中科技大學)　武漢　430074)

?

一種適用于異構(gòu)存儲系統(tǒng)的緩存管理算法

李勇1王冉1馮丹2施展2

1(中國電子科技集團公司第二十八研究所南京210007)2(武漢光電國家實驗室(籌)(華中科技大學)武漢430074)

(liyong01@hust.edu.cn)

當前數(shù)據(jù)中心廣泛采用虛擬化、混合存儲等技術(shù)以滿足不斷增長的存儲容量和性能需求，這使得存儲系統(tǒng)異構(gòu)性變得越來越普遍.異構(gòu)存儲系統(tǒng)的一個典型問題是由于設備負載和服務能力不匹配，使得存儲系統(tǒng)中廣泛使用的條帶等并行訪問技術(shù)難以充分發(fā)揮作用，導致性能降低.針對這一問題，提出了一種基于負載特征識別和訪問性能預測的緩存分配算法(access-pattern aware and performance prediction-based cache allocation algorithm, Caper)，通過緩存分配來調(diào)節(jié)不同存儲設備之間的IO負載分布，使得存儲設備上的負載和其本身服務能力相匹配，從而減輕甚至消除異構(gòu)存儲系統(tǒng)中的性能瓶頸.實驗結(jié)果表明，Caper算法能夠有效提高異構(gòu)存儲系統(tǒng)的性能，在混合負載訪問下，比Chakraborty算法平均提高了約26.1%，比Forney算法平均提高了約28.1%，比Clock算法平均提高了約30.3%,比添加預取功能的Chakraborty算法和Forney算法分別平均提高了約7.7%和17.4%.

異構(gòu)；存儲系統(tǒng)；緩存；預??；固態(tài)盤；性能預測

當前存儲系統(tǒng)廣泛存在存儲設備異構(gòu)性，主要有2個原因：1)新的存儲設備會因為擴容、替換故障設備等原因不斷加入存儲系統(tǒng)，隨著電子技術(shù)的快速發(fā)展，新存儲設備往往比舊存儲設備具有更高的性能.同時，因為存儲空間的碎片化、機械結(jié)構(gòu)等原因，磁盤的性能隨著使用時間而不斷降低.2)新型存儲設備不斷出現(xiàn)，比如當前存儲系統(tǒng)已經(jīng)廣泛使用固態(tài)盤，以固態(tài)盤為代表的新型存儲設備在性能等諸多方面和磁盤存在較大的差異.另外，隨著存儲系統(tǒng)規(guī)模的擴大，通過網(wǎng)絡連接存儲設備越來越普遍，比如存儲區(qū)域網(wǎng)絡(storage area network, SAN)[1]，存儲設備的性能因為網(wǎng)絡延遲變得更加不穩(wěn)定.

存儲系統(tǒng)一般使用條帶等技術(shù)將數(shù)據(jù)分布到多個存儲設備中，以提高數(shù)據(jù)訪問的并行性.在并行存儲系統(tǒng)中(如磁盤陣列)，一個較大的IO請求通常會被分成多個子請求，并同時訪問多個存儲設備.但是，在異構(gòu)存儲系統(tǒng)中，存儲系統(tǒng)的并行訪問技術(shù)存在著性能瓶頸問題.在異構(gòu)存儲系統(tǒng)中，IO請求在不同存儲設備的訪問延遲不一樣，性能較好的存儲設備的訪問延遲要小于性能較差的存儲設備的訪問延遲，因此，性能較差的存儲設備往往決定IO請求的最終性能.下面通過一個簡單的例子進一步闡釋這個問題，在這個例子中，同構(gòu)和異構(gòu)磁盤陣列都由4塊磁盤組成，如圖1所示.IO請求被分成4個子IO請求，并分別訪問陣列中的4個磁盤.在同構(gòu)磁盤陣列中，4個磁盤的訪問延遲是一樣的，都是5 ms，因此，IO請求在同構(gòu)磁盤陣列中的訪問延遲是5 ms.在異構(gòu)磁盤陣列中，3個磁盤的訪問延遲是5 ms，另外一個磁盤的訪問延遲是10 ms.因為不同磁盤的訪問延遲不一樣，所以異構(gòu)磁盤陣列必須等訪問延遲為10 ms的磁盤完成IO操作才能夠完成整個IO請求，因此，IO請求在異構(gòu)磁盤陣列中的訪問延遲是10 ms，大于同構(gòu)磁盤陣列的訪問延遲.從這個例子中可以發(fā)現(xiàn)：在異構(gòu)存儲系統(tǒng)中，性能最差的存儲設備是系統(tǒng)的性能瓶頸.

Fig. 1　Comparison of access delay.圖1　訪問延遲對比

針對異構(gòu)存儲系統(tǒng)的設備負載和其服務能力不匹配所導致的性能降低問題，本文提出了一種基于負載特征識別和訪問性能預測的緩存管理算法(access-pattern aware and performance prediction-based cache allocation algorithm).Caper算法的主要思想是通過優(yōu)化緩存調(diào)度來平衡IO請求在異構(gòu)存儲設備上的性能差異，減少甚至消除性能最差的存儲設備在異構(gòu)存儲系統(tǒng)中的性能瓶頸問題.Caper算法采用緩存分區(qū)策略，為了合理設置緩存分區(qū)的大小，Caper算法用CART(classification and regression trees)模型預測IO請求在存儲設備上的性能，并結(jié)合性能預測結(jié)果分析不同訪問特征負載的緩存需求.此外，Caper算法還改進時鐘緩存替換算法以進一步提高緩存效益(緩存效益是指單位緩存增減對性能的影響).實驗結(jié)果表明，和Clock算法[2]、Forney算法[3]以及Chakraborty算法[4]等相比，Caper算法整體上有較明顯的性能提升.

1　相關工作

緩存替換算法主要的出發(fā)點是利用數(shù)據(jù)訪問的局部性原理提高存儲系統(tǒng)性能.自從計算機體系結(jié)構(gòu)采用層次結(jié)構(gòu)以來，緩存替換算法一直都是研究的熱點領域.這里主要對當前的熱點算法進行介紹，并側(cè)重異構(gòu)存儲系統(tǒng)中的緩存算法研究.

有些研究利用應用隱示實現(xiàn)進一步提高緩存預取的準確率[5].也有研究利用數(shù)據(jù)熱度提高緩存命中率，羅德島大學的楊等人[6]提出了一種基于熱點的LPU算法，將訪問頻率擴展到訪問熱度，優(yōu)先保留與其他緩存塊相似度高同時訪問頻率也高的緩存塊，從而避免虛擬機或者云計算中的熱點數(shù)據(jù)的重復讀取.也有研究者利用緩存解決系統(tǒng)的某一方面問題，比如中國人民大學的柴等人[7]提出了PLC-Cache緩存算法，在重復數(shù)據(jù)刪除的存儲系統(tǒng)中，延長了固態(tài)盤的使用壽命，同時提高了性能.

也有很多工作研究異構(gòu)存儲系統(tǒng)中的緩存算法，比如威斯康星大學麥迪遜分校的Forney等人[3]根據(jù)累積延遲周期性調(diào)整緩存邏輯分區(qū)大小，實現(xiàn)不同設備之間的性能平衡.Chakraborty等人[4]則進一步改進Forney算法，通過一種基于有向無環(huán)圖的方法實現(xiàn)緩存邏輯分區(qū)的實時分配.其他的還比如ARC-H[8]，hStorage-DB[9]等算法都是通過緩存提高異構(gòu)存儲系統(tǒng)的性能.

2　問題分析

下面分析存儲設備異構(gòu)性對性能的影響，以及緩存在其中的作用.首先是沒有緩存時的情況，也就是說IO請求不經(jīng)過緩存直接訪問存儲設備，如圖2(a)所示.為方便描述，這里有n個存儲設備，分別標識為{D1，D2，…，Dn}，其訪問延遲分別為{T1，T2，…，Tn}.IO請求R在各個存儲設備上的子請求分別標識為{R1，R2，…，Rn}.性能最差的存儲設備將決定IO請求的訪問延遲T，可以用式(1)表示：

(1)

假設Tn為最大的訪問延遲，那么在異構(gòu)存儲系統(tǒng)中，大部分IO請求的訪問延遲都是Tn.

(2)

Fig. 2　The utility of cache for access performance.圖2　緩存對訪問性能的作用

3　算法描述

Fig. 3　The architeture of Caper algorithm.圖3　Caper算法結(jié)構(gòu)

Caper算法使用CART模型[10]建立存儲設備的性能預測模型.CART是一種被廣泛使用的機器學習方法，可用于性能預測，和其他機器學習方法一樣，CART首先需要在訓練階段建立性能預測模型.基于CART的性能預測模型可以形象地表示為一棵決策樹，如圖4所示.Caper算法使用4個屬性描述一個IO請求，分別是邏輯地址Li、請求大小Si、讀寫操作類型Ti，以及和上一個請求的邏輯地址距離Bi.因此，每個IO請求可以表示為一個4元組Li,Si,Ti,Bi.Caper算法的性能預測模型使用IO請求的訪問延遲表示最終的性能.

Fig. 4　Example of CART tree.圖4　CART樹的例子

CART采用自頂向下遞歸的分治方法構(gòu)造決策樹，假設訓練集為Z，根節(jié)點的判斷條件是Rj≤s，其中s是選中的分裂點.根據(jù)訓練集中的元素是否滿足判斷條件，將其進一步劃分為2個子集合：Z1(j;s)={R|Rj≤s}和Z2(j;s)={R|Rj>s}.然后分別在新分裂的2個子集合Z1和Z2中采用同樣的訓練方法，并進一步分裂集合.決策樹的層次隨著分裂點的增加而不斷增長，直到滿足停止條件，停止條件一般為決策樹的大小或設定的預測誤差閾值.最后，為每個葉子節(jié)點的子集合中的元素計算訪問延遲平均值，并作為該葉子節(jié)點的預測性能，文獻[10]指出平均值的預測誤差最小.

和傳統(tǒng)的性能預測模型相比，基于機器學習的CART性能預測模型具有開銷更低、適應性更強、構(gòu)建更方便等優(yōu)點.傳統(tǒng)方法通常在存儲系統(tǒng)或存儲設備的內(nèi)部結(jié)構(gòu)基礎上基于某種數(shù)學方法建立性能預測模型，如排隊論.但是這些方法往往受限于存儲廠商的信息公開程度，而且內(nèi)部結(jié)構(gòu)也會隨著存儲系統(tǒng)或設備的更新而不斷更新，因此，這種方法往往會存在一定的滯后性.相反，基于機器學習的CART模型是一種黑盒方法，不需要存儲系統(tǒng)或存儲設備的內(nèi)部結(jié)構(gòu)就可以建立性能預測模型，而且對于新系統(tǒng)或新設備，也只需要更新訓練集就能夠更新模型.此外，CART模型還充分考慮了應用負載特征對性能的影響，從而提高預測準確率.

3.2緩存需求分析

要想通過緩存分配減少性能最差存儲設備對整體性能的影響，首先必須要知道緩存大小和性能之間的關系，一方面方便計算提高瓶頸存儲設備性能所需的緩存數(shù)量，另一方面可以防止其他存儲設備因缺少緩存而成為新的性能瓶頸.Caper算法將應用負載分為3種不同的訪問特征，并分別分析在這3種負載訪問下緩存大小對IO請求訪問性能的影響.

3.2.1隨機訪問負載

對于隨機訪問的負載，一般難以捕獲其訪問規(guī)律，Caper算法使用基于概率的方法分析緩存大小對隨機訪問負載的影響.不失一般性，假設在隨機訪問負載中不同數(shù)據(jù)被訪問的概率相同并且相互獨立，那么隨機訪問負載的緩存命中率跟訪問區(qū)域和緩存大小相關.負載的訪問區(qū)域是指訪問請求序列中最小邏輯地址和最大邏輯地址之間的邏輯地址范圍，用Z表示隨機訪問負載的訪問區(qū)域.負載的訪問區(qū)域越大，就表示數(shù)據(jù)被重復訪問的概率越小，緩存命中率也會越低；相反，負載的訪問區(qū)域越小，就表示數(shù)據(jù)被重復訪問的概率越大，緩存命中率也會越高.當緩存大小為C時，隨機訪問負載的平均緩存命中率h≈CZ，那么一個存儲設備的平均訪問延遲Tavg為

(3)

其中,Tcache是IO請求訪問緩存的延遲，Tdisk是IO請求訪問存儲設備的延遲.因為緩存的訪問延遲通常遠低于存儲設備的訪問延遲，為了簡化分析，忽略緩存訪問延遲對性能的影響，那么存儲設備的平均訪問延遲可以簡化為Tavg=(1-h)×Tdisk.將隨機訪問負載的緩存命中率表達式h=CZ代入式(3)，就可以獲得存儲設備訪問延遲相等時的緩存分配方案，如式(4)所示：

(4)

其中,n是存儲設備的數(shù)量，Ci是第i個存儲設備分配的緩存大小，C是整個緩存的大小.

3.2.2順序訪問負載

Fig. 5　Example of prefetching operation.圖5　預取操作示例

(5)

其中,PR是IO請求的平均長度，每個存儲設備的預取緩存需求為Ci，Ci=Di+PR.在順序訪問負載中，為使訪問延遲相同，存儲設備之間的緩存分配如下：

(6)

在實際運行中，預取長度一般不會在一開始就被設置很大，而是隨著負載順序性增強而不斷增加，因此，存儲設備中的緩存分配也可以看作是對預取長度最大值的一個限制條件.

3.2.3循環(huán)負載

在循環(huán)負載中，順序訪問序列每隔一個循環(huán)周期重復出現(xiàn)，將循環(huán)負載中順序訪問序列的長度標記為Sloop.在分析緩存需求時，將循環(huán)負載分為順序訪問部分和隨機訪問部分，并分別參照前面順序訪問負載和隨機訪問負載的分析方法.在分析循環(huán)負載的順序訪問部分負載時，將緩存大小分2種情況：緩存充足和緩存不足.和順序訪問負載不同，循環(huán)訪問負載中發(fā)生預取緩存缺失的概率非常小，因為順序訪問部分的數(shù)據(jù)每隔一個循環(huán)周期重復出現(xiàn).如果緩存充足，那么順序訪問部分的請求數(shù)據(jù)可以全部預取在緩存中，因此，順序訪問部分負載的平均訪問延遲為

(7)

(8)

對于循環(huán)訪問負載中的隨機訪問部分，采用和隨機負載類似的分析方法.不同的是，由于循環(huán)訪問的負載特征，隨機訪問緩存的效益不如順序訪問緩存.因此，在緩存分配時，總是優(yōu)先保證順序訪問部分的緩存需求，隨機訪問部分負載的平均延遲為

(9)

3.3緩存替換策略

Caper算法還改進時鐘緩存替換策略，使其更加適應不同類型的負載混合訪問.和時鐘算法一樣，邏輯分區(qū)中的緩存塊被組織成一個環(huán)形鏈表，有一個指針執(zhí)行最老的緩存塊.和時鐘算法不同的是，Caper算法用計數(shù)器代替緩存塊的狀態(tài)標志位，并且根據(jù)負載類型為計數(shù)器設置不同的初值.如果是隨機訪問負載，那么這類緩存的計數(shù)器設置和時鐘算法一樣，都是為1;如果是順序訪問負載，那么這類緩存的計數(shù)器設置為0,因為順序訪問的緩存塊在短時間內(nèi)被再次訪問的概率非常低.如果是循環(huán)訪問負載，那么這部分緩存分2類處理.其中隨機部分和隨機負載一樣，其計數(shù)器初值都設置為1;順序訪問部分緩存的計數(shù)器設置為p，p是循環(huán)負載的循環(huán)周期長度.因為這部分數(shù)據(jù)每隔一個循環(huán)周期就被重復訪問，所以緩存命中率較高.當執(zhí)行緩存替換時，Caper算法從指針指向的緩存塊開始查找.如果該緩存塊的計數(shù)器大于0，那么將該計數(shù)器減1，然后查找下一個緩存塊，直到發(fā)現(xiàn)一個緩存塊的計數(shù)器為0才停止查找，并替換掉該緩存塊，然后將指針指向下一個未查找的緩存塊.因此，在改進的時鐘緩存替換策略中，循環(huán)訪問負載的順序訪問部分緩存塊被賦予較高的優(yōu)先級，并且循環(huán)周期長度越長其在緩存中的停留時間也越久，以保證這些緩存塊能夠在下次訪問中命中；隨機訪問負載的緩存塊優(yōu)先級次之，但是在緩存中的停留時間要遠少于循環(huán)訪問負載，這是因為循環(huán)訪問負載的重復訪問概率要遠遠高于隨機訪問負載；而順序訪問負載的緩存塊優(yōu)先級最低，這是因為順序訪問負載的重復訪問概率基本為0，因此，較早釋放能夠提高緩存整體效益.圖6是緩存替換策略示意圖，其中Sran表示隨機訪問，Sseq表示順序訪問，Sloop表示循環(huán)訪問，括號中的數(shù)字表示緩存塊計數(shù)器的初值.

Fig. 6　Replacement policy of Caper algorithm.圖6　Caper算法替換策略

3.4算法開銷分析

Caper算法的開銷主要包括2個部分：1)將Clock算法的狀態(tài)標志位擴展為n位的計數(shù)器，在算法中n=4 b.一般緩存以4 KB為單位，因此這部分的存儲空間開銷大約為0.012%，影響非常小.2)緩存邏輯分區(qū)的數(shù)據(jù)結(jié)構(gòu)，和緩存數(shù)量相比，與存儲設備一一對應的邏輯分區(qū)數(shù)量非常少，因此，這部分的存儲空間開銷可以忽略不計.

4　性能測試與分析

4.1實驗環(huán)境

在緩存仿真器DULO[11]中實現(xiàn)Caper算法，并且和存儲設備仿真器Disksim[12]組成完整的存儲系統(tǒng)仿真.DULO是韋恩州立大學(WSU)的Zhu等人[13]開發(fā)的緩存仿真器，并廣泛使用在緩存算法研究中.Disksim是卡內(nèi)基梅隆大學(CMU)并行數(shù)據(jù)實驗室(PDL)開發(fā)的磁盤仿真器，以高精度、配置靈活而著稱，并且被許多研究選作為實驗平臺[14]，通過加入微軟硅谷研究所Agrawal等人[15]開發(fā)的SSD模塊，Disksim也可以仿真固態(tài)盤.實驗選擇希捷公司的Cheetah9LP和Cheetah15k.5磁盤作為存儲設備，Cheetah9LP磁盤性能較差，Cheetah15k.5磁盤性能較好，具體配置如表1所示.此外，實驗的存儲設備還包括一款由8個4 GB大小的NAND閃存芯片組成的SLC類型固態(tài)盤，具體配置如表2所示，實驗用4塊存儲設備組成一個RAID-0.為了測試算法在不同條帶長度下的性能，實驗配置了5種不同條帶長度的RAID-0：4 KB，8 KB，16 KB，32 KB，64 KB.實驗模擬了2組不同的異構(gòu)磁盤陣列： 一組由1塊Cheetah9LP磁盤和3塊Cheetah15k.5磁盤組成，其中Cheetah9LP磁盤模擬性能較差的存儲設備，Cheetah15k.5磁盤模擬性能較好的存儲設備.另一組由1塊Cheetah15k.5磁盤和3塊固態(tài)盤組成，其中Cheetah15k.5磁盤模擬性能較差的存儲設備，固態(tài)盤模擬性能較好的存儲設備.實驗的緩存大小為64～512 MB不等，約為存儲設備容量的0.2%～1.4%.實驗中使用的應用負載包括Financial1，Web-Search1，TPC-C，Cscope，Gcc，Mplayer，Glimpse，F(xiàn)ile-Server.

Table 1　Parameters of Disks

Table 2　Parameters of SSD

為了測試算法在不同緩存大小時的性能，在5種不同緩存大小下運行實驗：64 MB，128 MB，256 MB，384 MB，512 MB.實驗選擇Clock緩存替換算法、Forney緩存替換算法和Chakraborty緩存替換算法，以及添加預取功能的Forney-prefetch緩存替換算法和Chakraborty-prefetch緩存替換算法作為Caper算法的對比算法.

4.2不同負載訪問時的性能

為了測試算法在不同負載訪問時的性能，將負載分為2組并分別測試.其中隨機訪問負載由Financial1，Web-Search1，TPC-C組成，順序訪問負載由Cscope，Gcc，Mplayer組成.算法運行在由不同性能磁盤組成的異構(gòu)磁盤陣列.

Fig. 7　Performance comparison under mixing of 　　　different performance disks.圖7　不同性能磁盤混合時的性能對比

圖7顯示算法在隨機訪問負載下的性能，因為預取算法主要針對順序訪問負載設計，所以對于隨機訪問負載只比較Caper算法、Chakraborty算法、Forney算法和Clock算法.如圖7所示，Caper算法的平均帶寬約為5.01 MBps(最高5.17 MBps)，分別超過Chakraborty算法平均約4.17%(最大4.65%)、Forney算法平均約4.46%(最大4.93%)和Clock算法平均約5.08%(最大5.50%).阻礙性能的主要原因是不同設備的訪問延遲不一致從而引入額外的等待延遲，導致增加數(shù)據(jù)在緩存中的停留時間，從而降低緩存命中率.特別是當緩存較小時，這種現(xiàn)象更加明顯.從實驗結(jié)果也證明這一點，在緩存大小只有64 MB時Caper算法的性能提升幅度最大.

圖8顯示算法在順序訪問負載下的性能，和隨機訪問負載相反，只有支持預取操作的緩存算法才能夠在順序訪問負載中受益，因此對于順序訪問負載只比較Caper算法、Chakraborty-prefetch算法，和Forney-prefetch算法.從圖8可以發(fā)現(xiàn)，當緩存較小時，Caper算法的性能略低于Chakraborty-prefetch算法和Forney-prefetch算法，分別約低1.2%和1.22%.這主要是因為為了平衡異構(gòu)存儲設備之間的性能差異，性能較差的存儲設備在緩存分配時具有較高的優(yōu)先級，但是在緩存較小時，過長的預取緩存容易在未被訪問之前就被淘汰出緩存，從而造成性能降低.當緩存逐漸增加時，Caper算法的效果逐漸顯現(xiàn)，這是因為當緩存變大后，預取緩存的停留時間也會增加，特別是性能較差的存儲設備的預取緩存更為明顯，這無疑顯著減少對其進行IO操作，從而獲得較大的性能提升.

Fig. 8　Performance comparison under mixing of disk and SSD.圖8　磁盤和固態(tài)盤混合時的性能對比

4.3測試不同緩存大小時的性能

圖9和圖10顯示Caper算法、Chakraborty-prefetch算法、Forney-prefetch算法、Chakraborty算法、Forney算法和Clock算法隨緩存大小變化的性能，其中圖9是6種算法在不同性能磁盤混合的異構(gòu)磁盤陣列中的性能，圖10是6種算法在磁盤與固態(tài)盤混合的異構(gòu)磁盤陣列中的性能.如圖9和圖10所示，Caper算法在大部分的情況下性能都要好于其他5個對比算法.在不同性能磁盤混合的陣列中，Caper算法的平均帶寬約為8.01 MBps(最高8.79 MBps)，分別超過Chakraborty-prefetch算法平均約9.08%(最大17.1%)、Forney-prefetch算法平均約13.6%(最大19.7%)、Chakraborty算法平均約31.0%(最大44.1%)、Forney算法平均約33.7%(最大47.3%)和Clock算法平均約36.1%(最大47.4%).在磁盤和固態(tài)盤混合的陣列中，Caper算法的平均帶寬約為50.3 MBps(最大54.4 MBps)，分別超過Chakraborty-prefetch算法平均約3.94%(最大6.99%)、Forney-prefetch算法平均約6.35%(最大11.6%)、Chakraborty算法平均約21.2%(最大28.8%)、Forney算法平均約22.5%(最大30.3%)和Clock算法平均約24.4%(最大30.8%).Caper算法、Chakraborty-prefetch和Forney-prefetch算法的性能要比其他3個算法高出不少，這是因為這3個算法同時對隨機訪問負載和順序訪問負載進行優(yōu)化，從而能夠更適應不同特征的負載混合訪問.與Chakraborty-prefetch和Forney-prefetch算法相比，Caper算法又針對異構(gòu)存儲系統(tǒng)的特征進行優(yōu)化，減少性能最差存儲設備對系統(tǒng)的影響，從而提高整體性能，特別是當緩存較為緊張的情況下提升更為明顯.

Fig. 10　Performance comparison under mixing of disk and SSD.圖10　磁盤和固態(tài)盤混合時的性能對比

當緩存從64 MB增加到128 MB時，Caper算法的性能提高幅度比較明顯.在不同性能磁盤混合的陣列中，Caper算法的性能提高幅度達到最大值1.16 MBps，比緩存大小為64 MB時的性能提高了17.7%.在磁盤和固態(tài)盤混合的陣列中，Caper算法的性能提高幅度達到最大值4.69 MBps，比緩存大小為64 MB時的性能提高了10.7%.當緩存大小從128 MB增加到512 MB時，Caper算法的性能提高幅度逐漸減少，這主要原因是：當緩存較小時，較長的預取緩存容易在未被訪問之前就被淘汰出緩存，導致緩存效益較低；當緩存增加時，預取緩存就會大幅度提高；當緩存增加到一定程度，就會逐漸趨于飽和，性能提升幅度逐漸降低.

4.4不同條帶長度時的性能

圖11和圖12顯示Caper算法、Chakraborty-prefetch算法、Forney-prefetch算法、Chakraborty算法、Forney算法和Clock算法隨條帶長度變化的帶寬分布，其中圖11是6種算法在不同性能磁盤混合的異構(gòu)磁盤陣列中的性能，圖12是6種算法在磁盤與固態(tài)盤混合的異構(gòu)磁盤陣列中的性能.

Fig. 11　Performance comparison under mixing of different performance disks.圖11　不同性能磁盤混合時的性能對比

Fig. 12　Performance comparison under mixing of disk and SSD.圖12　磁盤和固態(tài)盤混合時的性能對比

如圖11和圖12所示，Caper算法的性能在大部分情況下要好于其他5種對比算法.Caper算法在不同性能磁盤混合陣列中的平均帶寬約為7.97 MBps(最高8.43 MBps)，分別超過Chakraborty-prefetch算法平均約15.3%(最大17.1%)、Forney-prefetch算法平均約17.3%(最大19.7%)、Chakraborty算法平均約40.5%(最大44.0%)、Forney算法平均約43.6%(最大47.3%)和Clock算法平均約43.8%(最大47.5%).在磁盤和固態(tài)盤混合的陣列中，Caper算法的平均帶寬約為46.8 MBps(最大57.3 MBps)，分別超過Chakraborty-prefetch算法平均約3.76%(最大7.92%)、Forney-prefetch算法平均約4.71%(最大9.36%)、Chakraborty算法平均約24.3%(最大34.0%)、Forney算法平均約25.8%(最大35.9%)和Clock算法平均約26.2%(最大36.6%).

和其他算法相比，Caper算法的性能在不同條帶長度下雖然也有提升，但是提升幅度明顯較低，甚至在條帶大小為4 KB時，Caper算法的性能略低于Chakraborty-prefetch算法.和4.3節(jié)的實驗類似，和其他算法相比，Caper算法的性能提升主要來自于減少性能最差存儲設備對系統(tǒng)的影響.不同條帶的長度主要影響IO請求的并行性，但是相對于緩存的訪問性能，磁盤的訪問性能要低很多，所以算法隨條帶增加的性能提升比較小.特別是當條帶較小時，還會使得存儲設備上的子請求大小過小而降低讀寫的順序性，從而降低性能.

從圖11、圖12可以發(fā)現(xiàn)當條帶長度從4 KB增加到8 KB時，Caper算法的性能提高幅度都是最顯著的.以不同性能磁盤混合的陣列為例，Caper算法在條帶大小為8 KB時的性能比條帶大小為4 KB時的性能提高了10.7%.在磁盤和固態(tài)盤混合的陣列中，Caper算法在條帶大小為8 KB時的性能比條帶大小為4 KB時的性能提高了32.6%.在條帶長度從8 KB增加到64 KB的過程中，雖然性能也有提高，但是性能提高幅度都比條帶長度從4 KB增加到8 KB時的性能提高幅度小.在不同性能磁盤混合的陣列中，也是類似的結(jié)果.這主要是因為在緩存算法中一般以4 KB為單位進行數(shù)據(jù)讀寫，因此，當條帶大小只有4 KB時，單個IO請求同時訪問多個存儲設備的現(xiàn)象就比較頻繁.在異構(gòu)存儲系統(tǒng)中，因為IO請求在不同存儲設備上的訪問延遲不一樣，從而引入等待延遲.當條帶大小只要4 KB時，這種因為存儲系統(tǒng)異構(gòu)性而導致的等待延遲則非常嚴重，性能降低也比較明顯，因此，Caper算法能夠取得較大的性能提升.隨著條帶長度的增加，一個IO請求同時訪問多個存儲設備的現(xiàn)象將會逐漸減少，從而，Caper算法的性能提高幅度也逐漸減少.但是，因為Caper算法的緩存分配和替換策略可以減少IO請求在性能較差存儲設備上發(fā)生緩存缺失的概率，所以隨著條帶長度的增加，Caper算法的性能仍然能夠有所提高.

5　結(jié)束語

本文針對異構(gòu)存儲系統(tǒng)設計了一種緩存管理算法.Caper算法主要的出發(fā)點是解決異構(gòu)存儲系統(tǒng)中因設備負載和其服務能力不匹配造成的性能降低問題.Caper算法建立CART模型，并預測不同IO請求在存儲設備上的訪問性能；然后分析不同訪問特征負載的緩存需求，通過緩存的過濾作用，減少訪問性能較差的存儲設備上的負載，從而提高整體性能.同時，Caper算法利用不同訪問特征負載之間緩存效益不同這一負載特性，改進時鐘緩存替換算法，進一步提高緩存效益.實驗測試結(jié)果表明，Caper算法能夠有效提高異構(gòu)存儲系統(tǒng)的性能，其性能比Chakraborty算法、Forney算法和Clock算法有較大的提高，對添加預取功能的Chakraborty算法、Forney算法也有不少的提高.

[1]Brinkmann A, Salzwedel K, Scheideler C. Efficient, distributed data placement strategies for storage area networks[C]Proc of the 12th Annual ACM Symp on Parallel Algorithms and Architectures. New York: ACM, 2000: 119-128[2]Tanenbaum A S, Woodhull A S. Operating Systems Design and Implementation[M]. Translated by Wang Junhua. 3rd ed. Beijing: Publishing House of Electronics Industry, 2007 (in Chinese)(Tanenbaum A S, Woodhull A S. 操作系統(tǒng)設計與實現(xiàn)[M]. 王俊華, 譯. 3版. 北京: 電子工業(yè)出版社, 2007)[3]Forney B C, Arpaci-Dusseau A C, Arpaci-Dusseau R H. Storage-aware caching: Revisiting caching for heterogeneous storage systems[C]Proc of the 1st USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2002: 61-74[4]Chakraborty A, Singh A. Cost-aware caching schemes in heterogeneous storage systems[J]. The Journal of Supercomputing, 2011, 56(1): 56-78[5]Wu Chentao, He Xubin, Cao Qiang, et al. Hint-K: An efficient multilevel cache usingk-step hints[J]. IEEE Trans on Parallel and Distribution Systems, 2014, 25(3): 653-662[6]Ren J, Yang Q. A new buffer cache design exploiting both temporal and content localities[C]Proc of the 30th IEEE Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2010: 273-282[7]Liu J, Chai Y, Qin X, et al. PLC-Cache: Endurable SSD cache for deduplication-based primary storage[C]Proc of the 30th Int Conf on Mass Storage Systems and Technologies. Piscataway, NJ: IEEE, 2014: 1-12[8]Kim Y J, Kim J. ARC-H: Adaptive replacement cache management for heterogeneous storage devices[J]. Journal of Systems Architecture, 2012, 58(2): 86-97[9]Luo T, Lee R, Mesnier M, et al. hStorage-DB: Heterogeneity-aware data management to exploit the full capability of hybrid storage systems[J]. Proceedings of the VLDB Endowment, 2012, 5(10): 1076-1087[10]Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction[M]. 2nd ed. London: Springer, 2009: 295-335[11]Jiang S, Ding X, Chen F, et al. DULO: An effective buffer cache management scheme to exploit both temporal and spatial locality[C]Proc of the 4th Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2005: 101-114[12]Bucy J S, Schindler J, Schlosser S W, et al. The disksim simulation environment version 4.0 reference manual, cmu-pdl-08-101[R]. Pittsburgh, PA: Parallel Data Laboratory, 2008[13]Zhu Y, Jiang H. RACE: A robust adaptive caching strategy for buffer cache[J]. IEEE Trans on Computers, 2008, 57(1): 25-40[14]Wu Suzhen, Chen Xiaoxi, Mao Bo. GC-RAIS: Garbage collection aware and redundant array of independent SSDs[J]. Journal of Computer Research and Development, 2013, 50(1): 60-68 (in Chinese)(吳素貞, 陳曉熹, 毛波. GC-RAIS：一種基于垃圾回收感知的固態(tài)盤陣列[J]. 計算機研究與發(fā)展, 2013, 50(1): 60-68)[15]Agrawal N, Prabhakaran V, Wobber T, et al. Design tradeoffs for SSD performance[C]Proc of USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2008: 57-70

Li Yong, born in 1986. Received his PhD degree from Huazhong University of Science and Technology in 2014. Engineer in the 28th Research Institute of China Electronics Technology Group Corporation. His main research interests include cloud computing, massive storage system and cache algorithm.

Wang Ran, born in 1983. Engineer in the 28th Research Institute of China Electronics Technology Group Corporation. His main research interests include cloud computing, information system.

Feng Dan, born in 1971. Received her PhD degree from Huazhong University of Science and Technology. Professor and PhD supervisor. Senior member of China Computer Federation. Her main research interests include computer architecture, massive storage systems, and parallel file systems.

Shi Zhan, born in 1976. Received his PhD degree from Huazhong University of Science and Technology. Associate research fellow. His main research interests include storage management and big data.

A Cache Management Algorithm for the Heterogeneous Storage Systems

Li Yong1, Wang Ran1, Feng Dan2, and Shi Zhan2

1(The28thResearchInstituteofChinaElectronicsTechnologyGroupCorporation,Nanjing210007)2(WuhanNationalLaboratoryforOptoelectronics(HuazhongUniversityofScienceandTechnology),Wuhan430074)

The scale of storage system is becoming larger with the rapid increase of the amount of produced data. Along with the development of computer technologies, such as cloud computing, cloud storage and big data, higher requirements are put forward to storage systems: higher capacity, higher performance and higher reliability. In order to satisfy the increasing requirement of capacity and performance, modern data center widely adopts multi technologies to implement the dynamic increasing of storage and performance, such as virtualization, hybrid storage and so on, which makes the storage systems trend more and more heterogeneous. The heterogeneous storage system introduces multiple new problems, of which one key problem is the degradation of performance as load unbalance. That’s because the difference of capacity and performance between heterogeneous storage devices make the parallelism technologies hardly to obtain high performance, such as RAID, Erasure code. For this problem, we propose a caching algorithm based on performance prediction and identification of workload characteristic, named Caper (access-pattern aware and performance prediction-based cache allocation algorithm). The main idea of Caper algorithm is to allocate the load according to the capacity of the storage devices, which aims to alleviate the load unbalance or eliminate the performance bottleneck in the heterogeneous storage systems. The Caper algorithm is composed of three parts: prediction of performance for IO request, analysis of caching requirement for storage device, and caching replacement policy. The algorithm also classifies the application workload into three types: random access, sequential access, and looping access. In order to ensure high caching utility, the algorithm adjusts the size of logic cache partition based on the analysis of the caching requirement. Besides, in order to adapt to the heterogeneous storage system, the Caper algorithm improves the Clock cache replacement algorithm. The experimental results also show that the Caper algorithm can significantly improve the performance about 26.1% compared with Charkraborty algorithm under mixed workloads, 28.1% compared with Forney algorithm, and 30.3% compared with Clock algorithm. Even adding prefetching operation, Caper algorithm also improves the performance about 7.7% and 17.4% compared with Charkraborty algorithm and Forney algorithm respectively.

heterogeneous; storage system; cache; prefetch; solid state drives (SSDs); performance prediction

2015-02-15；

2015-08-11

國家“九七三”重點基礎研究發(fā)展計劃基金項目(2011CB302301)；國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2013AA013203)；國家自然科學基金項目(61025008，6123004，61472153)

施展(zshi@hust.edu.cn)

TP303

This work was supported by the National Basic Research Program of China (973 Program) (2011CB302301), the National High Technology Research and Development Program of China (863 Program) (2013AA013203), and the National Natural Science Foundation of China (61025008，6123004，61472153).