0 引言

    NAND Flash存儲設(shè)備與傳統(tǒng)機(jī)械磁盤相比，具有體積小,、存儲密度高,、隨機(jī)存儲和讀寫能力強(qiáng)、抗震抗摔,、功耗低等特點(diǎn)^[1],。它被廣泛用于智能手機(jī),、車載智能中心,、平板電腦等智能終端中。近年來,，以NAND Flash為存儲介質(zhì)的固態(tài)硬盤也得到越來越多的應(yīng)用,。目前Yaffs2文件系統(tǒng)(Yet Another Flash File System Two，Yaffs2)^[1]是使用最多,、可移植性最好的專用文件系統(tǒng),，在安卓、阿里云OS,、Linux等嵌入式系統(tǒng)中都有使用,。在Yaffs2文件系統(tǒng)下以NAND Flash為存儲介質(zhì)時存在磨損均衡的缺陷,，可通過對回收塊選擇機(jī)制作改進(jìn)和引入冷熱數(shù)據(jù)分離策略來提高磨損均衡的效果。

1 Yaffs2和Nand Flash關(guān)系

    這里以使用最多的Linux操作系統(tǒng)為實(shí)踐,，將Yaffs2文件系統(tǒng)移植到Linux操作系統(tǒng)中,。Linux系統(tǒng)通常可以分為3層：應(yīng)用層,、內(nèi)核層和設(shè)備層,，其中支持NAND Flash設(shè)備的Yaffs2文件系統(tǒng)屬于內(nèi)核層，如圖1所示,。

    最上層用戶應(yīng)用程序通過VFS(Virtual File System)提供的統(tǒng)一接口,，將數(shù)據(jù)更新等文件操作傳遞給Yaffs2。VFS代表虛擬文件系統(tǒng),，它為上層應(yīng)用提供統(tǒng)一的接口,。有了這些接口，應(yīng)用程序只用遵循抽象后的訪問規(guī)則,，而不必理會底層文件系統(tǒng)和物理構(gòu)成上的差異,。然后Yaffs2通過MTD（Memory Technology Device）提供的統(tǒng)一訪問接口對NAND Flash進(jìn)行讀、寫和擦除操作,，從而完成數(shù)據(jù)的更新或者存儲操作,。MTD代表內(nèi)存技術(shù)設(shè)備，它為存儲設(shè)備提供統(tǒng)一訪問的接口,。最終,，在NAND Flash上以怎樣的格式組織和存儲數(shù)據(jù)由Yaffs2文件系統(tǒng)決定。

    NAND Flash由若干塊(block)組成,，每個塊又是由若干頁(page)組成,，頁中含有數(shù)據(jù)區(qū)和附加區(qū)。NAND Flash的頁根據(jù)狀態(tài)不同,，可以分為有效頁,、臟頁、空閑頁,。有效頁中存放有效數(shù)據(jù),，臟頁中存放無效數(shù)據(jù)，空閑頁是經(jīng)過擦除后可以直接用于寫入數(shù)據(jù)的頁,。NAND Flash在寫入數(shù)據(jù)前需要執(zhí)行擦除操作,，因此數(shù)據(jù)不能直接在相同的位置更新。當(dāng)一個頁中數(shù)據(jù)需要更新時,，必須將該頁中有效數(shù)據(jù)拷貝到其他空閑頁上再更新,，并將原來頁上的數(shù)據(jù)置為無效。隨著時間的推移，許多無效頁累積在存儲器中使得空閑頁逐漸減少,。當(dāng)存儲器中的空閑空間不足時,，啟動垃圾回收操作，利用回收塊選擇機(jī)制從待回收塊中選取滿足要求的塊來擦除,，從而得到足夠的空閑空間,。NAND Flash中塊的擦除次數(shù)有限，通常為10 000次～100 000次^[2],。當(dāng)某個塊的擦除次數(shù)超過使用壽命時,，該塊將無法正常用于數(shù)據(jù)存儲。因此,，垃圾回收應(yīng)利用合理的回收塊選擇機(jī)制,，從待回收塊中找到回收后能產(chǎn)生良好磨損均衡效果且付出較少額外代價(jià)的塊來回收，從而獲得足夠的空閑空間用于數(shù)據(jù)更新操作,。

2 Yaffs2在磨損均衡方面的缺陷

    Yaffs2中回收塊的選擇機(jī)制^[3]是從待回收塊中找到有效數(shù)據(jù)最少的塊來回收,。回收過程中,，Yaffs2能夠減少有效數(shù)據(jù)的額外讀和寫操作,。當(dāng)數(shù)據(jù)更新處于均勻分布的情況下，Yaffs2表現(xiàn)出較好的磨損均衡效果,。

    但是,，通常情況下數(shù)據(jù)的更新頻率不同，有些數(shù)據(jù)經(jīng)常更新,，而有些數(shù)據(jù)很少更新,。經(jīng)常更新的數(shù)據(jù)稱為熱數(shù)據(jù)，很少更新的數(shù)據(jù)稱為冷數(shù)據(jù)^[1],。如果某個塊上總有熱數(shù)據(jù)不斷更新,，那么該塊上有效數(shù)據(jù)會變少，Yaffs2容易選中這樣的塊來更新,。而當(dāng)某個塊中含大量有效冷數(shù)據(jù)時,，冷數(shù)據(jù)少更新的特點(diǎn)使得Yaffs2難以選中這類塊來更新。更新后的塊會用于存放新寫入的數(shù)據(jù),，而新寫入的數(shù)據(jù)通常是熱數(shù)據(jù),，由此可知熱數(shù)所在塊會經(jīng)常被更新。最終熱數(shù)據(jù)所在的塊成為擦除次數(shù)多的塊,，冷數(shù)據(jù)所在的塊成為擦除次數(shù)少的塊,。因此Yaffs2的回收塊選擇機(jī)制會造成NAND Flash設(shè)備中塊的擦除次數(shù)呈兩級分化,，即塊的最大,、最小擦除次數(shù)差值不斷變大。所以Yaffs2中不應(yīng)只考慮數(shù)據(jù)更新所產(chǎn)生的額外讀寫代價(jià),，還應(yīng)考慮塊的存在年齡對磨損均衡效果的影響,，這才能解決磨損均衡中兩級分化的問題,。

    Yaffs2文件系統(tǒng)中更新某個塊時，需將該塊上的剩余有效數(shù)據(jù)拷貝到其他空閑塊上,。而剩余有效數(shù)據(jù)不能占滿整個塊,，系統(tǒng)會將新寫入的數(shù)據(jù)繼續(xù)存放到該塊上，直到它的存儲空間用完為止,。更新過程中保留下來的數(shù)據(jù)通常是冷數(shù)據(jù),，而新寫入的數(shù)據(jù)通常是熱數(shù)據(jù)，因此Yaffs2的更新策略會造成冷數(shù)據(jù)和熱數(shù)據(jù)同時存儲在一個塊中,。由于熱數(shù)據(jù)的更新速度快,，當(dāng)熱數(shù)據(jù)更新時會導(dǎo)致冷數(shù)據(jù)被迫更新。但更新后剩下的數(shù)據(jù)同樣不能占滿一個整塊,，系統(tǒng)會再次將冷數(shù)據(jù)和熱數(shù)據(jù)存放到同一個塊中,。隨著以上的更新方式不斷進(jìn)行，將導(dǎo)致一系列不必要的數(shù)據(jù)讀,、寫以及塊的擦除操作,。因此Yaffs2的更新策略會使冷熱數(shù)據(jù)共存的塊易被多次更新，而冷數(shù)據(jù)占據(jù)的塊很少更新,，最終使得塊擦除次數(shù)標(biāo)準(zhǔn)差過大,，導(dǎo)致磨損不均衡。由于Yaffs2的更新策略中沒有做冷熱數(shù)分離,，這使得磨損不均衡問題難以解決,。

3 Yaffs2的改進(jìn)方法

3.1 回收塊選擇機(jī)制的改進(jìn)

    對于Yaffs2回收塊選擇機(jī)制的缺陷，可以通過加入塊的年齡(age)參數(shù)^[4]解決,。增加age參數(shù)后的回收塊選擇機(jī)制遵循式(1),，這可以將一些長期不更新的塊選中更新。

其中,，age指塊從分配開始到當(dāng)前垃圾回收時刻為止的年齡,，u表示單個塊中有效數(shù)據(jù)的占有比率。新的回收塊選擇機(jī)制選取當(dāng)前時刻年齡最大且有效數(shù)據(jù)占有最少(即benefit/cost比值最大)的塊作為回收對象,。當(dāng)一個塊上存儲的是冷數(shù)據(jù)時,，一定時間后該塊沒有被更新，那么它的age參數(shù)會變得很大,。盡管該塊上有效數(shù)據(jù)很多(即(1-u)/2u的比值較小),，但age參數(shù)很大使得benefit/cost的比值足夠大，最終會選中被冷數(shù)據(jù)占據(jù)的塊來更新,。由此可知引入age參數(shù)后,，能解決Yaffs2文件系統(tǒng)下NAND Flash中最大、最小擦除次數(shù)差值過大的磨損均衡問題。

3.2 增加冷熱數(shù)據(jù)分離策略

    對于Yaffs2中數(shù)據(jù)更新的缺陷,，可以引入冷熱數(shù)據(jù)分離策略^[5]來解決,。冷熱數(shù)據(jù)分離策略能夠收集冷數(shù)據(jù)，解決同一個塊中存放不同溫度數(shù)據(jù)時,，由于熱數(shù)據(jù)更新而強(qiáng)制更新冷數(shù)據(jù)的問題,。在系統(tǒng)運(yùn)行過程中檢測到塊的最大、最小擦除次數(shù)差值過大時,，將收集到的冷數(shù)據(jù)用數(shù)據(jù)交換操作放置到擦除次數(shù)多的塊上,。當(dāng)冷池中塊被熱數(shù)據(jù)占據(jù)或者熱池中塊被冷數(shù)據(jù)占據(jù)時，冷熱數(shù)據(jù)分離策略也能處理這類塊反轉(zhuǎn)問題,。數(shù)據(jù)的冷熱程度對塊的擦除次數(shù)會產(chǎn)生直接影響,，因此冷熱數(shù)據(jù)分離策略通過塊擦除次數(shù)來判斷數(shù)據(jù)溫度。改進(jìn)步驟如下：

    (1)初始化：將NAND Flash中的所有塊平均分為兩個部分,，一部分塊放到熱池中,，另一部分塊放到冷池中。

    (2)數(shù)據(jù)交換：找出熱池中擦除次數(shù)最多（Hottest_hp）的塊,，冷池中擦除次數(shù)最少（Coldest_cp）的塊,。當(dāng)Hottest_hp減去Coldest_cp之差大于一個閾值時(如式(2))，則需要做數(shù)據(jù)交換操作,。數(shù)據(jù)交換操作是將擦除次數(shù)為Coldest_cp的塊中收集的冷數(shù)據(jù)拷貝到擦除次數(shù)為Hottest_hp的塊中,，將擦除次數(shù)為Hottest_hp的塊上原來的熱數(shù)據(jù)存放到任意其他空閑塊上。數(shù)據(jù)交換操作的目的是將冷數(shù)據(jù)放到擦除次數(shù)最多的塊上,，利用冷數(shù)據(jù)不易更新的特點(diǎn)來減少塊的繼續(xù)擦除,；而將新寫入的數(shù)據(jù)存放到擦除次數(shù)少的塊上，最終達(dá)到磨損均衡的目的,。

    (3)塊反轉(zhuǎn)：當(dāng)熱池中某個塊被冷數(shù)據(jù)突然占據(jù)時,，導(dǎo)致該塊中的冷數(shù)據(jù)無法用于數(shù)據(jù)交換操作。這需要找到熱池中擦除次數(shù)最多（Hottest_hp）的塊和熱池中擦除最少(Coldest_hp)的塊,，二者擦除次數(shù)之差小于一個閾值時(如式(3))則進(jìn)行熱塊反轉(zhuǎn)操作,。熱塊反轉(zhuǎn)操作，將熱池中擦除次數(shù)最少的塊放到冷池中去,。另外當(dāng)冷池中的某個塊數(shù)據(jù)突然變熱時,，導(dǎo)致該塊不能被數(shù)據(jù)交換操作降溫。這需要用該塊的eec參數(shù)來判別,，eec表示有效擦除周期（塊改變所屬池后的擦除次數(shù)）,。因此滿足式(4)時，進(jìn)行冷塊反轉(zhuǎn)操作,。冷塊反轉(zhuǎn)操作是將冷池中擦除次數(shù)為Hottesteec的塊放到熱池中,，并把該塊的eec參數(shù)清零,。

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

    實(shí)驗(yàn)環(huán)境是通過Vmware工具安裝Linux虛擬機(jī)，然后在Linux下安裝Qemu工具來搭建仿真實(shí)驗(yàn)開發(fā)板,，并移植Yaffs2文件系統(tǒng)。為了公平測試,，關(guān)閉Yaffs2自帶的緩存功能,。用于測試的文件大小是從16 KB～1 024 KB隨機(jī)生成，測試數(shù)據(jù)占據(jù)整個Flash設(shè)備容量的90%,，其中僅有15%的數(shù)據(jù)更新,，這樣的更新操作滿足齊夫分布（Zif）^[6]。

    實(shí)驗(yàn)中NAND Flash總?cè)萘渴?4 MB,，共有512個塊,，每個塊含64個頁，每個頁大小是2 048 B,。試驗(yàn)中T_h閾值選定為8,。

4.2 實(shí)驗(yàn)結(jié)果

    實(shí)驗(yàn)對比數(shù)據(jù)包含：總擦除次數(shù)、最大與最小擦除次數(shù)差值和塊擦除次數(shù)標(biāo)準(zhǔn)差,?？偛脸螖?shù)的差異表示額外付出的擦除代價(jià)，最大與最小擦除次數(shù)差值的差異表示磨損均衡中兩級分化情況,。塊擦除次數(shù)標(biāo)準(zhǔn)差隨擦除次數(shù)增長越快,，則表示閃存設(shè)備中的數(shù)據(jù)更新是在少部分塊中完成（表示磨損均衡效果差）；塊擦除次數(shù)標(biāo)準(zhǔn)差隨擦除次數(shù)增長緩慢,，則表示數(shù)據(jù)更新是在大部分塊間交替完成（表示磨損均衡效果好）,。因此，塊擦除次數(shù)標(biāo)準(zhǔn)差隨擦除次數(shù)的變化情況能直接反應(yīng)磨損均衡的效果,。

    改進(jìn)前后總的擦除次數(shù)對比圖如圖2所示,，可以看到改進(jìn)后相較于改進(jìn)前額外付出了4.05%的擦除代價(jià)。額外增加擦除代價(jià)足夠小,，這樣的開銷可以接受,。

    改進(jìn)前后最大、最小擦除次數(shù)差值對比圖如圖3所示,，可以看到改進(jìn)后的磨損均衡情況更好,。

    改進(jìn)前后塊擦除次數(shù)標(biāo)準(zhǔn)差對比圖如圖4所示，可以看到隨著擦除次數(shù)的增加,，改進(jìn)后塊擦除次數(shù)標(biāo)準(zhǔn)差增長的速度遠(yuǎn)小于改進(jìn)前,。

    在改進(jìn)后的Yaffs2文件系統(tǒng)下，塊的最大,、最小擦除次數(shù)差值減少為改進(jìn)前的1/4,，如圖3所示,。這表明在回收塊選擇機(jī)制中加入塊的年齡參數(shù)后，被冷數(shù)據(jù)占據(jù)的塊能夠及時得到更新,，使得NAND Flash設(shè)備中的塊可以更加均勻地參與擦除操作,。另外引入冷熱數(shù)據(jù)分離策略后，隨著擦除次數(shù)增加,，塊擦除次數(shù)標(biāo)準(zhǔn)差增加得更緩慢,，如圖4所示。這說明將冷數(shù)據(jù)拷貝到擦除次數(shù)多的塊上,，這樣的數(shù)據(jù)交換方法能有效阻止塊繼續(xù)擦除,。并且冷熱數(shù)據(jù)分離策略中冷數(shù)據(jù)的收集方式有效解決了冷熱數(shù)據(jù)共存時的更新問題。

    當(dāng)NAND Flash設(shè)備中出現(xiàn)一個壞塊后,，該壞塊不僅不能繼續(xù)用于存儲數(shù)據(jù),，而且會引起別的塊迅速壞掉。為了保障數(shù)據(jù)的穩(wěn)定,，通常情況下NAND Flash設(shè)備中出現(xiàn)一個壞塊后不會繼續(xù)使用^[7],。試驗(yàn)中塊的擦除壽命是100 000次，若每天需要做400次擦除操作,，在未做改進(jìn)的Yaffs2文件系統(tǒng)下,，NAND Flash僅有5%的塊輪流更新，那么可以得到閃存設(shè)備的使用壽命：

    在改進(jìn)后的Yaffs2文件系統(tǒng)下,，NAND Flash有20%的塊輪流更新,，而磨損均衡需要付出額外4.05%的擦除代價(jià)，那么可以得到閃存設(shè)備的使用壽命：

    由式(5)和式(6)可知,，改進(jìn)后的Yaffs2文件系統(tǒng)可以延長NAND Flash設(shè)備的使用壽命,。

5 結(jié)論

    本文從兩方面對Yaffs2文件系統(tǒng)作改進(jìn)：一方面對回收塊選擇機(jī)制作改進(jìn)，另一方面引入冷熱數(shù)據(jù)分離策略,。NAND Flash設(shè)備在改進(jìn)后的文件系統(tǒng)中,，磨損均衡效果得到明顯提升。良好的磨損均衡表現(xiàn)可以增加NAND Flash的使用壽命,，仿真實(shí)驗(yàn)?zāi)M了真實(shí)的設(shè)備運(yùn)行情況,，實(shí)驗(yàn)成果適用于以NAND Flash為存儲介質(zhì)的智能消費(fèi)電子產(chǎn)品或者計(jì)算機(jī)領(lǐng)域中。

參考文獻(xiàn)

[1] Yan Hua,，Yao Qian.An efficient file-aware garbage collection algorithm for NAND Flash-based consumer[J].IEEE Transactions on Consumer Electronics,，November 2014，60(4)：623-627.

[2] 姚乾,，嚴(yán)華.基于冷熱數(shù)據(jù)識別的NAND Flash數(shù)據(jù)存儲管理研究[D].成都：四川大學(xué),，2013.

[3] WU M，ZWAENEPOE W.eNvy：A non-volatile main memory storage system[C].CA,，USA：AMC,，In Proceedings of 6th International Conference on Architecture Support for Programming Language and Operating Systems,，1994：86-97.

[4] KAWAGUCHI A，NISHIOKA S,，MOTODA H.A flash memory based file system[C].LA,，USA：In Proceedings of 1995 USENIX Technical Conference，1995：155-164.

[5] Chang Lipin.On efficient wear leveling for large-scale flash memory storage systems[C].Proceedings of the 2007 ACM Symposium on Applied Computing,，SAC′07,，2007：1126-1130.

[6] Lin Mingwei，Chen Shuyu.Efficient and intelligent garbage collection policy for NAND Flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics,，2013,，59(3)：538-543.

[7] 楊習(xí)偉,，賀云健.車載娛樂系統(tǒng)的Nand Flash管理模式研究[J].Microcontrollers & Embedded Systems,，2008(3)：19-22.