基于逻辑页冷热分离的NAND闪存磨损均衡算法

王晋阳 严华

摘要：针对现有的NAND闪存垃圾回收算法对磨损均衡考虑不足的问题，提出了一种基于逻辑页冷热分离的NAND闪存磨损均衡算法。算法同时考虑了无效页的年龄、物理块的擦除次数以及物理块更新的频率，采用混合模式选择回收符合条件的物理块。同时，推导了一种新的逻辑页热度计算方法，并将回收块上有效页数据按照逻辑页的热度进行了冷热分离。实验结果表明，与GR算法、CB算法、CAT算法以及FaGC算法相比，该算法不仅在磨损均衡上取得了很好的效果，而且总的擦除次数与拷贝次数也有了明显减少。

关键词：NAND闪存；磨损均衡；垃圾回收；物理块；逻辑页

中图分类号：TP316 文献标志码：A

Abstract： According to the problem of the existing garbage collection algorithm for NAND flash memory， an efficient algorithm， called AWGC （Age With Garbage Collection）， was presented to improve wear leveling of NAND flash memory. A hybrid policy with the age of invalid page， erase count of physical blocks and the update frequency of physical blocks were redefined to select the returnable block. Meanwhile， a new heat calculation method logic pages was deduced， and coldhot separating of valid pages in returnable block was conducted. Compared with the GReedy （GR） algorithm， CostBenefit （CB） algorithm， CostAgeTime （CAT） algorithm and Fileaware Garbage Collection （FaGC） algorithm， not only some good results in wear leveling have been got， but also the total numbers of erase and copy operations have significantly been reduced.

Key words：NAND flash； wearleveling； garbage collection； physical block； logic page

0 引言

闪存（flash memory）由于具有非易失、存储容量大、体积小、抗震性好以及多次擦写等优点，已经成为嵌入式系统一种常见的存储介质[1-2]。NAND和NOR是当前主流的闪存技术，NAND写和擦除操作快，但随机存取慢；而NOR随机存取快，但擦除慢。NAND相对于NOR而言，存储单元密度高、成本相对较低、性价比好，所以被广泛采用。NAND Flash内部分为多个块（Block物理块），每个块由多个页（Page物理页）组成。页是写入数据的最小单元，块是擦除的最小单元。每个闪存物理块的擦除次数一般在10万次到100万次，若超过擦除次数的上限，会影响闪存数据存储的性能[3]。NAND闪存管理系统对数据的更新操作采用的是“异地更新”的策略[4]，即将最新的数据写入到别处，同时将原来的数据标注为无效。对于存在大量实时数据的嵌入式系统而言，会频繁地执行读写和更新操作，导致无效的数据会变得越来越多。为了回收这些无效数据，释放更多的可用空间，垃圾回收策略被提出，目的是从这些含有无效数据的块中选择出最符合条件的块进行擦除，以最优的方式释放更多的可用空间。好的垃圾回收算法不仅能大幅度减少拷贝和擦除次数，而且能有效改善磨损均衡的效果[5]。所以，磨损均衡的核心就是回收策略的选择。

近些年来，为了改善磨损均衡的效果，提出了很多的垃圾回收算法。如GR（GReedy）算法[6]，主要的策略是选择有效页最少的物理块进行回收，因为有效页的数量越少，拷贝的次数就会越少，算法核心是以最小的拷贝次数来获取更多的可用空间，但是，GR算法基本未考虑磨损均衡。CB （CostBenefit）算法[7]利用公式Age*（1-u）*2u选择回收块，Age表示物理块的年龄，即更新的时间间隔，u表示有效页的比例。选择公式值最大的物理块作为回收块，考虑到了物理块更新的时间间隔和有效页的比例，使得长期不更新的物理块被回收的可能性增大，所以磨损均衡的效果在一定程度上要好于贪心算法。CAT（CostAgeTime）算法[8]是对CB算法的改进，考虑了擦除次数对磨损均衡的影响，选择更新时间最长、有效页数量最少且擦除次数最少的块进行回收，并且CAT算法以物理块的擦除次数对有效页数据进行了冷热分离，所以磨损均衡效果要优于前两种算法。但是，以上三种算法仅仅只考虑了最近一次物理块的更新时间，不能准确反映物理块年龄，并且以擦除次数定义数据热度，其冷热分离的效果并不好。FaGC（Fileaware Garbage Collection）算法[9]提出了一种基于文件热度的磨损均衡算法，在磨损均衡方面取得了很大的突破，但是FaGC在回收策略上主要用到的是贪心算法，其回收的代价很大，而且计算热度的方法并不能够准确地反映当前逻辑页的热度，所以仍然有可以改进的地方。

通过对NAND闪存的磨损均衡机制进行更为深入的研究与分析，针对上述垃圾回收算法存在的问题，考虑逻辑页的热度以及无效页的年龄，重新定义了热度计算方法和回收策略，提出了一种基于逻辑页冷热分离的NAND闪存磨损均衡算法，即AWGC （Age With Garbage Collection）算法。实验基于Linux系统和Qemu嵌入式仿真开发板，从4个方面与上述算法作了对比，证明了该算法在磨损均衡应用中的优越性。

1 算法的实现

1.1 基本原理

如图1所示，NAND Flash存储设备的系统结构主要由文件系统、FTL（Flash Translation Layer）层、MTD（Memory Technology Driver）层和NAND闪存设备这4个部分构成。

FTL层和MTD层是文件系统与NAND闪存设备的中间层[10]。FTL层，又称为闪存转换层，是NAND闪存芯片与基础文件系统之间的一个转换层，它使操作系统和文件系统能够像访问硬盘一样访问NAND闪存设备，这里主要提供了三个重要的功能，分别是地址映射表、磨损均衡算法以及垃圾回收的策略[11]。MTD层，即内存技术设备（Memory Technology Device），主要功能是将文件系统与底层NAND闪存设备进行隔离，为上层的文件系统提供统一的接口。

文件系统管理的是一个逻辑空间，而NAND闪存设备则是物理空间，在页级映射的地址映射表中，逻辑地址对应逻辑页，物理地址对应物理页，逻辑页与物理页是一对一的关系。文件系统所操作的基本单位是逻辑页，只在需要进行更新操作时才进行逻辑页到物理页的映射，逻辑页作为一个抽象的概念，它必然要映射到具体的物理页上去，所以用逻辑页的更新频率来定义有效页的热度更为准确。

1.2 数据热度的定义

目前，大部分定义数据冷热的方式为物理页的更新频率或者物理块的擦除次数，然而这两种方式并不足以准确反映数据的热度。所以，为了能准确定义数据的冷热，有效地进行冷热分离，提出了一种新的热度计算方式，即考虑逻辑页更新的时间间隔和上一次的热度值，以这两个参数来推导出当前逻辑页的热度。

式（1）中，当权值w为0时，当前逻辑页热度的确定就只考虑了逻辑页更新的时间间隔；随着w的不断增大，更新的时间间隔的权重就会不断降低，相反，上一次逻辑页的热度值被考虑。为了平衡两个参数对热度值的影响，默认w的值为0.5，同时考虑逻辑页更新的时间间隔和上一次的热度值。

式（2）中，Tdiff表征的主要内容是逻辑页更新的时间间隔对热度值的影响。显然，当逻辑页更新的时间间隔比较大时，就说明已经有很长时间没有对它进行操作了，故热度值应该变小。所以，逻辑页更新的时间间隔与热度值成反比例的关系。这里加入Hmax参数，利用最大的热度值来调整逻辑页更新的时间间隔与热度值的关系，Hmax一般设定为10，故整个热度区间在0～10。由于初次数据的写入没有初始热度，所以设定了一个初始热度值Th，其值一般选定为Hmax的一半。

热度公式还解决了由于逻辑页更新时间间隔很长无法得出热度值的问题。若更新的时间很长，则式（2）中Tdiff的值可能为0，这时本次逻辑页的热度可以由上一次逻辑页的热度决定，这样就不会影响对于热度值的计算了。

1.3 数据的冷热分离

由于NAND闪存“异地更新”的特性，对选中物理块的有效页数据会先拷贝到空闲块上，然后进行擦除操作。数据的冷热分离是在有效页被拷贝之前，主要是为了将具有相近热度的有效页汇聚在指定的物理块上，以达到减少拷贝和擦除次数的目的。由于在进行冷热分离之后，页的热度相似，同时为无效或者有效的概率会增大，那么这些页所在的块，要么有效页多，要么无效页多，在下一次进行垃圾回收时，就可大大减少拷贝和擦除次数。

本文采用了一种基于逻辑页热度的冷热分离，通过有效页所对应逻辑页的热度来决定其物理页中数据写入的对象。这里的对象分别指代的是擦除次数最多的物理块和擦除次数最少的物理块。具体的冷热分离步骤如下：

1）设定判断冷热分离的阈值Th，并通过式（1）计算出当前逻辑页的热度值。

2）若当前逻辑页的热度≥Th，则该逻辑页所对应的有效页被定义为热页，这时应该将有效页写入擦除次数最少的物理块中。

3）若当前逻辑页的热度

4）完成有效页的冷热分离后，更新逻辑页的热度值以及操作的时间，用于下一次的热度计算和更新操作。

1.4 新的垃圾回收策略

数据的冷热分离减少了擦除和拷贝次数，但是在研究过程中发现，要提高NAND闪存的使用寿命，对于磨损均衡的要求比较高，所以一个好的回收策略很有必要。AWGC算法首先考虑了以无效页年龄[12]和擦除次数作为回收的条件，具体公式如下：

其中：n表示物理块中无效页的数目，Tc表示当前的时间，Ti表示变为无效页的时间，Agei则表示第i个无效页的年龄，ε表示物理块的擦除次数。对时间进行归一化处理，采用将时间取对数的方式，降低时间对算法的影响。

式（3）的主要思想是计算出每个块中无效页的年龄，然后用每个物理块中无效页的年龄之和来代表该物理块的年龄。显然，AWGC算法选择的是AWT值最大的物理块，即物理块年龄最大且擦除次数最少的块。因为影响物理块年龄的原因主要是两点：第一，无效页的比例较多；第二，变为无效页的时间间隔较长。所以这两种情况都是有可能被选中的，若选中的是无效页较多的物理块，则可以减少拷贝有效页的次数；若选中变为无效页时间较长的块，则说明该物理块长期没有得到回收更新，所以选择这类型的块能提高磨损均衡的效果。

2 实验及分析

2.1 实验环境

实验环境由两个主要步骤搭建完成。首先，通过Vmware工具安装Linux虚拟机，并移植Yaffs2文件系统；然后在Linux下安装Qemu嵌入式仿真开发板。利用NANDsim来模拟NAND Flash存储设备。用于测试的文件由已编写好的测试程序创建，大小为16kb～1024kb，测试的数据占整个NAND闪存设备容量的90%，并对15%的数据按照齐夫分布[13]进行更新操作。

实验选取NAND Flash的总容量为64MB，包括512个块，每个块由64个页组成。为了保证实验结果的客观性，关闭了Yaffs2文件系统的缓存功能，并选择在急迫（aggressive）模式下进行垃圾回收，并且设置FaGC的初始阈值与AWGC的初始阈值相等。AWGC算法在实验中所选取参数的值如表1所示。其中Fth表示磨损均衡的初始阈值；Hmax表示最大的热度值；w表示热度计算公式的权值；p表示时间的修正因子；Th表示判断冷热分离的阈值；Tscat表示分散度的阈值。

2.2 算法性能的分析

实验主要的对比对象为4种现存的算法，分别是GR算法、CB算法、CAT算法以及FaGC算法，并从总的擦除次数、总的拷贝次数、物理块最大擦除次数与最小擦除次数的差值和物理块擦除次数的标准差这四方面进行对比分析。其中，总的擦除次数和拷贝次数代表的是在整个回收过程中所要花费的总代价；物理块最大擦除次数与最小擦除次数的差值代表着磨损均衡两极分化的情况；而物理块擦除次数的标准差则代表整个回收过程中磨损均衡的稳定程度，若标准差的曲线越稳定且收敛，则表示磨损均衡稳定程度越好，反之则稳定程度越差。

由图2和图3可以得出，AWGC算法在总的擦除次数和总的拷贝次数上明显低于前四种算法，得到了很好的优化。

原因在于AWGC算法利用逻辑页的更新频率定义了数据的热度，比较准确对有效物理页数据进行了冷热分离，使得被定义为热数据的有效页汇聚到擦除次数最少的物理块上，被定义为冷数据的有效页汇聚到擦除次数最多的物理块上。这样在进行垃圾回收时，不仅大大减少拷贝有效页的次数，而且提高了垃圾回收的效率，从而减少了总的擦除次数。FaGC算法虽然也进行了数据的冷热分离，但是计算热度的方法并不是很准确，算法虽然同时考虑了逻辑页更新的时间间隔和上一次的热度值，但是当前逻辑页的热度值还是由上一次的热度乘以一个固定的系数所得，并不能完整准确地反映整个热度变化情况。而AWGC算法采用加权和的方式，平衡了两个参数对热度值的影响，使得计算出的当前热度值更为准确，所以冷热分离的效果要好， 因此，在擦除次数和拷贝次数的效果上要优于FaGC算法。

图4和图5代表的是物理块最大擦除次数和最小擦除次数的差值和物理块擦除次数的标准差，体现的是几种算法磨损均衡的整体效果。由图5可以看出随着擦除次数的不断增大，GR算法、CB算法和CAT算法都不断增大，呈现出非收敛的趋势；而AWGC算法和FaGC算法随着擦除次数的增大，曲线比较稳定，呈现收敛的趋势。这是因为AWGC算法和FaGC算法都引入了控制磨损均衡的阈值，采用混合的回收策略，对长期为冷的块进行了回收处理，磨损均衡的稳定程度要明显优于前三种算法。但是FaGC算法的混合回收策略主要采用是贪心算法，而AWGC算法考虑了无效页的时间以及物理块的擦除次数，从这两个方面限定了回收块的条件，使得回收的效率得到了很大提升，所以在如图4中可以看出，AWGC算法最大擦除次数与最小擦除次数的差值比其他几种算法小很多，说明磨损均衡两极分化较小。实验结果表明，随着擦除次数的不断增加，AWGC算法的分化情况能够基本保持稳定，而FaGC算法的分化情况会有所上升， 因此，AWGC算法整体的磨损均衡效果要好于前面四种算法，证明了AWGC算法在磨损均衡应用中的优越性。

3 结语

本文重新定义了冷热数据的计算方法，实现了对数据的冷热分离，并形成了新的垃圾回收策略。实验结果表明，与GR算法、CB算法、CAT算法以及FaGC算法相比，AWGC算法不仅磨损均衡的整体效果很好，而且在总的擦除次数和总的拷贝次数上也有明显的减少。虽然算法需要一定的内存开销，但是算法以最小的回收代价，取得了很好的回收效果，提高了回收的效率，改善了磨损均衡的效果，可在很大程度上延长NAND闪存的寿命。

参考文献：

[1]LI H， YANG C， TSENG H. Energyaware flash memory management in virtual memory system[J]. IEEE Transactions on Very Large Scale Integration Systems，2008，16（8）：952-964.

[2]XU G， LIN F， XIAO Y. CLRU： a new page replacement algorithm for NAND flashbased consumer electronics[J]. IEEE Transactions on Consumer Electronics， 2014，60（1）：38-44.

[3]CHUNG C C， SHENG D， HSUEH N. A highperformance wearleveling algorithm for flash memory system[J]. IEICE Electronics Express， 2012，9（24）：1874-1880.

[4]SHIN L. Hot/cold clustering for page mapping in NAND flash memory[J]. IEEE Transactions on Consumer Electronics， 2011，57（4）：1728-1731.

[5]时正，纪金松，陈香兰，等.一种基于差分进化的Flash文件系统垃圾回收算法[J]. 电子学报， 2011， 39（12）：280-284.（SHI Z， JI J S，CHEN X L， et al. A garbage collection algorithm for flash file system based on differential evolution[J]. Acta Electronica Sinica， 2011， 39（12）：280-284.）

[6]WU M， ZWAENEPOEL W. eNvy： A nonvolatile main memory storage system[C]// Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. New York： ACM， 1994：86-97.

[7]KAWAGUCHI A， NISHIOKA S， MOTODA H. A flash memory based file system[C]// Proceedings of the USENIX 1995 Technical Conference. Berkeley： USENIX， 1995：155-164.

[8]CHIANG M， CHANG R. Cleaning policies in mobile computers using flash memory[J]. Journal of Systems and Software， 1999， 48（3）：213-231.

[9]YAN H， YAO Q. An efficient fileaware garbage collection algorithm for NAND flashbased consumer electronics[J]. IEEE Transactions on Consumer Electronics， 2014， 60（4）：623-627.

[10]KIM H， SHIN D. Clustered pagelevel mapping for flash memorybased storage devices[J].IEEE Transactions on Consumer Electronics，2015，61（1）：47-55.

[11]张琦，王林章，张天，等.一种优化的闪存地址映射方法[J].软件学报， 2014，25（2）：314-325.（ZHANG Q， WANG L Z， ZHANG T， et al. Optimized address translation method for flash memory[J]. Journal of Software， 2014， 25（2）：314-325.）

[12]KWON O， KOH K， LEE J. FeGC： An efficient garbage collection scheme for flash memory based storage systems[J].Journal of Systems and Software， 2011， 84（9）：1507-1523.

[13]LIN M， CHEN S. Efficient and intelligent garbage collection policy for NAND flash based consumer electronics[J]. IEEE Transactions on Consumer Electronics， 2013， 59（3）：538-543.