面向SSD/HDD 混合存儲的動態緩存調度算法DRC

劉秉煦，張文軍，李小勇

面向SSD/HDD 混合存儲的動態緩存調度算法DRC

劉秉煦，張文軍，李小勇

云計算與大數據的發展，對存儲系統的性能提出了越來越高的要求。這些系統中的任務具有高并發度特征，使得存儲系統的數據訪問呈現隨機化。SSD具有優異的隨機讀寫性能，但其寫入次數受到限制，成本高昂，因此，基于SSD-HDD的混合系統成為存儲技術發展的主要方向。面向SSD-HDD混合存儲提出了一種基于動態替換代價的緩存調度算法（DRC），以請求中的熱點數據以及替換數據的代價作為緩存替換依據，不僅有效地提高了緩存命中率，而且，通過減少磁盤隨機寫操作提升了系統的整體性能。實驗結果表明，在高并發讀寫的場景下，DRC算法相對于LRU或FIFO算法緩存命中率提升可達11.6%，IO速度最多提升16.7%，在各種緩存大小條件下均取得了顯著的性能提升。

混合存儲系統；固態盤；緩存替換算法；熱點識別

0 引言

云計算與大數據的發展，使數據呈現爆炸性增長，對存儲系統的性能提出了嚴峻挑戰。特別是基于虛擬機的云計算系統中，存儲設備往往由很多個虛擬機所共享，導致數據讀寫訪問呈現隨機化和碎片化的特征，對存儲系統的隨機讀寫性能提出了更高的要求。

目前，磁盤仍然是存儲系統所使用的主要存儲器件，雖然其容量仍然依摩爾定律快速發展，但由于受到磁頭移動的機械特性限制，其隨機訪問性能早已到達瓶頸，在過去的幾十年里未有顯著提升。近年來興起的固態硬盤SSD具有優異的隨機訪問性能、低能耗和體積小等優點，受到了廣泛關注。閃存設備與磁盤的特性有著明顯區別。首先，閃存設備沒有磁頭，而磁頭尋道是磁盤IO過程中耗時最多的部分。其次，閃存設備在性能和能耗方面都呈現明顯的讀寫不對稱特征，NAND閃存的寫操作比讀操作的耗時高近6倍。第三，閃存設備中存儲結構分為頁面與塊，一個塊由多個頁面組成。閃存的寫操作不支持直接更新，在數據所在的閃存頁被擦除之前，新數據無法寫入此頁面。考慮到擦除操作的能耗與耗時約為讀操作的兩倍，擦除操作以塊為單位進行。在擦除操作完成之前，閃存塊中會有一定數量的“碎片空間”無法使用。最后，閃存設備顆粒有擦除次數的限制，需要使用垃圾回收策略使各個顆粒的磨損程度均衡[1]。

本文提出了一種新的基于動態替換代價策略的緩存調度算法DRC（Dynamic Replacement Cost），該算法綜合考慮了訪問次數、訪問頻率、數據塊是否“臟”等特性，計算出數據塊的替換代價，并基于替換代價來調度緩存，從而提高了數據讀寫的命中率，進而提升了混合存儲系統的性能。通過大量實驗，對算法進行了優化，通過犧牲算法的部分準確性降低了算法復雜度，從而提高了系統整體性能，達到了提高整體命中率、提高I/O速度和延長SSD使用壽命的效果。

1 混合存儲相關研究

研究人員對于固態硬盤SSD的使用方式進行了大量的研究，例如PCIE閃存卡、由固態硬盤組成的Raid卡和相關的文件系統FAWN等。Facebook的混合存儲系統Flashcache是固態硬盤SSD應用的典范，通過IO調度將數據請求分發到固態硬盤SSD和機械磁盤HDD，利用SSD極大提升了數據的讀寫性能，較小的SSD空間就能獲得較大的性能提升。

由于閃存與磁盤的訪問特性區別較大，內存替換中廣泛使用的FIFO，LRU算法在混合存儲中性能不盡如人意。韓國科技技術大學的Seon-Yeong Park等人針對閃存寫操作代價高的特點在LRU算法的基礎上，提出了CFLRU算法。LRU算法將緩存中的數據按照訪問次數分為兩組，訪問次數較高的按照LFU算法排序，訪問次數較低的按照LRU排序。當替換操作發生時，優先替換LRU隊列中的非“臟”數據。但CFLRU算法也有著明顯的缺陷，當系統運行一段時間后，LRU隊列中保留了大量臟數據，造成調度進緩存中的干凈數據很快被換出，影響了緩存的命中率。

Hoyoung Jung等針對CFLRU的這些缺陷對其進行了改善，并提出了LRU-WSR算法。LRU-WSR在CFLRU的基礎上為緩存中的每個數據增加了Cold Flag屬性來區分冷熱數據。數據調入緩存時，將其Cold Flag設置為冷，有請求命中該數據時，Cold Flag設置為熱。當緩存空間不足時，LRU-WSR算法將在LRU隊列尾部向頭部檢索，若數據頁面不為“臟”，直接替換出緩存。若數據為“臟”則檢查Cold Flag，如果Cold Flag為冷，則換出緩存；Cold Flag為熱時，將Flag設置為冷，并繼續向頭部檢索。LRU-WSR一定程度上解決了CFLRU的緩存命中率問題，獲得了較好的性能提升。

德國凱瑟斯勞騰大學的Yi Ou等人，根據閃存設備以塊數為單位據擦除的性質，設計了CFDC算法。Yi Ou認為，進入緩存時間相近的數據頁面更有可能是順序請求，而閃存的順序讀寫性能與磁盤的差別較小，緩存中應盡可能多的保留隨機請求的數據。基于這個思想，CFDC算法將緩存分為多個緩存集合，并為每個數據頁面標記序號記錄其進入緩存的順序，通過比較各個集合中數據頁面序號，選擇出一個請求連續性最高的緩存集合，將其中所有數據替換出緩存。CFDC算法充分利用了閃存的擦除特性，減少了系統的能耗。

2 基于替換代價的緩存替換算法DRC

以閃存設備作緩存的系統中發生數據頁面替換時，需將該數據頁面置為無效，在另一個空白頁面中寫入新數據。由于閃存的擦除操作能耗較高，代價較大，擦除操作往往以塊為單位，所以被置為無效的頁面在其所在的數據塊擦除后才能釋放空間。若替換掉的數據為“臟”，替換代價將會大幅度上升[2]。在放棄該頁面之前，需將頁面中的數據寫入磁盤，才能將閃存頁面置為無效等待回收。所以在混合存儲的緩存調度算法中，選擇“臟”頁面作為被替換頁面時需要十分謹慎。如何減少閃存寫操作和擦除操作成為提高閃存性能亟待解決的問題，緩沖區管理算法的優劣直接影響整個的性能、效率以及SSD的使用壽命。

2.1 系統設計

本文采用的混合存儲系統基于Linux 的Device Mapper架構而實現，如圖1所示：

圖1 數據讀流程

Device Mapper將多個設備映射為一個虛擬設備，此虛擬設備接收上層的IO請求，并通過映射表將請求分發到物理設備中。系統的存儲設備分高速設備和低速設備兩種。利用緩存替換算法，系統通過將頻繁訪問的數據緩存到高速設備上，使用較小的存儲空間即可對整體的性能進行大幅度的提升。

混合存儲系統的讀寫操作的流程如圖2所示：

圖2 數據寫流程

當讀請求命中后，若緩存設備正忙，系統會將請求的內容加入緩存設備的請求隊列中。若未命中且緩存有空閑空間時，從磁盤讀數據到內存中并異步的寫入緩存設備。若請求未命中且緩存設備無空閑空間，系統會調用緩存清理模塊，根據設定的算法異步地將部分數據清理出緩存，并將請求直接發往磁盤，進行磁盤讀操作。 寫操作進行時，如果請求命中，需要確認被寫數據是否為“臟”，若不為“臟”，則將數據塊標記為“臟”再進行寫操作；如果寫請求未命中，先將數據寫入緩存設備中即可返回寫成功。

“臟”數據被替換到慢速設備（磁盤）時，需要先將“臟”數據頁面寫入磁盤，再將緩存設備（SSD）中的對應數據頁面置為無效，待此頁面所在的塊擦除完成后釋放存儲空間。相對于未被修改的干凈數據頁面，增加了一次寫磁盤的操作。在高并發的情境下，此操作與其他磁盤讀寫操作被分割為隨機寫，由于此數據存在被替換后很快被再次訪問的可能，系統需要重新調度該頁面到緩存設備中，一次對“臟”頁的錯誤預測的代價要遠遠大于干凈頁面未命中的代價，將“臟”頁替換回磁盤的操作也將成為整個系統的瓶頸。

2.2 算法設計

通過對負載請求記錄的研究我們發現，數據的訪問符合“二八”原理[3]，即80%請求所訪問的數據占總數據的20%，Web搜索場景下90%請求所訪問的數據甚至占到總數據10%。不僅如此，數據的訪問熱點還隨著時間遷移[4][5]。例如新浪微博的熱門話題，每天的關注點不同，最終反映在存儲系統中就是：某些數據塊的總訪問次數并不突出，但是，在一段時間內會呈現爆炸性的增長，隨后又迅速降低。Facebook提出超過3天的數據被訪問的可能性會大大降低。基于以上分析，我們認為緩存替換算法必須考慮到數據的熱點遷移與訪問頻率的變化[6]，并提出了動態代價替換算法DRC。

本算法以在緩存中的數據頁面的替換代價作為主要的排序標準，不但考慮熱點的遷移，而且新增熱點數據能夠更好的響應。每一個緩存集合由兩個隊列組成，分別是頻繁訪問隊列和偶爾訪問隊列。當數據頁面調度入緩存中時，先將其加入緩存的偶爾訪問隊列中，偶爾訪問隊列使用LRU算法排序。當偶爾訪問隊列中的數據塊被訪問時，將其訪問次數增加1，若達到了遷移閾值，就將其加入頻繁訪問隊列的隊尾，并將訪問次數清零。由于熱點數據會隨著時間遷移，所以每隔時間T_half，將兩個隊列中的數據塊被訪問次數左移一位，避免在過去時間內某個數據塊的訪問次數積累較多，造成新的熱點數據被替換的情況。在計算替換代價時，如果某個緩存中數據為“臟”，此數據塊的替換代價即為d_cost * ref_count；否則此數據塊的替換代價為訪問次數ref_count。將緩存內所有的數據替換代價計算后，根據替換代價進行排序。

算法設計初期提出的思想是通過“半衰”時間來追蹤熱點數據，通過數據是否為“臟”來計算替換代價，將工作隊列加鎖，根據替換代價為整個工作隊列進行排序。進行試驗并分析后，此算法雖然大幅度提高了整體的命中率和緩存替換次數，但系統性能的提升不明顯。因為緩存隊列的排序是系統的瓶頸，在之后的算法設計中，我們降低了排序算法的復雜度，犧牲了部分排序的精確度獲得了更大的性能提升。

根據數據的訪問特性，我們挑選出替換代價最高的前1/P，其余的數據按照LRU方式排列。排序完成后，如果需要將一定數量的頁面換出緩存，則優先從偶爾隊列中選擇；若偶爾隊列為空，選擇頻繁隊列中LRU端的數據頁面并清理出緩存。由于“臟”數據的替換代價較高，這類數據頁面不會發生過于頻繁替換操作，使得IO操作盡可能選擇代價較小的閃存的寫操作，大幅度降低了數據從閃存寫入磁盤的次數。以下是替換算法的偽代碼：

算法1 替換代價排序。

SortByCost(CacheSet)

1.if(T_now〉T_sort)

2. if（T_now〉T_half）

3 （ref_count = ref_count/2）

4. if (block.dirty == true)

5. （cost_repl = d_cost * ref_count）;

6. else

7. （cost_repl = ref_count）;

8. 選出替換代價最大的num_block * percent 數據塊;

9. 將這些數據塊移動到CacheSet的頭部;

10 end if

算法中所使用的參數說明：num_block代表每個緩存集合中的數據塊數量，T_half為將訪問次數減半的時間間隔；T_sort為重新計算替換代價的時間間隔；percent 代表選擇集合排序的百分比；d_cost代表臟寫操作和讀操作的權重比，cost_repl代表每個緩存塊的替換代價，ref_count代表每個塊被訪問的次數。

混合存儲系統將一個緩存設備通過hash映射成多個cache集合，每個集合有一個數據結構保存著元數據，其中包括用雙鏈表表示的cache隊列。每個請求最終都會對cache隊列進行修改，所以對cache隊列的操作的算法要求復雜度較低。由于cache中被訪問次數較少的數據塊在cache隊列中的先后順序對整體性能的影響并不大，所以對被訪問可能較低的數據塊進行排序的收益不大，只對高頻訪問數據塊進行排序的結果是，犧牲了極小一部分命中率，來獲得IOPS指標的提升。根據cache隊列是雙鏈表的特性，所以調整順序時采用刪除后插入到隊列頭的操作方式。

3 實驗結果分析

本實驗使用的計算機配置為Intel Core 2 P4 Duo CPU 2.8GHz, 4GB內存，操作系統為Centos 6.5。使用Intel 330 120G SSD固態硬盤WD10EZEX 1TB 機硬盤組合作為混合存儲系統的存儲介質。

本文用于測試的 I/O trace由spc協會發布，分別是全讀請求的Web搜索記錄和含有寫請求的財務訪問Financial記錄。Web搜索記錄磁盤數據6.3G，請求的數據共64G，讀寫比例分別是100%和0%，80%的請求訪問了16%的數據，數據塊大小為8K的整數倍。Financial記錄的磁盤數據12.9G，請求的數據共106G，讀寫比例為66%和34%，80%的請求訪問了22%的數據，數據塊大小為8K的整數倍。使用這兩個trace不但可以模擬在高并發條件下數據訪問的隨機化和碎片化，而且其訪問行為的真實性使得研究的結果更有意義。

為了驗證算法的有效性，我們針對不同的cache大小，不同緩存替換算法FIFO，LRU，DRC，和不同的trace類型進行了對比試驗，主要比較混合存儲設備的I/O速度和命中率兩個性能。實驗過程中使用Linux的系統工具SysStat和iostat記錄實驗數據。SysStat通過讀取存儲系統中的統計信息記錄吞吐量與讀寫操作的命中率。iostat是Linux系統的性能檢測工具，通過對整個混合存儲系統進行監控來測量IO速度。

為驗證算法中熱點追蹤部分相對FIFO和LRU的優越性，實驗室的第一組trace的請求中不包含寫請求，在這組對比實驗中DRC算法的臟數據替換代價部分未起作用。

采用全讀Trace且緩存大小較小時的命中率對比圖如圖3所示：

圖3 Trace1不同緩存的命中率

從圖3中可以發現，DRC算法的整體命中率提升顯著，1GB大小的緩存情況下對比FIFO和LRU算法33%、41%的命中率提高到了44%。緩存大小為2GB時，命中率為80%左右，與Trace“80%的請求訪問16%的數據”基本吻合。當緩存大小超過3GB時，3種算法的命中率區別不大。

如圖4所示：

圖4 Trace1 不同緩存的I/O速度

Cache空間為3GB時，DRC算法相比FIFO和LRU使I/O速度獲得了明顯的提升，分別提升了9.5%和7.7%。DRC算法通過熱點數據的識別，充分利用了有限的緩存空間，將未來一段時間內最有可能被訪問的數據保留在緩存中。

第二組對比試驗中，我們選用了帶有一定比例寫操作的請求trace，是本算法的主要應用場景。第一組實驗驗證了DRC熱點識別后，進一步驗證通過替換代價作為依據的調度算法如圖5所示：

圖5 緩存較小時請求命中率

從圖5中可以發現，當混合存儲系統的緩存較小時，DRC算法對于熱點數據的預測相比FIFO和LRU更準確，使緩存命中率獲得明顯提升。在命中率提升的基礎上，DRC著重考慮的臟頁面的替換代價，提高了寫效率從而達到提升I/O吞吐量的效果。圖6表示緩存大小分別為1GB和2GB時，三種調度算法的I/O速度差別如圖6所示：

圖6 緩存較小時I/O速度

DRC算法在緩存為2G時I/O速度相對FIFO和LRU提高了10.4%和16.7%。通過上述的兩組對比實驗，DRC算法在緩存空間較為緊張時，通過提高整體命中率達到提升系統性能的目的。

在緩存較為充足情況下3種調度算法的命中率和I/O速度對比如圖7、圖8所示：

圖7 緩存空間充足的命中率對比

圖8 緩存空間充足的I/O速度對比

當緩存空間較大時，能夠將大部分頻繁被訪問的數據保留在緩存中，DRC算法雖然在命中率的提升并不明顯，但仍能通過調度替換代價較小的數據塊來降低寫磁盤的操作次數，與另外兩種調度算法相比仍有明顯的性能提升。另外值得一提的是，在緩存空間充足時，由于DRC調度算法的算法復雜度較低，存儲設備高負荷運行時仍能保持90%左右的時間處于IO狀態，略低于FIFO和LRU算法的93%。

從Trace2的實驗結果中我們可以得出結論：當數據的訪問請求呈現隨機化和碎片化時，無論緩存空間較小或者緩存空間充足，DRC算法都能通過提升命中率和提升臟數據寫效率的方式使系統的I/O性能獲得顯著提升。

4 總結

動態代價替換算法DRC針對混合存儲系統架構和讀寫調度機制，在充分考慮到了SSD和機械磁盤的優缺點的基礎上，通過判斷熱點數據的訪問模式、減少SSD的擦除操作、減少機械磁盤的隨機讀寫操作的方式降低了混合存儲系統的讀寫延遲，通過識別熱點數據來提高緩存的命中率。與混合存儲中的常用FIFO和LRU調度算法相比，DRC在各種緩存條件下均使系統的整體性能獲得了顯著提升。在接下來的研究中，我們計劃優化混合存儲中的設備工作隊列，實現設備隊列中的讀寫合并，從而進一步提升系統在訪問數據隨機化場景下的性能。

[1]Yang Q, Ren J. I-CASH: Intelligently coupled array of SSD and HDD[C]//High Performance Computer Architecture (HPCA), 2011 IEEE 17th International Symposium on. IEEE, 2011: 278-289.

[2]Chen F, Koufaty D A, Zhang X. Hystor: making the best use of solid state drives in high performance storage systems[C]//Proceedings of the internationalconference on Supercomputing. ACM, 2011: 22-32.

[3]陸游游, 舒繼武. 閃存存儲系統綜述[J]. Journal of Computer Research and Development, 2013, 50(1): 49-59.

[4]鄭文靜, 李明強, 舒繼武. Flash 存儲技術[J]. 計算機研究與發展, 2010, 47(4): 716-726.

[5]Zhang X, Davis K, Jiang S. iTransformer: Using SSD to improve disk scheduling for high-performance I/O[C]//Parallel & Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International. IEEE, 2012: 715-726.

[6]TANG Xian. ACR:An adaptive cost-aware buffer replacement algorithm for flash storage devices[A].2010.

DRC:A Dynamic-replacement-cost-based Algorithm For SSD/HDD Storage System

Liu Bingxu, Zhang Wenjun, Li Xiaoyong
(Department of Information Security, Shanghai Jiaotong University, Shanghai 200240,China)

With the development of cloud computing and big data, the requirements of storage system are higher. Multi-task sharing raises the system concurrency and data requests show fragmentation characteristics. Solid State Driver has

extensive attention due to its excellent reading and writing performance. However, the asymmetry of its reading and writing performance and cost consideration make the hybrid storage system of SSD-HDD become the main direction of research. By analyzing the characteristics of SSD and HDD, it presents a scheduling algorithm based on dynamic replacement costs (DRC), fully considering the hot data in the request and the cost of replacing dirty data. It not only effectively improves the cache hit rate, but also reduces random writing operations in HDD so that it can improve the overall performance of the system. The experiment results show that in high concurrency scene, DRC algorithm enhances the hit rate up to 11.6% and I/O speed up by 16.7% comparing to LRU or FIFO. In a variety of cache size conditions, DRC has achieved remarkable performance improvement.

Hybrid Storage Systems; SSD; Cache replacement Algorithm; Hotspot Computer

TP311

A

2015.12.16）

1007-757X(2015)04-0015-04

劉秉煦（1989-），男，上海交通大學，信息安全工程學院，碩士研究生，研究方向：分布式存儲系統，混合存儲系統，上海，200240

張文軍（1972-），男，上海交通大學，信息安全工程學院，講師，博士，研究方向：海量存儲，上海，200240

李小勇（1972-），男，上海交通大學，信息安全工程學院，副教授，博士，研究方向：海量存儲，上海，200240