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

雷兵兵,嚴 華

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

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

雷兵兵*,嚴 華

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

針對現有的NAND閃存垃圾回收算法中回收性能不高,磨損均衡效果差,并且算法內存開銷大的問題,提出了一種基于邏輯區間熱度的垃圾回收算法。該算法重新定義了熱度計算公式,把連續邏輯地址的NAND內存定義為一個熱度區間,以邏輯區間的熱度來代替邏輯頁的熱度,并將不同熱度的數據分開存儲到不同擦除次數的閃存塊上,有效地實現了數據冷熱分離,并且節約了內存空間。同時,算法還構造了一種新的回收代價函數來選擇回收塊,在考慮回收效率的同時,還兼顧了磨損均衡的問題。實驗結果表明,該算法與性能優異的FaGC算法相比,總的擦除次數減少了11%,總的拷貝次數減少了13%,擦次數最大差值減少了42%,內存消耗能減少了75%。因此,該算法有利于增加閃存可用空間,改善閃存系統的讀寫性能,延長閃存使用壽命。

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

0 引言

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

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

針對以上算法的不足,本文提出了一種垃圾回收算法——LRGC(LogicRegionbasedGarbageCollection)算法。該算法的目標是減少系統的內存消耗,減少垃圾回收過程中的開銷以及提高塊的磨損均衡度。算法將連續邏輯地址空間劃分為同一個熱度區間以減少系統的內存消耗;通過代價函數來選擇最優塊回收,并針對數據長期沒有更新的物理塊采用了一種特殊的回收機制,改善了磨損均衡效果；同時,根據空閑頁的分布情況來判斷啟動垃圾回收的時機,以防止過早地擦除塊。

1 算法描述

1.1 基本原理

基于NAND閃存的存儲系統結構可以分為文件系統層、閃存轉換層(FlashTranslationLayer,FTL)、內存技術設備(MemoryTechnologyDevice,MTD)層和NAND閃存,如圖1所示。

圖1 NAND Flash存儲系統結構

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

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

1.2 邏輯區間定義

考慮到在實際系統中,如果一個邏輯地址最近被訪問到,則系統中有可能在將來一段時間里再次訪問到該邏輯地址或其附近的地址[11]。Kim等[12]通過對智能手機的日常使用的讀寫操作跟蹤研究發現,對邏輯地址的訪問具有空間局部性,也就是說,部分連續邏輯地址被頻繁地訪問,而其余的邏輯地址訪問次數很少。同時,由于NAND閃存介質固有的特性,寫數據是以頁為單位進行的,這樣每一次下發到介質的寫都是頁的整數倍, 因此,如果某邏輯頁為熱數據,那么該邏輯頁所屬的若干連續頁的數據在很大概率上具有同一個熱度,因此可以定義此連續邏輯地址區間為一個熱度區間。

定義1 在邏輯地址區間(la1,la2)中,若每一個地址所存儲的數據熱度相同,則為一個熱度區間,其長度為la2-la1。因此,若熱度區間的長度為M,則將邏輯地址空間中每M個地址空間標記為一個熱度區間,每一個熱度區間內的邏輯地址具有同一個熱度區間編號。如果邏輯地址為la,則它所在的熱度區間編號Hn為:

Hn=[la/M]

(1)

1.3 邏輯區間熱度定義

理想的熱數據識別方案是,隨著時間的動態變化能夠反映各個時間點數據的冷熱權值,并且具有較小的內存消耗,計算復雜度較低。為了準確計算回收塊中有效數據頁對應邏輯頁的熱度大小,采用一種基于邏輯區間更新頻率和上一次熱度值來識別當前邏輯區間熱度的方法。定義如下:

(2)

(3)

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

1.4 回收塊選擇策略

系統在進行垃圾回收時,首先需要考慮垃圾回收的效率,為了獲得較高的回收效率,通常選擇無效頁最多的物理塊進行回收。由于NAND閃存的擦除次數是有限的,為了盡可能延長閃存的使用壽命,在垃圾回收過程中還需要考慮閃存塊的磨損均衡度。現有的垃圾回收策略主要要考慮了回收效率,但在改善磨損均衡度方面還有所缺陷。為了兼顧回收效率和磨損均衡度,采用了一種回收代價函數C:

(4)

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

有些塊中數據長時間沒有更新,有效頁比例接近1,通過式(4)難以選擇到這樣的塊,顯然這是對于磨損均衡的改善是不利的。為此采用了另一種回收機制,定義如下:

(5)

ε=εmax-εmin

(6)

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

一般的垃圾回收算法中,是以空閑塊的數目來確定垃圾回收的時機,即當閃存中的空閑塊數目小于保留塊數時,啟動急迫模式的垃圾回收,此種模式下的觸發條件并不能準確地確定垃圾回收的時機。為了避免不必要的垃圾回收操作,減少垃圾回收的次數,提高垃圾回收的效率,LRGC算法通過空塊中的空閑頁數與閃存中總的空閑頁數的比值來判斷是否要啟動垃圾回收操作,具體公式定義如下:

SC=(Bf·Np)/Pf

(7)

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

1)當滿足SC≤TSC時,啟動垃圾回收;

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

3)根據式(1)確定邏輯區間編號,通過式(2)～(3)計算邏輯區間的熱度,并判斷該邏輯區間內所對應的有效頁冷熱情況;

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

5)當按照步驟2)回收物理塊的次數大于Se時,對最冷塊進行一次回收。

2 實驗與分析

2.1 實驗環境及實驗參數

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

表1 仿真實驗參數值

2.2 性能比較

算法性能比較采用的指標包括:所有物理塊總的擦除次數、總的拷貝次數、所有物理塊的擦除次數最大差值、所有物理塊擦除次數的標準差。表2反映了LRGC算法在M=8,λ取不同值時,各項性能指標情況。由表中數據可知λ=0.4時,擦除次數和拷貝次數最少,且擦除次數的最大差值比較小,因而在驗證邏輯區間長度對算法性能影響時,設定λ=0.4。

表2 LRGC算法取不同λ值時的各項性能指標

FaGC算法的各項性能指標均明顯優于GR算法、CB算法和CAT算法,為了驗證本文算法的有效性,選取FaGC算法作為比較。

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

圖2 總的擦除次數對比

圖3 總的拷貝次數對比

圖4 擦除次數的最大差值對比

圖5 擦除次數的標準差對比

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

2.3 內存消耗

算法對于系統性能的改善,一定程度上是以犧牲內存空間為代價的。兩種算法均對冷熱數據進行了識別,而這一過程必然要開辟內存,來保存邏輯頁熱度值。FaGC算法中構造了一個熱度表,表中記錄了每個邏輯頁的上次更新時間和熱度值。對于一個單片容量為16GB,頁大小為2KB,塊大小為128KB的NAND閃存,總的頁數為16×1 024×1 024/2=8 192×1 024,保存每個邏輯頁的熱度和上次更新時間大約占用3B,則FaGC算法需要占用8 192×1 024×3=24MB存儲空間,可見為了維護這張表,內存的開銷是比較大的。

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

圖6 內存消耗對比

3 結語

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

)

[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] 陳金忠, 姚念民, 蔡紹濱, 等. 基于頁面寫相關的閃存轉換層策略[J]. 通信學報, 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。 基金項目:國家自然科學基金資助項目(61172181)。

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

1001- 9081(2017)04- 1149- 04

10.11772/j.issn.1001- 9081.2017.04.1149

TP

A