雷兵兵,嚴(yán) 華

四川大學(xué) 電子信息學(xué)院,成都 610065)(*通信作者電子郵箱296751736@qq.com)

基于邏輯區(qū)間熱度的NAND閃存垃圾回收算法

雷兵兵*,嚴(yán) 華

四川大學(xué) 電子信息學(xué)院,成都 610065)(*通信作者電子郵箱296751736@qq.com)

針對(duì)現(xiàn)有的NAND閃存垃圾回收算法中回收性能不高,磨損均衡效果差,并且算法內(nèi)存開(kāi)銷大的問(wèn)題,提出了一種基于邏輯區(qū)間熱度的垃圾回收算法。該算法重新定義了熱度計(jì)算公式,把連續(xù)邏輯地址的NAND內(nèi)存定義為一個(gè)熱度區(qū)間,以邏輯區(qū)間的熱度來(lái)代替邏輯頁(yè)的熱度,并將不同熱度的數(shù)據(jù)分開(kāi)存儲(chǔ)到不同擦除次數(shù)的閃存塊上,有效地實(shí)現(xiàn)了數(shù)據(jù)冷熱分離,并且節(jié)約了內(nèi)存空間。同時(shí),算法還構(gòu)造了一種新的回收代價(jià)函數(shù)來(lái)選擇回收塊,在考慮回收效率的同時(shí),還兼顧了磨損均衡的問(wèn)題。實(shí)驗(yàn)結(jié)果表明,該算法與性能優(yōu)異的FaGC算法相比,總的擦除次數(shù)減少了11%,總的拷貝次數(shù)減少了13%,擦次數(shù)最大差值減少了42%,內(nèi)存消耗能減少了75%。因此,該算法有利于增加閃存可用空間,改善閃存系統(tǒng)的讀寫(xiě)性能,延長(zhǎng)閃存使用壽命。

NAND閃存;磨損均衡;垃圾回收;邏輯區(qū)間;回收塊

0 引言

如今NAND Flash已經(jīng)被廣泛地運(yùn)用在嵌入式系統(tǒng)中,例如手機(jī)、平板電腦、數(shù)碼相機(jī)等。閃存正逐漸代替硬盤,成為一種流行的存儲(chǔ)設(shè)備。它和傳統(tǒng)硬盤相比有許多優(yōu)點(diǎn),如體積小、功耗低、非易失、抗震性好、便攜性好[1-2]等。閃存由若干個(gè)物理塊(block)組成,每個(gè)塊又包含若干個(gè)物理頁(yè)(page),頁(yè)是讀和寫(xiě)的最小單位,塊是擦除操作的最小單位。讀寫(xiě)操作具有嚴(yán)重的不對(duì)稱性,寫(xiě)操作的速度比讀操作慢很多,而擦除操作相對(duì)于讀寫(xiě)操作來(lái)說(shuō)相當(dāng)慢且具有較大的功耗。閃存設(shè)備在寫(xiě)操作之前往往都要執(zhí)行擦除操作,即具有“寫(xiě)前擦除”[3]的硬件特性。為了緩解寫(xiě)前擦除的延遲,它采用“異地更新”(out-of-place update)[4]策略,即在執(zhí)行更新操作時(shí),將更新后的數(shù)據(jù)寫(xiě)入其他位置,并將原數(shù)據(jù)所在的物理頁(yè)標(biāo)記為無(wú)效頁(yè)。當(dāng)閃存中無(wú)效頁(yè)越來(lái)越多時(shí),必須進(jìn)行進(jìn)行垃圾回收將無(wú)效頁(yè)數(shù)據(jù)擦除,來(lái)獲取更多的空閑空間。閃存中每個(gè)塊允許的擦寫(xiě)次數(shù)是有限的,一般是104～105次。一旦某個(gè)塊的擦除次數(shù)達(dá)到了上限,數(shù)據(jù)存儲(chǔ)將變得不可靠,進(jìn)而影響到整個(gè)閃存的讀寫(xiě)性能和效率。

由于NAND閃存的特點(diǎn),垃圾回收算法需要考慮減少回收代價(jià)、獲得更好的磨損均衡度[5]以延長(zhǎng)閃存的使用壽命,同時(shí)電子產(chǎn)品的內(nèi)存容量有限,還需要考慮算法對(duì)系統(tǒng)的內(nèi)存消耗。Wu等[6]提出了GR(GReedy)算法,該算法選擇無(wú)效頁(yè)最多的塊作為回收塊,以減少回收時(shí)對(duì)有效頁(yè)的拷貝次數(shù),這樣的回收塊選擇策略雖然回收效率較高,但是并沒(méi)有考慮塊的磨損均衡度,在存儲(chǔ)大量冷數(shù)據(jù)的系統(tǒng)中磨損均衡效果比較差。Kawaguhi等[7]提出了CB(Cost-Benefit)回收算法,該算法選擇使age×(1-u)/2u值最大的塊作為回收塊。其中：u表示塊中有效頁(yè)的比例,1-u表示塊中無(wú)效頁(yè)的比例,2u表示塊中有效頁(yè)遷移代價(jià)；age表示物理塊的年齡,即當(dāng)前物理塊更新距離上一次更新的時(shí)間差。算法中物理塊年齡的引入,使得那些數(shù)據(jù)長(zhǎng)期沒(méi)有更新的物理塊得到更多的擦除機(jī)會(huì),在一定程度上改善了磨損均衡效果。Chiang等[8]提出了CAT(Cost-Age-Times)算法,該算法選擇使age×(1-u)/(2u×n)值最大的塊作為回收塊。其中：u表示塊中有效頁(yè)的比例；age表示塊的物理年齡；n表示塊的擦除次數(shù)。由于CAT算法在回收塊時(shí)考慮了塊的擦除次數(shù),并且通過(guò)塊的擦除次數(shù)對(duì)冷熱數(shù)據(jù)進(jìn)行了分離,磨損均衡效果要好于GR和CB。但CAT算法中以最近一次物理塊的更新時(shí)間來(lái)反映物理塊的年齡和以物理塊的擦除次數(shù)來(lái)判定數(shù)據(jù)熱不夠準(zhǔn)確,冷熱分離效果并不好。Yan等[9]提出了FaGC算法,該算法基于文件結(jié)構(gòu),準(zhǔn)確定義了邏輯頁(yè)的熱度,并將冷熱數(shù)據(jù)分開(kāi)存儲(chǔ)到不同擦除次數(shù)的塊上,有效地實(shí)現(xiàn)了冷熱數(shù)據(jù)分離,比以上三種傳統(tǒng)的算法,性能有了很大提升。但該算法也存在一定的局限性,它采用了GR算法中的回收塊選擇策略,并額外開(kāi)辟了較大的內(nèi)存空間來(lái)保存邏輯頁(yè)的熱度。雖然基于邏輯頁(yè)識(shí)別冷熱數(shù)據(jù)準(zhǔn)確度較高,但占用相對(duì)較大的內(nèi)存空間,這樣的情況對(duì)于內(nèi)存消耗嚴(yán)重的Flash存儲(chǔ)器來(lái)說(shuō)是不利的。

針對(duì)以上算法的不足,本文提出了一種垃圾回收算法——LRGC(LogicRegionbasedGarbageCollection)算法。該算法的目標(biāo)是減少系統(tǒng)的內(nèi)存消耗,減少垃圾回收過(guò)程中的開(kāi)銷以及提高塊的磨損均衡度。算法將連續(xù)邏輯地址空間劃分為同一個(gè)熱度區(qū)間以減少系統(tǒng)的內(nèi)存消耗;通過(guò)代價(jià)函數(shù)來(lái)選擇最優(yōu)塊回收,并針對(duì)數(shù)據(jù)長(zhǎng)期沒(méi)有更新的物理塊采用了一種特殊的回收機(jī)制,改善了磨損均衡效果；同時(shí),根據(jù)空閑頁(yè)的分布情況來(lái)判斷啟動(dòng)垃圾回收的時(shí)機(jī),以防止過(guò)早地擦除塊。

1 算法描述

1.1 基本原理

基于NAND閃存的存儲(chǔ)系統(tǒng)結(jié)構(gòu)可以分為文件系統(tǒng)層、閃存轉(zhuǎn)換層(FlashTranslationLayer,FTL)、內(nèi)存技術(shù)設(shè)備(MemoryTechnologyDevice,MTD)層和NAND閃存,如圖1所示。

圖1 NAND Flash存儲(chǔ)系統(tǒng)結(jié)構(gòu)

文件系統(tǒng)提供管理NAND閃存設(shè)備的方法。FTL是一種軟件中間層,用于將閃存模擬成為虛擬塊設(shè)備,從而能夠在閃存上實(shí)現(xiàn)Ext3、FAT等塊設(shè)備類文件系統(tǒng)，它主要包含了地址映射、垃圾回收、磨損均衡等幾個(gè)方面的內(nèi)容。MTD層將文件系統(tǒng)與底層Flash存儲(chǔ)器進(jìn)行了隔離,并為上層文件系統(tǒng)提供一個(gè)統(tǒng)一的接口,如讀、寫(xiě)、擦除操作等。

NAND閃存具有基于日志結(jié)構(gòu)的專有文件系統(tǒng),如JFFS、YAFFS文件系統(tǒng),它們都提供了邏輯地址到物理地址之間的映射。根據(jù)映射粒度的不同,可以分為頁(yè)級(jí)映射、塊級(jí)映射和混合映射[10]。雖然頁(yè)級(jí)映射對(duì)數(shù)據(jù)熱度的判斷最為準(zhǔn)確,但是在內(nèi)存容量有限的電子產(chǎn)品中,頁(yè)級(jí)映射并不適用。在本文中,采用一種新的映射方式——邏輯區(qū)間映射,和頁(yè)級(jí)映射相比,它可以在保證較為準(zhǔn)確識(shí)別數(shù)據(jù)熱度的前提下,減少系統(tǒng)的內(nèi)存消耗。

1.2 邏輯區(qū)間定義

考慮到在實(shí)際系統(tǒng)中,如果一個(gè)邏輯地址最近被訪問(wèn)到,則系統(tǒng)中有可能在將來(lái)一段時(shí)間里再次訪問(wèn)到該邏輯地址或其附近的地址[11]。Kim等[12]通過(guò)對(duì)智能手機(jī)的日常使用的讀寫(xiě)操作跟蹤研究發(fā)現(xiàn),對(duì)邏輯地址的訪問(wèn)具有空間局部性,也就是說(shuō),部分連續(xù)邏輯地址被頻繁地訪問(wèn),而其余的邏輯地址訪問(wèn)次數(shù)很少。同時(shí),由于NAND閃存介質(zhì)固有的特性,寫(xiě)數(shù)據(jù)是以頁(yè)為單位進(jìn)行的,這樣每一次下發(fā)到介質(zhì)的寫(xiě)都是頁(yè)的整數(shù)倍, 因此,如果某邏輯頁(yè)為熱數(shù)據(jù),那么該邏輯頁(yè)所屬的若干連續(xù)頁(yè)的數(shù)據(jù)在很大概率上具有同一個(gè)熱度,因此可以定義此連續(xù)邏輯地址區(qū)間為一個(gè)熱度區(qū)間。

定義1 在邏輯地址區(qū)間(la1,la2)中,若每一個(gè)地址所存儲(chǔ)的數(shù)據(jù)熱度相同,則為一個(gè)熱度區(qū)間,其長(zhǎng)度為la2-la1。因此,若熱度區(qū)間的長(zhǎng)度為M,則將邏輯地址空間中每M個(gè)地址空間標(biāo)記為一個(gè)熱度區(qū)間,每一個(gè)熱度區(qū)間內(nèi)的邏輯地址具有同一個(gè)熱度區(qū)間編號(hào)。如果邏輯地址為la,則它所在的熱度區(qū)間編號(hào)Hn為:

Hn=[la/M]

(1)

1.3 邏輯區(qū)間熱度定義

理想的熱數(shù)據(jù)識(shí)別方案是,隨著時(shí)間的動(dòng)態(tài)變化能夠反映各個(gè)時(shí)間點(diǎn)數(shù)據(jù)的冷熱權(quán)值,并且具有較小的內(nèi)存消耗,計(jì)算復(fù)雜度較低。為了準(zhǔn)確計(jì)算回收塊中有效數(shù)據(jù)頁(yè)對(duì)應(yīng)邏輯頁(yè)的熱度大小,采用一種基于邏輯區(qū)間更新頻率和上一次熱度值來(lái)識(shí)別當(dāng)前邏輯區(qū)間熱度的方法。定義如下:

(2)

(3)

其中:Ti+1表示邏輯區(qū)間第i+1次更新時(shí)的熱度值;Ti表示第i次更新時(shí)的熱度值;α表示邏輯區(qū)間更新頻率;t表示當(dāng)前更新時(shí)間與上一次更新時(shí)間的時(shí)間間隔;Tmax、Tmin分別表示根據(jù)實(shí)際情況設(shè)定的熱度最大值和最小值,通常取10和0;Nt表示可自行調(diào)節(jié)的時(shí)間靈敏度參數(shù),目的是使更新操作的時(shí)間差值得到線性壓縮,降低時(shí)間對(duì)熱度計(jì)算的影響,一般取1 024。由于初次寫(xiě)入的數(shù)據(jù)沒(méi)有歷史熱度,無(wú)法通過(guò)公式計(jì)算出當(dāng)前熱度,因此設(shè)定一個(gè)初始熱度值Th,取熱度最大值和最小值的中間值,即剛寫(xiě)入的數(shù)據(jù)熱度設(shè)為5。假定由式(2)～(3)計(jì)算所得邏輯區(qū)間的熱度值為T：當(dāng)T≥Th時(shí),判定該邏輯區(qū)間所對(duì)應(yīng)的有效頁(yè)為熱數(shù)據(jù)頁(yè)；當(dāng)T

1.4 回收塊選擇策略

系統(tǒng)在進(jìn)行垃圾回收時(shí),首先需要考慮垃圾回收的效率,為了獲得較高的回收效率,通常選擇無(wú)效頁(yè)最多的物理塊進(jìn)行回收。由于NAND閃存的擦除次數(shù)是有限的,為了盡可能延長(zhǎng)閃存的使用壽命,在垃圾回收過(guò)程中還需要考慮閃存塊的磨損均衡度?，F(xiàn)有的垃圾回收策略主要要考慮了回收效率,但在改善磨損均衡度方面還有所缺陷。為了兼顧回收效率和磨損均衡度,采用了一種回收代價(jià)函數(shù)C:

(4)

其中:μ表示塊內(nèi)有效頁(yè)所占的比例;εi表示該物理塊的擦除次數(shù);εmax表示塊的最大擦除次數(shù);εmin表示塊的最小擦除次數(shù);λ表示可配置參數(shù)。一般來(lái)說(shuō),回收效率和磨損均衡是互相制約的,當(dāng)λ較小時(shí),主要考慮回收效率;當(dāng)λ較大時(shí),主要考慮磨損均衡。為了權(quán)衡兩者之間所占的比重,可根據(jù)實(shí)際情況取最優(yōu)值。垃圾回收時(shí),選擇使C值最大的塊進(jìn)行回收。當(dāng)存儲(chǔ)系統(tǒng)中物理塊的磨損均衡度較好時(shí),回收效率優(yōu)先,側(cè)重選擇有效頁(yè)較少的物理塊回收,從而減少回收時(shí)對(duì)有效頁(yè)的拷貝次數(shù),提高了回收效率;當(dāng)磨損均衡較差時(shí),磨損效果優(yōu)先,側(cè)重選擇擦除次數(shù)較少的塊進(jìn)行回收,使得擦除操作盡可能均勻地分布在每個(gè)閃存塊上,從而提高了磨損均衡度。

有些塊中數(shù)據(jù)長(zhǎng)時(shí)間沒(méi)有更新,有效頁(yè)比例接近1,通過(guò)式(4)難以選擇到這樣的塊,顯然這是對(duì)于磨損均衡的改善是不利的。為此采用了另一種回收機(jī)制,定義如下:

(5)

ε=εmax-εmin

(6)

其中:Sth表示控制磨損均衡度的閾值;ε表示最大擦除次數(shù)和最小擦除次數(shù)的差值。當(dāng)利用式(2)～(3)回收物理塊的回收次數(shù)大于Se時(shí),啟用該回收機(jī)制,即對(duì)最冷數(shù)據(jù)塊進(jìn)行一次回收。每次回收完成后,按照式(5)～(6)再次更新Se的值,以供下次回收時(shí)使用。

一般的垃圾回收算法中,是以空閑塊的數(shù)目來(lái)確定垃圾回收的時(shí)機(jī),即當(dāng)閃存中的空閑塊數(shù)目小于保留塊數(shù)時(shí),啟動(dòng)急迫模式的垃圾回收,此種模式下的觸發(fā)條件并不能準(zhǔn)確地確定垃圾回收的時(shí)機(jī)。為了避免不必要的垃圾回收操作,減少垃圾回收的次數(shù),提高垃圾回收的效率,LRGC算法通過(guò)空塊中的空閑頁(yè)數(shù)與閃存中總的空閑頁(yè)數(shù)的比值來(lái)判斷是否要啟動(dòng)垃圾回收操作,具體公式定義如下:

SC=(Bf·Np)/Pf

(7)

其中:Bf表示閃存中空塊的數(shù)目;Np表示每個(gè)塊所含的頁(yè)數(shù);Pf表示所有空閑頁(yè)的數(shù)目。SC的值越小,說(shuō)明空白頁(yè)在閃存塊中分布越分散,系統(tǒng)中空閑塊越少。通常情況下,當(dāng)SC的值接近10%時(shí),空閑頁(yè)數(shù)量已經(jīng)很少,這時(shí)急需啟動(dòng)垃圾回收,因而可設(shè)定一個(gè)閾值TSC=10%。采用LRGC算法的整個(gè)垃圾回收過(guò)程具體如下:

1)當(dāng)滿足SC≤TSC時(shí),啟動(dòng)垃圾回收;

2)根據(jù)式(4)計(jì)算,選擇使回收代價(jià)C值最大的塊作為回收塊;

3)根據(jù)式(1)確定邏輯區(qū)間編號(hào),通過(guò)式(2)～(3)計(jì)算邏輯區(qū)間的熱度,并判斷該邏輯區(qū)間內(nèi)所對(duì)應(yīng)的有效頁(yè)冷熱情況;

4)將步驟3)中判斷的熱數(shù)據(jù)拷貝到擦除次數(shù)最少的塊上,冷數(shù)據(jù)拷貝到擦除次數(shù)最大的塊上;

5)當(dāng)按照步驟2)回收物理塊的次數(shù)大于Se時(shí),對(duì)最冷塊進(jìn)行一次回收。

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)參數(shù)

使用基于Linux2.6和QEMU的嵌入式開(kāi)發(fā)仿真平臺(tái),并移植YAFFS2文件系統(tǒng),使用QEMU模擬ARM處理器,使用NANDSim模擬NAND閃存,最后編寫(xiě)測(cè)試程序進(jìn)行測(cè)試。測(cè)試程序創(chuàng)建創(chuàng)建大小在16KB～1 024KB之間的文件,文件大小總和占NAND閃存容量的90%。文件創(chuàng)建完畢后,對(duì)15%的數(shù)據(jù)按照齊夫分布[13]進(jìn)行更新操作。使用NANDSim模擬出NAND閃存頁(yè)的大小為2KB,塊的大小為128KB,總?cè)萘繛?4MB。為了公平比較不同算法的性能,實(shí)驗(yàn)中關(guān)閉了YAFFS2文件系統(tǒng)的緩存功能以及后臺(tái)垃圾回收,并且都使用aggressive模式。仿真實(shí)驗(yàn)中各項(xiàng)參數(shù)如表1所示。

表1 仿真實(shí)驗(yàn)參數(shù)值

2.2 性能比較

算法性能比較采用的指標(biāo)包括:所有物理塊總的擦除次數(shù)、總的拷貝次數(shù)、所有物理塊的擦除次數(shù)最大差值、所有物理塊擦除次數(shù)的標(biāo)準(zhǔn)差。表2反映了LRGC算法在M=8,λ取不同值時(shí),各項(xiàng)性能指標(biāo)情況。由表中數(shù)據(jù)可知λ=0.4時(shí),擦除次數(shù)和拷貝次數(shù)最少,且擦除次數(shù)的最大差值比較小,因而在驗(yàn)證邏輯區(qū)間長(zhǎng)度對(duì)算法性能影響時(shí),設(shè)定λ=0.4。

表2 LRGC算法取不同λ值時(shí)的各項(xiàng)性能指標(biāo)

FaGC算法的各項(xiàng)性能指標(biāo)均明顯優(yōu)于GR算法、CB算法和CAT算法,為了驗(yàn)證本文算法的有效性,選取FaGC算法作為比較。

由圖2～3可知除M=16外,LRGC算法的擦除次數(shù)和拷貝次數(shù)均少于FaGC算法,這是由于該算法采用了新的熱度計(jì)算公式,更加準(zhǔn)確地刻畫(huà)了數(shù)據(jù)訪問(wèn)的頻繁度,并且改進(jìn)了回收塊選擇策略,回收塊的選擇更為合理。對(duì)于LRGC算法,M=1表示熱度區(qū)間長(zhǎng)度為1,即沒(méi)有基于邏輯區(qū)間計(jì)算熱度,仍然是計(jì)算單個(gè)邏輯頁(yè)的熱度。當(dāng)M=4時(shí),LRGC算法總的擦除次數(shù)和總的拷貝次數(shù)與FaGC算法相比,分別減少了11%、13%。隨著熱度區(qū)間長(zhǎng)度M取值增大,拷貝次數(shù)、擦除次數(shù)均有所增加,這是由于隨著熱度區(qū)間大小的增加,邏輯頁(yè)熱度會(huì)出現(xiàn)少量誤判的情況。當(dāng)熱度區(qū)間長(zhǎng)度M=2,4,8,16時(shí),擦除次數(shù)的增長(zhǎng)率分別為9.07%、9.11%、8.01%、52.49%;拷貝次數(shù)的增長(zhǎng)率分別為16.89%、15.82%、13.08%、82.00%。由以上數(shù)據(jù)可知熱度區(qū)間長(zhǎng)度M取值較小時(shí),擦除次數(shù)和拷貝次數(shù)增長(zhǎng)相對(duì)緩慢；而M取值相對(duì)較大時(shí),擦除次數(shù)和拷貝次數(shù)會(huì)急劇增加是由于設(shè)定的熱度區(qū)間長(zhǎng)度過(guò)大,并不能客觀準(zhǔn)確反映實(shí)際數(shù)據(jù)的讀寫(xiě)特性,出現(xiàn)了較大偏差,導(dǎo)致熱度誤判概率較大。

圖2 總的擦除次數(shù)對(duì)比

圖3 總的拷貝次數(shù)對(duì)比

圖4 擦除次數(shù)的最大差值對(duì)比

圖5 擦除次數(shù)的標(biāo)準(zhǔn)差對(duì)比

由圖4可知LRGC算法在五種情況下的擦除次數(shù)最大差值均小于FaGC算法,這是由于在對(duì)回收塊進(jìn)行選擇時(shí),LRGC算法綜合考慮了垃圾回收效率和磨損均衡因素,總是偏向選擇無(wú)效頁(yè)較多且擦除次數(shù)較小的塊進(jìn)行回收,在提高回收效率的同時(shí),還盡可能使擦除操作均勻地分布在每個(gè)閃存塊上,從而提高了磨損均衡度。而FaGC算法采用GR算法中的回收塊選擇策略,即總是選擇無(wú)效頁(yè)最多的塊,該回收塊的選擇并沒(méi)有考慮磨損均衡度。當(dāng)M=4時(shí),LRGC算法擦除次數(shù)的最大差值與FaGC算法相比,減少了42%。由于M=8時(shí)擦除次數(shù)最大差值相對(duì)最小,M=16時(shí)擦除次數(shù)最大差值相對(duì)最大,選取這兩種情況下的標(biāo)準(zhǔn)差和FaGC算法對(duì)比。由圖5可知不管是FaGC算法,還是取不同M值的LRGC算法,其標(biāo)準(zhǔn)差曲線均呈現(xiàn)收斂狀態(tài),并且最終大致穩(wěn)定在一個(gè)恒定的值,也就表明各物理塊的擦除次數(shù)波動(dòng)較小,擦除操作比較均勻。這是由于兩種算法都將冷熱數(shù)據(jù)進(jìn)行了分離,并分開(kāi)存儲(chǔ)在不同擦除次數(shù)的空閑塊上。綜合圖4～5可知,LRGC算法的磨損均衡效果仍然好于FaGC算法。

2.3 內(nèi)存消耗

算法對(duì)于系統(tǒng)性能的改善,一定程度上是以犧牲內(nèi)存空間為代價(jià)的。兩種算法均對(duì)冷熱數(shù)據(jù)進(jìn)行了識(shí)別,而這一過(guò)程必然要開(kāi)辟內(nèi)存,來(lái)保存邏輯頁(yè)熱度值。FaGC算法中構(gòu)造了一個(gè)熱度表,表中記錄了每個(gè)邏輯頁(yè)的上次更新時(shí)間和熱度值。對(duì)于一個(gè)單片容量為16GB,頁(yè)大小為2KB,塊大小為128KB的NAND閃存,總的頁(yè)數(shù)為16×1 024×1 024/2=8 192×1 024,保存每個(gè)邏輯頁(yè)的熱度和上次更新時(shí)間大約占用3B,則FaGC算法需要占用8 192×1 024×3=24MB存儲(chǔ)空間,可見(jiàn)為了維護(hù)這張表,內(nèi)存的開(kāi)銷是比較大的。

圖6反映了兩種算法下內(nèi)存開(kāi)銷對(duì)比情況。LRGC算法把若干連續(xù)邏輯地址定義為一個(gè)熱度區(qū)間,同一個(gè)熱度區(qū)間內(nèi)的邏輯頁(yè)具有相同的熱度,這樣在保存熱度值時(shí)只需要保存邏輯區(qū)間的熱度,在保證性能優(yōu)勢(shì)的前提下,擴(kuò)大邏輯區(qū)間長(zhǎng)度,內(nèi)存消耗成倍降低。同時(shí)，從圖2～6可知，M的取值,對(duì)垃圾回收的回收效率以及內(nèi)存消耗影響較大,對(duì)磨損均衡影響較小。當(dāng)M=16時(shí),雖然占有最少的內(nèi)存空間,但拷貝次數(shù)和擦出次數(shù)較大,回收代價(jià)較高,這樣的取值并不具有實(shí)際意義;當(dāng)M=8或者M(jìn)=4時(shí),各項(xiàng)性能指標(biāo)比較均衡,因而在實(shí)際應(yīng)用中,可設(shè)定M=8或者M(jìn)=4,使得系統(tǒng)不僅具有高的回收效率,好的磨損效果,而且內(nèi)存消耗少。

圖6 內(nèi)存消耗對(duì)比

3 結(jié)語(yǔ)

本文提出的LRGC算法是基于邏輯區(qū)間識(shí)別冷熱數(shù)據(jù),在擦除回收塊之前,首先計(jì)算回收塊中有效頁(yè)所對(duì)應(yīng)的邏輯區(qū)間編號(hào),根據(jù)所在的邏輯區(qū)間來(lái)判斷有效頁(yè)的熱度,將冷數(shù)據(jù)拷貝到擦除次數(shù)最大的塊上,熱數(shù)據(jù)拷貝到擦除次數(shù)最小的塊上,不僅有效地實(shí)現(xiàn)了冷熱數(shù)據(jù)分離,而且占用了相對(duì)較小的內(nèi)存空間。本文算法也存在一定的缺陷,在通過(guò)代價(jià)函數(shù)選擇回收塊時(shí),相當(dāng)于擴(kuò)大了回收塊的回收范圍,算法時(shí)間復(fù)雜度較高,并且相比FaGC,算法,一定時(shí)間內(nèi)會(huì)選擇到更多符合條件的回收塊,增加了回收次數(shù)。但從整體來(lái)看,在FaGC算法比經(jīng)典算法有更多優(yōu)勢(shì)的情況下,LRGC算法在性能上有了進(jìn)一步提升,而且內(nèi)存消耗大幅度減少。

)

[1]LEES,KIMJ.Effectivelifetime-awaredynamicthrottlingforNANDflash-basedSSDs[J].IEEETransactionsonComputers, 2016, 65(4):1075-1089.

[2]CHANGY,CHANGY,CHENJ,etal.Ontradingwear-levelingwithheal-leveling[C]//DAC2014:Proceedingsofthe51stAnnualDesignAutomationConference.NewYork:ACM, 2014:1-6.

[3] LEE J, KIM Y, SHIPMAN G M, et al. Preemptible I/O scheduling of garbage collection for solid state drives[J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2013, 32(2):247-260.

[4] LAM K Y, ZHU C J, CHANG Y H, et al. Garbage collection of multi-version indexed data on flash memory[J]. Journal of Systems Architecture, 2014, 60(8):630-643.

[5] KIM S H, CHOI J H, KWAK J W. HaWL: hidden cold block-aware wear leveling using bit-set threshold for NAND flash memory[J]. IEICE Transactions on Information and Systems, 2016, E99-D(4):1242-1245.

[6] WU M, ZWAENEPOEL W. eNVy: a non-volatile main memory storage system[C]// ASPLOS VI: Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 1994:86-97.

[7] KAWAGUCHI A, NISHIOKA S, MOTODA H A. Flash memory based file system[C]// Proceedings of the USENIX 1995 Technical Conference. Berkeley: USENIX Association, 1995:155-164.

[8] CHIANG M L, CHANG R C. Cleaning policies inmobile computers using flash memory[J]. Journal of Systems and Software, 1999, 48(3):213-231.

[9] YAN H, YAO Q. An efficient file-aware garbage collection algorithm for NAND flash based consumer electronics[J]. IEEE Transactions on Consumer Electronics, 2014, 60(4):623-627.

[10] 陳金忠, 姚念民, 蔡紹濱, 等. 基于頁(yè)面寫(xiě)相關(guān)的閃存轉(zhuǎn)換層策略[J]. 通信學(xué)報(bào), 2013, 34(6):76-84.(CHEN J Z, YAO N M, CAI S B, et al. Page write-related scheme for flash translation layer[J]. Journal on Communications, 2013, 34(6):76-84.)

[11] CHANG L-P, KUO T-K. Efficient management for large-scale flash memory storage systems with resource conservation[J]. ACM Transactions on Storage, 2005, 1(4):381-418.

[12] KIM H, SHIN D. Clustered page-level mapping for flash memory based storage devices[J]. IEEE Transactions on Consumer Electronics, 2015, 61(1):47-55.

[13] LIN M, CHEN S. Efficient and intelligent garbage collection policy for NAND flash-based consumer electronics[J]. IEEE Transactions on Consumer Electronics, 2013, 59(3):538-543.

This work is partially supported by the National Natural Science Foundation of China (61172181).

LEI Bingbing, born in 1989, M. S. candidate. His research interests include intelligent control.

YAN Hua, born in 1971, Ph. D., professor. His research interests include pattern recognition, intelligent control.

GarbagecollectionalgorithmforNANDflashmemorybasedonlogicalregionheat

LEIBingbing*,YANHua

(CollegeofElectronicsandInformationEngineering,SichuanUniversity,ChengduSichuan610065,China)

To solve the problems of low collection performance, poor wear leveling effect, and high memory overhead in the existing NAND flash memory garbage collection algorithms, a new garbage collection algorithm based on logical region heat was proposed. The heat calculation formula was redefined, the NAND memory of continuous logical address was defined as a heat range which was used to replace the heat of logical page, then the data with different heat was separated into the corresponding flash blocks with different erase counts. The cold and hot data were effectively separated,and the memory space was also saved. Meanwhile, a new collection cost function was constructed to improve the collection efficiency and wear leveling effect. The experimental results showed that compared with the excellent File-aware Garbage Collection (FaGC) algorithm, the total number of erase operations was reduced by 11%, the total number of copy operations was reduced by 13%, the maximum difference of erase counts was reduced by 42%, and the memory consumption was reduced by 75%. Therefore, the available flash memory space can be increased, the read and write performance of flash memory can be improved, and the flash memory life can be also extended by using the proposed algorithm.

NAND flash memory; wear leveling; garbage collection; logical region; collection block

2016- 09- 20;

2016- 12- 23。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61172181)。

雷兵兵(1989—),男,湖北荊門人,碩士研究生,主要研究方向:智能控制; 嚴(yán)華(1971—),男,四川渠縣人,教授,博士,主要研究方向:模式識(shí)別、智能控制。

1001- 9081(2017)04- 1149- 04

10.11772/j.issn.1001- 9081.2017.04.1149

TP

A