0 引言

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

1 Yaffs2和Nand Flash關系

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

    最上層用戶應用程序通過VFS(Virtual File System)提供的統(tǒng)一接口，將數(shù)據(jù)更新等文件操作傳遞給Yaffs2。VFS代表虛擬文件系統(tǒng)，它為上層應用提供統(tǒng)一的接口。有了這些接口，應用程序只用遵循抽象后的訪問規(guī)則，而不必理會底層文件系統(tǒng)和物理構(gòu)成上的差異。然后Yaffs2通過MTD（Memory Technology Device）提供的統(tǒng)一訪問接口對NAND Flash進行讀、寫和擦除操作，從而完成數(shù)據(jù)的更新或者存儲操作。MTD代表內(nèi)存技術(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ù)不能直接在相同的位置更新。當一個頁中數(shù)據(jù)需要更新時，必須將該頁中有效數(shù)據(jù)拷貝到其他空閑頁上再更新，并將原來頁上的數(shù)據(jù)置為無效。隨著時間的推移，許多無效頁累積在存儲器中使得空閑頁逐漸減少。當存儲器中的空閑空間不足時，啟動垃圾回收操作，利用回收塊選擇機制從待回收塊中選取滿足要求的塊來擦除，從而得到足夠的空閑空間。NAND Flash中塊的擦除次數(shù)有限，通常為10 000次～100 000次^[2]。當某個塊的擦除次數(shù)超過使用壽命時，該塊將無法正常用于數(shù)據(jù)存儲。因此，垃圾回收應利用合理的回收塊選擇機制，從待回收塊中找到回收后能產(chǎn)生良好磨損均衡效果且付出較少額外代價的塊來回收，從而獲得足夠的空閑空間用于數(shù)據(jù)更新操作。

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

    Yaffs2中回收塊的選擇機制^[3]是從待回收塊中找到有效數(shù)據(jù)最少的塊來回收。回收過程中，Yaffs2能夠減少有效數(shù)據(jù)的額外讀和寫操作。當數(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容易選中這樣的塊來更新。而當某個塊中含大量有效冷數(shù)據(jù)時，冷數(shù)據(jù)少更新的特點使得Yaffs2難以選中這類塊來更新。更新后的塊會用于存放新寫入的數(shù)據(jù)，而新寫入的數(shù)據(jù)通常是熱數(shù)據(jù)，由此可知熱數(shù)所在塊會經(jīng)常被更新。最終熱數(shù)據(jù)所在的塊成為擦除次數(shù)多的塊，冷數(shù)據(jù)所在的塊成為擦除次數(shù)少的塊。因此Yaffs2的回收塊選擇機制會造成NAND Flash設備中塊的擦除次數(shù)呈兩級分化，即塊的最大、最小擦除次數(shù)差值不斷變大。所以Yaffs2中不應只考慮數(shù)據(jù)更新所產(chǎn)生的額外讀寫代價，還應考慮塊的存在年齡對磨損均衡效果的影響，這才能解決磨損均衡中兩級分化的問題。

    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ù)的更新速度快，當熱數(shù)據(jù)更新時會導致冷數(shù)據(jù)被迫更新。但更新后剩下的數(shù)據(jù)同樣不能占滿一個整塊，系統(tǒng)會再次將冷數(shù)據(jù)和熱數(shù)據(jù)存放到同一個塊中。隨著以上的更新方式不斷進行，將導致一系列不必要的數(shù)據(jù)讀、寫以及塊的擦除操作。因此Yaffs2的更新策略會使冷熱數(shù)據(jù)共存的塊易被多次更新，而冷數(shù)據(jù)占據(jù)的塊很少更新，最終使得塊擦除次數(shù)標準差過大，導致磨損不均衡。由于Yaffs2的更新策略中沒有做冷熱數(shù)分離，這使得磨損不均衡問題難以解決。

3 Yaffs2的改進方法

3.1 回收塊選擇機制的改進

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

其中，age指塊從分配開始到當前垃圾回收時刻為止的年齡，u表示單個塊中有效數(shù)據(jù)的占有比率。新的回收塊選擇機制選取當前時刻年齡最大且有效數(shù)據(jù)占有最少(即benefit/cost比值最大)的塊作為回收對象。當一個塊上存儲的是冷數(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ù)更新而強制更新冷數(shù)據(jù)的問題。在系統(tǒng)運行過程中檢測到塊的最大、最小擦除次數(shù)差值過大時，將收集到的冷數(shù)據(jù)用數(shù)據(jù)交換操作放置到擦除次數(shù)多的塊上。當冷池中塊被熱數(shù)據(jù)占據(jù)或者熱池中塊被冷數(shù)據(jù)占據(jù)時，冷熱數(shù)據(jù)分離策略也能處理這類塊反轉(zhuǎn)問題。數(shù)據(jù)的冷熱程度對塊的擦除次數(shù)會產(chǎn)生直接影響，因此冷熱數(shù)據(jù)分離策略通過塊擦除次數(shù)來判斷數(shù)據(jù)溫度。改進步驟如下：

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

    (2)數(shù)據(jù)交換：找出熱池中擦除次數(shù)最多（Hottest_hp）的塊，冷池中擦除次數(shù)最少（Coldest_cp）的塊。當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ù)不易更新的特點來減少塊的繼續(xù)擦除；而將新寫入的數(shù)據(jù)存放到擦除次數(shù)少的塊上，最終達到磨損均衡的目的。

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

4 仿真實驗

4.1 實驗環(huán)境

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

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

4.2 實驗結(jié)果

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

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

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

    改進前后塊擦除次數(shù)標準差對比圖如圖4所示，可以看到隨著擦除次數(shù)的增加，改進后塊擦除次數(shù)標準差增長的速度遠小于改進前。

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

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

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

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

5 結(jié)論

    本文從兩方面對Yaffs2文件系統(tǒng)作改進：一方面對回收塊選擇機制作改進，另一方面引入冷熱數(shù)據(jù)分離策略。NAND Flash設備在改進后的文件系統(tǒng)中，磨損均衡效果得到明顯提升。良好的磨損均衡表現(xiàn)可以增加NAND Flash的使用壽命，仿真實驗模擬了真實的設備運行情況，實驗成果適用于以NAND Flash為存儲介質(zhì)的智能消費電子產(chǎ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] 姚乾，嚴華.基于冷熱數(shù)據(jù)識別的NAND Flash數(shù)據(jù)存儲管理研究[D].成都：四川大學，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] 楊習偉，賀云健.車載娛樂系統(tǒng)的Nand Flash管理模式研究[J].Microcontrollers & Embedded Systems，2008(3)：19-22.