一種代價感知的細粒度閃存緩沖區(qū)替換算法

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

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

1 引 言

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

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

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

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

本文提出的代價感知的細粒度緩沖區(qū)替換算法不僅考慮到各頁的訪問頻率和冷熱特征,同時也考慮到了在頁替換的時候讀寫代價的異構性特征,優(yōu)先替換代價小的干凈頁.

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

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

本文采用閃存模擬平臺來對提出的代價感知的細粒度緩沖區(qū)替換算法進行評價.在不同負載下對比多種替換算法,實驗結果表明代價感知的細粒度緩沖區(qū)替換算法具有很好的命中率和較少的擦除/寫操作

2 相關工作

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

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

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

沒有機械延遲,比如沒有尋道時間.

運用一種寫時擦除機制來進行數據的更新,傳統(tǒng)硬盤如果運用這種機制就代價太大.

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

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

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

為了提高閃存存儲單元的性能,固態(tài)盤中有一個緩沖區(qū)用于緩存閃存數據,從而減少對閃存單元的讀寫操作,有利于閃存性能的提升和壽命的延長.圖1給出了閃存的整體架構[8].

圖1 閃存的整體架構Fig. 1 Framework of flash

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

緩存管理可以說是固態(tài)硬盤里面的一個關鍵部分,緩沖區(qū)能夠加速閃存數據的訪問,同時減少對閃存的讀寫操作,也就有效降低閃存的擦除過程,從而對固態(tài)盤的性能和壽命起到很好的提升.通常,我們假定有兩級存儲系統(tǒng),主存和外部(第二級)存儲系統(tǒng).它們在邏輯上都被組織成一組邏輯頁的形式,邏輯頁是兩級存儲之間的唯一交換單元.當上層模塊請求頁面時,如果數據頁沒有在緩存中,緩存管理必須從二級存儲設備讀取數據.如果沒有可用的頁框,必須選擇一些頁面淘汰.緩存替換策略的好壞決定緩存管理的性能[9].

傳統(tǒng)替換算法主要關注于命中率,因為在機械磁盤中,讀操作和寫操作的代價是一致的,高命中率就等于低代價,也意味著高性能.許多算法因此被提出.他們大多基于最近最久未使用(LRU)算法,或者最近最少使用算法[10].

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

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

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

窗口大小必須根據不同的負載進行調整,不能適應不同的負載,因此根據這個原因,提出了一種動態(tài)調整窗口大小的根據周期性的讀寫比例來動態(tài)的調整窗口大小.但是這在真實場景中是不夠的,這是因為引用的局部性和緩沖區(qū)大小對窗口w大小有著實質的影響；

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

需要在Clean-First區(qū)域中找尋干凈頁來進行替換,帶來了額外的開銷；

CFLRU同LRU一樣,沒有考慮訪問頻率的影響.

LRU-WSR算法首先將數據進行冷熱劃分,將僅僅只有一次訪問的數據劃分為冷數據,將多次訪問的數據劃分為熱數據.因為臟數據替換時需要寫回操作,代價較高,同時熱數據重用的概率較大,因此LRU-WSR優(yōu)先替換冷數據,盡量長時間的保留熱臟數據,減少對閃存的寫操作,從而降低了閃存的開銷,提高性能.

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

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

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

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

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

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

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

用4個LRU隊列來存儲數據訪問的頻率和最近訪問,分別分為熱-干凈隊列、熱-臟隊列、冷-干凈隊列、冷臟隊列.冷LRU隊列存儲只訪問一次的頁；熱隊列用于存儲訪問超過一次的頁.所以,熱-干凈隊列存儲訪問次數超過一次且沒有被修改過的頁；熱-臟隊列用于存儲訪問次數超過一次但被修改過的頁；冷-干凈隊列存儲訪問次數為一次且沒有被修改過的頁；冷-臟隊列用于存儲訪問次數為一次但被修改過的頁.

4個隊列的大小是動態(tài)調整的,當一個冷頁被再次訪問時,這時這個頁就根據其臟或者干凈屬性被替換到熱隊列中去.此時,對應的冷隊列中的長度就減少,相應熱隊列的長度就增加.

在進行淘汰的時候,我們在四個隊列中選擇一個頁進行替換.替換的依據是根據不同的代價與訪問頻度來進行替換,替換的頁依據公式(1)進行選擇.

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

=min(cc,cd,hc,hd)

(1)

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

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

圖2 四個LRU列表Fig.2 List of four LRUs

頁面替換總是發(fā)生在LRU鏈表尾部,當每次找尋得時候,我們會從四個LRU鏈表里面找一個該種屬性最近沒有被訪問的元素來進行選擇.根據其替換的代價和最近訪問的時間來計算出替換該鏈表LRU頁的代價.從中選擇最小替換代價的頁把其進行替換.如果在進行選擇替換的時候,里面其中有一個或者兩個隊列為空,那么我們就從非空的隊列里進行選擇替換.算法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說明了一個頁面中如果命中,應該如何進行調整.算法2給出了頁面在不同列表中的調整過程.如果在冷鏈表中命中了,需要調整鏈表的位置,把這個頁面移動到熱鏈表中.比如,一個頁原本是冷干凈頁,現(xiàn)在對這個頁面進行了讀操作,那么原來的冷干凈頁就被移動到熱干凈鏈表中去；如果對該頁進行了一個寫操作,那么原來的頁面就被移動到熱臟頁列表中.

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選擇驅逐頁的時候依據公式(1)從每個鏈表里面的LRU中選出最代價最小的頁進行替換,保留替換代價大的頁,從而減少擦除/寫操作的目的.

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都具有減少寫操作總體目標.FSO是一個新的設計,它與其他幾種算法的不同具體如下所示：

1)FSO-LRU 考慮了訪問的頻度,以及替換頁面所需要的代價.這是CF-LRU和LRU-WSR沒有考慮過的.AD-LRU雖然考慮了頁面所命中的頻度,但是沒有考慮到替換替換頁的代價與頻度的一個關系.

2)CF-LRU會優(yōu)先替換工作區(qū)域的干凈頁.如果沒有找到頁面的話會替換工作區(qū)的臟頁,此時CF-LRU就可能退化為LRU.

3)LRU-WSR雖然避免了冷臟頁長時間駐留內存,但是沒有考慮干凈頁的冷熱屬性.而且找尋替換頁的代價相對較大.

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

4 實驗與性能評價

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

4.1 實驗設計

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

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

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

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

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

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

3)物理寫操作(寫閃存)的次數：寫操作次數是緩存替換算法優(yōu)劣的一個重要指標；

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

表2 測試數據集的統(tǒng)計信息Table 2 Statistical information about test data

在對CF-LRU進行性能比較的時候參數W設置為0.5,在對AD-LRU的性能進行比較的時候.

4.2 FSO-LRU最佳參數設置

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

4.3 命中率

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

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

4.4 閃存讀次數分析

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

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

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

4.5 物理寫操作次數

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

圖5 在不同數據集上寫閃存次數Fig. 5 Comparisons of flash write times on different data sets

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

5 結束語

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

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