張 劍 吳崇建 閔紹榮 楊子晨

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

1 引言

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

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

2 相關(guān)研究

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

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

圖1 LRU算法示意圖

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

圖2 LFU算法示意圖

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

圖3 CFLRU緩存算法示意圖

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

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

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

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

使用DRCC算法時(shí)，固態(tài)硬盤的數(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ì)列記錄剛被訪問不久的數(shù)據(jù)塊。當(dāng)數(shù)據(jù)塊初次被訪問加入到固態(tài)硬盤中時(shí)，先將其加入固態(tài)硬盤的預(yù)約隊(duì)列中，預(yù)約隊(duì)列使用LRU算法排序。

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

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

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

最小代價(jià)優(yōu)先隊(duì)列的長度設(shè)置要適中，才能使得算法更能適應(yīng)時(shí)間局部性的數(shù)據(jù)訪問特點(diǎn)。最小代價(jià)優(yōu)先隊(duì)列的長度設(shè)置過大，會(huì)使很多變冷的數(shù)據(jù)污染固態(tài)硬盤緩存空間；最小代價(jià)優(yōu)先隊(duì)列的長度設(shè)置過小，則會(huì)造成熱數(shù)據(jù)的頻繁替換，增大替換開銷和對(duì)底層存儲(chǔ)的讀寫次數(shù)。因此，需要給最小代價(jià)優(yōu)先隊(duì)列設(shè)置一個(gè)合適的長度。假設(shè)固態(tài)硬盤的容量為V，默認(rèn)設(shè)置最小代價(jià)優(yōu)先隊(duì)列的最大長度為，具體取值可以根據(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代表寫操作和讀操作的時(shí)間開銷比；accenum代表數(shù)據(jù)塊訪問次數(shù)；accedis代表數(shù)據(jù)塊最近一次訪問到現(xiàn)在的時(shí)間間隔。

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

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

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

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

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

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

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

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

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

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

4.1 測試方案

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

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

4.2 測試環(huán)境

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

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

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

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

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

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

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

4.4 測試結(jié)果

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

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

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

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

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

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

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

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

5 結(jié)語

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