基于数据更新间隔的NAND 闪存垃圾回收算法

余 进，严 华

（四川大学 电子信息学院，成都 610065）

0 概述

NAND 闪存具有体积小、速度快、价格低、非易失等优点，在电子设备的数据存储中被广泛应用［1-2］。NAND 闪存在结构上由若干个物理块组成，每个物理块又由若干个物理页组成。在NAND 闪存中，数据读写以页为单位进行，数据擦除以块为单位进行，数据更新则采用异地更新策略［3-4］。NAND 数据在进行更新时，不能直接将新数据覆写在原数据位置，需要将原始数据标记为无效，再将新数据写到其他空闲页［5-6］。异地更新策略会导致NAND 闪存中产生大量无效页，无效页需要经过擦除操作变为空闲页后才可再次使用，因此，合理地处理无效页可以大幅提高NAND 闪存的存储效率，这一过程也被称为垃圾回收［7-8］。同时，NAND 闪存每个块的擦除次数存在上限［9-10］，为避免某些块被频繁擦除而导致无法使用，在擦除过程中应尽量使操作均匀分布在各个块上，这一过程被称为磨损均衡［11］。磨损均衡效果好的垃圾回收算法是提高NAND 闪存使用效率、延长其使用寿命的关键［12］。

近年来，研究人员提出了许多垃圾回收算法。WU 等提出一种GR 算法［13］，该算法选取有效页比例最小的块进行回收，垃圾回收效率较高，但是其未考虑磨损均衡效果。KAWAGUCHI 等提出一种CB（Cost-Benefit）算法［14］，该算法选取有效页比例小且距上一次更新时间长的块进行回收，其磨损均衡效果较GR 算法有一定提升。CHIANG 等提出一种CAT（Cost-Age-Time）算法［15］，其在CB 算法的基础上选择擦除次数最小的块进行回收，同时将回收块中冷热数据分开存储在不同块中，磨损均衡效果有了进一步提升，但该算法依据块的擦除次数区分数据冷热，准确性不高。YAN 等提出一种FaGC（Fileaware Garbage Collection）算法［16］，该算法基于GR 算法进行回收块选取，根据页的更新频率区分回收块中有效页的冷热，其能取得较好的磨损均衡效果。HUANG 等提出FaGC+算法［17］，其在FaGC 算法的基础上，选择各逻辑页更新间隔累加和最大的块进行回收，同时使用逻辑页更新序号改进回收块中有效页热度的计算公式，进一步提升了磨损均衡效果，但是该算法仅考虑逻辑页上一次的更新序号，并以此进行回收块选取和热度计算，缺少对逻辑页整体更新情况的考虑。

本文考虑闪存中数据整体的更新情况，提出一种基于数据更新间隔的垃圾回收（UIGC）算法。UIGC 算法综合考虑块中无效页年龄累计和以及块中有效页比例，结合物理块磨损均衡效果选取回收块，并根据回收块中有效页热度和数据更新稳定性，将有效页数据进行分块存储，从而提高块中数据的同步更新概率。

1 基于数据更新间隔的垃圾回收算法

UIGC 算法进行垃圾回收的过程由分散度判断、回收块选择、数据分离3 个部分组成，算法整体流程如图1 所示：首先，计算闪存中空闲页分散度，判断是否进入回收块选择阶段；在回收块选择阶段，根据闪存状态选择合适的策略进行回收块选择；最后处理回收块中的有效页，将不同类型的有效页数据迁移至不同的块中。在数据分离完成后，将原有效页标记为无效，对全为无效页的块进行块擦除操作，从而完成一次垃圾回收过程。

图1 基于数据更新间隔的垃圾回收算法流程Fig.1 Procedure of garbage collection algorithm based on data update interval

1.1 分散度判断

为了提高垃圾回收效率，UIGC 算法使用分散度的概念作为回收块选择过程的触发条件［18］。分散度计算公式如式（1）所示：

其中：Nfc为闪存中空闲页的总数；Nfb为空闲块的总数；Nc为单个物理块中页的数量。分散度S表示闪存中空闲页的分布情况，空闲页分布越分散，S值越大，反之S值越小。当S大于阈值fsc时，启动回收块选择策略。当闪存中空闲页分布比较分散时，文件系统需要频繁寻找可用块，降低了闪存使用效率，此时进行垃圾回收，在降低分散度的同时也能产生更多的空闲页，从而提高垃圾回收的效率。分散度判断过程描述如算法1 所示。

算法1分散度判断算法

1.2 回收块选择

在回收块选择策略上，大部分研究考虑块中无效页比例以及物理块上一次更新时间间隔，此为垃圾回收效率上的考量。本文回收块选择策略由常规状态下的动态回收块选择策略以及特定状态下的静态回收块选择策略组成，分2 个部分综合考虑闪存的回收效率以及磨损均衡效果。

1.2.1 动态回收块选择

本文基于页序号概念设计动态回收块选择策略［17］，综合考虑回收块中有效页比例以及无效页年龄，最终使用的动态回收块选择公式如式（2）所示：

其中：u为块中有效页比例；n为块中无效页数量；Snow为启动垃圾回收时的页序号；Si为对应的物理页变成无效页时的页序号；Snow-Si表示对应的无效页年龄。式（2）计算块中所有无效页年龄累加和，同时考虑块中有效页比例，综合选取块中无效页年龄大且有效页比例小的块进行回收，即最终选择CCB值最大的块作为回收块，以此降低回收块中有效页的数量，减少垃圾回收时迁移有效数据带来的页拷贝操作开销，提高垃圾回收效率。

1.2.2 静态回收块选择

在数据非随机写入时，存在部分物理块中有效页比例较高但长期未得到更新的情况，此时使用动态回收块选择策略将无法选择到该块进行回收，从而影响算法整体的磨损均衡效果。针对此类情况，本文在动态回收块选择策略的基础上，设计静态回收块选择策略，以改善算法的磨损均衡效果。

启动静态回收块选择策略的条件为闪存中物理块的最大擦除次数和最小擦除次数之差大于阈值Te，阈值Te的计算公式如式（3）所示：

其中：Nblock为闪存系统中物理块总数；Nvalid为全是有效页的块的数量；Twl为初始设置阈值。静态回收块选择策略直接选择擦除次数最少的块进行回收，当擦除次数一样时，优先选择块中有效页比例小的块进行回收。算法每进行一次垃圾回收过程，则更新闪存系统中的Nvalid值，重新计算策略选择阈值Te。通过2 种策略切换的回收块选择方式，在保证闪存系统垃圾回收效率的同时，使块擦除操作均匀分布在各个物理块上，从而提升算法的磨损均衡效果。回收块选择具体处理流程如算法2 所示。

算法2回收块选择算法

1.3 数据分离

若回收块中存在有效页，回收时需要先将块中存在的有效页数据迁移到其他空闲页中，并将该有效页置为无效页。若将更新间隔相近的数据迁移到同一块中，则该块中有效页将有较大概率同时变为无效页，从而降低回收块中有效页比例，提高垃圾回收效率［19］。在FaGC+算法的基础上，本文重新设计数据热度计算公式，根据回收块中有效页更新间隔判断热度，相关计算公式如式（4）、式（5）所示：

其中：Di为对应物理块被分配使用时的页序号；ui为对应物理块中有效页比例；Slast为回收块中有效页数据上一次更新时的页序号。式（4）计算得到的AAI表示垃圾回收时闪存中有效页数据全局平均更新间隔，式（5）计算得到的UUI表示回收块中有效页当前更新间隔。当回收块中有效页当前更新间隔UUI大于全局平均更新间隔AAI时，有效页数据定义为热数据，反之定义为冷数据。本文将冷热数据做了进一步划分，分别以AAI/2 和AAI×3/2 为界限，将数据依次划分为冷页、次冷页、次热页、热页4 种类型。

闪存系统在实际使用过程中，由于数据使用情况的不同，存在定期更新和不定期更新数据，即各数据前后更新间隔的变化幅度存在差异，本文将这种数据更新间隔变化幅度定义为数据更新稳定性。为进一步提升垃圾回收效率，本文在根据回收块中有效页更新间隔进行热度划分的同时，判断有效页中数据更新稳定性，将稳定更新数据和不稳定更新数据分块存储，相关计算公式如式（6）～式（8）所示：

其中：Sinit为有效页数据初次写入时的页序号；c为有效页数据更新次数；Iave为有效页数据平均更新间隔；Spred为利用平均更新间隔预测得到的当前更新序号值；DDF为当前实际序号与预测序号之间的绝对差值。当计算得到的DDF值大于Iave/2 时，说明该有效页当前更新间隔与其平均更新间隔差距过大，数据前后更新间隔幅度变化剧烈，处于不稳定更新状态，反之数据则为稳定更新状态。算法将稳定更新的数据按热度分块存储，使得块中数据拥有稳定且相近的更新间隔，从而进一步提高块中数据同步更新的概率以及垃圾回收效率。结合数据热度和更新稳定性进行有效页类型划分，结果如表1 所示，数据分离过程如算法3 所示。

表1 有效页类型划分Table 1 Type division of valid pages

算法3数据分离算法

2 实验结果与分析

2.1 实验环境

本文在Ubuntu20.04 平台上使用QEMU（Quick EMUlator）搭建基于Linux2.6 的嵌入式仿真系统［20］，并使用NANDsim 模拟NAND 闪存，在移植Yaffs2 文件系统后［21］编写程序进行测试。模拟出的NAND 闪存容量为64 MB，其中物理块的大小为128 KB，物理页的大小为2 KB。测试程序随机创建出大小为16～1 024 KB 的文件，创建文件的总和占NAND 总容量的90%，随后对其中15%的内容按齐夫分布进行更新操作［22-23］。本文选取GR、CB、CAT、FaGC、FaGC+这5 种算法与UIGC 算法进行对比测试。为了保证对比测试的公平进行，实验关闭Yaffs2 文件系统的缓存功能和后台垃圾回收，所有实验均在aggressive模式下完成。实验相关参数设定如表2 所示。

表2 实验参数Table 2 Experimental parameters

2.2 结果分析

本文主要从块擦除操作总数、页拷贝操作总数、块擦除次数标准差等方面分析比较垃圾回收算法性能，根据擦除和拷贝操作总数考察算法垃圾回收效率，根据块擦除次数标准差考察算法磨损均衡能力。

图2 和图3 分别对比使用不同算法进行测试时闪存中块擦除次数和页拷贝次数。从中可以看出：UIGC 算法在垃圾回收时实现了更低的块擦除次数和页拷贝次数；CAT 算法在GR、CB 算法的基础上进行数据冷热分离，磨损均衡效果有了较大提升，由于回收块选择部分改进不大，且仅以擦除次数来区分数据冷热，不够准确，造成了一些额外的擦除和拷贝操作，因此，其在提升磨损均衡效果的同时反而增加了擦除和拷贝次数；FaGC 算法改进了数据分离算法，以数据更新频率区分数据的冷热，进一步提升了磨损均衡效果，降低了擦除和拷贝操作次数；FaGC+算法在FaGC 算法的基础上提出页序号的概念，同时改进回收块选择策略，提高了回收块选择和数据冷热划分的准确性；UIGC 算法在选取回收块时，考虑块中无效页年龄累计和以及块中有效页比例，选取无效页多且年龄和大的块作为回收块，有效减少了处理回收块时造成的页拷贝操作次数，UIGC 算法从全局角度对回收块中有效页数据进行热度划分，避免了自定义热度参数导致的局限性，此外，该算法提出数据更新稳定性的概念，根据数据热度和更新稳定性将回收块中有效页数据分块存储，提高同一块中数据的同步更新概率，配合分散度判断，大幅降低了垃圾回收程序被触发的次数，有效减少了块擦除次数，进一步提高了算法的垃圾回收效率。

图2 各算法块擦除次数对比Fig.2 Comparison of block erasure times of each algorithm

图3 各算法页拷贝次数对比Fig.3 Comparison of page copy times of each algorithm

图4 对比了使用不同算法进行测试时每个物理块的擦除次数分布情况，图5 显示了各块擦除次数标准差随着擦除次数的变化情况。从图4、图5 可以看出：UIGC 算法得到的各块擦除次数分布均匀，维持在一个较低水平，且随着擦除次数的增加，各块擦除次数标准差始终保持稳定，与FaGC+算法块擦除次数标准差变化曲线基本重合；UIGC 算法在动态回收块选择的基础上结合静态回收块选择策略，在有效提升垃圾回收效率的同时，仍具有和FaGC+算法相近的磨损均衡效果，即具有更优的垃圾回收性能。

图4 物理块擦除次数分布情况Fig.4 Distribution of erasure times of physical blocks

图5 各算法擦除次数标准差对比Fig.5 Comparison of standard deviation of erasure times of each algorithm

3 结束语

为了优化NAND 闪存在进行垃圾回收时的性能表现，本文提出一种基于数据更新间隔的垃圾回收算法UIGC。选择无效页多且存在时间长的块进行回收，判断回收块中有效页热度以及数据更新稳定性状态，将不同类型的有效页数据分块存储，同时以分散度作为回收块选择过程的触发条件，从而在有效提高垃圾回收效率的同时保持较高的磨损均衡能力。实验结果表明，UIGC 算法的垃圾回收效率以及磨损均衡效果优于GR、CB 等算法。但是，UIGC 算法在实现过程中引入了额外的内存空间来存储数据更新的页序号等信息，下一步考虑使用逻辑区间的方式减少额外存储的数据量，以在保证垃圾回收性能的前提下降低额外的内存空间消耗。