一種適用于異構存儲系統的緩存管理算法

李　勇　王　冉　馮　丹　施　展

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

?

一種適用于異構存儲系統的緩存管理算法

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

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

(liyong01@hust.edu.cn)

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

異構；存儲系統；緩存；預取；固態盤；性能預測

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

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

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

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

1　相關工作

緩存替換算法主要的出發點是利用數據訪問的局部性原理提高存儲系統性能.自從計算機體系結構采用層次結構以來，緩存替換算法一直都是研究的熱點領域.這里主要對當前的熱點算法進行介紹，并側重異構存儲系統中的緩存算法研究.

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

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

2　問題分析

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

(1)

假設Tn為最大的訪問延遲，那么在異構存儲系統中，大部分IO請求的訪問延遲都是Tn.

(2)

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

3　算法描述

Fig. 3　The architeture of Caper algorithm.圖3　Caper算法結構

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

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

3.2緩存需求分析

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

3.2.1隨機訪問負載

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

(3)

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

(4)

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

3.2.2順序訪問負載

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

(5)

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

(6)

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

3.2.3循環負載

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

(7)

(8)

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

(9)

3.3緩存替換策略

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

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

3.4算法開銷分析

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

4　性能測試與分析

4.1實驗環境

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

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%).阻礙性能的主要原因是不同設備的訪問延遲不一致從而引入額外的等待延遲，導致增加數據在緩存中的停留時間，從而降低緩存命中率.特別是當緩存較小時，這種現象更加明顯.從實驗結果也證明這一點，在緩存大小只有64 MB時Caper算法的性能提升幅度最大.

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

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

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

圖9和圖10顯示Caper算法、Chakraborty-prefetch算法、Forney-prefetch算法、Chakraborty算法、Forney算法和Clock算法隨緩存大小變化的性能，其中圖9是6種算法在不同性能磁盤混合的異構磁盤陣列中的性能，圖10是6種算法在磁盤與固態盤混合的異構磁盤陣列中的性能.如圖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%).在磁盤和固態盤混合的陣列中，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個算法同時對隨機訪問負載和順序訪問負載進行優化，從而能夠更適應不同特征的負載混合訪問.與Chakraborty-prefetch和Forney-prefetch算法相比，Caper算法又針對異構存儲系統的特征進行優化，減少性能最差存儲設備對系統的影響，從而提高整體性能，特別是當緩存較為緊張的情況下提升更為明顯.

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

當緩存從64 MB增加到128 MB時，Caper算法的性能提高幅度比較明顯.在不同性能磁盤混合的陣列中，Caper算法的性能提高幅度達到最大值1.16 MBps，比緩存大小為64 MB時的性能提高了17.7%.在磁盤和固態盤混合的陣列中，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種算法在不同性能磁盤混合的異構磁盤陣列中的性能，圖12是6種算法在磁盤與固態盤混合的異構磁盤陣列中的性能.

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

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

如圖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%).在磁盤和固態盤混合的陣列中，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節的實驗類似，和其他算法相比，Caper算法的性能提升主要來自于減少性能最差存儲設備對系統的影響.不同條帶的長度主要影響IO請求的并行性，但是相對于緩存的訪問性能，磁盤的訪問性能要低很多，所以算法隨條帶增加的性能提升比較小.特別是當條帶較小時，還會使得存儲設備上的子請求大小過小而降低讀寫的順序性，從而降低性能.

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

5　結束語

本文針對異構存儲系統設計了一種緩存管理算法.Caper算法主要的出發點是解決異構存儲系統中因設備負載和其服務能力不匹配造成的性能降低問題.Caper算法建立CART模型，并預測不同IO請求在存儲設備上的訪問性能；然后分析不同訪問特征負載的緩存需求，通過緩存的過濾作用，減少訪問性能較差的存儲設備上的負載，從而提高整體性能.同時，Caper算法利用不同訪問特征負載之間緩存效益不同這一負載特性，改進時鐘緩存替換算法，進一步提高緩存效益.實驗測試結果表明，Caper算法能夠有效提高異構存儲系統的性能，其性能比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. 操作系統設計與實現[M]. 王俊華, 譯. 3版. 北京: 電子工業出版社, 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：一種基于垃圾回收感知的固態盤陣列[J]. 計算機研究與發展, 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

國家“九七三”重點基礎研究發展計劃基金項目(2011CB302301)；國家“八六三”高技術研究發展計劃基金項目(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).