GC算法与仿真原理解析

原创内容,转载请注明:  [http://www.ssdfans.com]  谢谢!

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算法结构。

分类目录 SSD, 技术文章.
扫一扫二维码或者微信搜索公众号ssdfans关注(添加朋友->点最下面的公众号->搜索ssdfans),可以经常看到SSD技术和产业的文章(SSD Fans只推送干货)。
ssdfans微信群介绍
技术讨论群 覆盖2000多位中国和世界华人圈SSD以及存储技术精英
固件、软件、测试群 固件、软件和测试技术讨论
异构计算群 讨论人工智能和GPU、FPGA、CPU异构计算
ASIC-FPGA群 芯片和FPGA硬件技术讨论群
闪存器件群 NAND、3D XPoint等固态存储介质技术讨论
企业级 企业级SSD、企业级存储
销售群 全国SSD供应商都在这里,砍砍价,会比某东便宜20%
工作求职群 存储行业换工作,发招聘,要关注各大公司招聘信息,赶快来
高管群 各大SSD相关存储公司高管和创始人、投资人

想加入这些群,请微信扫描下面二维码,或搜索nanoarchplus,加阿呆为微信好友,介绍你的昵称-单位-职务,注明群名,拉你进群。SSD业界需要什么帮助,也可以找阿呆聊。