GC算法与仿真原理解析
NVMe SSD的核心算法众多，Garbage Collection（后文简称GC）就是其中之一。一个好的GC算法可以有效的降低SSD的写放大系数，对于SSD的性能和寿命都大有益处。本篇文章就介绍下Memblaze在GC算法及其仿真方面的一些工作。
NAND中，block必须先擦除，然后才能写入数据，且数据写入和擦除的粒度不一致，是需要GC的一个重要原因。擦除粒度block远大于写入粒度page，当系统写入一段时间后，会存在一些block，这些block中有些page中的数据是无效的，如下图。
GC原理示意（图中字母标识的page包含有效数据）
对于上图，GC完成的功能就是把图中左边的两个block选出来，然后搬移Block中的有效数据到右边的block中。首先，Block x和Block y上有效的数据被搬移到Block z中，然后，Block x和Block y将被擦除以便后来数据写入。显然这个机制作用下，SSD上NAND的写入量要比主机写到SSD上的数据量大（因为GC搬移数据也是NAND写入操作）。由此就有了写放大（WA）：
好的GC算法能够得到较小的WA。实现GC功能，SSD需要提供额外的存储空间，来存储这些需要搬移的数据，这个额外的空间就是OP（此外，当SSD出现坏块时，OP也可以保障足够的用户空间）。OP越大，GC工作起来越得心应手，大开大合无拘无束，OP越小，GC越累。
这里做一个进一步的解释，OP很重要，OP越大意味着使用的NAND越多，成本也越高；但是没有OP，SSD的WA会非常大，进而影响到性能和寿命。GC的目标就是努力使的相同OP下，WA尽可能小；或者相同WA下，OP尽可能小，这是等价的表述。随着OP减小，SSD的性能表现会逐渐变差。
仿真平台
GC侧重在算法研究，这需要明确输入是什么。困难的是，我们无法找到一个形式化的描述，或者一个数据集，来明确定义GC算法的输入。由此，仿真是一个解决办法。通过建立GC算法运行的环境，把不同的GC算法，加载到这个环境中来运行，观察其效果，不断对比评估，从而得到期望的GC算法。Memblaze开发了自己的SSD算法仿真平台，该平台将SSD高度抽象，着重突出其NAND擦写逻辑，从而简单明了的直接支持GC算法的研究。
仿真平台由输入、输出、算法和框架几个部分组成。输入模拟了用户IO；输出是监测到的系统状态数据；算法对GC研究来说就是GC算法；框架是平台核心，模拟了SSD逻辑，并将各个部分有机组合在一起协同工作，如下图。
框架部分可以扩展，以实现不同的SSD逻辑，以此来仿真各种SSD实卡环境。IO部分，目前能够支持多种形式化描述的用户流模式，如顺序流、随机流及其混合流；以及文件形式的用户数据流。文件形式的数据流多是从实际环境中采集得到。在框架的支持下，多种算法可以联合研究，比如，Memblaze最近的顺序流算法，就通过和GC算法联合研究，以检测其有效性。
GC算法
GC对SSD来说，必不可少，众多的从业人员和学者都进行了很多研究。Memblaze基于算法仿真平台，在GC方面也进行了大量研究。GC算法，如上文所介绍，当没有地方写用户数据的时候，把那些已经写上数据的block，挑一些出来，这些block上有用的数据都搬到另一个新的block上，这些被挑出来的block就可以擦除，用来写新的用户数据了。因此，GC的核心就是怎么挑选block。一个GC算法需要考虑：
1
什么时候开始做GC；
2
怎么挑选block；
3
搬移的数据和用户数据怎么写。
这些问题没有一个确定的答案，不同的SSD应用环境，不同的设计目标，会有不同的选择。
Memblaze研究的GC算法，目标是在尽可能多的应用场景下，使得block的磨损基本均衡，且WA尽可能小。GC算法包括单流、双流以及多流算法。这里流指的是NAND里选出的一串block，及其上存储的数据。不同流的数据，基本都有明确可区分的来源。
对于一个双流的GC算法来说，区分为用户流和GC流，它们最后会写入到不同的block中，以此来利于冷热数据各自聚集。用户流是直接来自host的IO构成的流，GC流是搬移产生的IO构成的流。
GC在系统空闲容量达到阈值时启动，并依据众多的状态因素和统计信息来挑选block，最后将用户流和GC流分别写到不同的block里。GC算法好比一个进程，其中包含多个线程。每个线程都专注于分析处理各自关心的因素或信息，并给出挑哪个block来擦除的选择。
一个主线程，根据策略来管理和选择使用哪个线程提供的结果，做为最终选中的block。有一个线程处理磨损均衡，当各个block擦除的次数差别超过阈值时，它就提供擦除次数最小的一个block做为备选，提供给主线程。有一个线程处理冷热数据，如果冷数据需要搬移，就把它搬到擦除次数最小的block中，以利于磨损均衡，这个block就提供给主线程备选。
有一个线程在不断的计算每个block的优先级分数，并提供分数最小的那个block给主线程。分数的计算需要考虑很多因素，比如，block里面有用的数据越少，分数要越低；block的擦除次数越少，分数要越低。主线程根据整个SSD的状态，来确定选择哪个block来擦除。
GC算法的效果
下面两个图，分别是采用全盘随机写和JESD219的输入IO时的仿真结果。通过对比仿真结果，可以持续调整优化算法。
图1：全盘随机写（横轴是时间，主纵坐标轴是写放大WA，辅纵坐标轴WL是block的擦除次数PE。Gap是最大PE和最小PE的差。下同。）
图2：JESD219
在多流的GC算法方面，Memblaze也做了大量仿真研究，正逐步加强实践检验方面的内容。更进一步，仿真平台可以扩展SSD的抽象逻辑，以支持各种SSD算法的研究。同时，GC算法一方面也可以考虑更多的应用场景，来继续优化算法；同时可以考虑更新的GC算法结构。
本文作者
来自Memblaze研究中心的技术高手。GC、磨损均衡等NVMe SSD的核心算法和平台仿真技术正是他的重要研究领域。这篇文章就是他执笔结合自身研究写的一篇文章，旨在帮助读者理解GC算法的设计与实现的基本原理。
更多文章可以长按识别下面二维码获取更多Memblaze关于技术的解读文章。