减轻读干扰的垃圾回收算法

赵乾瑞 冉全

收稿日期：2023-05-20

基金项目：武汉工程大学研究生创新基金（CX2021290）

DOI：10.19850/j.cnki.2096-4706.2024.07.018

摘  要：NAND闪存凭借许多特点让其在各种应用场景中得到广泛的应用，例如手机、平板电脑等，但是闪存也有两个受关注的特性：使用寿命和数据的可靠性。在闪存的使用过程中，读干扰对数据准确性的影响会随着时间的增长变大，因此，通过对读干扰造成的影响进行研究，提出了一种减轻读干扰的垃圾回收算法FRT-GC，该算法通过对每个闪存块的使用次数和使用频率进行统计计算，在合适的时机启动垃圾回收，最大限度地减轻读干扰造成的影响。实验验证该算法在减轻读干扰方面有很好的效果。

关键词：NAND闪存；垃圾回收；读干扰；FRT-GC

中图分类号：TP333；TP312  文献标识码：A  文章编号：2096-4706（2024）07-0081-05

A Garbage Collection Algorithm of Reducing Read Disturb

ZHAO Qianrui， RAN Quan

（Wuhan Institute of Technology， Wuhan  430205， China）

Abstract： NAND flash memory is widely used in various application scenarios due to its many characteristics， such as mobile phones， tablet computers and so on， but flash memory also has two characteristics of concern： service life and data reliability. In the using process of flash memory， the influence of read disturb on data accuracy will increase with time. Therefore， by studying the influence caused by read disturb， a garbage collection algorithm FRT-GC （Frequency and Read Times-Garbage Collection） that can reduce the influence caused by read disturb is proposed. This algorithm starts garbage collection at the right time by counting the usage times and frequency of each flash memory block， and minimizes the influence caused by read disturb. The experiments show that the algorithm has a good effect in reducing read disturb.

Keywords： NAND flash memory; garbage collection; read disturb; FRT-GC

0  引  言

闪存读干扰产生的原因是存储单元之间电荷的相互干扰，这导致读取到的数据发生错误，具体有两个主要原因：一是存储单元之间的距离非常相近，电荷可能会在相邻的单元之间泄露，从而导致读干扰；二是高速写入和擦除操作可能会引起存储单元之间的电荷迁移，产生读干扰。这种读干扰是不可避免的，详细原因解释如下。

如图1所示，当读取某个page时，需要对所有的WL的ControlGate上都施加一个Vpass电压，Vpass电压一般都大于其阈值电压Vth，保证所有的单元都可以导通。而对于要读取的page，需要在其ControlGate上施加一个读取电压Vread（或者叫参考电压Vref），然后通过BL上的电流检测来判断单元内的状态。为了保证所有的单元都导通，所以Vpass电压是比较大的，通过图1（b）可以看出，此时不被读取的页面状态有点像写数据时的状态，有的单元中电子会被吸入浮栅中，久而久之，浮栅中的电子越来越多，数据被读取时就会发生错误。

根据读干扰产生的原因，各个学者研究出了以下优化方案。

许毅等人提出了一种针对MLC存储介质的缓解读干扰的方案[1]，该方法将每个存储单元的字线Wordline分为最低有效位（LSB）和最高有效位（MSB），并根据每个Wordline的编程程度设置三种状态，根据不同的状态设置不同的旁路电压。该方法有效地降低了读干扰的影响，间接增加了闪存设备的寿命，但是适用场景过于单一。

Jung等人通过实验分析得出，当相应的块被物理擦除，读干扰可以被纠正，因此他们提出将产生干扰的块擦除并迁移来消除读干扰产生的影响[2]。虽然通过实验得知该方法在减少读干扰产生的错误率方面有所提升，但是擦除迁移会导致长时间的延迟，进而影响性能。

Huang等人提出了感知读干扰的写调度和数据重新分配算法[3]，该算法通过参考块的P/E周期和对块的累计读取计数的因素来估计由读干扰引起的块读取错误率，再分析哪些数据的读取频繁，将频繁的数据放入读干扰错误率低的区域，不频繁的数据放入读干扰错误率较高的区域。该算法一定程度上优化了读干扰问题，但是通过构建模型分析块的错误率，具有一定的随机性，不太稳定。

Wu等人提出了具有原位重新编程的自适应单元位密度的闪存读干扰管理方案[4]，该方案通过识别热数据，并将热数据迁移到低密度块中，从而减少读取刷新的需要。为了减少用于读取刷新的数据迁移量，设计了就地重新编程算法。该方案减少了读干扰的影响，但是就地重新编程的算法会导致额外的磨损，间接影响了闪存的寿命。

1  减轻读干扰的垃圾回收算法

1.1  设计思路

读干扰产生的原因无非是阈值电压的改变导致读取错误，但是当重新对块进行擦除操作后，这种错误就会消失，但是在擦除操作之前，块中的有效页需要进行迁移，因此想要减轻读干扰有两个步骤：

1）将目标块中的有效页面进行迁移。

2）对目标块进行擦除操作，以消除累计的读计数。

上面的两步操作，等同于一次垃圾回收操作。换句话说，当目标块的读计数达到指定的阈值，那么就可以对该块进行垃圾回收。

对于垃圾回收的启动时机，由于闪存的擦除次数越多氧化层绝缘性就越差，读干扰的现象就会越严重，因此FRT-GC（Frequency and Read Times-Garbage Collection）算法需要设定指定的阈值，当大于指定阈值时启动垃圾回收，这样可以很好地考虑到每个块的磨损情况。

对于垃圾回收过程中回收块的选择，需要在FRT-GC算法中设计方法来获取每个块的访问热度，根据热度判断每个块的读取频率，以此获得受读干扰的影响程度，据此进行回收块的选择。

1.2  详细设计

1.2.1  算法启动策略

总结前文算法的缺点，本章中的垃圾回收算法FRT-GC的启动时机，也就是读干扰产生的影响的临界时间，根据读取次数和读取频率两个方面进行判别，从而决定何时启动垃圾回收。

如图2所示，FRT-GC算法在进行一次读取操作后就进行判断，判断总读取次数（Total Read Times， TRT）是否大于指定阈值，如果没有，则将被读取块的读取次数（Block Read Times， BRT）和频率（Block Read Frequence， BRF）进行自增。如果大于指定阈值，则根据下文的规则选取回收块，进行一次垃圾回收，并将回收块的BRT和TRT进行归0操作。

1.2.2  算法回收块的选择

FRT-GC算法中回收块的选择主要考虑BRF和BRT两个方面。如果一个块的BRF高，则说明该块之后被读的次数会很多，那么之后产生的读干扰也会非常严重，需要进行预防，所以可以选择该块进行回收，继而消除读干扰的影响；如果一个块的BRT高，说明该块之前被读了很多次，所以之后如果再去读，极有可能会发生数据错误，所以也可以选择该块进行回收。

该步骤通过在映射表中添加统计项来实现。在映射表中添加读取次数和被读取的时间，通过记录最近5次被读取的时间计算被读取的频率。由于擦除是以块为单位，所以需要计算平均BRF，如式（1）所示：

（1）

其中VC为有效页的数量（Vaild Count），PRF为有效页的读取频率（Page Read Frequence）。

通过算式再次计算闪存设备的平均读取频率，如式（2）所示：

（2）

其中TVC为总的有效页的数量（Total Vaild Count），FRF为闪存读频率（Flash Read Frequence）。计算出各个块的平均读频率和闪存的平均读频率，可以得出每个块的平均读取频率在闪存中的占比。式（3）为回收块的选择方式：

（3）

其中CF为回收因子（Collection Factor），通过判断每个块的回收因子的值来决定是否进行回收，选择CF值大的进行回收。FRT为闪存读次数（Flash Read Times）。

通过算式可以得出，如果一个块的CF大，那么可能是BRT大，也可能是AvgBRF大，还有可能为两者都大，具体情况有：

1）如果是BRT大，代表其被读次数多，说明其在之前已经被读了很多次，这就代表如果再读，读出来的数据很有可能发生错误，此时就需要垃圾回收进行有效页的迁移和无效页的擦除，如图3所示，如果在t时刻需要执行垃圾回收，此时块A和块B的读次数相同，但是在之前块A的读次数明显多余块B，所以选择块A作为回收块。

2）如果是AvgBRF大，则代表其最近的访问频率有所上升，根据数据访问的时间局部性来看，其之后有极大的可能被频繁访问，因此之后该块内的数据在被读取时，也很有可能发生错误，如图4所示，t时刻之前，虽然块A的读取次数多，但是最近几次块B的读取更为频繁，且之后还会被频繁访问，可能会对数据的读取产生影响，因此选择块B做回收块。

图4  AvgBRF影响较大示意图

3）如果BRT和AvgBRF都比较大，那么说明其之前被读次数很高，之后也将会被频繁读取，这样如果之后再被读取，那么被读干扰影响，读取错误数据的概率也非常高。

2  实验结果分析

本实验选用FlashSim [5]作为垃圾回收算法的测试平台，由于FlashSim是装在DiskSim下的，所以需要先安装DiskSim。FlashSim的核心部分包括模拟器、文件系统驱动和用户空间工具，模拟器是FlashSim的核心，它提供了对读、写、擦除等操作的模拟，并且文件系统驱动提供了对各种文件系统的支持，包括ext4 [6]、FAT32 [7]、YaFFS [8]等。

2.1  实验实现方式说明

安装DiskSim后，DiskSim中文件如图5所示，其中，src文件夹中存放的是可执行文件，如图6所示，test.release文件为数据集文件，其余则为编译和配置文件。将FlashSim下载好后，更名为src覆盖原有的src文件。

在Disksim-3.0文件中的Parfile文件，用来设置仿真的闪存设备的参数：FTL算法、Block数量、SSD接口、总线、控制器参数，等等。

在FlashSim中实现自己的映射算法方式：DiskSim-3.0/src文件夹下的.c文件中为FTL算法的具体实现方式，.h文件为FTL算法所声明的函数库的头文件，这些头文件在disksim_iodriver.c，ssd_interface，c，disksim_main.c和disksim_simpleflash.c中以选择的形式，供disksim执行模拟仿真。

在执行文件runvalid中可以输入多条命令，如图7所示。运行命令./runvalid，运行结果如图8所示。运行结果新增文件如图9所示。

在测试结束后，会生成.outv文件，该文件是测试数据结果文件，通过在结果文件中寻找想要的数据，并通过Excel来进行所需图表的生成。

2.2  参数配置

NAND闪存参数配置如表1所示。

2.3  性能比较

本实验对比的算法为传统读干扰算法Refresh [9]，与RDD [10]算法，Referesh算法是通过固定阈值来进行数据迁移来以免有效数据受到读干扰的影响。RDD算法在Refresh的基础上，通过实时检测来判断数据的干扰情况，从而减轻读干扰的影响。

本实验通过以下几个方面进行FRT-GC算法与其他算法的性能评测：

1）平均响应时间。平均响应时间是指从上层文件系统发送请求到返回结果的平均时间，该标准可以直观判断算法对闪存效率的影响。

2）数据错误率。数据错误率主要是通过判断读取出错数据的比特占总数据的比例。该标准可以判断出算法对减轻读干扰的效果情况，可以直观的反应算法的可靠性。

3）数据迁移量。在减轻读干扰的过程中，需要对有效数据进行数据迁移，而对数据读干扰的情况判断极大的影响这数据迁移量，所以该标准可以反映算法的性能情况。

2.3.1  平均响应时间

图10为实验结果，为了使数据便于观察，此处将数据使用最大最小归一化方式进行了处理，使所有数据都趋于区间0和1之间，从图中可以看出，Refresh算法的响应时间较长，主要是因为其通过固定阈值去判断干扰情况，判断方式过于固定和单一，因此会导致很多不必要的数据迁移。通过实验可知FRT-GC算法对比Refresh算法和RDD算法时，分别提升了6.1%和0.7%，所以可以看出FRT-GC算法在平均响应时间方面优于其余两个算法。

2.3.2  数据错误率

如图11所示，该数据也进行了归一化处理，FRT-GC算法在数据错误率方面优于其他算法。相比Refresh和RDD算法，错误率降低了7%和0.7%，主要是因为FRT-GC算法在进行垃圾回收的过程中，在回收块的选择方面，选择之前受读干扰影响较大或之后会受读干扰影响的块，所以在错误率方面低于其他两个算法。

2.3.3  数据迁移量

如图12所示，通过实验可以看出FRT-GC在数据迁移量方面优于Refresh算法和RDD算法。相比其他两个算法，FRT-GC算法在数据迁移量方面减少了54.7%和17.7%，主要是因为两个算法通过固定阈值和固定间隔去进行数据迁移，导致一些未受读干扰影响的数据被迁移，产生不必要的迁移操作。

3  结  论

本文提出了一种减轻读干扰的垃圾回收算法FRT-GC，该算法通过计算每个页的读频率和读次数，通过近几次的读频率可以看出该页最近将要被访问的概率，通过读次数可以判断该页之前被读的次数，通过这两项来判断周围页的读干扰情况来进行垃圾回收。该算法在减轻读干扰影响以及提高闪存性能方面都有着不错的性能。

参考文献：

[1] 许毅，姚兰，郑春阳.一种缓解MLC闪存读干扰问题的方法：201711225482.0 [P].2017-11-29.

[2] JUNG M，KANDEMIR M. Revisiting Widely Held SSD Expectations and Rethinking System-level Implications [C]//Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems.Pittsburgh：ACM，2013：203-216.

[3] HUANG B W，LIAO J W，LI J，et al. Read Disturb-aware Write Scheduling and Data Reallocation in SSDs [J].IEICE Electronics Express，2020，17（8）：20200015.

[4] WU T C，MA Y P，CHANG L P. Flash Read Disturb Management Using Adaptive Cell Bit-density with In-place Reprogramming [C]//2018 Design， Automation & Test in Europe Conference & Exhibition（DATE）.Dresden：IEEE，2018：325-330.

[5] KIM Y，TAURAS B，GUPTA A，et al. Flashsim： A Simulator for NAND Flash-based Solid-state Drives [C]//2009 First International Conference on Advances in System Simulation.Porto：IEEE，2009：125-131.

[6] MATHUR A，CAO M M，BHATTACHARYA S，et al. The New Ext4 Filesystem： Current Status and Future Plans [C]//Proceedings of the Linux symposium.Ottawa：[S.I]，2007，2：21-33.

[7] BHAT W A，QUADRI S M K. Review of FAT Data Structure of FAT32 file system [J].Oriental Journal of Computer Science & Technology，2010，3（1）：161-164.

[8] MANNING C. How Yaffs Works [EB/OL].（2012-06-02）.https：//yaffs.net/documents/how-yaffs-works.

[9] FROST H H，CAMP C J，FISHER T J，et al. Efficient reduction of Read Disturb Errors in NAND FLASH Memory：US12879966 [P].2010-09-10.

[10] 翁阳.固态盘内读干扰感知的智能管理优化方法研究 [D].武汉：华中科技大学，2020.

作者简介：赵乾瑞（1998—），男，汉族，山西运城人，硕士在读，研究方向：嵌入式、存储性能、闪存数据库。