梁 鑫, 林銘煒,2, 姚志強(qiáng),2

1(福建師范大學(xué) 數(shù)學(xué)與信息學(xué)院,福州 350108)

2(福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程技術(shù)研究中心,福州 350108)

隨著技術(shù)的高速發(fā)展以及成本價(jià)格的不斷降低,閃存相對(duì)于傳統(tǒng)磁盤(pán)的優(yōu)勢(shì)越來(lái)越大,基于閃存的存儲(chǔ)介質(zhì)被認(rèn)為具有很大的潛力取代傳統(tǒng)的機(jī)械式硬盤(pán).基于閃存的設(shè)備由于其體積小、質(zhì)量輕、能耗低、更高的讀取速度等優(yōu)良特性[1],它不僅深受IT行業(yè)所鐘愛(ài),在其它行業(yè)中也有著廣泛的應(yīng)用并發(fā)揮著巨大的優(yōu)勢(shì),如醫(yī)藥業(yè)、航天航空、金融市場(chǎng)等.

閃存盡管比磁盤(pán)具有更好的I/O訪問(wèn)性能,但仍然比內(nèi)存的速度低兩個(gè)數(shù)量級(jí). 在閃存與內(nèi)存之間設(shè)置高速緩沖區(qū)不僅可以減少代價(jià)高昂的磁盤(pán)訪問(wèn)開(kāi)銷(xiāo),還可以提高數(shù)據(jù)庫(kù)的性能. 作為數(shù)據(jù)庫(kù)系統(tǒng)的核心組件,緩沖區(qū)利用局部性特性將訪問(wèn)密度高的數(shù)據(jù)頁(yè)存儲(chǔ)在內(nèi)存上,以快速響應(yīng)中央處理器的讀寫(xiě)請(qǐng)求[2]. 當(dāng)請(qǐng)求訪問(wèn)數(shù)據(jù)頁(yè)的時(shí),如果所請(qǐng)求的頁(yè)正好在緩沖區(qū)中,則不需要到外部存儲(chǔ)中讀取該數(shù)據(jù)頁(yè),由于緩沖區(qū)的存取速度比二次存儲(chǔ)快得多,從而可以提高整體的I/O性能. 對(duì)于那些使用閃存存儲(chǔ)作為外部存儲(chǔ)的系統(tǒng),當(dāng)緩沖區(qū)已滿并且需要釋放緩存頁(yè)來(lái)釋放空間時(shí),應(yīng)考慮到閃存讀寫(xiě)不對(duì)稱的特性[3],同時(shí)盡可能減少代價(jià)較大的寫(xiě)操作和緩沖區(qū)數(shù)據(jù)頁(yè)脫靶的次數(shù). 此外,閃存比磁盤(pán)快一個(gè)數(shù)量級(jí)的訪問(wèn)速度,這種低的訪問(wèn)延遲,不允許采用復(fù)雜的、具有高計(jì)算代價(jià)的數(shù)據(jù)結(jié)構(gòu)與算法,也就是說(shuō)緩沖區(qū)驅(qū)逐頁(yè)的算法應(yīng)盡可能簡(jiǎn)單且具備低的時(shí)間復(fù)雜度和空間復(fù)雜度,避免抵消由閃存低訪問(wèn)延遲帶來(lái)的I/O收益.

1 相關(guān)工作

閃存緩沖區(qū)替換代價(jià)主要為兩方面： 1) 是將頁(yè)面從輔助存儲(chǔ)讀取到緩沖區(qū)的代價(jià); 2) 為將從緩沖區(qū)中被驅(qū)逐的頁(yè)寫(xiě)入到輔助存儲(chǔ)中的代價(jià). 一種代價(jià)的減少往往以另一種代價(jià)的增加為前提. 因而,一個(gè)優(yōu)秀的緩沖區(qū)替換算法必須在保持較高命中率的同時(shí)降低閃存的寫(xiě)操作和擦除操作次數(shù),從而獲得整體性能的提升.

目前關(guān)于閃存緩沖區(qū)置換算法的研究主要包括：LRU、CF-LRU、LRU-WSR、CCF-LRU、PB-LRU和AD-LRU、F-LRU[4]等算法.

LRU (Least Recently Used)策略將緩沖區(qū)中所有緩存數(shù)據(jù)頁(yè)存放在一個(gè)鏈表中,LRU 端保存最近最不常使用的數(shù)據(jù)頁(yè),MRU (Most Recently Used)端保存最近頻繁使用的數(shù)據(jù)頁(yè). 當(dāng)訪問(wèn)頁(yè)面P時(shí),首先從鏈表的LRU端開(kāi)始往MRU端查找,若命中(鏈表中找到)P,則將P從當(dāng)前位置移除并將其移至鏈表的MRU端,若脫靶(鏈表中不存在所需頁(yè))且緩沖區(qū)還有額外空間時(shí),則把P頁(yè)放入MRU端,如過(guò)發(fā)生脫靶且緩沖區(qū)空間已滿,則需要進(jìn)行頁(yè)的驅(qū)逐替換,把LRU端的頁(yè)作為首選替換頁(yè)驅(qū)逐出緩沖區(qū),騰出空間后再將P頁(yè)放在鏈表的MRU端. LRU算法具有較高的命中率,但也存在以下缺陷： (1) 沒(méi)有記錄緩沖區(qū)頁(yè)的訪問(wèn)頻度; (2)算法替換的是鏈表的LRU端,而在實(shí)際應(yīng)用中臟頁(yè)往往集中在這,替換這些臟頁(yè)會(huì)帶來(lái)大量的寫(xiě)和擦除操作,惡化了閃存數(shù)據(jù)庫(kù)的性能.

CFLRU(Clean-First LRU)[5]算法,不僅考慮到緩沖區(qū)的命中率還考慮了驅(qū)逐臟頁(yè)的的替換代價(jià)[6],該算法能有效地減少寫(xiě)和擦除操作的次數(shù),進(jìn)而提高閃存數(shù)據(jù)庫(kù)的讀寫(xiě)性能. 但CFLRU替換區(qū)的大小w并不是一個(gè)容易確定的值且算法沒(méi)有考慮緩沖區(qū)頁(yè)的訪問(wèn)頻度,容易保留較老的臟頁(yè)而驅(qū)逐熱干凈頁(yè)從而降低命中率,另外,尋找干凈頁(yè)的開(kāi)銷(xiāo)比較大,有時(shí)甚至要遍歷整個(gè)LRU鏈表.

LRU-WSR替換策略克服了CFLRU策略的缺陷.使用“冷探測(cè)”技術(shù)來(lái)判斷一個(gè)頁(yè)是不是冷頁(yè),增加了選擇驅(qū)逐頁(yè)前臟頁(yè)的頻度判斷. 在實(shí)驗(yàn)中可以看出使用這種策略,雖然命中率比普通LRU算法低,但能在有效減少寫(xiě)操作和擦除操作的次數(shù)的同時(shí)不導(dǎo)致命中率的嚴(yán)重惡化. 然而LRU-WSR在替換頁(yè)面時(shí)仍然沒(méi)有考慮到干凈頁(yè)的訪問(wèn)頻度,很有可能被驅(qū)逐替換的是熱干凈頁(yè). CCF-LRU針對(duì)以上缺陷進(jìn)行改進(jìn),將鏈表分為兩個(gè),ML鏈表(Mixed LRU List)和CCL鏈表(Cold Clean LRU List). 替換策略優(yōu)先替換CCL鏈表中的數(shù)據(jù)頁(yè),當(dāng)CCL鏈表為空時(shí)才按照LRU-WSR策略替換ML鏈表中的數(shù)據(jù)頁(yè). CCF-LRU獲取了干凈頁(yè)和臟頁(yè)的訪問(wèn)頻度,一定程度上優(yōu)化了存儲(chǔ)性能. 但存在一個(gè)干凈頁(yè)剛進(jìn)入緩沖區(qū)還未變成熱頁(yè)便被驅(qū)逐的情況.

AD-LRU將閃存緩沖區(qū)分為冷區(qū)和熱區(qū)兩個(gè)區(qū)域且區(qū)域大小可動(dòng)態(tài)調(diào)整,冷區(qū)容量設(shè)定下限min_lc,當(dāng)冷區(qū)容量大于最小值時(shí),替換操作發(fā)生在冷區(qū),否則替換操作發(fā)生在熱區(qū). 當(dāng)訪問(wèn)脫靶需要驅(qū)逐頁(yè)面時(shí)總是優(yōu)先替換干凈頁(yè),若冷區(qū)中沒(méi)有干凈頁(yè),則按照LRU算法替換臟頁(yè),若熱區(qū)沒(méi)有干凈頁(yè),則使用二次機(jī)會(huì)策略替換臟頁(yè). 該算法雖獲得了更好的性能,但依然沒(méi)有徹底解決冷區(qū)總是無(wú)條件替換干凈頁(yè)最后會(huì)導(dǎo)致臟頁(yè)完全占領(lǐng)緩沖區(qū),導(dǎo)致一個(gè)干凈頁(yè)剛進(jìn)入到緩沖區(qū)便被驅(qū)逐的情況,同時(shí)也很難找到一個(gè)min_lc值,使它能在于不同數(shù)據(jù)類(lèi)型下都獲得良好性能.

2 干凈頁(yè)優(yōu)先的自適應(yīng)緩沖區(qū)置換算法

傳統(tǒng)的ARC算法[7]在磁頭盤(pán)片式的機(jī)械磁盤(pán)上可以獲得不錯(cuò)的性能,但在閃存數(shù)據(jù)庫(kù)系統(tǒng)中會(huì)把很多的臟頁(yè)替換出去,而替換臟頁(yè)會(huì)帶來(lái)大量開(kāi)銷(xiāo)大的寫(xiě)操作.

為了解決ARC算法運(yùn)用在閃存數(shù)據(jù)庫(kù)上的不足,本文提出一種新的面向閃存的緩沖區(qū)置算法CF-ARC(Clean First Adaptive Replacement Cache),給緩沖區(qū)的每個(gè)數(shù)據(jù)頁(yè)定義一個(gè)參數(shù)ref,ref初始為0,每當(dāng)緩沖區(qū)的頁(yè)命中則該頁(yè)的ref加1,用來(lái)記錄緩沖區(qū)熱頁(yè)的命中次數(shù),替換時(shí)優(yōu)先替換ref最小的干凈頁(yè),若緩沖區(qū)不存在干凈頁(yè)再替換ref最小的臟頁(yè),采用這種置換策略的優(yōu)勢(shì)是： (1) 優(yōu)先替換干凈頁(yè),盡管增加了讀操作的次數(shù),但減少了寫(xiě)操作的次數(shù). (2) 能夠有效保證驅(qū)逐的頁(yè)不會(huì)是最熱頁(yè),從而也保證了緩沖區(qū)較高的命中率.

2.1 基本思想

CF-ARC采用LRU-WSR算法類(lèi)似的“冷探測(cè)”技術(shù),CF-ARC算法將緩沖區(qū)劃分為冷區(qū)(T1)和熱區(qū)(T2),冷、熱區(qū)中都包含干凈頁(yè)和臟頁(yè),緩沖區(qū)的數(shù)據(jù)頁(yè)都帶有冷、臟標(biāo)識(shí),當(dāng)冷標(biāo)識(shí)位為1則代表該頁(yè)為冷頁(yè),否則為熱數(shù)據(jù)頁(yè),當(dāng)臟標(biāo)識(shí)位為1則代表該頁(yè)為臟頁(yè),否則為干凈頁(yè),首次進(jìn)入緩沖區(qū)的頁(yè)默認(rèn)為冷頁(yè),當(dāng)該頁(yè)再次被訪問(wèn)時(shí)則將其冷標(biāo)識(shí)位設(shè)為0,同時(shí)定義兩個(gè)鏈表B1用來(lái)存儲(chǔ)替換T1時(shí)的頁(yè)號(hào),B2用來(lái)存儲(chǔ)替換T2時(shí)的頁(yè)號(hào),B1和B2的數(shù)據(jù)不存入到緩沖區(qū)中,定義參數(shù)P,L1,L2. 且L1、L2鏈表長(zhǎng)度滿足如下等式：

Len[]函數(shù)定義為計(jì)算鏈表的長(zhǎng)度算法主要思想如下：

(1) 將緩沖區(qū)分為冷區(qū)(T1)和熱區(qū)(T2),冷區(qū)保存僅訪問(wèn)過(guò)一次的數(shù)據(jù)頁(yè),熱區(qū)保存訪問(wèn)過(guò)兩次及以上的數(shù)據(jù)頁(yè).

(2) 首次進(jìn)入緩沖區(qū)的Page進(jìn)入冷區(qū)的MRU端,當(dāng)緩沖區(qū)的頁(yè)被命中后則將該命中頁(yè)移至熱區(qū)MRU端.

(3) 當(dāng)緩沖區(qū)已滿且Page不在緩沖區(qū)中,如果在B1中找到Page的記錄則更新P=min{p+X,C},其中如果B1的長(zhǎng)度大于或等于B2的長(zhǎng)度則X=1,否則X=(B2的長(zhǎng)度)/(B1的長(zhǎng)度),常數(shù)C等于緩沖區(qū)的大小. 并執(zhí)行替換策略后,將Page從B1中移除并添加到T2的MRU端,放入緩沖區(qū).

(4) 當(dāng)緩沖區(qū)已滿并且Page不在緩沖區(qū)中,如果在B2中找到Page的記錄則更新P=max{p-X,C},其中如果B2的長(zhǎng)度大于或等于B1的長(zhǎng)度則X=1,否則X=(B1的長(zhǎng)度)/(B2的長(zhǎng)度),常數(shù)C等于緩沖區(qū)的大小. 并執(zhí)行替換策略后,將Page從B2中移除并添加到T2的MRU端,放入緩沖區(qū).

(5) 當(dāng)緩沖區(qū)已滿且在T1、T2、B1、B2 中都找不到Page的記錄時(shí),如果L1(T1加B1的長(zhǎng)度)等于緩沖區(qū)的大小并且如果T1的小于緩沖區(qū)大小則刪除B1的LRU項(xiàng),執(zhí)行替換策略,同時(shí)P=min{p+X,C},如果T1不小于緩沖區(qū)的大小則刪T1的LRU端,從緩沖區(qū)刪除并將刪除的頁(yè)號(hào)添加到B1的MRU端,并將頁(yè)從緩沖區(qū)刪除. 執(zhí)行替換策略,將Page添加到T1的MRU端并放入緩沖區(qū); L1小于緩沖區(qū)的大小并且L1+L2大于或等于緩沖區(qū)大小,如果L1+L2等于兩倍的緩沖區(qū)大小則刪除B2的LRU項(xiàng). 執(zhí)行替換操作,將Page添加到T1的MRU端并放入緩沖區(qū);

本算法的替換策略是,如果滿足(T1>=1)&&(((Page in B2)&&(T1 = P))||(T1>p))的條件則優(yōu)先刪除T1中的干凈頁(yè),然后替換T1中的臟頁(yè). 否則優(yōu)先替換T2中ref最小的干凈頁(yè),如果T2中沒(méi)有干凈頁(yè)則從LRU端開(kāi)始尋找ref=0的替換頁(yè),若當(dāng)前頁(yè)ref>0則將其ref-2并移至MRU端后重新尋找直到找到ref=0的冷臟頁(yè)作為替換頁(yè).

2.2 算法設(shè)計(jì)

CF-ARC算法細(xì)節(jié)如算法1所示.

算法1. CF-ARC算法的偽代碼

輸入： 請(qǐng)求頁(yè) x1,x2,x3,…

輸出： p

1 IF x is in T1 or T2;

2 move x to the MRU position of T2;

3 ELSE IF x is not in T1 or T2 but B1;

4 p = min{p+Y,C};

5 If |B1|>=|B2| then Y=1;

6 else Y=|B2|/|B1|;

8 ELSE IF x is not in T1 or T2 but B2;

9 UPDATE p = max{p-Y,0};

10 If |B1|>=|B2| then Y=1;

11 else Y=|B2|/|B1|;

12 ELSE IF x is not in T1∪T2∪B1∪B2;

13 Case A： L1 = T1∪B1 = DEBUFFSIZE;

14 If(|T1| ＜ DEBUFFSIZE);

15 DELETE LRU page of B1;

16 Case B： L1 = T1∪b1 ＜ DEBUFFSIZE;

17 If(|T1|+|T2|+|B1|+|B2|>=DEBUFFSIZE);

18 DELETE LRU page;

19 if(|T1|+|T2|+|B1|+|B2|=2*DEBUFFSIZE) ;

20 RETURN p

2.3 CF-ARC算法與AD-LRU算法實(shí)例分析

通過(guò)實(shí)驗(yàn)可知： 多數(shù)情況下AD-LRU算法總是可以獲得比LRU、CF-LRU、CCF-LRU、LRU-WSR算法更高的性能[8],下面通過(guò)一組實(shí)例來(lái)論證CF-LRU算法相對(duì)AD-LRU算法的性能優(yōu)勢(shì).

假設(shè)閃存緩沖區(qū)的大小只能容納5個(gè)數(shù)據(jù)頁(yè). 初始情況如圖1(a) 、圖2(a)所示,假設(shè)AD-LRU算法的下界min_lc為3,指針FC用來(lái)指向最不常使用干凈頁(yè). 緩沖區(qū)內(nèi)存在P1、P2、P3、P4、P5五個(gè)數(shù)據(jù)頁(yè).當(dāng)一個(gè)對(duì)P2頁(yè)的讀操作到達(dá)時(shí),CF-ARC算法和ADLRU算法都會(huì)發(fā)現(xiàn)P2存在緩沖區(qū)當(dāng)中,這時(shí)就直接從緩沖區(qū)中讀取數(shù)據(jù)頁(yè)P(yáng)2,訪問(wèn)完之后將P2移至Hot(T2)LRU鏈表的MRU端并把冷標(biāo)記位設(shè)置為熱.如圖1(b) 、圖2(b)所示.

圖1 AD-LRU鏈表

然而假設(shè)一個(gè)針對(duì)P6的讀操作到達(dá),AD-LUR算法檢查發(fā)現(xiàn)P6不在緩沖區(qū)中,且此時(shí)緩沖區(qū)已滿且冷區(qū)容量為2小于min_lc,按照AD-LRU算法可知此時(shí)將會(huì)選取熱區(qū)上的P5作為首選驅(qū)逐頁(yè),最終效果如圖1(c)所示.

而針對(duì)P6操作采用CF-ARC算法將會(huì)出現(xiàn)更優(yōu)的性能,根據(jù)算法描述替換最后發(fā)生在冷區(qū)還是熱區(qū)由多種參數(shù)共同決定,如果替換發(fā)生在T2則執(zhí)行跟AD-LRU算法一樣的操作,本例中假設(shè)通過(guò)參數(shù)計(jì)算后發(fā)現(xiàn)替換操作發(fā)生在T1,即替換FC指向的頁(yè)P(yáng)3,然后把P6放入冷區(qū)的MRU位置,如圖2(c)所示,此時(shí)CF-ARC替換的是冷區(qū)中的干凈頁(yè),而AD-LRU替換的是熱區(qū)的干凈頁(yè),因?yàn)樘鎿Q熱區(qū)的數(shù)據(jù)頁(yè)P(yáng)5所帶來(lái)的開(kāi)銷(xiāo)大于替換冷區(qū)中的數(shù)據(jù)頁(yè)P(yáng)3,且將熱頁(yè)驅(qū)逐出緩沖區(qū)會(huì)降低命中率,因此在這種情況下CFARC算法具有更優(yōu)的性能.

圖2 CF-ARC鏈表

通過(guò)實(shí)例分析,CF-ARC算法的性能至少與ADLRU算法保持一致,在某些情形下優(yōu)于AD-LRU算法,下面將通過(guò)實(shí)驗(yàn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證.

3 實(shí)驗(yàn)分析

本節(jié)首先介紹實(shí)驗(yàn)設(shè)計(jì)及參數(shù)配置(3.1節(jié)); 進(jìn)而通過(guò)大數(shù)據(jù)抽樣選取4種符合Zipf分布的數(shù)據(jù)集來(lái)測(cè)試算法,通過(guò)對(duì)4種數(shù)據(jù)的大量重復(fù)實(shí)驗(yàn),得出實(shí)驗(yàn)結(jié)果并進(jìn)一步對(duì)比分析,因每種數(shù)據(jù)集所得出的結(jié)論大致相同,特選取T8282數(shù)據(jù)集來(lái)詳細(xì)說(shuō)明CF-ARC具有良好的性能優(yōu)勢(shì)(3.2～3.3節(jié)).

3.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)使用Flash-DBSim平臺(tái)[9]模擬閃存存儲(chǔ)系統(tǒng),一個(gè)用于進(jìn)行閃存數(shù)據(jù)庫(kù)研究的仿真工具,能夠?qū)﹂W存技術(shù)研究中出現(xiàn)的各種實(shí)驗(yàn)環(huán)境進(jìn)行盡可能準(zhǔn)確的模擬,盡可能的減少了接口數(shù)量并且很容易就能對(duì)整個(gè)Flash-DBSim的環(huán)境進(jìn)行配置,使之適應(yīng)當(dāng)前的閃存研究實(shí)驗(yàn)[4]. 本實(shí)驗(yàn)?zāi)M一個(gè)128 G的閃存固態(tài)盤(pán),配置參數(shù)如表1所示.

表1 閃存的參數(shù)

在本次性能測(cè)試中,AD-LRU算法的min_lc取值為0.1倍的緩沖區(qū)大小,CF-LRU算法的w取值為0.5,FlashDBsim通過(guò)統(tǒng)計(jì)閃存的命中率、讀次數(shù)、寫(xiě)次數(shù)來(lái)實(shí)現(xiàn)算法之間的差異性比較[2].

為了盡量真實(shí)的模擬數(shù)據(jù)庫(kù)系統(tǒng)運(yùn)行時(shí)的數(shù)據(jù)訪問(wèn)方式,我們采用4種符合Zipf分布的數(shù)據(jù)集來(lái)評(píng)判緩沖區(qū)替換算法的性能[10],如表2. 其中“讀寫(xiě)比x%/y%”表示待測(cè)試的數(shù)據(jù)集當(dāng)中讀操作占x%,寫(xiě)操作占y%,“局部性x%/y%”表示數(shù)據(jù)集當(dāng)中x%的操作集中在y%的數(shù)據(jù)中. 通過(guò)評(píng)判緩沖區(qū)的命中率、讀操作的次數(shù)和寫(xiě)操作的次數(shù)來(lái)評(píng)判算法的整體優(yōu)越性[11]. 通過(guò)多次重復(fù)實(shí)驗(yàn)并采用單因素方差分析方法進(jìn)一步分析實(shí)驗(yàn)結(jié)果.

表2 測(cè)試數(shù)據(jù)集的詳細(xì)信息

3.2 命中率

圖3展示了各個(gè)緩沖區(qū)置換算法在不同的緩沖區(qū)大小的形況下運(yùn)行T8282數(shù)據(jù)的命中率情況. 從圖中可以看出： 那些采用了“冷判斷”機(jī)制并且充分考慮了替換干凈頁(yè)和替換臟頁(yè)代價(jià)差異特性的算法,在多數(shù)情況下命中率明顯高于其他算法,而CF-ARC算法在大多數(shù)的情況下都比AD-LRU和CCF-LRU命中率高,這充分說(shuō)明CF-ARC算法是一個(gè)具有較高命中率的閃存緩沖區(qū)置換算法. 例如,在緩沖區(qū)容量在1-4 M的時(shí)候,CF-ARC都能取得最佳的命中率,就算是在緩沖區(qū)容量在5 M的時(shí)候也與AD-LRU性能相當(dāng). 通過(guò)實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)在另外3中測(cè)試數(shù)據(jù)集T1982,T3773,T7373中,CF-ARC依然具有更高的命中率,因4種數(shù)據(jù)集的測(cè)試結(jié)論具有較高的一致性,本文省略另外3中測(cè)試數(shù)據(jù)集的詳細(xì)介紹.

圖3 運(yùn)行T8282數(shù)據(jù)的命中率

3.3 物理讀、寫(xiě)操作次數(shù)

圖4、圖5展示了各個(gè)緩沖區(qū)替換算法在不同的緩沖區(qū)大小下運(yùn)行T8282測(cè)試數(shù)據(jù)集的情況. 從圖中可以看出,LRU算法沒(méi)有考慮頁(yè)的訪問(wèn)頻度等問(wèn)題,在物理讀和寫(xiě)方面總是表現(xiàn)為最差. 由于充分考慮了數(shù)據(jù)頁(yè)的訪問(wèn)頻度以及在優(yōu)先替換訪問(wèn)頻度小的干凈頁(yè)的策略,CF-ARC算法物理讀的次數(shù)在多數(shù)情況下總是低于其他算法,在緩沖區(qū)大小為1-4 M時(shí)候,算法寫(xiě)操作次數(shù)也低于其它算法,甚至在5 M的時(shí)候,也僅次于AD-LRU算法. 更少的物理寫(xiě)操作一方面降低了開(kāi)銷(xiāo),另一方面也延長(zhǎng)了閃存的使用壽命.

圖4 物理讀操作次數(shù)

3.4 本章小結(jié)

本章首先介紹實(shí)驗(yàn)平臺(tái)的相關(guān)信息,以及對(duì)參與實(shí)驗(yàn)的不同測(cè)試數(shù)據(jù)的分析與解釋. 通過(guò)模擬在正常使用中產(chǎn)生的數(shù)據(jù)頁(yè)對(duì)幾種面向閃存緩沖區(qū)置換算法進(jìn)行性能比較,分別從命中率、讀操作次數(shù)和寫(xiě)操作次數(shù)綜合判斷LRU、CFLRU、LRU-WSR、CCFLRU、AD-LRU和CF-ARC算法的性能,并在后面給出了具體測(cè)試數(shù)據(jù),實(shí)驗(yàn)結(jié)果充分表明CF-ARC算法具有以下良好的特性： (1) 優(yōu)先替換最不常使用干凈頁(yè),降低替換頁(yè)的代價(jià); (2) 替換臟頁(yè)時(shí)按照頁(yè)的訪問(wèn)頻度優(yōu)先替換不常使用頁(yè),能夠保證最熱頁(yè)始終在緩沖區(qū)內(nèi),保證了命中率; (3) 本算法替換冷區(qū)數(shù)據(jù)頁(yè)的時(shí)候考慮到冷區(qū)的大小,因此不會(huì)出現(xiàn)隨著時(shí)間的推移最終冷區(qū)為空的情況.

圖5 物理寫(xiě)操作次數(shù)

4 結(jié)論與展望

隨著科技的發(fā)展、閃存存儲(chǔ)技術(shù)的日益完善,基于閃存數(shù)據(jù)庫(kù)的應(yīng)用也逐漸普及,現(xiàn)有的緩沖區(qū)置換算法大多面向磁盤(pán)設(shè)計(jì),沒(méi)有充分考慮閃存獨(dú)特的特性,無(wú)法取得較好的性能. 一個(gè)高效的緩沖區(qū)置換算法不僅能優(yōu)化PC性能,也能進(jìn)一步促進(jìn)社會(huì)生產(chǎn)力的提高. CF-ARC算法充分考慮閃存的寫(xiě)前擦除、異地更新、讀寫(xiě)速度不對(duì)稱的特性,通過(guò)優(yōu)先替換訪問(wèn)頻度小的冷干凈頁(yè),不但可以最小化驅(qū)逐頁(yè)的代價(jià),而且能避免一個(gè)干凈頁(yè)剛進(jìn)入緩沖區(qū)便被驅(qū)逐的情況,同時(shí)替換訪問(wèn)頻度最小的臟頁(yè)能夠有效的保證最熱臟頁(yè)始終保存在緩沖區(qū)中保證命中率的同時(shí)減少了寫(xiě)操作的次數(shù),從而提高閃存數(shù)據(jù)庫(kù)的性能.

1Chiang ML,Lee PCH,Chang RC. Managing flash memory in personal communication devices. Proceedings of the 1997 IEEE International Symposium on Consumer Electronics.Singapore. 1997. 177-182.

2王江濤,賴文豫,孟小峰. 閃存數(shù)據(jù)庫(kù)： 現(xiàn)狀、技術(shù)與展望.計(jì)算機(jī)學(xué)報(bào),2013,36(8)： 1549-1567.

3Effelsberg W,Haerder T. Principles of database buffer management. ACM Transactions on Database Systems,1984,9(4)： 560-595. [doi： 10.1145/1994.2022]

4Lin MW,Yao ZQ,Huang TQ. F-LRU： An efficient buffer replacement algorithm for NAND flash-based databases.Optik-International Journal for Light and Electron Optics,2016,127(2)： 663-667. [doi： 10.1016/j.ijleo.2015.10.155]

5Park SY,Jung D,Kang JU,et al. CFLRU： A replacement algorithm for flash memory. Proceedings of the 2006 International Conference on Compilers,Architecture and Synthesis for Embedded Systems. Seoul,Korea. 2006.234-241.

6Koltsidas I,Viglas SD. Flashing up the storage layer.Proceedings of the VLDB Endowment,2008,1(1)： 514-525.[doi： 10.14778/1453856]

7Megiddo N,Modha DS. Outperforming LRU with an adaptive replacement cache algorithm. Computer,2004,37(4)： 58-65. [doi： 10.1109/MC.2004.1297303]

8李志. 面向閃存的緩沖區(qū)管理算法研究[碩士學(xué)位論文]. 合肥： 中國(guó)科學(xué)技術(shù)大學(xué),2010.

9Su X,Jin PQ,Xiang XY,et al. Flash-DBsim： A simulation tool for evaluating flash-based database algorithms. 2nd IEEE International Conference on Computer Science and Information Technology. Beijing,China. 2009. 185-189.

10Johnson T,Shasha D. 2Q： A low overhead high performance buffer management replacement algorithm. Proceedings of the 20th International Conference on Very Large Data Bases.San Francisco,CA,USA. 1994. 439-450.

11Jiang S,Zhang X. Making LRU friendly to weak locality workloads： A novel replacement algorithm to improve buffer cache performance. IEEE Transactions on Computers,2005,54(8)： 939-952. [doi： 10.1109/TC.2005.130]