劉翠梅,楊 璇,賈剛勇,韓光潔

1(常州機(jī)電職業(yè)技術(shù)學(xué)院 信息工程學(xué)院,江蘇 常州 213164)2(河海大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 常州 213022)3(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院, 杭州 310018)

1 引 言

基于閃存的固態(tài)硬盤(pán)是近年來(lái)出現(xiàn)的一種新型存儲(chǔ)設(shè)備.這種存儲(chǔ)設(shè)備不僅有優(yōu)秀的帶寬,并且還有良好的隨機(jī)或者順序I/O性能.性能遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的機(jī)械硬盤(pán),更重要的是閃存具有更低的耗電量,而且因?yàn)闆](méi)有可移動(dòng)部件,因此閃存具有比機(jī)械硬盤(pán)更好的可靠性[1].

現(xiàn)在,閃存固態(tài)硬盤(pán)已經(jīng)慢慢成為大型服務(wù)器,便攜計(jì)算機(jī)、移動(dòng)終端、手持設(shè)備等的各種設(shè)備上的存儲(chǔ)部件.然而閃存的異地更新、先擦后寫(xiě)、擦寫(xiě)有次數(shù)限制,寫(xiě)操作時(shí)間遠(yuǎn)大于讀操作時(shí)間等特性需要有效解決,以提高閃存的效率.針對(duì)閃存的特征,閃存的緩存替換算法能夠解決其中的讀寫(xiě)代價(jià)異構(gòu)性和壽命有限性特征,從而可以有效的提高閃存的性能和壽命.所以閃存的緩存替換算法是目前研究的一個(gè)熱點(diǎn)[2].

傳統(tǒng)針對(duì)機(jī)械磁盤(pán)的緩存替換算法不能滿(mǎn)足閃存的上述挑戰(zhàn).大多數(shù)算法只關(guān)注命中率的提高而忽視了替換過(guò)程閃存讀寫(xiě)操作代價(jià)的異構(gòu)性.目前針對(duì)閃存已經(jīng)提出了多種緩存替換算法,如CF-LRU[4],LRU-WSR[5],AD-LRU[3]等,這些算法優(yōu)先從閃存緩沖區(qū)中替換出干凈頁(yè),從而可以減少寫(xiě)入閃存頁(yè)的數(shù)量,降低替換代價(jià).然而現(xiàn)有的這些算法往往優(yōu)先替換干凈頁(yè),導(dǎo)致臟頁(yè)長(zhǎng)時(shí)間保留在緩沖區(qū)中,從而引起干凈頁(yè)的抖動(dòng)現(xiàn)象,即剛調(diào)入緩沖區(qū)就被替換的現(xiàn)象,嚴(yán)重降低了緩沖區(qū)的命中率,增加閃存的讀寫(xiě)操作,降低閃存性能.而且冷臟頁(yè)長(zhǎng)期駐留緩沖區(qū),浪費(fèi)了寶貴的緩沖區(qū)資源,降低系統(tǒng)的性能.

為了解決現(xiàn)有閃存緩沖區(qū)替換算法存在的問(wèn)題,本文提出了一個(gè)代價(jià)感知的細(xì)粒度緩沖區(qū)替換算法(FSO-LRU),這個(gè)算法不但考慮系統(tǒng)的命中率,同時(shí)關(guān)注如何有效的減少寫(xiě)和擦除操作.這個(gè)算法可以由下面的幾點(diǎn)來(lái)介紹.

本文提出的代價(jià)感知的細(xì)粒度緩沖區(qū)替換算法不僅考慮到各頁(yè)的訪(fǎng)問(wèn)頻率和冷熱特征,同時(shí)也考慮到了在頁(yè)替換的時(shí)候讀寫(xiě)代價(jià)的異構(gòu)性特征,優(yōu)先替換代價(jià)小的干凈頁(yè).

同時(shí),代價(jià)感知的細(xì)粒度緩沖區(qū)替換算法還考慮了各頁(yè)的重用概率,重用概率越高,替換代價(jià)越大,重用概率越低,替換代價(jià)越小.從而優(yōu)先替換重用概率低的頁(yè).

結(jié)合讀寫(xiě)代價(jià)的異構(gòu)性特征和重用概率,決定閃存緩沖區(qū)的替換.

本文采用閃存模擬平臺(tái)來(lái)對(duì)提出的代價(jià)感知的細(xì)粒度緩沖區(qū)替換算法進(jìn)行評(píng)價(jià).在不同負(fù)載下對(duì)比多種替換算法,實(shí)驗(yàn)結(jié)果表明代價(jià)感知的細(xì)粒度緩沖區(qū)替換算法具有很好的命中率和較少的擦除/寫(xiě)操作

2 相關(guān)工作

2.1 閃存存儲(chǔ)系統(tǒng)

基于閃存的固態(tài)盤(pán),是由一種基于閃存芯片的新型半導(dǎo)體存儲(chǔ)設(shè)備.閃存主要分為NOR型閃存、NAND型閃存,這些閃存都是基于浮柵場(chǎng)效應(yīng)管作為存儲(chǔ)單位,改變了傳統(tǒng)存儲(chǔ)系統(tǒng)的特性.目前使用較多的是NAND型閃存,本文也是針對(duì)NAND型閃存進(jìn)行研究.

相對(duì)于傳統(tǒng)硬盤(pán),基于閃存的固態(tài)盤(pán)有如下特性：

沒(méi)有機(jī)械延遲,比如沒(méi)有尋道時(shí)間.

運(yùn)用一種寫(xiě)時(shí)擦除機(jī)制來(lái)進(jìn)行數(shù)據(jù)的更新,傳統(tǒng)硬盤(pán)如果運(yùn)用這種機(jī)制就代價(jià)太大.

讀、寫(xiě)、擦除操作有著不一樣的延遲.讀操作最快,擦除操作最慢.

閃存具有擦除限制,SLC、MLC、TLC有著不同的擦除限制SLC大約可擦出100000次、MLC大約可擦除5000次、TLC大約可擦除1000次.當(dāng)閃存芯片達(dá)到擦除閾值的時(shí)候,存儲(chǔ)數(shù)據(jù)將變得不可靠.其中,SLC(Single Level Cell)表示一個(gè)存儲(chǔ)單元存儲(chǔ)一個(gè)信息,MLC(Multi Level Cell)表示一個(gè)單元可以存儲(chǔ)兩個(gè)信息.

閃存芯片的操作過(guò)程比較獨(dú)特,每個(gè)閃存單元相對(duì)獨(dú)立,眾多的閃存芯片綜合形成閃存存儲(chǔ)系統(tǒng).為了統(tǒng)一管理所有的閃存芯片,固態(tài)盤(pán)中給出了一個(gè)統(tǒng)一的軟件層次,叫做文件轉(zhuǎn)換層(File Translate Layer).文件轉(zhuǎn)換層的主要功能是實(shí)現(xiàn)將上層文件系統(tǒng)所有的請(qǐng)求通過(guò)地址映射、操作分類(lèi)等,轉(zhuǎn)換為各個(gè)單元的閃存操作[7].

為了提高閃存存儲(chǔ)單元的性能,固態(tài)盤(pán)中有一個(gè)緩沖區(qū)用于緩存閃存數(shù)據(jù),從而減少對(duì)閃存單元的讀寫(xiě)操作,有利于閃存性能的提升和壽命的延長(zhǎng).圖1給出了閃存的整體架構(gòu)[8].

圖1 閃存的整體架構(gòu)Fig. 1 Framework of flash

2.2 傳統(tǒng)的緩存替換策略

緩存管理可以說(shuō)是固態(tài)硬盤(pán)里面的一個(gè)關(guān)鍵部分,緩沖區(qū)能夠加速閃存數(shù)據(jù)的訪(fǎng)問(wèn),同時(shí)減少對(duì)閃存的讀寫(xiě)操作,也就有效降低閃存的擦除過(guò)程,從而對(duì)固態(tài)盤(pán)的性能和壽命起到很好的提升.通常,我們假定有兩級(jí)存儲(chǔ)系統(tǒng),主存和外部(第二級(jí))存儲(chǔ)系統(tǒng).它們?cè)谶壿嬌隙急唤M織成一組邏輯頁(yè)的形式,邏輯頁(yè)是兩級(jí)存儲(chǔ)之間的唯一交換單元.當(dāng)上層模塊請(qǐng)求頁(yè)面時(shí),如果數(shù)據(jù)頁(yè)沒(méi)有在緩存中,緩存管理必須從二級(jí)存儲(chǔ)設(shè)備讀取數(shù)據(jù).如果沒(méi)有可用的頁(yè)框,必須選擇一些頁(yè)面淘汰.緩存替換策略的好壞決定緩存管理的性能[9].

傳統(tǒng)替換算法主要關(guān)注于命中率,因?yàn)樵跈C(jī)械磁盤(pán)中,讀操作和寫(xiě)操作的代價(jià)是一致的,高命中率就等于低代價(jià),也意味著高性能.許多算法因此被提出.他們大多基于最近最久未使用(LRU)算法,或者最近最少使用算法[10].

所有傳統(tǒng)的算法都沒(méi)有考慮閃存的讀寫(xiě)不對(duì)稱(chēng)性[11].然而,減少閃存的讀寫(xiě)次數(shù),不僅有助于減少運(yùn)行時(shí)間,還可以延長(zhǎng)固態(tài)盤(pán)的使用壽命.因此近些年來(lái)緩存替換算法大多研究如何減少寫(xiě)操作次數(shù).

2.3 現(xiàn)有的閃存緩沖區(qū)替換算法

CFLRU是第一個(gè)基于閃存的緩存算法.它把LRU分為工作區(qū)和和Clean-First區(qū)域,該區(qū)域有個(gè)窗口大小w,替換總是發(fā)生在Clean-First區(qū)域中的最近最少使用干凈頁(yè)面中,因此減少了寫(xiě)操作的數(shù)量.如果沒(méi)有干凈頁(yè)面在Clean-First區(qū)域中,那么CFLRU會(huì)退化成LRU.所以CFLRU有下列問(wèn)題：

窗口大小必須根據(jù)不同的負(fù)載進(jìn)行調(diào)整,不能適應(yīng)不同的負(fù)載,因此根據(jù)這個(gè)原因,提出了一種動(dòng)態(tài)調(diào)整窗口大小的根據(jù)周期性的讀寫(xiě)比例來(lái)動(dòng)態(tài)的調(diào)整窗口大小.但是這在真實(shí)場(chǎng)景中是不夠的,這是因?yàn)橐玫木植啃院途彌_區(qū)大小對(duì)窗口w大小有著實(shí)質(zhì)的影響；

CFLRU優(yōu)先替換干凈頁(yè),從而造成冷臟頁(yè)長(zhǎng)時(shí)間留在緩存中,導(dǎo)致系統(tǒng)命中率的下降；

需要在Clean-First區(qū)域中找尋干凈頁(yè)來(lái)進(jìn)行替換,帶來(lái)了額外的開(kāi)銷(xiāo)；

CFLRU同LRU一樣,沒(méi)有考慮訪(fǎng)問(wèn)頻率的影響.

LRU-WSR算法首先將數(shù)據(jù)進(jìn)行冷熱劃分,將僅僅只有一次訪(fǎng)問(wèn)的數(shù)據(jù)劃分為冷數(shù)據(jù),將多次訪(fǎng)問(wèn)的數(shù)據(jù)劃分為熱數(shù)據(jù).因?yàn)榕K數(shù)據(jù)替換時(shí)需要寫(xiě)回操作,代價(jià)較高,同時(shí)熱數(shù)據(jù)重用的概率較大,因此LRU-WSR優(yōu)先替換冷數(shù)據(jù),盡量長(zhǎng)時(shí)間的保留熱臟數(shù)據(jù),減少對(duì)閃存的寫(xiě)操作,從而降低了閃存的開(kāi)銷(xiāo),提高性能.

AD-LRU算法首先將緩沖區(qū)劃分為冷區(qū)和熱區(qū),冷區(qū)由僅僅一次訪(fǎng)問(wèn)的緩存頁(yè)組成,熱區(qū)由訪(fǎng)問(wèn)過(guò)至少2次以上的緩存頁(yè)組成.然而,冷區(qū)和熱區(qū)的大小是根據(jù)數(shù)據(jù)訪(fǎng)問(wèn)的情況動(dòng)態(tài)的變化的.AD-LRU算法給出了一個(gè)冷、熱區(qū)的閾值,當(dāng)冷區(qū)的存儲(chǔ)空間大于等于閾值,替換發(fā)生在冷區(qū),否則,熱區(qū)中的數(shù)據(jù)頁(yè)被替換.

讀寫(xiě)代價(jià)的非一致性已經(jīng)融合到現(xiàn)有的緩沖區(qū)替換算法中,但是沒(méi)有細(xì)粒度的考慮閃存緩沖區(qū)中各頁(yè)的重用性,重用性越高,被重復(fù)讀寫(xiě)的概率越高,替換代價(jià)就越大；重用性越低,被重復(fù)讀寫(xiě)的概率越低,替換代價(jià)就越小.只有在替換時(shí)結(jié)合了緩沖區(qū)各頁(yè)的讀寫(xiě)異構(gòu)性和重用性才能保證替換代價(jià)最低,才能提高系統(tǒng)的性能.

為了提高系統(tǒng)的性能,降低寫(xiě)閃存的次數(shù)和延長(zhǎng)閃存壽命,本文提出了代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法,不但考慮閃存讀寫(xiě)操作的異構(gòu)性,而且結(jié)合閃存緩沖區(qū)中各頁(yè)的重用性.

3 代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法(FSO-LRU)

基于閃存的緩存替換算法,我們不僅需要考慮到命中率,還要考慮到寫(xiě)閃存代價(jià).替換干凈頁(yè)可以減少寫(xiě)操作的數(shù)量,從而減少了負(fù)載運(yùn)行的時(shí)間.但是傳統(tǒng)的算法不總是替換干凈頁(yè).CF-LRU和LRU-WSR總是優(yōu)先從緩存中選擇干凈頁(yè)進(jìn)行替換.AD-LRU將緩沖區(qū)分成冷、熱兩個(gè)區(qū),但是沒(méi)有考慮替換的代價(jià)問(wèn)題,所以會(huì)導(dǎo)致干凈頁(yè)可能剛進(jìn)入緩存區(qū)就被替換；冷臟頁(yè)長(zhǎng)時(shí)間在緩沖區(qū)中,浪費(fèi)資源.基于這些原因,命中率可能會(huì)受很大影響.

因此,本文考慮在傳統(tǒng)的最近最久未使用算法(LRU)上結(jié)合替換代價(jià)、訪(fǎng)問(wèn)頻率、以及數(shù)據(jù)的局部性用以降低寫(xiě)入代價(jià),同時(shí)提高緩存命中率.

代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法的思想如下：

用4個(gè)LRU隊(duì)列來(lái)存儲(chǔ)數(shù)據(jù)訪(fǎng)問(wèn)的頻率和最近訪(fǎng)問(wèn),分別分為熱-干凈隊(duì)列、熱-臟隊(duì)列、冷-干凈隊(duì)列、冷臟隊(duì)列.冷LRU隊(duì)列存儲(chǔ)只訪(fǎng)問(wèn)一次的頁(yè)；熱隊(duì)列用于存儲(chǔ)訪(fǎng)問(wèn)超過(guò)一次的頁(yè).所以,熱-干凈隊(duì)列存儲(chǔ)訪(fǎng)問(wèn)次數(shù)超過(guò)一次且沒(méi)有被修改過(guò)的頁(yè)；熱-臟隊(duì)列用于存儲(chǔ)訪(fǎng)問(wèn)次數(shù)超過(guò)一次但被修改過(guò)的頁(yè)；冷-干凈隊(duì)列存儲(chǔ)訪(fǎng)問(wèn)次數(shù)為一次且沒(méi)有被修改過(guò)的頁(yè)；冷-臟隊(duì)列用于存儲(chǔ)訪(fǎng)問(wèn)次數(shù)為一次但被修改過(guò)的頁(yè).

4個(gè)隊(duì)列的大小是動(dòng)態(tài)調(diào)整的,當(dāng)一個(gè)冷頁(yè)被再次訪(fǎng)問(wèn)時(shí),這時(shí)這個(gè)頁(yè)就根據(jù)其臟或者干凈屬性被替換到熱隊(duì)列中去.此時(shí),對(duì)應(yīng)的冷隊(duì)列中的長(zhǎng)度就減少,相應(yīng)熱隊(duì)列的長(zhǎng)度就增加.

在進(jìn)行淘汰的時(shí)候,我們?cè)谒膫€(gè)隊(duì)列中選擇一個(gè)頁(yè)進(jìn)行替換.替換的依據(jù)是根據(jù)不同的代價(jià)與訪(fǎng)問(wèn)頻度來(lái)進(jìn)行替換,替換的頁(yè)依據(jù)公式(1)進(jìn)行選擇.

prob=recency*cost(cc,cd,hc,hd),select_P

=min(cc,cd,hc,hd)

(1)

如公式(1)所示,recency表示該頁(yè)面最近訪(fǎng)問(wèn)的頻率,cost(cc,cd,hc,hd)表示選擇一個(gè)頁(yè)面的代價(jià),其中cc表示冷干凈頁(yè),cd表示冷臟頁(yè),hc表示熱干凈頁(yè),hd表示熱臟頁(yè),而替換的代價(jià)通常情況是costcc

如圖2所示,4個(gè)LRU鏈表構(gòu)成了整個(gè)代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法的核心.當(dāng)在一個(gè)冷干凈鏈表中命中一個(gè)頁(yè)面時(shí)候,將該頁(yè)依據(jù)讀寫(xiě)不同替換到相應(yīng)的頁(yè)面中去.這里假設(shè)將頁(yè)面替換到熱干凈鏈表中去.那么這樣熱干凈隊(duì)列長(zhǎng)度增加,冷干凈頁(yè)面長(zhǎng)度減少,從而實(shí)現(xiàn)了鏈表長(zhǎng)度的動(dòng)態(tài)增減.

圖2 四個(gè)LRU列表Fig.2 List of four LRUs

頁(yè)面替換總是發(fā)生在LRU鏈表尾部,當(dāng)每次找尋得時(shí)候,我們會(huì)從四個(gè)LRU鏈表里面找一個(gè)該種屬性最近沒(méi)有被訪(fǎng)問(wèn)的元素來(lái)進(jìn)行選擇.根據(jù)其替換的代價(jià)和最近訪(fǎng)問(wèn)的時(shí)間來(lái)計(jì)算出替換該鏈表LRU頁(yè)的代價(jià).從中選擇最小替換代價(jià)的頁(yè)把其進(jìn)行替換.如果在進(jìn)行選擇替換的時(shí)候,里面其中有一個(gè)或者兩個(gè)隊(duì)列為空,那么我們就從非空的隊(duì)列里進(jìn)行選擇替換.算法1給出了本文提出的FSO-LRU算法的偽代碼.

Algorithm1：FSO-LRU

data：Lcc,Lcd,Lhc,Lhd,Lmeans list

ifpis inL(cc,cd,hc,hd)then//pis in the buffer

AdjustList(L(cc,cd,hc,hd))

else//pis not in the buffer

ifthere is free space in the bufferthen

adjustLccorLcdand putpinto its MRU

else

victim=SelectVictim(L(cc,cd,hc,hd))

ifvictim is dirtythen

WriteDirty(P)

圖2說(shuō)明了一個(gè)頁(yè)面中如果命中,應(yīng)該如何進(jìn)行調(diào)整.算法2給出了頁(yè)面在不同列表中的調(diào)整過(guò)程.如果在冷鏈表中命中了,需要調(diào)整鏈表的位置,把這個(gè)頁(yè)面移動(dòng)到熱鏈表中.比如,一個(gè)頁(yè)原本是冷干凈頁(yè),現(xiàn)在對(duì)這個(gè)頁(yè)面進(jìn)行了讀操作,那么原來(lái)的冷干凈頁(yè)就被移動(dòng)到熱干凈鏈表中去；如果對(duì)該頁(yè)進(jìn)行了一個(gè)寫(xiě)操作,那么原來(lái)的頁(yè)面就被移動(dòng)到熱臟頁(yè)列表中.

Algorithm2：AdjustList

data：Lcc,Lcd,Lhc,Lhd,Lmeans list

ifpis inLccthen

movep// movepmeans adjust lru lists by its operation and feature

elseifpis inLcdthen

movep

elseifpis inLhcthen

movep

elseifp is inLhdthen

movep

算法3選擇驅(qū)逐頁(yè)的時(shí)候依據(jù)公式(1)從每個(gè)鏈表里面的LRU中選出最代價(jià)最小的頁(yè)進(jìn)行替換,保留替換代價(jià)大的頁(yè),從而減少擦除/寫(xiě)操作的目的.

Algorithm3：SelectVictim

data：Lcc,Lcd,Lhc,Lhc,Lmeans list

prob(cc,cd,hc,hd)=recency*cost(cc,cd,hc,hd)

select_P=min(cc,cd,hc,hd)

victim=select_P

FSO-LRU 與CF-LRU、LRU-WSR、AD-LRU都具有減少寫(xiě)操作總體目標(biāo).FSO是一個(gè)新的設(shè)計(jì),它與其他幾種算法的不同具體如下所示：

1)FSO-LRU 考慮了訪(fǎng)問(wèn)的頻度,以及替換頁(yè)面所需要的代價(jià).這是CF-LRU和LRU-WSR沒(méi)有考慮過(guò)的.AD-LRU雖然考慮了頁(yè)面所命中的頻度,但是沒(méi)有考慮到替換替換頁(yè)的代價(jià)與頻度的一個(gè)關(guān)系.

2)CF-LRU會(huì)優(yōu)先替換工作區(qū)域的干凈頁(yè).如果沒(méi)有找到頁(yè)面的話(huà)會(huì)替換工作區(qū)的臟頁(yè),此時(shí)CF-LRU就可能退化為L(zhǎng)RU.

3)LRU-WSR雖然避免了冷臟頁(yè)長(zhǎng)時(shí)間駐留內(nèi)存,但是沒(méi)有考慮干凈頁(yè)的冷熱屬性.而且找尋替換頁(yè)的代價(jià)相對(duì)較大.

4)AD-LRU將緩沖區(qū)分為熱區(qū)和冷區(qū).其中冷熱區(qū)域是動(dòng)態(tài)調(diào)整的.其中冷區(qū)域容量有一個(gè)下界min_lc,因此,當(dāng)冷區(qū)域大小小于min_lc時(shí),替換總是發(fā)生在熱區(qū)域.AD-LRU總是替換干凈頁(yè),無(wú)法避免干凈頁(yè)剛進(jìn)入緩沖區(qū)就被替換的情況,冷臟頁(yè)長(zhǎng)期留在內(nèi)存,浪費(fèi)了寶貴的資源,降低了命中率.

4 實(shí)驗(yàn)與性能評(píng)價(jià)

該部分先介紹實(shí)驗(yàn)的設(shè)計(jì),然后通過(guò)實(shí)驗(yàn)得到了代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法獲得最佳性能的參數(shù)配置,最后通過(guò)對(duì)比現(xiàn)有的幾種典型算法來(lái)評(píng)價(jià)本文提出的FSO-LRU算法的性能.

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

本文基于Flash-DBSim[6]模擬器實(shí)現(xiàn)了FSO-LRU算法,同時(shí)為了實(shí)現(xiàn)對(duì)比,在該模擬器中也實(shí)現(xiàn)LRU、LRU-WSR、AD-LRU幾個(gè)現(xiàn)有的典型緩沖區(qū)替換算法.Flash-DBSim模擬器具有許多優(yōu)點(diǎn),包括平臺(tái)的開(kāi)放性,能支持各種不同的算法等,是目前使用較多的模擬器平臺(tái).

表1給出了本文采用的閃存配置參數(shù).文中模擬一個(gè)容量大小為128MB的NAND固態(tài)盤(pán),頁(yè)面的大小為2KB,每個(gè)數(shù)據(jù)塊中有64個(gè)頁(yè),讀操作的代價(jià),寫(xiě)操作的代價(jià)已經(jīng)擦除操作的代價(jià)在表中給出,同時(shí)參考了現(xiàn)在主流NAND固態(tài)盤(pán)的參數(shù).

為了盡可能模擬真實(shí)固態(tài)盤(pán)的數(shù)據(jù)頁(yè)的訪(fǎng)問(wèn)模擬,我們產(chǎn)生了4種符合Zipf分布的測(cè)試數(shù)據(jù).表2給出了4組數(shù)據(jù)集的特征,其中讀/寫(xiě)比例的參數(shù)給出了數(shù)據(jù)集中讀操作所占的比例以及寫(xiě)操作所占的比例,如Trace1的讀/寫(xiě)比例90%/10%表示Trace1中90%的操作是讀操作,10%的操作是寫(xiě)操作.局部性的參數(shù)給出了數(shù)據(jù)集的局部性特征,比如Trace1中局部性是60%/40%,其所表示的含義是指60%的操作集中在40%的數(shù)據(jù)頁(yè)中.為了評(píng)價(jià)算法的性能,本文主要針對(duì)以下幾個(gè)參數(shù)進(jìn)行對(duì)比：

表1 NAND固態(tài)盤(pán)的配置參數(shù)Table 1 Characteristic parameters of NAND flash

1)命中率：對(duì)比閃存系統(tǒng)總體的命中率；

2)物理讀操作(讀閃存)的次數(shù)：讀操作次數(shù)部分反映了緩存替換算法有沒(méi)有考慮讀操作；

3)物理寫(xiě)操作(寫(xiě)閃存)的次數(shù)：寫(xiě)操作次數(shù)是緩存替換算法優(yōu)劣的一個(gè)重要指標(biāo)；

4)運(yùn)行時(shí)間：緩存替換算法總體性能的綜合體現(xiàn).

表2 測(cè)試數(shù)據(jù)集的統(tǒng)計(jì)信息Table 2 Statistical information about test data

在對(duì)CF-LRU進(jìn)行性能比較的時(shí)候參數(shù)W設(shè)置為0.5,在對(duì)AD-LRU的性能進(jìn)行比較的時(shí)候.

4.2 FSO-LRU最佳參數(shù)設(shè)置

結(jié)合頁(yè)替換的真實(shí)代價(jià)以及實(shí)驗(yàn)結(jié)果,本文將代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法的參數(shù)設(shè)置如下：cold_clean_cost=0.1,cold_dirty_cost=1.5,這個(gè)是冷鏈表的代價(jià).hot_clean_cost=0.7,hot_dirty_cost=3.5,min_lc=0.其中min_lc是參考AD-LRU進(jìn)行設(shè)置.實(shí)驗(yàn)表明min_lc=0時(shí)實(shí)驗(yàn)效果最好.

4.3 命中率

圖3給出了不同緩沖區(qū)替換算法的命中率.基于實(shí)驗(yàn)數(shù)據(jù)可以發(fā)現(xiàn)：基于數(shù)據(jù)訪(fǎng)問(wèn)頻度和數(shù)據(jù)冷熱性的算法比沒(méi)有考慮數(shù)據(jù)訪(fǎng)問(wèn)頻度的算法在命中率上有更好的表現(xiàn).我們從圖中可以看出代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法在數(shù)據(jù)局部性較差(Trace 1)的情況下,比其他同類(lèi)算法有著更高的命中率.緩沖區(qū)大小為5MB時(shí),在數(shù)據(jù)集為T(mén)race 1的試驗(yàn)中,代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法比其他相似的算法有著更高的命中率.AD-LRU緩沖區(qū)替換算法的時(shí)間的命中率大約在34%,LRU算法的命中率大約在27%,而我們提出的代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法緩沖區(qū)替換算法的命中率大約在35%左右,比LRU算法高了接近7.5%.如果數(shù)據(jù)的局部性更好一些,在數(shù)據(jù)Trance4中,我們可以看到代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法在緩存大小為4M的時(shí)候,命中率高達(dá)77.9%,而普通的LRU,命中率只有57.8%.因此我們可以看出代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法在局部性較好的負(fù)載中,具有巨大優(yōu)勢(shì).

圖3 在不同數(shù)據(jù)集上的命中率比較Fig. 3 Comparisons of hit rates on different data sets

4.4 閃存讀次數(shù)分析

圖4給出了不同的緩沖區(qū)替換算法在物理閃存讀操作上的不同表現(xiàn)結(jié)果.實(shí)驗(yàn)數(shù)據(jù)同樣表明：基于數(shù)據(jù)訪(fǎng)問(wèn)頻度和數(shù)據(jù)冷熱性的算法比沒(méi)有考慮數(shù)據(jù)訪(fǎng)問(wèn)頻度以及冷熱屬性的緩沖區(qū)替換算法在物理頁(yè)讀操作的參數(shù)上表現(xiàn)得更好.

圖4 在不同數(shù)據(jù)集上讀閃存次數(shù)Fig. 4 Comparisons of flash read times on different data sets

在緩存大小為4MB的情況下,代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法在Trace 1數(shù)據(jù)集中的讀閃存次數(shù)約為2150k次,而LRU的讀閃存次數(shù)大約為2300k次,AD-LRU讀閃存次數(shù)大約為2220k次.

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

圖5給出不同緩存替換算法在寫(xiě)操作次數(shù)這個(gè)參數(shù)上的性能表現(xiàn).實(shí)驗(yàn)數(shù)據(jù)結(jié)果表明結(jié)合數(shù)據(jù)訪(fǎng)存頻度和數(shù)據(jù)冷熱特征的緩存替換算法比其他算法表現(xiàn)得更好,具有更少的物理寫(xiě)操作次數(shù).

圖5 在不同數(shù)據(jù)集上寫(xiě)閃存次數(shù)Fig. 5 Comparisons of flash write times on different data sets

在緩存大小為5MB的情況下,代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法在Trace 1數(shù)據(jù)集中的寫(xiě)閃存次數(shù)約為125次,而LRU的讀閃存次數(shù)大約為362次,AD-LRU讀閃存次數(shù)大約為276次.

5 結(jié)束語(yǔ)

隨著閃存越來(lái)越普及,閃存的使用壽命和I/O性能以通過(guò)改善緩存替換算法來(lái)進(jìn)行改善.NAND閃存的讀寫(xiě)速度和傳統(tǒng)的DRAM讀寫(xiě)時(shí)間還是有差距的,所以采用緩存是有必要的.我們需要減少寫(xiě)閃存的次數(shù),根據(jù)閃存的讀寫(xiě)不對(duì)稱(chēng)性,因此我們提出了四鏈表形式的代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法,動(dòng)態(tài)的調(diào)整四個(gè)隊(duì)列的長(zhǎng)度,以及訪(fǎng)問(wèn)時(shí)間遠(yuǎn)近的信息,以及替換代價(jià),我們動(dòng)態(tài)的選擇隊(duì)列中的替換頁(yè).保證了命中率以及寫(xiě)操作數(shù)的減少.

然而本文的一個(gè)研究假設(shè)是閃存固態(tài)盤(pán)的讀寫(xiě)代價(jià)比是固定的.然而,現(xiàn)實(shí)中讀寫(xiě)代價(jià)比可以是動(dòng)態(tài)調(diào)整的.所以,之后研究工作會(huì)重點(diǎn)考慮讀寫(xiě)代價(jià)比非固定的設(shè)備上分析代價(jià)感知的細(xì)粒度閃存緩沖區(qū)替換算法的性能表現(xiàn),從而為不同讀寫(xiě)代價(jià)別的設(shè)備確定最優(yōu)的參數(shù)組合.