0 引言

如今NAND Flash已经被广泛地运用在嵌入式系统中, 例如手机、平板电脑、数码相机等。闪存正逐渐代替硬盘, 成为一种流行的存储设备。它和传统硬盘相比有许多优点, 如体积小、功耗低、非易失、抗震性好、便携性好^[1-2]等。闪存由若干个物理块 (block) 组成, 每个块又包含若干个物理页 (page), 页是读和写的最小单位, 块是擦除操作的最小单位。读写操作具有严重的不对称性, 写操作的速度比读操作慢很多, 而擦除操作相对于读写操作来说相当慢且具有较大的功耗。闪存设备在写操作之前往往都要执行擦除操作, 即具有“写前擦除”^[3]的硬件特性。为了缓解写前擦除的延迟, 它采用“异地更新”(out-of-place update)^[4]策略, 即在执行更新操作时, 将更新后的数据写入其他位置, 并将原数据所在的物理页标记为无效页。当闪存中无效页越来越多时, 必须进行进行垃圾回收将无效页数据擦除, 来获取更多的空闲空间。闪存中每个块允许的擦写次数是有限的, 一般是10⁴~10⁵次。一旦某个块的擦除次数达到了上限, 数据存储将变得不可靠, 进而影响到整个闪存的读写性能和效率。

由于NAND闪存的特点, 垃圾回收算法需要考虑减少回收代价、获得更好的磨损均衡度^[5]以延长闪存的使用寿命, 同时电子产品的内存容量有限, 还需要考虑算法对系统的内存消耗。Wu等^[6]提出了GR (GReedy) 算法, 该算法选择无效页最多的块作为回收块, 以减少回收时对有效页的拷贝次数, 这样的回收块选择策略虽然回收效率较高, 但是并没有考虑块的磨损均衡度, 在存储大量冷数据的系统中磨损均衡效果比较差。Kawaguhi等^[7]提出了CB (Cost-Benefit) 回收算法, 该算法选择使age×(1-u)/2u值最大的块作为回收块。其中：u表示块中有效页的比例, 1-u表示块中无效页的比例, 2u表示块中有效页迁移代价；age表示物理块的年龄, 即当前物理块更新距离上一次更新的时间差。算法中物理块年龄的引入, 使得那些数据长期没有更新的物理块得到更多的擦除机会, 在一定程度上改善了磨损均衡效果。Chiang等^[8]提出了CAT (Cost-Age-Times) 算法, 该算法选择使age×(1-u)/(2u×n) 值最大的块作为回收块。其中：u表示块中有效页的比例；age表示块的物理年龄；n表示块的擦除次数。由于CAT算法在回收块时考虑了块的擦除次数, 并且通过块的擦除次数对冷热数据进行了分离, 磨损均衡效果要好于GR和CB。但CAT算法中以最近一次物理块的更新时间来反映物理块的年龄和以物理块的擦除次数来判定数据热不够准确, 冷热分离效果并不好。Yan等^[9]提出了FaGC算法, 该算法基于文件结构, 准确定义了逻辑页的热度, 并将冷热数据分开存储到不同擦除次数的块上, 有效地实现了冷热数据分离, 比以上三种传统的算法, 性能有了很大提升。但该算法也存在一定的局限性, 它采用了GR算法中的回收块选择策略, 并额外开辟了较大的内存空间来保存逻辑页的热度。虽然基于逻辑页识别冷热数据准确度较高, 但占用相对较大的内存空间, 这样的情况对于内存消耗严重的Flash存储器来说是不利的。

针对以上算法的不足, 本文提出了一种垃圾回收算法——LRGC (Logic Region based Garbage Collection) 算法。该算法的目标是减少系统的内存消耗, 减少垃圾回收过程中的开销以及提高块的磨损均衡度。算法将连续逻辑地址空间划分为同一个热度区间以减少系统的内存消耗; 通过代价函数来选择最优块回收, 并针对数据长期没有更新的物理块采用了一种特殊的回收机制, 改善了磨损均衡效果；同时, 根据空闲页的分布情况来判断启动垃圾回收的时机, 以防止过早地擦除块。

1 算法描述 1.1 基本原理

基于NAND闪存的存储系统结构可以分为文件系统层、闪存转换层 (Flash Translation Layer, FTL)、内存技术设备 (Memory Technology Device, MTD) 层和NAND闪存, 如图 1所示。

文件系统提供管理NAND闪存设备的方法。FTL是一种软件中间层, 用于将闪存模拟成为虚拟块设备, 从而能够在闪存上实现Ext3、FAT等块设备类文件系统，它主要包含了地址映射、垃圾回收、磨损均衡等几个方面的内容。MTD层将文件系统与底层Flash存储器进行了隔离, 并为上层文件系统提供一个统一的接口, 如读、写、擦除操作等。

NAND闪存具有基于日志结构的专有文件系统, 如JFFS、YAFFS文件系统, 它们都提供了逻辑地址到物理地址之间的映射。根据映射粒度的不同, 可以分为页级映射、块级映射和混合映射^[10]。虽然页级映射对数据热度的判断最为准确, 但是在内存容量有限的电子产品中, 页级映射并不适用。在本文中, 采用一种新的映射方式——逻辑区间映射, 和页级映射相比, 它可以在保证较为准确识别数据热度的前提下, 减少系统的内存消耗。

1.2 逻辑区间定义

考虑到在实际系统中, 如果一个逻辑地址最近被访问到, 则系统中有可能在将来一段时间里再次访问到该逻辑地址或其附近的地址^[11]。Kim等^[12]通过对智能手机的日常使用的读写操作跟踪研究发现, 对逻辑地址的访问具有空间局部性, 也就是说, 部分连续逻辑地址被频繁地访问, 而其余的逻辑地址访问次数很少。同时, 由于NAND闪存介质固有的特性, 写数据是以页为单位进行的, 这样每一次下发到介质的写都是页的整数倍, 因此, 如果某逻辑页为热数据, 那么该逻辑页所属的若干连续页的数据在很大概率上具有同一个热度, 因此可以定义此连续逻辑地址区间为一个热度区间。

定义1   在逻辑地址区间 (la1, la2) 中, 若每一个地址所存储的数据热度相同, 则为一个热度区间, 其长度为la2-la1。因此, 若热度区间的长度为M, 则将逻辑地址空间中每M个地址空间标记为一个热度区间, 每一个热度区间内的逻辑地址具有同一个热度区间编号。如果逻辑地址为la, 则它所在的热度区间编号H_n为:

$ {{H}_{n}}=[la/M] $

(1)

1.3 逻辑区间热度定义

理想的热数据识别方案是, 随着时间的动态变化能够反映各个时间点数据的冷热权值, 并且具有较小的内存消耗, 计算复杂度较低。为了准确计算回收块中有效数据页对应逻辑页的热度大小, 采用一种基于逻辑区间更新频率和上一次热度值来识别当前逻辑区间热度的方法。定义如下:

$ {{T}_{i+1}}=\left\{ \begin{align} & \ {{T}_{\min }}, \ \ \ \ \ {{T}_{i+1}}<{{T}_{\min }} \\ & \alpha *{{T}_{i}}, \ \ \ {{T}_{\min }}\le {{T}_{i+1}}\le {{T}_{\text{max}}} \\ & \ {{T}_{\max }}, \ \ \ {{T}_{i+1}}>{{T}_{\max }} \\ \end{align} \right. $

(2)

$ \alpha =\left\{ \begin{align} & 2-t/{{N}_{t}}, \ \ \ \ \ \ 0\le \left\lfloor t/{{N}_{t}} \right\rfloor <2 \\ & 0\, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left\lfloor t/{{N}_{t}} \right\rfloor \ge 2 \\ \end{align} \right. $

(3)

其中:T_i+1表示逻辑区间第i+1次更新时的热度值; T_i表示第i次更新时的热度值; α表示逻辑区间更新频率; t表示当前更新时间与上一次更新时间的时间间隔; T_max、T_min分别表示根据实际情况设定的热度最大值和最小值, 通常取10和0;N_t表示可自行调节的时间灵敏度参数, 目的是使更新操作的时间差值得到线性压缩, 降低时间对热度计算的影响, 一般取1 024。由于初次写入的数据没有历史热度, 无法通过公式计算出当前热度, 因此设定一个初始热度值T_h, 取热度最大值和最小值的中间值, 即刚写入的数据热度设为5。假定由式 (2)~(3) 计算所得逻辑区间的热度值为T：当T≥T_h时, 判定该逻辑区间所对应的有效页为热数据页；当T < T_h时, 判定该逻辑区间所对应的有效页为冷数据页。

1.4 回收块选择策略

系统在进行垃圾回收时, 首先需要考虑垃圾回收的效率, 为了获得较高的回收效率, 通常选择无效页最多的物理块进行回收。由于NAND闪存的擦除次数是有限的, 为了尽可能延长闪存的使用寿命, 在垃圾回收过程中还需要考虑闪存块的磨损均衡度。现有的垃圾回收策略主要要考虑了回收效率, 但在改善磨损均衡度方面还有所缺陷。为了兼顾回收效率和磨损均衡度, 采用了一种回收代价函数C:

$ C=(1-\lambda ).\frac{1-\mu }{1+\mu }+\lambda \frac{{{\varepsilon }_{\max }}-{{\varepsilon }_{i}}}{{{\varepsilon }_{\text{max}}}-{{\varepsilon }_{\min }}} $

(4)

其中: μ表示块内有效页所占的比例; ε_i表示该物理块的擦除次数; ε_max表示块的最大擦除次数; ε_min表示块的最小擦除次数; λ表示可配置参数。一般来说, 回收效率和磨损均衡是互相制约的, 当λ较小时, 主要考虑回收效率; 当λ较大时, 主要考虑磨损均衡。为了权衡两者之间所占的比重, 可根据实际情况取最优值。垃圾回收时, 选择使C值最大的块进行回收。当存储系统中物理块的磨损均衡度较好时, 回收效率优先, 侧重选择有效页较少的物理块回收, 从而减少回收时对有效页的拷贝次数, 提高了回收效率; 当磨损均衡较差时, 磨损效果优先, 侧重选择擦除次数较少的块进行回收, 使得擦除操作尽可能均匀地分布在每个闪存块上, 从而提高了磨损均衡度。

有些块中数据长时间没有更新, 有效页比例接近1, 通过式 (4) 难以选择到这样的块, 显然这是对于磨损均衡的改善是不利的。为此采用了另一种回收机制, 定义如下:

$ {{S}_{e}}=\left\{ \begin{align} & {{S}_{th}}-\varepsilon, \ \ \ \ \ \ \ \ \varepsilon \le {{S}_{th}} \\ & 0, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \varepsilon >{{S}_{th}} \\ \end{align} \right. $

(5)

$ \varepsilon ={{\varepsilon }_{\max }}-{{\varepsilon }_{\min }} $

(6)

其中:S_th表示控制磨损均衡度的阈值; ε表示最大擦除次数和最小擦除次数的差值。当利用式 (2)~(3) 回收物理块的回收次数大于S_e时, 启用该回收机制, 即对最冷数据块进行一次回收。每次回收完成后, 按照式 (5)~(6) 再次更新S_e的值, 以供下次回收时使用。

一般的垃圾回收算法中, 是以空闲块的数目来确定垃圾回收的时机, 即当闪存中的空闲块数目小于保留块数时, 启动急迫模式的垃圾回收, 此种模式下的触发条件并不能准确地确定垃圾回收的时机。为了避免不必要的垃圾回收操作, 减少垃圾回收的次数, 提高垃圾回收的效率, LRGC算法通过空块中的空闲页数与闪存中总的空闲页数的比值来判断是否要启动垃圾回收操作, 具体公式定义如下:

$ SC=\left( {{B}_{\text{f}}}\cdot {{N}_{\text{p}}} \right)/{{p}_{\text{f}}} $

(7)

其中:B_f表示闪存中空块的数目; N_p表示每个块所含的页数; P_f表示所有空闲页的数目。SC的值越小, 说明空白页在闪存块中分布越分散, 系统中空闲块越少。通常情况下, 当SC的值接近10%时, 空闲页数量已经很少, 这时急需启动垃圾回收, 因而可设定一个阈值T_SC=10%。采用LRGC算法的整个垃圾回收过程具体如下:

1) 当满足SC≤T_SC时, 启动垃圾回收;

2) 根据式 (4) 计算, 选择使回收代价C值最大的块作为回收块;

3) 根据式 (1) 确定逻辑区间编号, 通过式 (2)~(3) 计算逻辑区间的热度, 并判断该逻辑区间内所对应的有效页冷热情况;

4) 将步骤3) 中判断的热数据拷贝到擦除次数最少的块上, 冷数据拷贝到擦除次数最大的块上;

5) 当按照步骤2) 回收物理块的次数大于S_e时, 对最冷块进行一次回收。

2 实验与分析 2.1 实验环境及实验参数

使用基于Linux 2.6和QEMU的嵌入式开发仿真平台, 并移植YAFFS2文件系统, 使用QEMU模拟ARM处理器, 使用NANDSim模拟NAND闪存, 最后编写测试程序进行测试。测试程序创建创建大小在16 KB~1 024 KB之间的文件, 文件大小总和占NAND闪存容量的90%。文件创建完毕后, 对15%的数据按照齐夫分布^[13]进行更新操作。使用NANDSim模拟出NAND闪存页的大小为2 KB, 块的大小为128 KB, 总容量为64 MB。为了公平比较不同算法的性能, 实验中关闭了YAFFS2文件系统的缓存功能以及后台垃圾回收, 并且都使用aggressive模式。仿真实验中各项参数如表 1所示。

2.2 性能比较

算法性能比较采用的指标包括:所有物理块总的擦除次数、总的拷贝次数、所有物理块的擦除次数最大差值、所有物理块擦除次数的标准差。表 2反映了LRGC算法在M=8, λ取不同值时, 各项性能指标情况。由表中数据可知λ=0.4时, 擦除次数和拷贝次数最少, 且擦除次数的最大差值比较小, 因而在验证逻辑区间长度对算法性能影响时, 设定λ=0.4。

FaGC算法的各项性能指标均明显优于GR算法、CB算法和CAT算法, 为了验证本文算法的有效性, 选取FaGC算法作为比较。

由图 2~3可知除M =16外, LRGC算法的擦除次数和拷贝次数均少于FaGC算法, 这是由于该算法采用了新的热度计算公式, 更加准确地刻画了数据访问的频繁度, 并且改进了回收块选择策略, 回收块的选择更为合理。对于LRGC算法, M=1表示热度区间长度为1, 即没有基于逻辑区间计算热度, 仍然是计算单个逻辑页的热度。当M =4时, LRGC算法总的擦除次数和总的拷贝次数与FaGC算法相比, 分别减少了11%、13%。随着热度区间长度M取值增大, 拷贝次数、擦除次数均有所增加, 这是由于随着热度区间大小的增加, 逻辑页热度会出现少量误判的情况。当热度区间长度M =2, 4, 8, 16时, 擦除次数的增长率分别为9.07%、9.11%、8.01%、52.49%;拷贝次数的增长率分别为16.89%、15.82%、13.08%、82.00%。由以上数据可知热度区间长度M取值较小时, 擦除次数和拷贝次数增长相对缓慢；而M取值相对较大时, 擦除次数和拷贝次数会急剧增加是由于设定的热度区间长度过大, 并不能客观准确反映实际数据的读写特性, 出现了较大偏差, 导致热度误判概率较大。

由图 4可知LRGC算法在五种情况下的擦除次数最大差值均小于FaGC算法, 这是由于在对回收块进行选择时, LRGC算法综合考虑了垃圾回收效率和磨损均衡因素, 总是偏向选择无效页较多且擦除次数较小的块进行回收, 在提高回收效率的同时, 还尽可能使擦除操作均匀地分布在每个闪存块上, 从而提高了磨损均衡度。而FaGC算法采用GR算法中的回收块选择策略, 即总是选择无效页最多的块, 该回收块的选择并没有考虑磨损均衡度。当M=4时, LRGC算法擦除次数的最大差值与FaGC算法相比, 减少了42%。由于M=8时擦除次数最大差值相对最小, M=16时擦除次数最大差值相对最大, 选取这两种情况下的标准差和FaGC算法对比。由图 5可知不管是FaGC算法, 还是取不同M值的LRGC算法, 其标准差曲线均呈现收敛状态, 并且最终大致稳定在一个恒定的值, 也就表明各物理块的擦除次数波动较小, 擦除操作比较均匀。这是由于两种算法都将冷热数据进行了分离, 并分开存储在不同擦除次数的空闲块上。综合图 4~5可知, LRGC算法的磨损均衡效果仍然好于FaGC算法。

2.3 内存消耗

算法对于系统性能的改善, 一定程度上是以牺牲内存空间为代价的。两种算法均对冷热数据进行了识别, 而这一过程必然要开辟内存, 来保存逻辑页热度值。FaGC算法中构造了一个热度表, 表中记录了每个逻辑页的上次更新时间和热度值。对于一个单片容量为16 GB, 页大小为2 KB, 块大小为128 KB的NAND闪存, 总的页数为16×1 024×1 024/2=8 192×1 024, 保存每个逻辑页的热度和上次更新时间大约占用3 B, 则FaGC算法需要占用8 192×1 024×3=24 MB存储空间, 可见为了维护这张表, 内存的开销是比较大的。

图 6反映了两种算法下内存开销对比情况。LRGC算法把若干连续逻辑地址定义为一个热度区间, 同一个热度区间内的逻辑页具有相同的热度, 这样在保存热度值时只需要保存逻辑区间的热度, 在保证性能优势的前提下, 扩大逻辑区间长度, 内存消耗成倍降低。同时，从图 2~6可知，M的取值, 对垃圾回收的回收效率以及内存消耗影响较大, 对磨损均衡影响较小。当M=16时, 虽然占有最少的内存空间, 但拷贝次数和擦出次数较大, 回收代价较高, 这样的取值并不具有实际意义; 当M=8或者M=4时, 各项性能指标比较均衡, 因而在实际应用中, 可设定M=8或者M=4, 使得系统不仅具有高的回收效率, 好的磨损效果, 而且内存消耗少。

3 结语

本文提出的LRGC算法是基于逻辑区间识别冷热数据, 在擦除回收块之前, 首先计算回收块中有效页所对应的逻辑区间编号, 根据所在的逻辑区间来判断有效页的热度, 将冷数据拷贝到擦除次数最大的块上, 热数据拷贝到擦除次数最小的块上, 不仅有效地实现了冷热数据分离, 而且占用了相对较小的内存空间。本文算法也存在一定的缺陷, 在通过代价函数选择回收块时, 相当于扩大了回收块的回收范围, 算法时间复杂度较高, 并且相比FaGC, 算法, 一定时间内会选择到更多符合条件的回收块, 增加了回收次数。但从整体来看, 在FaGC算法比经典算法有更多优势的情况下, LRGC算法在性能上有了进一步提升, 而且内存消耗大幅度减少。