0 引言

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

1 Yaffs2和Nand Flash關系

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

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

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

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

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

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

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

3 Yaffs2的改進方法

3.1 回收塊選擇機制的改進

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

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

3.2 增加冷熱數據分離策略

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

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

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

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

4 仿真實驗

4.1 實驗環境

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

    實驗中NAND Flash總容量是64 MB，共有512個塊，每個塊含64個頁，每個頁大小是2 048 B。試驗中T_h閾值選定為8。

4.2 實驗結果

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

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

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

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

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

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

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

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

5 結論

    本文從兩方面對Yaffs2文件系統作改進：一方面對回收塊選擇機制作改進，另一方面引入冷熱數據分離策略。NAND Flash設備在改進后的文件系統中，磨損均衡效果得到明顯提升。良好的磨損均衡表現可以增加NAND Flash的使用壽命，仿真實驗模擬了真實的設備運行情況，實驗成果適用于以NAND Flash為存儲介質的智能消費電子產品或者計算機領域中。

參考文獻

[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] 姚乾，嚴華.基于冷熱數據識別的NAND Flash數據存儲管理研究[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] 楊習偉，賀云健.車載娛樂系統的Nand Flash管理模式研究[J].Microcontrollers & Embedded Systems，2008(3)：19-22.