0 引言

    NAND闪存具有体积小、抗震性能好、功耗低、无运行噪声、存取速度快、便携性好等特点，同时还具有远超传统机械硬盘的读写速度。因此，NAND闪存在各种电子产品中被广泛应用，如手机、U盘、固态硬盘^[1-5]。

    NAND闪存具有如下特点：

    (1)NAND闪存的读写操作以页(page)为单位，擦除操作以块(block)为单位。NAND闪存的写操作耗时远大于读操作，擦除操作耗时远大于写操作。

    (2)NAND闪存具有“写前擦除”的特点，即在进行重复写操作之前，必须先对写入的存储区进行擦除操作。

    (3)NAND闪存具有“异地更新”的特点。NAND闪存在对一个页进行数据更新时，需要先将要更新的数据写入新的空闲页，然后将原数据页标为无效页。

    (4)NAND闪存具有有限的块擦除次数。当某个块的擦除次数超过一定值时，该块将无法进行数据存储，成为“坏块”。

    NAND闪存中，会根据情况启动回收块选择策略，对满足回收块选择策略要求的块进行擦除操作，用以回收无效页所占的存储空间，得到足够的空闲空间来进行数据更新操作。

    在设计垃圾回收算法时应将减少垃圾回收代价、提高垃圾回收效率作为主要考虑点。同时，还要尽可能使每个物理块均衡地参与到擦除操作中，从而提升闪存磨损均衡程度、延长使用寿命。

    MICHAEL W等提出了GR(Greedy)算法^[6]。GR算法选择有效页最少的块进行回收。该算法的拷贝代价小，可回收较多的无效页空间。其特点是算法实现简单，回收效率较高。然而，当且仅当文件更新频率均匀时，磨损均衡效果较好。若数据更新频率相差较大，块之间的擦除次数差别较大，磨损均衡效果较差。

    KAWAGUCHI A等提出了CB(Cost-Benefit)算法^[7]。该算法采用age×(1-u)/2u公式进行回收块选择，其值最大的块将被选择成为回收块。其中u表示有效页在单个块中的比例，即物理块更新的时间差，age表示块的年龄。该算法考虑了块的年龄，因此获得比GR算法更好的效果。

    CHIANG M L等提出了CAT(Cost-Age-Times)算法^[8]。该算法采用age×(1-u)/(2u×n)公式进行回收块选择。其中u表示单个块中的有效页比例，age表示块的年龄，n表示块擦除次数。该算法在CB基础上考虑了块擦除次数，比CB具有更好的磨损均衡效果。

    Yan Hua等提出了FaGC(File-aware Garbage Collection)算法^[9]。该算法沿用GR算法的回收块选择策略，且根据逻辑页更新频率进行冷热数据的划分。数据冷热分离时，冷数据分配到擦除次数最多的块，而热数据则分配到擦除次数最少的块。

    石乐健等提出了一种基于物理块年龄和逻辑页热度的磨损均衡算法GCbAH(GC based Age and Hot)^[10]。该算法选择无效页年龄和最大的块作为回收块。同时，采用了与FaGC不同的热度计算公式来进行冷热数据的划分。在回收时，使用热数据回收策略回收热块，使用冷数据回收策略回收冷块。

    综上所述，相较于GR、CB、CAT等经典算法，FaGC和GCbAH考虑了逻辑页的冷热分离，进一步减少了垃圾回收代价，取得了更好的磨损均衡效果。但是，FaGC和GCbAH均采用固定的预设阈值来作为判定冷热数据的标准，并不能准确反映逻辑页的冷热程度。针对这个问题，本文提出了一种基于逻辑页平均更新频率的闪存垃圾回收算法AUFbGC(Average Update Frequency based Garbage Collection Algorithm)。该算法采用了一种新的热度计算公式，并采用逻辑页平均更新频率取代固定阈值作为冷热数据的判定依据，取得了更好的效果。

1 算法描述

1.1 算法原理

    NAND闪存进行垃圾回收时有如下操作：

    (1)根据回收块选择策略，进行回收块选择；

    (2)拷贝回收块中的有效数据至空闲块；

    (3)将被拷贝的有效数据所对应的原数据页标记为无效页；

    (4)对选中的回收块进行擦除操作；

    (5)回收块被擦除后成为空闲块。

    如图1所示，AUFbGC算法选择无效页年龄和最大的块作为回收块，根据热度计算公式和新的冷热判定依据，对回收块的有效数据进行冷热分离，并将有效数据存入擦除次数最少的空闲块中。

    和垃圾回收过程类似，AUFbGC算法在进行数据异地更新时也采用了冷热分离策略以获得更好的磨损均衡效果。

    AUFbGC算法主要包括三种策略：回收块选择策略、冷热数据分离策略和空闲块分配策略。

1.2 回收块选择策略

    AUFbGC算法在挑选回收块时有两种策略：采用无效页年龄和选择策略^[10-11]和自适应最冷块选择策略[9]。

其中，n为物理块中的无效页数目，agei为物理块中第i页变为无效页的时长。CwA即物理块中无效页的年龄和。CwA值最大的块将被选择成为回收块。采用年龄和进行选择可以兼顾无效页比例高的块和有少量无效页但长期未被回收的块，可获得更好的磨损均衡效果。

    同时，算法采用一种自适应策略对最冷块进行回收。自适应最冷块回收策略启动条件如下：

其中，T_wl是先前被设置好用于控制磨损均衡程度的阈值，e_max是所有块的最大擦除次数，e_min是所有块的最小擦除次数。当e_max和e_min之间的差值增大，T_erase值越小，冷块选择策略越容易被调用。若T_erase值小于零，则将T_erase置零。当一个块的擦除次数超过T_erase值时，最冷块回收策略被调用。该策略将选择有最小擦除次数的块作为回收块，以增加选中有较低更新频率的逻辑页的块的几率。如果有多个块具有最小擦除次数，则选择其中含有最少有效页的块作为回收块。在每次冷块回收策略被调用时，T_erase值会被计算和更新。

1.3 数据热度定义

    在热度判定上，FaGC以更新频率作为判定数据热度的标准，大于预先设置的特定阈值则为热数据，反之则为冷数据。

    GCbAH通过上一次判定的热度与热度调节因子相乘作为本次热度的计算标准。当逻辑页两次更新操作的时间差值大于特定值时，逻辑页热度被强制归零，因此不能细分部分数据的冷热程度。此外，GCbAH也采用预先设置的特定阈值作为判断冷热数据的标准。

    AUFbGC算法采用更新频率作为衡量冷热数据的指标^[12]，每个逻辑页的更新频率可通过如下公式进行计算。

其中，CurrentT是当前时间，IWT_i是该逻辑页i的初始写入时间。UPDC_i是逻辑页i的更新次数。因此，FREQ_i代表逻辑页i写操作的更新间隔。

    衡量冷热数据的标准如下：

其中，n是物理块的总数，CurrentT是当前时间，AllocT是编号为i的块被分配使用时的时间，u_i是该块中有效页的百分比。因此AverF_i代表有效页的平均更新频率。而每当回收块选择策略选中回收块后，平均更新频率AverFi会被立刻计算。

    当逻辑页的更新频率FREQ_i小于平均更新频率AverF_i，则该逻辑页包含的数据是为热数据；当逻辑页更新频率时间FREQ_i大于平均更新频率时间AverF_i，则为冷数据。

1.4 算法步骤

    使用无效页年龄和与自适应最冷块回收策略选择到回收块之后，根据回收块中有效页对应的热度对数据进行冷热分离，具体步骤如下：

    (1)根据逻辑页i的当前更新时间CurrentT和初始写入时间IWT_i及更新次数UPDC_i，根据式(3)得到该逻辑页的更新频率FREQ_i。

    (2)若逻辑页的更新频率FREQ_i小于平均更新频率AverF_i，则该逻辑页包含的数据为热数据；反之则为冷数据；

    (3)将数据根据热度进行冷热分离，具有相似热度的有效页将会被存入同一个物理块；

    (4)修改更新次数UPDC_i，用于下一次热度的计算和更新操作。

2 实验及分析

2.1 实验环境

    实验中使用VMware和Ubuntu 12.04平台，使用QEMU搭建嵌入式Linux仿真环境，使用NANDSim来模拟NAND闪存，基于NAND闪存专用文件系统YAFFS2进行测试。

    测试程序随机生成16 KB到1 024 KB大小的测试文件，所有测试文件总量占NAND闪存容量的90%。创建文件后，按照齐夫分布^[13]对其中15%的文件进行更新操作。

    实验中，NAND闪存容量被设置为64 MB，包含512个物理块，由512×64个页组成，其中每个页为2 048 B。为了公平对比不同算法，实验时YAFFS2文件系统的缓存功能被关闭，且都采用aggressive模式以完成垃圾回收。自适应最冷块回收策略采用的阈值和FaGC、GCbAH算法完全一样。

2.2 算法性能分析

    本文将AUFbGC算法与GR、CB、CAT、FaGC及GCbAH算法在垃圾回收代价和磨损均衡效果两个方面进行了比对。其中，垃圾回收代价主要考虑块总擦除次数、页总拷贝次数这两个指标，磨损均衡效果主要考虑块最大最小擦除次数差值、块擦除次数标准差这两个指标。同时，通过擦除次数分布图也可直观地观察不同算法的磨损均衡效果。

    从图2和图3中可以看出FaGC、GCbAH和AUFbGC算法获得了相对更小的块总擦除次数和页总拷贝次数。这是由于GR、CB、CAT算法中未考虑冷热数据分离，而FaGC、GCbAH和AUFbGC考虑了较为准确的基于逻辑页的冷热分离。在这三种算法当中，FaGC和GCbAH在数据热度进行定义时，均通过与事先设定的阈值进行比较，以划分冷热数据。AUFbGC算法有更准确的热度计算公式和判据，可将热度相近的逻辑页更加准确地放在同一个空闲块中。由于热度相近，这些逻辑页有更大可能同时被更新而变为无效，从而使该数据块有尽可能少的有效页，最终减少有效页拷贝次数和块擦除次数。

    在磨损均衡方面，从图4对比中不难看出，GR算法的物理块擦除次数最为分散，CB、CAT算法次之。FaGC、GCbAH和AUFbGC算法相对集中地分布在一个较小区域。其中，AUFbGC算法得到了较为良好的磨损均衡效果，擦除次数分布集中，且分布在较低值。

    不同算法的块最大最小擦除次数差值如图5所示，不同算法的擦除次数标准差如图6所示。从图5和图6中可以得出，FaGC、GCbAH和AUFbGC算法在磨损均衡方面相对GR、CB、CAT有更优异的表现。一方面，FaGC、GCbAH和AUFbGC算法获得了远小于GR、CB、CAT算法的块最大最小擦除次数差值；另一方面，这三种算法的擦除次数标准差呈收敛趋势。这是因为GR算法仅考虑回收有效页最少的物理块，未考虑磨损均衡。尽管CB算法考虑了物理块的年龄和有效页的比例，CAT算法在CB算法的基础上增添了块擦除次数的考量，但CB、CAT算法既没有考虑冷热数据分离，对最冷块的回收也不及时。FaGC、GCbAH和AUFbGC算法均采用了冷热数据分离和自适应最冷块回收策略，因此取得了更好的磨损均衡效果。同时，在这三种算法中，FaGC在回收块选择策略上沿用了GR算法，而GCbAH和AUFbGC算法的无效页年龄和回收块选择策略可兼顾对无效页比例高及无效页比例不高但是很长时间未被回收的物理块的回收，让回收块的选择更加均衡。相较于GCbAH算法，AUFbGC算法在定义数据热度时采用动态变化的平均更新频率取代固定阈值作为比较标准，对冷热数据的划分更准确，分类效果更好，且AUFbGC算法不断地将有效数据分配至擦除次数最少的块，以减少不同块擦除次数的差异。因此，AUFbGC算法的磨损均衡效果最好。

3 结论

    针对NAND闪存的特点，提出一种基于逻辑页平均更新频率的NAND闪存垃圾回收算法AUFbGC。该算法在FaGC和GCbAH算法基础之上，重新定义了数据热度计算公式和冷热判断依据。实验结果表明，相较于GR、CB、CAT、FaGC和GCbAH算法，AUFbGC算法在NAND闪存垃圾回收代价和磨损均衡方面均取得了更好的效果。

参考文献

[1] KIM J，KIM J M，NOH S H，et al.A space-efficient flash translation layer for CompactFlash systems[J].IEEE Transactions on Consumer Electronics，2002，48(2)：366-375.

[2] 白石，廖学良，胡事民.HFB:一种闪存上的块页混合缓存管理方法[J].清华大学学报(自然科学版)，2012(5)：688-693.

[3] CHEN R，LIN M.Energy-aware buffer management scheme for NAND and flash-based consumer electronics[J].IEEE Transactions on Consumer Electronics，2015，61(4)：484-490.

[4] JIN X，JUNG S，SONG Y H.Write-aware buffer management policy for performance and durability enhancement in NAND flash memory[J].IEEE Transactions on Consumer Electronics，2010，56(4)：2393-2399.

[5] LEE S，JUNG S，SONG Y H.An efficient use of PRAM for an enhancement in the performance and durability of NAND storage systems[J].IEEE Transactions on Consumer Electronics，2012，58(3)：825-833.

[6] WU M.The architecture of eNVy，a non-volatile, main memory storage system[C].The Workshop on Workstation Operating Systems.IEEE，1994：116-118.

[7] KAWAGUCHI A，NISHIOKA S，MOTODA H.A flash-memory based file system[C].USENIX 1995 Technical Conference Proceedings.USENIX Association，1994：13-13.

[8] CHIANG M L，CHANG R C.Cleaning policies in mobile computers using flash memory[J].Journal of Systems & Software，1999，48(3)：213-231.

[9] Yan Hua，Yao Qian.An efficient file-aware garbage collection algorithm for NAND Flash-based consumer[J].IEEE Transactions on Consumer Electronics，2014，60(4)：623-627.

[10] 石乐健，严华.考虑物理块年龄和逻辑页热度的NAND闪存磨损均衡算法[J].小型微型计算机系统，2015，36(11)：2618-2621.

[11] KWON O，KOH K，LEE J，et al.FeGC：an efficient garbage collection scheme for flash memory based storage systems[J].Journal of Systems & Software，2011，84(9)：1507-1523.

[12] HWANG S H，CHOI J H，KWAK J W.Migration cost sensitive garbage collection technique for non-volatile memory systems[J].IEICE Transactions on Information & Systems，2016，99(12)：3177-3180.

[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.

作者信息：

黄敏媛，严  华

(四川大学 电子信息学院，四川 成都610065)