基于块更新序号的NAND闪存垃圾回收算法

陈 琳， 严 华

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

伴随发展迅猛的信息化技术，存储数据所需介质在容量、种类等方面不断增长。与传统机械硬盘相比，NAND闪存具有体积小、无噪声、功耗低、访问速度快、防震抗摔性好等诸多优点，因此得到广泛应用，逐渐成为主要的存储介质[1-2]。NAND闪存由一定数量的物理块(block)构成，而每个物理块又由一定数量的物理页(page)构成。闪存的读取操作与写入操作以页为单位进行，但擦除操作只能在包含了多个页的块上来完成[3]。当系统请求页重写时，NAND闪存不能在同一物理页上进行“本地更新”，通常采用“异地更新”策略以满足写前擦除的特性，即新数据不能直接在旧页上改动，而需写入另一空闲物理页，并将旧页标记为无效页[4-5]。当无效页积累到一定数量时，就形成了无用的垃圾(garbage)。为充分利用闪存的存储空间，需要选择回收块(victim block)进行垃圾回收将无效页擦除。但由于NAND闪存擦除的基本单位是块，因此在擦除前需要将回收块中的全部有效页复制到另一空闲块。对闪存而言，擦除操作的速度比读写操作慢很多，且需要更大的功耗[6]。此外，闪存可支持的每个块的擦除次数具有上限。因此，在考虑减少物理块的擦除次数与回收代价的同时，提高闪存磨损均衡程度，是提高闪存读写性能并延长使用寿命的研究重点。

为了提升NAND闪存垃圾回收的效率与性能，中外学者们提出了诸多垃圾回收算法，这些算法的管理粒度主要分为块、页。

GR(GReedy)算法[7]、CB(cost-benefit)算法[8]、CAT(cost-age-time)算法[9]、WOGC(write order-based garbage collection)算法[10]是经典的以块为管理粒度的垃圾回收算法。GR算法将有效页最少的块选为回收块，以降低回收代价，但未考虑块的磨损均衡度。CB算法在考虑块中无效页占比的同时将物理块的年龄纳入考量，以获得更好的磨损均衡。CAT算法在CB算法的基础上考虑了物理块的擦除次数，在读写性能和磨损均衡取得了较好的平衡。但CAT仍存在不足，一是CAT算法需利用绝对时间来计算年龄，设备断电后可能导致年龄信息丢失；二是其年龄计算对时间敏感，针对不同工作负载需要试探性地确定计算方法[10]；WOGC算法用写序号代替CAT算法中的年龄，以避免上述不足。

为了进一步提高算法性能，需要更准确地计算数据热度，因此基于页的垃圾回收算法的提出，如FaGC(file-aware garbage collection)算法[11]证明以逻辑页为管理粒度能大幅提升算法性能。FaGC算法基于文件结构，对逻辑页热度进行准确定义，并将热数据存储到擦除次数最少的块中，而将冷数据存储到擦除次数最多的块中，有效实现数据的冷热分离，在磨损均衡方面增加考虑了最冷块的回收。该算法在性能方面获得了很大提升，但为了保存逻辑页热度需额外占用大量内存空间。为减少内存消耗，LRGC(logic region-based garbage collection)算法[12]， LRGC+(logic region-based garbage collection plus)算法[13]。LRGC与LRGC+算法考虑了访问的空间局部性，将连续逻辑地址空间划分为同一个热度区间，用逻辑区间热度替代逻辑页热度，以减少额外的内存消耗。与FaGC算法相比，这两种算法在减少内存消耗的同时，进一步提升了垃圾回收的性能，但在逻辑区间较大时，冷页与热页可能被强行划分在一个区间中，造成数据热度判断失误。另外，FaGC、LRGC与LRGC+算法的热度计算仍然基于逻辑页或逻辑区间前后两次更新操作的时间间隔，因此存在时间敏感的局限性，以及在实际使用中可能存在的无操作休眠时间会对热度计算造成影响。

针对当前垃圾回收算法占用大量内存与性能不足的问题，提出一种基于块更新序号的垃圾回收算法，即UsnGC(update sequence number based garbage collection)算法。该算法将管理粒度定位到块，基于块更新顺序对块进行热度计算，以对有效数据进行冷热分离；同时，给出了新的回收块选择策略以兼顾磨损均衡效果和减少垃圾回收代价。

1 UsnGC算法

1.1 算法概述

考虑到NAND闪存擦除操作的基本单位为块，且基于页的垃圾回收算法势必带来大量内存消耗，UsnGC算法将管理粒度重新定位到块，提出以块更新序号来计算块更新周期和系统平均更新周期，并结合系统平均更新周期来计算块的热度值。根据分散度来触发垃圾回收，同时采用混合回收策略选出回收块，然后将回收块中的有效页进行有效的冷热分离，最终提升垃圾回收效率和磨损均衡效果。

为了区分新旧数据页的写操作，我们把新数据的写操作定义为新写操作，把旧数据的写操作定义为更新操作，二者统称为写操作。同时，为避免重复描述参数定义，列出本文中主要使用的参数及其定义，如表1所示。

表1 主要使用的参数及其定义

1.2 更新序号

本文中提出一个称为更新序号(update sequence number, USN)的计数器来记录块的更新情况。USN为全局变量。同时，设置一张单独的块信息表来存储每个物理块的当前更新序号USNi(i=1, 2,…,Nblock)。如图1所示为块更新序号确定算法示例。

图1 块更新序号确定算法示例

“异地更新”策略将旧数据所在的页(称为旧页)标记为无效页，将新数据写入另一空闲物理页，因此USN会随着数据写入块(即写操作)而递增。最初，USN被设置为0，每当NAND闪存的块完成1次写操作时，该变量加1。若该写操作为更新操作，则在写操作完成后，将新的全局USN值赋值给旧页所在块的USNi。同时，若写入块为首次写入，新的全局USN值同样赋值给写入块的USNi。需要强调的是，当连续的页写操作是对同一个块的更新操作时，USN仅递增一次。如图1所示，假设已存在7个数据页，当前全局USN为10，块1、2、3的当前USNi分别为3、7、8，即USN1=3，USN2=7，USN3=8。依次更新页2、3、5、4。按照上述算法，由于页2、3连续更新且源自同一个块，Step1完成后USN仅增加1后为11，USN1则由3变为11。Step2先更新页5，那么USN加1后为12，则USN2也为12；接着更新页4，USN加1后为13，然后USN1为13。依次更新页2、3、5、4后的全局USN和块1、2和3的数值如图1中Step3所示。

1.3 块热度定义

UsnGC算法以块为单位计算热度，当且仅当物理块进行1次或连续多次更新操作时才触发1次块热度计算。为避免块内少数页更新造成整个块热度的骤升而导致块内大部分页的热度误判，考虑用上一次块热度值与当前块更新周期共同决定当前块的热度。定义全局变量n、S，n记录热度计算次数，初始值为0，每次触发热度计算后递增1；S记录更新周期的累计和。假设对物理块i(i=1, 2,…,Nblock)的更新引起了第n次热度计算，则块热度的计算步骤如下。

首先，计算当前物理块i的更新周期Ti，Ti为临时变量，在完成本次热度计算后即可释放，计算公式为

(1)

然后，计算更新周期的累计和S，以及系统的平均更新周期Tavg，计算公式为

S→S+Ti

(2)

(3)

最后，为了准确计算块的当前热度以更好地进行数据冷热分离，将式(3)得出的平均更新周期Tavg作为分段计算依据，再结合块的上一次热度计算出块的当前热度。基于式(1)～式(3)的物理块热度分段计算函数为

(4)

式(4)中：Ht+1和Ht分别表示块的当前热度值、块的上一次热度值。把块热度值限定在[Hmin,Hmax]的范围内。一般地，Hmin取1，Hmax取每个物理块所包含页数的4倍；c是一个常量，一般取1。

1.4 回收块选择策略

NAND闪存系统进行垃圾回收时，为了提高回收效率，要考虑选中的回收块有效页少，以减少垃圾回收引起的拷贝次数。由于NAND闪存的块擦除次数具有上限，磨损均衡度影响其使用寿命，因此在回收块选择策略中，采取包含了常规回收策略与最冷块回收策略的混合策略。

(1)常规回收策略采用一种综合考虑回收效率和磨损均衡的回收代价函数，即

(5)

式(5)中：u表示一个物理块中有效页的占比；εi和εmin分别表示当前物理块的已擦除次数、当前系统中物理块的最小擦除次数。块的有效页占比越小、擦除次数越少、最近一次更新周期越小，则C值越小。显然，UsnGC算法选择C值最小的块为回收块。该回收代价函数可很好地避免在只考虑有效页占比与擦除次数时，闪存中出现较多最冷块，最冷块的有效页比例高甚至全为有效页且最冷块长时间未更新，这些最冷块的存在会导致磨损均衡较差。

(2)最冷块回收策略用于进一步减少最冷块的存在并改善磨损均衡效果，该策略选择擦除次数最少的块为回收块。

(3)混合策略设置动态变化的阈值Te控制在常规回收策略与最冷块回收策略之间的合理切换，其定义为

(6)

(7)

式中：Twl表示控制混合策略切换的初始阈值；Nvalid表示全为有效页或只有一页为无效页的块数；δ为Nvalid在系统中所占比例，在垃圾回收过程结束时对δ进行更新；εmax和εmin分别表示当前系统中物理块的最大、最小擦除次数。在触发垃圾回收后，计算系统当前擦除次数与上一次启动最冷块回收策略时系统擦除次数的差值，若差值大于阈值Te，则启动最冷块回收策略，记录本次启动的系统擦除次数并重新计算Te；否则，采用常规回收策略进行回收块的选择。

1.5 垃圾回收的启动时机

为选择合适的时机来进行垃圾回收，以避免不必要的回收操作，引入分散度[3]的概念为

(8)

式(8)中：Nf表示当前所有物理块的空闲页总数目；Nb表示当前NAND闪存中的空闲物理块数目；Np表示每个物理块上包含的物理页数目。分散度越高，表明当前系统中空闲块越少且空闲页的分布越分散，启动垃圾回收带来的效益才越大。选取适当阈值Fth，当Fsc达到该阈值时才启动垃圾回收，可减少垃圾回收次数。

1.6 数据冷热分离

由于NAND闪存的“异地更新”策略，为了减少擦除次数以及垃圾回收过程中对回收块中有效页的拷贝操作，需对数据进行冷热分离。恰当的冷热分离后，同一个物理块上的数据拥有相似的热度值即相近的更新频率，一般情况下这些数据有更大的概率同时变为无效，由此有更多的无效页、更少的有效页。UsnGC算法将有效数据分为热数据、次热数据、次冷数据和冷数据四类，分别存储到不同的空闲块中，以提高回收效率。具体的数据冷热分离步骤如下。

(1)根据有效页数据所在物理块编号，结合式(1)～式(4)计算出该物理块热度Ht，即为该有效页热度。

(2)若Ht>3Hmax/4，则有效页为热数据页，数据迁移目标为擦除次数最少的空闲块。

(3)若Hmax/2

(4)若Hmax/4

(5)若Ht≤Hmax/4，则有效页为冷数据页，数据迁移目标为擦除次数最多的空闲块。

2 实验环境

对于操作系统框架中的NAND闪存管理体系，目前主要可分为以下两种类型：一是基于闪存专用文件系统(图2)，如JFFS、YAFFS；二是基于闪存转换层(flash translation layer, FTL)。

图2 基于专用文件系统的NAND闪存系统结构

由于闪存专用文件系统对闪存存储特性更具针对性，相关算法能直接进行地址映射、垃圾回收、磨损均衡的管理，比FTL文件管理系统更高效可靠，因此本文选择在VMware和Ubuntu14.0的环境下，基于Linux和QEMU搭建嵌入式仿真平台，NAND闪存借助NANDSim模拟，并通过对文件系统YAFFS2的移植以进行闪存管理。

如表2所示实验对象选取存储容量为64 MB的NAND闪存，其共有512个物理块，每个物理块由64个物理页组成，每页的容量为2 048 B。测试文件由测试程序随机创建，单个文件的大小在16～1 024 KB，测试文件总体对NAND闪存存储空间的占用率为90%，完成测试文件创建后，对其中15%的数据按照齐夫分布[3]进行更新。为了对不同算法的性能进行公平客观的比较，取消后台垃圾回收并关闭缓存功能，且YAFFS2文件系统的垃圾回收都采用aggressive模式。仿真实验中各项参数如表2所示。

表2 实验参数设定值

3 实验结果与分析

选取GR、CB、CAT、FaGC、LRGC和LRGC+算法为本文提出UsnGC算法的实验对比算法，对比指标包括垃圾回收效率与磨损均衡效果两个方面。垃圾回收效率包括NAND闪存物理块总的擦除次数、总的拷贝次数，磨损均衡效果包括系统中所有物理块擦除次数的最大差值、物理块擦除次数标准差。其中，擦除次数与拷贝次数越少，表明垃圾回收效率越高；物理块擦除次数的最大差值与擦除次数标准差越小，表明磨损均衡效果越好。

LRGC和LRGC+算法的逻辑区间长度记作M，由于UsnGC算法的管理粒度为块，可类比于M=64，参照图3、图4中M=64的情况可知，UsnGC算法在总擦除次数、总拷贝次数两个指标下的表现明显好于对比的6种算法。LRGC和LRGC+算法的总擦除次数与总拷贝次数随着M的取值增大而增大，这是由于逻辑区间增大后，极有可能将更新频率不同的逻辑页强行划分为同一热度，导致冷热分离不准确。UsnGC算法考虑到NAND闪存特性，以物理块管理，随着更新的进行，不同更新频率的页将逐渐聚集到相近频率的块上。即使在LRGC和LRGC+算法M=1的情况下，UsnGC算法在这两个指标上的性能表现依然更好。原因在于UsnGC算法采取动态阈值对块更新频率进行分段处理，并结合块的历史热度线性地计算当前热度，可根据系统使用情况动态调整热度计算，减少热度误判，优化冷热分离效果。同时，将有效数据分为冷、次冷、次热、热四类，进一步提高了冷热分离的精度，确保迁移进同一物理块的数据具有相近更新频率，减少回收块中有效页占比，从而降低回收代价。

图3 总的擦除次数对比

图4 总的拷贝次数对比

由于LRGC和LRGC+算法在M=1时，与UsnGC算法的擦除次数和拷贝次数接近，为了更合理比较不同算法的磨损均衡效果，对比LRGC和LRGC+算法时选取M=1。如图5和图6分别展示了各个算法的最大最小擦除次数的差值和物理块擦除次数的标准差。可以看出FaGC、LRGC、LRGC+和UsnGC算法的磨损均衡表现明显优于其他算法。这是因为GR、CB和CAT算法虽然已在回收块有效页数目少的标准下逐步增加对物理块年龄、物理块擦除次数的考量，但未进行冷热数据分离；FaGC算法在不触发最冷块回收策略时仍选取无效页最多的块为回收块；LRGC和LRGC+算法分别采用固定比重因子和动态权重来调节回收效率与磨损均衡的影响，但使用固定阈值计算有效页当前热度；而UsnGC算法的回收代价函数兼顾回收效率与磨损均衡，有效数据热度计算采取动态阈值分段处理且数据分类更加精确，因而在磨损均衡方面取得了更好的表现。

图5 擦除次数的最大差值对比

图6 擦除次数的标准差对比

3.1 内存消耗

如表2所示以存储容量为64 MB的NAND闪存为例，其物理块总数为512，每块有64个物理页，则物理页总数为512×64=32 768，存储每个信息需消耗4 B内存。GR算法不需要占据额外内存；CB算法消耗512×4 B=2 kB以存储每个物理块的年龄信息；CAT算法在CB基础上增加记录擦除次数，因此需消耗内存512×8 B=4 kB；FaGC、LRGC和LRGC+算法在记录每个块的擦除次数之外，还需构建热度表以存储每个逻辑页或每个逻辑区间的更新时间和热度值，因此需要消耗内存32 768×8 B+512×4 B=258 kB；UsnGC算法则只需在记录每个块的擦除次数之外，记录每个块的更新序号和热度值，因此仅消耗内存512×12 B=6 kB。

表3 内存消耗

4 结论

最初垃圾回收算法的管理粒度为块，无需占用大量内存，但算法性能有限。后续研究考虑基于页管理，以额外消耗内存为代价获得了性能的大幅提升。为了提升垃圾回收算法的性能，并减少NAND闪存内存的牺牲，提出了一种基于块更新序号的动态阈值数据冷热分离的垃圾回收算法UsnGC。UsnGC算法将管理粒度重新定位到块，基于块的更新序号定义有效数据热度的分段计算，提出一种兼顾回收效率与磨损均衡的回收代价函数，实现对数据的冷热分离。实验结果表明，与主流垃圾回收算法相比，UsnGC算法在大幅减少系统内存消耗的同时，在磨损均衡效果与垃圾回收效率两方面都取得了更好的表现。