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.