0 引言

    NAND Flash存儲(chǔ)設(shè)備與傳統(tǒng)機(jī)械磁盤相比，具有體積小、存儲(chǔ)密度高、隨機(jī)存儲(chǔ)和讀寫能力強(qiáng)、抗震抗摔、功耗低等特點(diǎn)^[1]。它被廣泛用于智能手機(jī)、車載智能中心、平板電腦等智能終端中。近年來(lái)，以NAND Flash為存儲(chǔ)介質(zhì)的固態(tài)硬盤也得到越來(lá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為存儲(chǔ)介質(zhì)時(shí)存在磨損均衡的缺陷，可通過(guò)對(duì)回收塊選擇機(jī)制作改進(jìn)和引入冷熱數(shù)據(jù)分離策略來(lái)提高磨損均衡的效果。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    (3)塊反轉(zhuǎn)：當(dāng)熱池中某個(gè)塊被冷數(shù)據(jù)突然占據(jù)時(shí)，導(dǎo)致該塊中的冷數(shù)據(jù)無(wú)法用于數(shù)據(jù)交換操作。這需要找到熱池中擦除次數(shù)最多（Hottest_hp）的塊和熱池中擦除最少(Coldest_hp)的塊，二者擦除次數(shù)之差小于一個(gè)閾值時(shí)(如式(3))則進(jìn)行熱塊反轉(zhuǎn)操作。熱塊反轉(zhuǎn)操作，將熱池中擦除次數(shù)最少的塊放到冷池中去。另外當(dāng)冷池中的某個(gè)塊數(shù)據(jù)突然變熱時(shí)，導(dǎo)致該塊不能被數(shù)據(jù)交換操作降溫。這需要用該塊的eec參數(shù)來(lái)判別，eec表示有效擦除周期（塊改變所屬池后的擦除次數(shù)）。因此滿足式(4)時(shí)，進(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)境是通過(guò)Vmware工具安裝Linux虛擬機(jī)，然后在Linux下安裝Qemu工具來(lái)搭建仿真實(shí)驗(yàn)開發(fā)板，并移植Yaffs2文件系統(tǒng)。為了公平測(cè)試，關(guān)閉Yaffs2自帶的緩存功能。用于測(cè)試的文件大小是從16 KB～1 024 KB隨機(jī)生成，測(cè)試數(shù)據(jù)占據(jù)整個(gè)Flash設(shè)備容量的90%，其中僅有15%的數(shù)據(jù)更新，這樣的更新操作滿足齊夫分布（Zif）^[6]。

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

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

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

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

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

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

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

    當(dāng)NAND Flash設(shè)備中出現(xiàn)一個(gè)壞塊后，該壞塊不僅不能繼續(xù)用于存儲(chǔ)數(shù)據(jù)，而且會(huì)引起別的塊迅速壞掉。為了保障數(shù)據(jù)的穩(wěn)定，通常情況下NAND Flash設(shè)備中出現(xiàn)一個(gè)壞塊后不會(huì)繼續(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)可以延長(zhǎng)NAND Flash設(shè)備的使用壽命。

5 結(jié)論

    本文從兩方面對(duì)Yaffs2文件系統(tǒng)作改進(jìn)：一方面對(duì)回收塊選擇機(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為存儲(chǔ)介質(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ù)識(shí)別的NAND Flash數(shù)據(jù)存儲(chǔ)管理研究[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í)偉，賀云健.車載娛樂(lè)系統(tǒng)的Nand Flash管理模式研究[J].Microcontrollers & Embedded Systems，2008(3)：19-22.