0 引言

近年来，基于NAND Flash的固态硬盘 (Solid-State Drive, SSD) 因其性能高、功耗低、抗震性好等诸多优点获得广泛的应用。由于NAND闪存异地更新的特点，写更新产生的无效页需经由垃圾回收操作才能重新成为可用页。SSD的垃圾回收操作涉及到目标块的选择、有效数据的迁移和块的擦除操作^[1-3]，因而对SSD的读写性能和寿命都有很大的影响。

根据采用fio^[4]对Intel SSD DC P3700固态盘的测试结果，当执行读写请求大小为4 KB、读写请求比例为7:3的随机I/O时，若SSD是空盘，其每秒进行读写操作的次数 (Input/Output Operations Per Second, IOPS) 能达到20万次，读、写延迟分别为180 μs和2 000 μs；但对SSD进行数据预埋和碎片化处理后再进行相同的测试，其IOPS下降到6万次/s，读写延迟上升了3~7倍, 造成这种性能差距的直接原因是SSD内部的垃圾回收 (Garbage Collection, GC) 操作。当SSD中用于容纳异地更新的预留空间越来越少，就会频繁地触发垃圾回收，导致正常的读写访问被阻塞。由于垃圾回收需通过块擦除获得可用页，因此垃圾回收操作的执行频率也会对SSD的寿命造成影响。

全程优化的垃圾回收方法 (Whole Process Optimized Garbage Collection, WPO-GC)，从数据初始放置、垃圾回收目标块的选择、有效数据的迁移位置、触发回收的时间点以及中断处理方式上，全面优化与垃圾回收方面相关的各个步骤，有效减少了SSD正常读写的响应延迟，同时提升了SSD的寿命。

1 背景与动机 1.1 SSD的架构

SSD主要由SSD控制器和闪存芯片构成, 如图 1所示。SSD中的闪存控制器控制多个通道 (Channel)，每个通道上挂载多颗闪存芯片 (Chip)^[5-6]。如图 2所示，闪存芯片由多个晶圆 (Die) 组成，每个晶圆又由多个分组 (Plane) 组成，每个分组包含多个块 (Block)。块是芯片擦除的基本单位，每个块包含多个页 (Page)，页是芯片读写的基本单位。

1.2 垃圾回收的机制

闪存芯片具有写前擦除的特性，更新数据时要采用异地更新方式 (旧数据成为无效页)^[7]。为保证SSD的正常使用，需要对无效页进行垃圾回收操作，即擦除选定的目标块以供用户再次使用。由于闪存芯片的读写粒度 (页单位) 和擦除粒度 (块单位) 不同，在擦除一个目标块之前，垃圾回收首先需要迁移其有效数据页到其他块中。如图 3所示，一次完整的垃圾回收操作包括3个步骤：① 选择要回收的目标块；② 迁移有效数据到其他块中；③ 擦除目标块。在数据迁移时，数据的源物理页和目的物理页所处的芯片和通道均会被占用，在随后执行块擦除操作时，虽然不会占用通道资源，但被擦除块所处的芯片也会被占用。因此在SSD内部执行垃圾回收操作过程中，上层向SSD发出的读写请求若要访问垃圾回收占用的芯片或者通道资源^{[3, 8]}，其响应时间和吞吐率都会受到较大影响。另外由于闪存芯片擦除次数有限的特性，垃圾回收的执行频率会直接影响SSD的寿命。

在设计垃圾回收算法时通常需要考虑如下几个问题：1) 何时触发垃圾回收操作？2) 如何选择目标块？3) 怎样安置和迁移数据？

1.3 相关工作

针对上述问题，现有垃圾回收算法提出不同的解决方法。

对于何时触发垃圾回收操作，文献[9]设置了一个表示SSD空闲页比例的固定阈值，当空闲页比例小于该阈值时，触发垃圾回收。这种方法的缺点在于：当垃圾回收被触发时，系统中的空闲页比例已经很低，此时容易造成垃圾回收的频繁执行。为避免垃圾回收的频繁触发，文献[10]在SSD空闲时根据SSD当前的多个状态和统计值，如块擦除次数、页的状态等，确认是否触发垃圾回收操作。该方法能够让垃圾回收操作避开正常读写请求，最小化垃圾回收对SSD性能的影响；其缺点在于：针对读写访问密集的应用，垃圾回收操作始终不能有效进行，此外对SSD空闲时间的准确预测也很难实现。文献[11]提出的GC算法允许用户I/O请求中断正在执行的GC操作，待用户I/O请求完成后再恢复执行被中断的GC进程，但是针对I/O密集型应用，垃圾回收操作可能会被连续的I/O请求多次中断，难以及时有效回收SSD空间。为避免垃圾回收的频繁触发，文献[12]设计了一个两级阈值的方式，既能充分利用SSD的空闲时间进行垃圾回收，从而避免后期垃圾回收的频繁触发，针对密集型应用，又能设计强制GC保证SSD的空闲空间。

对于如何选择垃圾回收的目标物理块。贪婪算法选取该垃圾回收请求对应Plane中无效页最多的块作为回收块。该算法优点是能够最大限度地减少数据迁移量，提高垃圾回收的效率；缺点是没有考虑回收块的擦除次数，容易导致块被过早地擦穿，缩短固态盘的使用寿命。另一方面，基于损耗均衡的GC算法选择最少磨损的块作为回收块^[13]，但会增加GC迁移数据的开销。在GC过程中同时考虑回收块的无效页比例和擦除次数常常是一对矛盾，为达到二者的平衡，文献[14]利用块的有效页比例和擦除次数计算加权分，来选择合适的回收块。但是其回收块选择机制是基于特定的Flash文件系统 (Flash File System, FFS)，不具有普遍性。WECO (WEar COnscious)^[15]在文献[14]评分机制的基础上，对评分公式作了优化并将其扩展到块设备，但是对有大量空闲页的块，其评分机制不准确，会导致有较多空闲页和无效页的块被选中回收，这样造成了低下的回收效率。

有效数据迁移的关键在于确定数据迁移安放的位置，一个好的GC算法应通过分析迁移数据的温度等特点，重新规划迁移数据的安放，使相近温度的数据聚集到一块中，提高垃圾回收的效率。WECO提出一种数据分离策略，在数据迁移过程中，能够分离冷热数据。该方法优点是提高垃圾回收的效率和保护磨损严重的块，以增加使用寿命；其不足之处在于冷热数据分离的算法复杂，开销较大。

文献[16]提出缓存感知的垃圾回收算法，当缓存进行替换往下写时，考虑下层通道是否进行垃圾回收操作，避免对正在进行的通道进行分发请求，以此减少响应等待时延, 但这不能从根本上减少垃圾回收带来的影响。

1.4 动机

现有的GC算法^[9-15]，都不能很好地解决垃圾回收对正常读写请求的影响，都是针对垃圾回收的某一个步骤中的问题作优化，例如只针对垃圾回收的触发条件^[9-12]或者回收目标块的选择^[13-15]，缺乏对GC的整体优化改进，更没有针对数据的访问频率 (温度) 特点，防患于未然，在数据放置和迁移时就提前考虑如何减少垃圾回收带来的影响问题。

为了更进一步地减少GC对用户正常读写请求响应延时的影响，更好地提升SSD的性能和寿命，针对现有GC算法的缺陷，深入分析GC的每一步操作，探讨其优化策略，从而达到全过程的优化，提出一种全面的WPO-GC策略。WPO-GC主要工作是在其他研究者的工作上进行优化，包括以下4点：

1) 分离放置冷热数据。依据数据访问频度，确认数据冷热温度，在数据放置时就考虑数据的特点，使温度相近的数据聚集一起，便于达到全盘整体均衡，提高垃圾回收的效率。

2) 建立两级阈值引入一种可中断GC策略，依据SSD当前的工作状态，控制垃圾回收的触发条件，采用不同的中断方式处理，进一步减少GC对SSD读写性能的影响。其中提出中断开放策略，即垃圾回收中的每次有效页迁移结束后开放系统中断，既可以利用不同请求到来的时间间隔进行垃圾回收，又可以及时响应用户请求，减少用户读写操作的等待延时，提高系统的平均响应时间。

3) 选择适当的垃圾回收目标块。采用综合考虑块中无效页所占比例和擦除次数的均衡策略，提高垃圾回收的效率，延长闪存寿命。

4) 在数据迁移时，进一步依据数据冷热程度选择数据的放置位置，减少垃圾回收中不必要的反复迁移。

2 设计和实现

WPO-GC主要目标是减少GC对用户正常读写延时的影响，其设计思路是全面考虑与GC相关的各个方面，并对GC每一步骤进行全局优化，以兼顾SSD性能和寿命的提升。WPO-GC主要包括以下部分：1) 产生不同优先级的垃圾回收请求; 2) 控制垃圾回收的触发条件，允许中断开放策略; 3) 平衡性能和寿命的目标块选择; 4) 通过冷热数据分离提高垃圾回收效率。

2.1 产生垃圾回收请求

目前关于垃圾回收请求响应时机，有不同的研究：文献[9]通过设置较低的空闲空间阈值来作为触发条件，但这会导致使用后期垃圾回收的频繁触发，严重影响性能; 文献[10]采用在SSD空闲时间进行垃圾回收，但是无法准确预测空闲时间; 文献[11]提出可被I/O请求中断的GC算法，但是这会导致垃圾回收操作被连续到来的I/O请求多次中断，难以有效回收SSD空间。

WPO-GC根据SSD空闲空间的多少，设置两级阈值，赋予垃圾回收操作不同的紧迫程度，采用文献[12]提出的方法和公式，分别是不可中断阈值H和可中断阈值T，用于区分垃圾回收操作的紧迫级别。当Plane的空闲空间比例FP低于不可中断阈值H时，需立刻执行垃圾回收，因而产生不可中断垃圾回收请求; 当FP的值在不可中断阈值H和可中断阈值T之间时，产生可中断垃圾回收请求，当FP高于T时不产生垃圾回收请求。基于固态盘中每个Plane的状态 (空闲页数、无效页数、有效页数)，采用式 (1) 和 (2) 动态计算得出H和T的值。

$H = aE + B(1 - {V_{\rm{p}}})$

(1)

$T = AE + B(1 - {V_{\rm{p}}}) + c{I_{\rm{p}}}$

(2)

其中：E表示SSD预留空间比例，由SSD厂商设定; V_p是有效页比例; I_p是无效页比例; a、b、c、A、B均为权值系数，满足具体取值为：a取0.3~0.5，b取0.1~0.3，A取0.5~0.7，B取0.1~0.4，c取0.1~0.3，且0＜H＜T＜1。通过实验验证各参数的具体取值为a=0.3, b=0.1, A=0.5, B=0.3, c=0.2, E=0.1。不可中断垃圾回收请求会立刻执行，对正常读写请求影响较大，因此应将H的值设定得较小，以尽可能避免产生这类请求。根据式 (1)，H的最大值为aE+b，且随有效页比例V_p的上升而下降。可中断垃圾回收请求会在系统空闲时间执行，T的值以AE+B为参考基准，随着有效页比例的上升而下降，随无效页比例的上升而上升。这意味着在无效页较多而有效页较少时，T值较高，可及早触发无效页的回收; 而当有效页比例较高时，T值较低，以避免低效的垃圾回收。

为平衡SSD计算资源和及时产生垃圾回收请求，WPO-GC以每个Plane为单位，每消耗一定数量的页空间，进行一次垃圾回收请求判断。产生的GC请求同正常的读写请求一起挂载到通道请求队列上。为了减少SSD正常的读写请求和两类垃圾回收请求之间的相互干扰，设定这三类请求的服务优先级由高到低依次为：1) 不可中断垃圾回收请求; 2) 正常读写请求; 3) 可中断的垃圾回收请求。

当通道上有不可中断垃圾回收请求时，立即响应不可中断垃圾回收请求，否则优先处理读写请求; 当通道空闲时执行可中断垃圾回收请求。对于可中断垃圾回收请求，在其执行过程中可能会被SSD的正常读写请求中断，以减小GC对正常读写请求响应时延的影响。

2.2 目标回收块的选择

在垃圾回收的目标块选择研究方面，贪婪算法只注重回收的效率，会造成块磨损的不均衡; 文献[13]采用回收磨损次数最少的块进行回收，但会增加GC迁移数据的开销。文献[15]综合考虑了块磨损和回收效率的考虑，相对其他策略有了很大的改进。

WPO-GC为了保证固态盘的使用寿命和回收效率，对文献[15]作进一步的优化改进，选用式 (3) 计算每个块得分，得分最低的作为回收块。式 (3) 是在Tjioe等^[15]提出的公式基础上提出的，缺乏对特殊情况块的考虑，会选择主要包含空闲页和无效页的块，这是不合理的。

式 (3) 由两部分相加而成。第一部分强调GC操作的性能，即块中无效页越多，越可能被回收。

$\begin{array}{l} score = \left( {1 - a} \right)\left( {\frac{{page\_blockinvalid\left( i \right)}}{{page\_block}}} \right) + \\ \quad \quad \quad a\left( {\frac{{erasures\left( i \right)}}{{1 + max}}} \right);\\ a = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 2/(1 + {{\rm{e}}^{{k_\varepsilon }/\Delta \varepsilon }}),\Delta \varepsilon \ne 0\\ 0,\quad \quad \quad \quad \quad \Delta \varepsilon = 0 \end{array}&{;\Delta \varepsilon = max - min} \end{array}} \right. \end{array}$

(3)

其中：invalid(i) 表示第i块中无效页数量；page_block表示一块中的物理页数；erasure(i) 表示第i块的擦除次数；max表示所有块中，块擦除次数最大的值；min表示所有块中，块擦除次数最小的值。

第二部分强调磨损均衡，即块的擦除次数越少，越可能被回收。两部分的比重由系数a决定，a是块磨损次数极差Δε的单调递增函数 (图 4)。k_ε是表征系统响应能力的常数，k_ε越小，系统平均响应时间越短，磨损越不均衡，k_ε取10时，a约为0.5，即两部分权重相同。特别地，当a为0时，算法不考虑磨损均衡，即选取有效数据最少的块回收 (贪婪策略); 当a为1时，算法为纯磨损均衡，即选取磨损次数最少的块回收。回收块的选择在更好地考虑SSD性能的同时，能够兼顾SSD的磨损均衡，提高SSD的寿命。

2.3 有效数据迁移策略

在垃圾回收过程中有效页的迁移方面，闪存芯片手册指出可以使用高级命令copy-back进行有效数据的迁移，但是这有很多限制条件^[17-18]；部分GC算法^{[11, 13]}直接将回收块中的有效数据迁移到空闲块，没有考虑数据的特性；文献[15]提出考虑数据的特性，将其进行冷热分离，来减少后续的GC开销。

WPO-GC在文献[15]的基础上，增加了对“页温度”和“块温度”的逐级考虑，提出冷热数据分离及迁移放置算法，尽可能使冷热程度 (访问频度) 相近的数据聚集到同类的块中，避免后续垃圾回收时冷数据页的无效迁移，提高垃圾回收的效率，也减少了写放大，延长闪存的寿命。为了实现这一策略，在SSD固件中维护了一张逻辑页码 (Logical Page Number, LPN) 温度表，用于记录每个LPN对应的温度，一个表项及其各个字段的含义见表 1。

每当有写子请求到来时，按照图 5所示流程更新LPN温度表。其中:ct是系统的当前时间; u是用于界定是否是最近访问的时间间隔门限，当本次访问时间 (即系统当前时间) 距离最近访问时间大于u时，将最近访问次数置为1。更新TemLPN的方法为TemLPN=Luc，LPN的温度由最近写访问次数决定。

一个块中有3种页温度，其中:1) 有效页的温度就是其对应的LPN的温度值TemLPN; 2) 无效页的温度值显示为其过期前对应的LPN的温度值; 3) 空闲页的温度值为0。为了更好地考虑块中的数据情况，将页更准确地放到温度相近的块中。提出用块温度 (记为TemBlock) 来表示一个块的访问频度，TemBlock的计算公式：

$TemBlock = \frac{1}{{sum}}\left( {\sum\limits_{i = 1}^{valid} {TemPage\left( i \right)} + \sum\limits_{j = 1}^{invalid} {TemPage\left( j \right)} } \right)$

其中各符号的意义见表 2。TemBlock的值由其中的有效页温度和无效页温度计算得到，温度相近的页聚集一起，失效速率也会大体相当，以便于减少回收块时的数据迁移。温度越高的块更加容易失效，提高回收效率。

3 实验结果与分析

WPO-GC的测试平台是开源的SSDsim^[19]，首先分析所用负载trace的特点，然后描述了测试方案及测试过程，最后分析实验结果。

3.1 测试环境

测试使用SSDsim，一个经过验证的固态盘模拟器，它可以根据测试具体需要修改其配置文件。本方案测试所用SSDsim模拟的硬件配置参数见表 3，SSD物理总容量：4×2×2×2×1 024×64×2 KB=4 GB；用户可用容量：4 GB×0.8=3.2 GB。

3.2 测试负载分析

测试使用4种trace：Exchange、Financial、IntelSSD_1和IntelSSD_2，特性统计如表 4。其中，Exchange是从一台供5 000企业用户使用的Microsoft Exchange 2007 SP1邮件服务器上采集的trace^[20-21]，以小的随机访问的读请求为主。Financial是在线事务处理 (On-Line Transaction Processing, OLTP) 应用程序运行在一个大型金融机构产生的I/O trace^[21]；IntelSSD_1和IntelSSD_2是用fio在服务器上生成请求，并利用block_trace工具采集得到的。

3.3 测试方案介绍

本文选用一种典型的垃圾回收算法Basic-GC，以及文献[12]提出的DT-GC作为WPO-GC的测试对照组。Basic-GC采用的策略如下：1) 目标回收块的选取采用贪婪策略，即回收无效数据最多的块; 2) 有效数据迁移采用WECO中的冷热数据分离方案; 3) 垃圾回收过程不可被中断。

本文主要测量了以下4个指标来评估WPO-GC方案：

1) 平均响应时间。即请求从提交给Flash SSD到被响应的平均时间，用于评估WPO-GC方案的读写响应性能。

2) 擦除次数的标准偏差。记录每个闪存分组在实验过程中被擦除的次数的标准偏差，用于评估WPO-GC方案的磨损均衡性能。

3) 擦除次数。记录同一trace下两种策略分别引发的回收次数，用于评估WPO-GC方案减少的磨损。

4) 总写页数。垃圾回收会造成写放大，记录固态盘全部的写页次数，进一步评估WPO-GC方案减少的磨损。

3.4 测试结果分析

本文以Basic-GC和DT-GC方案为对照方案，对WPO-GC方案的整体性能进行了评估。

通过比较4种负载下三者的平均响应时间，可以看到WPO-GC方案相对于Basic-GC在性能上有很大的提升，读/写平均响应时间减少了接近20%，特别是对于分时间段密集请求的负载 (如Financial)，读/写平均响应时间减少达40%；相对于DT-GC在性能上的提升不是很明显，最高提升10%左右。

图 6、7分别显示了以Basic-GC方案为基准对照，归一化后的读、写平均响应时间，纵坐标对应为三种方案平均读、写响应时间与Basic-GC方案平均读、写响应时间的比值。从图 6中可以看出，WPO-GC对4种trace的读平均响应时间相对于Basic-GC均有较大提升，提升最少的接近20%，最多的达到40%。从图 7中可以看出，WPO-GC方案相对于Basic-GC对所有trace测试的结果表现出写平均响应时间均有很大提升，提升最少的也有17%，最多的达到40%；但是相对于DT-GC方案，WPO-GC在性能上的提升并不明显，最高提升10%，而且对于IntelSSD_1负载，读写平均响应性能均有所下降，约2%。

通过对SSDsim的输出信息进行分析，发现三种方案在处理一些请求所花费的响应时间是一致的，但是有些请求，Basic-GC方案的响应时间远大于WPO-GC和DT-GC方案，这应该是导致图 6、7结果的原因。造成这种情况是因为Basic-GC方案在写请求到来时还在执行垃圾回收操作，无法及时响应，造成时延，并对后续请求造成累计时延。而在WPO-GC和DT-GC方案中，产生的是可中断的垃圾回收请求，当写请求到来时垃圾回收操作还未完成，就中断垃圾回收操作，及时响应，不造成时延。

图 8显示了以Basic-GC方案为基准对照，归一化的总擦除次数，纵坐标为三种方案擦除总次数与基准方案Basic-GC擦除总次数的比值。对于不同的trace，块擦除的总次数有很大不同，且跟Basic-GC方案配置文件中垃圾回收阈值的设定有关。

图 9显示了以Basic-GC方案为基准对照，归一化的写放大造成的总写页次数对比情况。由于IntelSSD trace写请求的总量偏小，进行异地更新操作次数有限，在垃圾回收次数有限的情况下，使用WPO-GC方案中目标块选取策略，相对于原方案中选取无效页最多的块进行回收，新方案优异性并不明显。另外3种trace进行更新的次数较多，尽管在目标块选取的回收效率上没有贪婪算法好，但由于考虑了冷热数据的分离，在长时间的使用中弥补了回收效率的欠缺。测试结果表明，WPO-GC方案与Basic-GC方案在总写页次数方面相比差异性不大，WPO-GC方案稍微优异一点。

由于WPO-GC中触发垃圾回收时是参考DT-GC的，所以两者在擦除次数针对每个trace大致相同，其中的细微差异是由于WPO-GC采用冷热数据分离算法，减少了一些有效页的多次迁移，从而减少了写放大。从图 9可以看到WPO-GC方案在总写页数上始终保证低于DT-GC方案，尤其对负载Exchage更是减少了20%的写操作。

图 10表现了三种方案导致的磨损均衡差异。当Flash SSD所有块擦除次数的标准差较低时，表明磨损均匀分布。图 10显示了以Basic-GC方案为基准对照，归一化的块擦除次数标准差，纵坐标为三种方案块擦除次数标准差与Basic-GC方案块擦除次数标准差的比值。从图中可得，在各个trace下，DT-GC方案的分组的擦除次数标准差与Basic-GC方案近似相等，而WPO-GC方案的分组的擦除次数标准差均小于其他两种方案，其中3种trace的测试结果的标准差降低近30%，表现出优异的磨损均衡性能。本文提出的新方案兼顾效率和磨损均衡，在块擦除次数分布不均时，倾向于选择擦除次数小的块进行回收，使各个块的擦出次数趋向于相同。同时由于SSDsim的垃圾回收机制是基于分组的，各分组中块的擦除次数实际上更为平均，有利于提升固态盘的寿命。

4 结语

本文在详细剖析垃圾回收过程的基础上，提出了一种全程优化的垃圾回收方法WPO-GC，尽可能全面地考虑各步骤对SSD正常读写请求和寿命的影响。在开源的模拟器SSDsim上实现并验证了WPO-GC的有效性。实验结果表明，同典型GC算法相比，WPO-GC可以减少SSD读请求延迟20%~40%，写请求延迟17%~40%，并能将均衡磨损近30%，从而延长其使用寿命；同DT-GC策略比较，在性能方面的优化不是很明显，最高提升10%，但是在减少写放大和均衡磨损上有了近30%的优化。如何在保证读写性能的情况下，进一步延长SSD的寿命，是一个值得深入研究的课题。本文提出的方案主要是优化并结合前人的工作，接下来的工作重心将放在如何将垃圾回收与缓存有效结合，在进行有效数据迁移时，判断该数据所对应的逻辑地址是否在缓存已经被更新，从而减少迁移耗时。