在线客服

联系电话

0755-83258725

返回顶部

点击立即购买

Non-Balance磨损平衡算法,提升固态硬盘3倍以上寿命

发表时间:2018-12-03 发表人:领存兵哥 评论数:0
为了让闪存拥有更长久的生命周期,避免一些块(Block)被频繁擦除而迅速成为坏块,而另一些块则因极少擦除这样不均衡的擦写而导致SSD整体生命周期缩短的弊端,闪存从业者提出了多种磨损平衡算法(Wear-Levelling)和垃圾回收(Garbage Collection)策略来规避这些问题的产生。

为了让闪存拥有更长久的生命周期,避免一些块(Block)被频繁擦除而迅速成为坏块,而另一些块则因极少擦除这样不均衡的擦写而导致SSD整体生命周期缩短的弊端,闪存从业者提出了多种磨损平衡算法(Wear-Levelling)和垃圾回收(Garbage Collection)策略来规避这些问题的产生。




磨损平衡算法产生的背景




磨损平衡算法是基于闪存的基本特征而产生:




1、不支持本地更新(outplace-update,即不能在原数据位置进行覆盖写入或者直接更改,更改数据需要将更改后的数据搬迁至新的可用的page,原有位置的page被标示为无效页,必须要先擦除无效页才能在原位置重新写入数据);




2、以page为单位写入,以Block为单位擦除,擦除Block需要先将可用page中的数据搬迁,那么,当有大量的Block可以被选择擦除时,搬迁哪些Block中的page并重新利用就关系到对不同Block的擦除次数;




3、每个Block有擦除次数限制,经常被擦除的Block会很快成为坏块(bad block因此,只有均衡每个Block的擦除次数,才能让闪存具有更长的使用寿命。




FTL通常将page分为三种类型:有效页(valid page)、无效页(Invilid page)、可用页(Free page,若物理页有逻辑地址相对应则表明该页的数据是有效的,称为有效页,反之,称为无效页,当垃圾回收运行后,无效页被Erase,成为可用页,此时,才可以重新被写入数据。




举例来说,当逻辑地址A(假设对应物理地址1)数据需要被修改,无法直接对A地址的数据修改,需要将A地址数据读取到cache中进行修改,然后将修改好的数据写入新的物理地址(假设物理地址6),同时将逻辑地址A对应到物理地址6TRIM将物理地址1标为无效页,当可用页越来越少时,就会启动垃圾回收(Garbage Collection,将无效页进行Erase,重新变成可用页,此时,问题就来了:




由于Erase是以Block为单位,如果需要擦除的Block中仍然包含有效页,那么就需要先将有效页进行搬迁,然后才能擦除,那么,是对包含有效页最少的Block进行擦除还是对虽然包含有效页较多但擦除次数较少的Block进行擦除?是否考虑有效块冷数据所在Block的擦除次数?还是有他条件的对某些Block进行擦除?由于这些垃圾回收直接关系到Block的擦除次数,因此,如何做到每个Block都能够被平均的擦除,而不是对某些包含热点数据的Block经常被擦除,而另一些Block则极少被擦除,磨损平衡算法正是在此背景下产生。



垃圾回收策略




所谓的磨损平衡是指在执行垃圾回收的过程中,对哪些Block执行垃圾回收,用什么样的机制进行回收才能保证每个Block被擦除的次数接近均衡。




简单的回收策略可以缩短计算回收Block所需的时间,但会导致每个Block磨损的不均衡。复杂的回收策略均衡了算法,但导致系统效能降低,因此,好的回收策略需要平衡系统效能和磨损次数之间的微妙关系。




垃圾回收策略从最基本的Greedy算法(选择包含最少有效页的Block来回收)到逐步演进的cost-Benefit算法(考虑的Block的擦除频率,也就是冷热数据的影响),公式如下:





再到CAT回收算法,在cost-benefit的基础上考虑了Block的擦除次数因素,需要回收的Block由决定,选择所得值最小的Block来回收)。公式如下:





进而CICL算法则更进一步进行了优化,需要回收的BlockBlock中的有效page数与所有Block擦除次数是否平均两个因素来决定,l为决定这两个因素的权重,如果所有Block的平均擦除次数相同,则l0,选择需要回收的Block时只需要考虑Block中的有效page数即可,否则,就需要考虑此两种因素。公式如下:





基于上述垃圾回收策略的基础思想,各家Controller厂商演变出多种多样的各不相同垃圾回收算法,以及冷热数据的分析方法。




被动回收策略和主动回收策略




垃圾回收有两个重要的问题需要考虑:回收无效Block的时机以及每次回收的数量。因此,又关系到两种回收策略:主动回收策略与被动回收策略。




被动回收策略是当接收到写入请求时,系统根据目前状况判断是否执行垃圾回收,此策略模式下,系统通常会对可用空间设定一个临界值,当可用空间小于临界值时开始执行垃圾回收。每次需要回收多少空间则有Firmware工程师自己定义。




这种磨损的弊端在于:当执行垃圾回收时,写入请求会被延迟,每次需要执行回收的Block数量越多,延迟的时间就越长,外在表现为写入性能急速下降。对于普通用户而言,会感觉系统卡顿或者假死现象,对于数据采集用户而言,在执行垃圾回收过程中将会出现大量的丢帧现象。


下图:被动垃圾回收机制下的性能表现:





主动回收策略则是利用系统空闲时间执行垃圾回收,通过固件设定周期性任务,定时检查可用块的剩余情况,如有需要就执行垃圾回收。主动回收策略等同于利用空闲时间提前进行垃圾回收,避免了被动策略所造成的性能波动。




单一利用系统空闲时间执行主动垃圾回收同样存在弊端,假设系统一直没有空闲时间,垃圾回收同样无法有效执行,例如:城市道路视频监控,闪存会一直有文件写入,此种情形下垃圾回收与被动策略基本雷同。




领存在主动回收策略中采用了更加优化的方式:PR-Latency技术,同时,根据不同的应用场景,配合自动可调的OP空间,可以使SSD即使在100%/读负荷的情况下都可以保持同样的性能,使用IOMeter 设置2MB pattern100%写模式进行不间断的测试,一周后直接测试性能曲线,仍然可以表现为一条直线。





静态磨损平衡和动态磨损平衡




动态磨损平衡是指当需要更改某个page中的数据时,将新的数据写入擦除次数较少的物理页上,同时将原页标为无效页,动态磨损平衡算法的缺点在于,如果刚刚写入的数据很快又被更新,那么,刚刚更新过的数据块很快又变成无效页,如果频繁更新,无疑会让保存冷数据的Block极少得到擦除,对闪存整体寿命产生不利影响。早期的SSD主控多用动态磨损平衡算法,现在则更多是研究动态和静态共同使用。




静态磨损平衡则是考虑了那些更新频率很低的Block(冷数据),例如:系统数据所在的Block,或者某些只读数据,这些冷数据所在的Block被更新的频率比热数据所在的Block明显低很多,静态磨损平衡算法就是把这些冷数据所在的Block也加入磨损平衡中,增加了闪存的总体寿命。




静态磨损平衡的算法非常多,没有那种算法是绝对的完美,后人的算法总是在前人算法的基础上更进一步,不同应用场景、不同需求都会导致不同的算法产生。




一种寿增三倍的算法:领存Non-Blance磨损平衡算法




目前垃圾回收算法基本都是围绕如何更加平均的擦除每个Block这种思想进行设计,这些算法是基于Block耐磨度完全一致的假设基础之上,但事实上,每个pageBlock的耐磨状态是不同的,当对一个闪存上的所有Block进行平均擦除时,必然会有一些Block先成为Bad Block,而另一些Block则会有更长时间的耐磨度。这是由晶圆设计工艺所决定的,在目前的工艺条件下,尚无法确保每个Block完全一致,而且晶圆一定会存在一些错误,不可控制的是这些错误是随机分布的。




下图为全新Nand Flash(型号:JS29F16B08CCME2Intel 16GB MLC)做10P/E后的情形,结果显示每个BlockErase时间是不同的,不同的操作时间反应了每个Block的原始状态不同,操作时间短的Block健康状态理论上好于操作时间长的Block



如果每个Block的耐磨度本来是不均衡的,人为通过算法保持每个Block擦除一致的结果,不是延长了闪存整体寿命,恰恰是损害了闪存最佳使用寿命。




领存 Non-Blance算法思想是:能者多劳。打破前人假设每个Block寿命一致基础上的平衡算法,在使用过程中对每个pageBlock真实耐磨度进行评估,让耐磨度强的Block得到更多的擦写次数,而耐磨度差的则得到相应的保护。只有每个Block都不成为坏块,才能最大程度上减少对每个Block的擦除次数,举例来说:100Block写入1TB数据和1000Block写入1TB数据,假设100Block写入1TB数据需要被擦除10次,那么,1000Block只需要被擦除1次。




Non-Blance算法的另一个精要是:当Block的不可纠正误码率(UBERUncorrectable Bit Error Rate)达到一定的阈值时,将MLC模式转自动换为SLC模式。




Non-Blance算法涉及到重要的技术难题是:如何判断闪存的真实耐磨度(如:page13000P/E cyclepage35000P/E cycle)。




测试page真实耐磨度的方法有很多,可以通过某个关键指标或者多个指标综合判断,也可以通过高温或者低温条件下的加速测试事先做好某一型号Nand Flash的耐磨度关键指标测试,具体做法有如下思路:




通过对某一个型号的Nand Flash做破坏性测试,对Nand Flash做最彻底的P/E测试,记录原始误码率变化、不可纠正误码率和操作时间的精准数据,建立三者之间的数学模型,定义不同误码率(原始误码率及低强度ECC下的误码率)及操作时间对应page真实的耐磨度,通过高温条件下的加速测试修正此数学模型。




尽管从实际的操作过程上看,会增加很高的复杂度(测试是个非常耗费时间的过程,且需要对数学模型不断的修正使其更加精准),但实际的效果会远远好于不考虑page实际耐磨度的做法,技术的进步往往是从细节和耐心开始。




SSD是木桶理论的最佳践行者,SSD的整体寿命取决于最差的那片闪存,因此,如何筛选出耐磨度一致的闪存才决定了SSD到底可以使用多久,否则,无论多么优秀的算法,终究会败给最孱弱的那片闪存。 


评论
发表评论
icon