一種針對時間局部性訪問的固態(tài)硬盤緩存算法*

張 劍 吳崇建 閔紹榮 楊子晨

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

1 引言

隨著人類對自然界了解的不斷深入，以及建模技術(shù)、信息技術(shù)的不斷發(fā)展，人類用數(shù)據(jù)抽象自然界中客觀事物的能力逐漸增強，從而使得積累的數(shù)據(jù)呈現(xiàn)出領(lǐng)域越來越廣、數(shù)量越來越多、類型越來越豐富的趨勢。由于這些數(shù)據(jù)表現(xiàn)出不同的特點，因此在使用這些數(shù)據(jù)的過程中，存儲系統(tǒng)的數(shù)據(jù)訪問模式會不斷變化。其中的一種典型數(shù)據(jù)訪問模式就是時間局部性［1］。時間局部性訪問有兩個顯著的特點：1）熱點遷移［2］。隨著時間的變化，數(shù)據(jù)熱點區(qū)域會發(fā)生變化，在不同的時間段內(nèi)不同存儲區(qū)域的數(shù)據(jù)分別被頻繁訪問。2）訪問頻率變化。某段時間內(nèi)特定的數(shù)據(jù)被高頻次訪問，而過了這段時間后該數(shù)據(jù)被訪問的可能性大大降低甚至不再被訪問。

為了有效應(yīng)對存儲系統(tǒng)中的時間局部性訪問，本文針對內(nèi)存、固態(tài)硬盤、機械硬盤構(gòu)成的混合存儲系統(tǒng)，設(shè)計了一種基于變化替換代價［3～4］的動態(tài)緩存算法DRCC，并將DRCC算法與多種主流緩存算法進行了測試對比。測試結(jié)果表明，與其他緩存算法相比，DRCC算法具有更高的讀寫效率。

2 相關(guān)研究

緩存算法主要解決數(shù)據(jù)的組織方式和容量滿時數(shù)據(jù)的淘汰機制。國內(nèi)外對于緩存算法開展了廣泛研究。其中，比較經(jīng)典的算法為LRU［5～6］算法、LFU［7］算法。由于固態(tài)硬盤具有區(qū)別于內(nèi)存的特點，于是一些針對固態(tài)硬盤的緩存算法被提出，其中的典型代表就是CFLRU（Clean-First LRU）緩存算法［8］和LRU-WSR（LRU-Write Sequence Reordering）算法［9～10］。

LRU算法著重考慮數(shù)據(jù)是否最近被訪問，通過一個隊列來保留緩存頁的訪問時間信息，優(yōu)先淘汰最久沒有被訪問的數(shù)據(jù)。如圖1所示。

圖1 LRU算法示意圖

LFU算法著重考慮數(shù)據(jù)的訪問頻次，認為訪問頻次最低的頁最不可能被再次訪問，按照訪問頻次從大到小對緩存頁進行排序，容量滿時優(yōu)先淘汰訪問頻次最低的數(shù)據(jù)。如圖2所示。

圖2 LFU算法示意圖

CFLRU算法將鏈表分為工作區(qū)和淘汰區(qū)兩個區(qū)域，工作區(qū)管理最近被訪問的頁，淘汰區(qū)管理即將被淘汰的頁。當發(fā)生替換操作時，算法會在淘汰區(qū)中優(yōu)先選擇干凈的頁進行淘汰，如果淘汰區(qū)不存在干凈的頁，那么就把LRU端的臟頁作為替換頁。如圖3所示。

圖3 CFLRU緩存算法示意圖

LRU-WSR算法將緩存頁劃分為三種類型：干凈頁，冷臟頁和熱臟頁。臟頁通過一個冷熱標識進行冷熱劃分。發(fā)生淘汰時，判別LRU端的頁類型：若為干凈頁或冷臟頁，直接淘汰；若為熱臟頁，則將標記為冷臟頁，并把該頁插入MRU端，給熱臟頁一次被保留的機會。如圖4所示。

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

3 DRCC算法設(shè)計

3.1 數(shù)據(jù)記錄結(jié)構(gòu)

使用DRCC算法時，固態(tài)硬盤的數(shù)據(jù)按照兩個隊列進行組織：預(yù)約隊列和最小代價優(yōu)先隊列，如圖5所示。

圖5 預(yù)約隊列和最小代價優(yōu)先隊列示意圖

兩個隊列的內(nèi)涵分別如下：

1）預(yù)約隊列

預(yù)約隊列記錄剛被訪問不久的數(shù)據(jù)塊。當數(shù)據(jù)塊初次被訪問加入到固態(tài)硬盤中時，先將其加入固態(tài)硬盤的預(yù)約隊列中，預(yù)約隊列使用LRU算法排序。

2）最小代價優(yōu)先隊列。

最小代價優(yōu)先隊列記錄從預(yù)約隊列中篩選出來的達到一定訪問次數(shù)閾值的數(shù)據(jù)塊。最小代價優(yōu)先隊列以替換代價為標準進行排序。最小代價優(yōu)先隊列中的數(shù)據(jù)被訪問會重新計算其替換代價，根據(jù)替換代價插入到隊列的相應(yīng)位置。

計算數(shù)據(jù)塊的替換代價以及對最小代價優(yōu)先隊列進行排序會帶來較大的開銷，一定程度上會影響整個存儲系統(tǒng)的性能。為此通過降低代價計算復(fù)雜度和排序復(fù)雜度，在不影響命中率的前提下，犧牲部分熱數(shù)據(jù)的排序精確度來降低系統(tǒng)開銷，從而獲得性能的提升。最小代價優(yōu)先隊列采用最小堆［11～12］的形式進行不完全排序，以完全二叉樹的形式，每次只確定最小代價的根節(jié)點位置。

最小代價優(yōu)先隊列的長度設(shè)置要適中，才能使得算法更能適應(yīng)時間局部性的數(shù)據(jù)訪問特點。最小代價優(yōu)先隊列的長度設(shè)置過大，會使很多變冷的數(shù)據(jù)污染固態(tài)硬盤緩存空間；最小代價優(yōu)先隊列的長度設(shè)置過小，則會造成熱數(shù)據(jù)的頻繁替換，增大替換開銷和對底層存儲的讀寫次數(shù)。因此，需要給最小代價優(yōu)先隊列設(shè)置一個合適的長度。假設(shè)固態(tài)硬盤的容量為V，默認設(shè)置最小代價優(yōu)先隊列的最大長度為，具體取值可以根據(jù)實際情況動態(tài)調(diào)整。

3.2 替換代價計算

替換代價計算方法如式（1）所示：

式（1）中各變量的含義如下：

CR代表最小代價優(yōu)先隊列中數(shù)據(jù)塊的替換代價；dircost代表寫操作和讀操作的時間開銷比；accenum代表數(shù)據(jù)塊訪問次數(shù)；accedis代表數(shù)據(jù)塊最近一次訪問到現(xiàn)在的時間間隔。

在計算替換代價時，對于緩存中的臟數(shù)據(jù)，需要乘上寫讀操作的開銷比dircost，給臟數(shù)據(jù)塊更多保留在緩存中的機會。

具體實施時，由于熱數(shù)據(jù)會隨著時間遷移，所以將最小代價優(yōu)先隊列中的數(shù)據(jù)塊訪問次數(shù)計算考慮時間間隔的因素，同時設(shè)置老化周期定時將數(shù)據(jù)訪問次數(shù)右移一位，避免在過去時間內(nèi)訪問次數(shù)積累較多而現(xiàn)在已經(jīng)變冷較少被訪問的數(shù)據(jù)塊一直占據(jù)緩存空間，造成新加入的較低訪問次數(shù)熱數(shù)據(jù)被替換的情況。

3.3 數(shù)據(jù)組織方法

當數(shù)據(jù)被訪問時，根據(jù)被訪問的數(shù)據(jù)是否已經(jīng)存在于固態(tài)硬盤中，存在兩種情況。不同的情況會有不同的數(shù)據(jù)組織流程。

1）當被訪問數(shù)據(jù)不在固態(tài)硬盤時，數(shù)據(jù)組織流程如圖6所示。數(shù)據(jù)被訪問后，將其提取到固態(tài)硬盤的預(yù)約隊列中，并按照LRU算法進行數(shù)據(jù)的組織。

圖6 被訪問數(shù)據(jù)不在固態(tài)硬盤時的數(shù)據(jù)組織流程

2）當被訪問的數(shù)據(jù)存在于固態(tài)硬盤中時，數(shù)據(jù)組織流程如圖7所示。若數(shù)據(jù)被訪問時存在于預(yù)約隊列中，則檢查其訪問次數(shù)是否達到閾值，若達到閾值，則將其提升到最小代價優(yōu)先隊列中，計算其替換代價，并在最小代價優(yōu)先隊列容量滿時淘汰替換代價最小的數(shù)據(jù)；若未達到閾值，則繼續(xù)保留在預(yù)約隊列，并按照LRU算法進行排序。若數(shù)據(jù)被訪問時存在于最小代價優(yōu)先隊列中，則重新計算其替換代價，再次確定替換代價最小的數(shù)據(jù)。

圖7 被訪問數(shù)據(jù)在固態(tài)硬盤時的數(shù)據(jù)組織流程

可以看出，預(yù)約隊列和最小代價隊列都有各自的淘汰方式，最小優(yōu)先代價隊列并不等待預(yù)約隊列為空時才開始淘汰數(shù)據(jù)。這種數(shù)據(jù)淘汰方式考慮了時間局部性數(shù)據(jù)熱點遷移的特點，能及時將變冷的數(shù)據(jù)塊淘汰出固態(tài)硬盤，避免緩存空間污染［13］。

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

4.1 測試方案

測試時存儲系統(tǒng)的實現(xiàn)基于開源的iSCSI（Internet Small Computer System Interface，Internet小型計算機接口）［14～15］代碼。i SCSI是當前存儲界的熱門技術(shù)之一，其使用TCP/IP協(xié)議，用廣域網(wǎng)仿真高性能本地存儲總線，從而創(chuàng)建了一個存儲局域網(wǎng)。內(nèi)存、固態(tài)硬盤、機械硬盤構(gòu)成的混合存儲系統(tǒng)安裝在作為iSCSI目標端的存儲服務(wù)器，客戶端通過iSCSI發(fā)起端將讀寫請求負載發(fā)送到iSCSI目標端的存儲服務(wù)器。

測試時將本文中所提的DRCC算法與經(jīng)典的LRU算法、LFU算法，以及針對固態(tài)硬盤的高效算法CFLRU進行比較，以證明DRCC算法的優(yōu)勢。

4.2 測試環(huán)境

測試環(huán)境配置如表1所示。根據(jù)測試數(shù)據(jù)集的大小，通過代碼進行控制，將用于測試的混合存儲系統(tǒng)的內(nèi)存大小設(shè)置為500M，固態(tài)硬盤大小設(shè)置為1G×3，機械硬盤大小設(shè)置為20G×6。

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

4.3 測試數(shù)據(jù)

測試數(shù)據(jù)通過模擬產(chǎn)生，在某個服務(wù)器部署待訪問數(shù)據(jù)，通過另一個客戶端對其進行時間局部性訪問。通過訪問記錄收集工具記錄一段時間之內(nèi)服務(wù)器的訪問情況。為了充分反映數(shù)據(jù)的訪問特點，記錄約120h的數(shù)據(jù)。

表2所示統(tǒng)計了以1000、5000、10000、20000次訪問為數(shù)據(jù)第一次訪問起點，數(shù)據(jù)被再次重新訪問的平均距離。

表2 平均重用距離統(tǒng)計

從表2可以看出，數(shù)據(jù)以20000次訪問為數(shù)據(jù)第一次訪問起點時，平均重用距離相比較以10000次訪問為起點時陡然增大了約7倍，這與時間局部性訪問的特點非常相符，熱數(shù)據(jù)在一段時間內(nèi)被頻繁訪問過后，熱度迅速降低甚至不再被訪問。

4.4 測試結(jié)果

1）每小時平均IOPS對比測試

DRCC算法與LRU算法、LFU算法、CFLRU算法的每小時平均IOPS的測試結(jié)果如圖8所示。

可以看出，DRCC算法的每小時平均IOPS絕大多數(shù)時間都要高于LRU算法、LFU算法、CFLRU算法。

圖8 每小時平均IOPS測試結(jié)果

2）總平均IOPS對比測試

DRCC算法與LRU算法、LFU算法、CFLRU算法的總平均IOPS的測試結(jié)果如圖9所示。

圖9 總平均IOPS測試結(jié)果

可以看出，存儲系統(tǒng)運行一小段時間后，DRCC算法的總平均IOPS就開始表現(xiàn)出明顯的優(yōu)勢，而且隨著時間的推移，這種優(yōu)勢進一步擴大。在總平均IOPS方面，相比較于LRU、LFU、CFLRU三種算法，DRCC算法的提升幅度均超過了10%。

5 結(jié)語

本文針對內(nèi)存、固態(tài)硬盤、機械硬盤組成的混合存儲系統(tǒng)中的時間局部性訪問，設(shè)計了一種高效的緩存算法。該算法通過預(yù)約隊列和最小代價優(yōu)先隊列實現(xiàn)數(shù)據(jù)的組織，同時兩個隊列分別進行數(shù)據(jù)的淘汰，充分解決了高時間局部性數(shù)據(jù)熱點遷移所帶來的緩存污染問題。測試結(jié)果表明，該算法不僅比經(jīng)典的LRU算法和LFU算法更有優(yōu)勢，而且相比較于針對固態(tài)硬盤的高效緩存算法CFLRU，同樣表現(xiàn)出較大的性能提升。