一種針對(duì)時(shí)間局部性訪(fǎng)問(wèn)的固態(tài)硬盤(pán)緩存算法*

張 劍 吳崇建 閔紹榮 楊子晨

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

1 引言

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

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

2 相關(guān)研究

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

LRU算法著重考慮數(shù)據(jù)是否最近被訪(fǎng)問(wèn)，通過(guò)一個(gè)隊(duì)列來(lái)保留緩存頁(yè)的訪(fǎng)問(wèn)時(shí)間信息，優(yōu)先淘汰最久沒(méi)有被訪(fǎng)問(wèn)的數(shù)據(jù)。如圖1所示。

圖1 LRU算法示意圖

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

圖2 LFU算法示意圖

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

圖3 CFLRU緩存算法示意圖

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

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

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

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

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

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

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

1）預(yù)約隊(duì)列

預(yù)約隊(duì)列記錄剛被訪(fǎng)問(wèn)不久的數(shù)據(jù)塊。當(dāng)數(shù)據(jù)塊初次被訪(fǎng)問(wèn)加入到固態(tài)硬盤(pán)中時(shí)，先將其加入固態(tài)硬盤(pán)的預(yù)約隊(duì)列中，預(yù)約隊(duì)列使用LRU算法排序。

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

最小代價(jià)優(yōu)先隊(duì)列記錄從預(yù)約隊(duì)列中篩選出來(lái)的達(dá)到一定訪(fǎng)問(wèn)次數(shù)閾值的數(shù)據(jù)塊。最小代價(jià)優(yōu)先隊(duì)列以替換代價(jià)為標(biāo)準(zhǔn)進(jìn)行排序。最小代價(jià)優(yōu)先隊(duì)列中的數(shù)據(jù)被訪(fǎng)問(wèn)會(huì)重新計(jì)算其替換代價(jià)，根據(jù)替換代價(jià)插入到隊(duì)列的相應(yīng)位置。

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

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

3.2 替換代價(jià)計(jì)算

替換代價(jià)計(jì)算方法如式（1）所示：

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

CR代表最小代價(jià)優(yōu)先隊(duì)列中數(shù)據(jù)塊的替換代價(jià)；dircost代表寫(xiě)操作和讀操作的時(shí)間開(kāi)銷(xiāo)比；accenum代表數(shù)據(jù)塊訪(fǎng)問(wèn)次數(shù)；accedis代表數(shù)據(jù)塊最近一次訪(fǎng)問(wèn)到現(xiàn)在的時(shí)間間隔。

在計(jì)算替換代價(jià)時(shí)，對(duì)于緩存中的臟數(shù)據(jù)，需要乘上寫(xiě)讀操作的開(kāi)銷(xiāo)比dircost，給臟數(shù)據(jù)塊更多保留在緩存中的機(jī)會(huì)。

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

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

當(dāng)數(shù)據(jù)被訪(fǎng)問(wèn)時(shí)，根據(jù)被訪(fǎng)問(wèn)的數(shù)據(jù)是否已經(jīng)存在于固態(tài)硬盤(pán)中，存在兩種情況。不同的情況會(huì)有不同的數(shù)據(jù)組織流程。

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

圖6 被訪(fǎng)問(wèn)數(shù)據(jù)不在固態(tài)硬盤(pán)時(shí)的數(shù)據(jù)組織流程

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

圖7 被訪(fǎng)問(wèn)數(shù)據(jù)在固態(tài)硬盤(pán)時(shí)的數(shù)據(jù)組織流程

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

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

4.1 測(cè)試方案

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

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

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

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

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

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

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

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

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

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

4.4 測(cè)試結(jié)果

1）每小時(shí)平均IOPS對(duì)比測(cè)試

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

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

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

2）總平均IOPS對(duì)比測(cè)試

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

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

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

5 結(jié)語(yǔ)

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