寿增3倍的磨损平衡算法思想.pdf

《寿增3倍的磨损平衡算法思想.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1寿增三倍的固态硬盘磨损平衡算法思想【原创】瑞耐斯技术兵哥本文前面部分介绍磨损平衡产生的背景以及常用的算法思想，后半部分介绍了一种可以寿增三倍的磨损平衡算法：Non-Blance算法，高手可以直接跳过前面部分。为了让闪存拥有更长久的生命周期，避免一些块（Block）被频繁擦除而迅速成为坏块，而另一些块则因极少擦除这样不均衡的擦写而导致SSD整体生命周期缩短的弊端，闪存从业者提出了多种磨损平衡算法（Wear-Levelling）和垃圾回收（GarbageCollection）策略来规避这些问题的产生。磨损平衡算法产生的背景磨损平衡算法是基于闪存的基本特征而产生：1、不支

2、持本地更新（outplace-update，即不能在原数据位置进行覆盖写入或者直接更改，更改数据需要将更改后的数据搬迁至新的可用的page，原有位置的page被标示为无效页，必须要先擦除无效页才能在原位置重新写入数据）；2、以page为单位写入，以Block为单位擦除，擦除Block需要先将可用page中的数据搬迁，那么，当有大量的Block可以被选择擦除时，搬迁哪些Block中的page并重新利用就关系到对不同Block的擦除次数；3、每个Block有擦除次数限制，经常被擦除的Block会很快成为“坏块（badblock）”因此，只有均衡每个Block的擦除次数，才

3、能让闪存具有更长的使用寿命。FTL通常将page分为三种类型：有效页（validpage）、无效页（Invilidpage）、可用页（Freepage）,若物理页有逻辑地址相对应则表明该页的数据是有效的，称为有效页，反之，称为无效页，当垃圾回收运行后，无效页被Erase，成为可用页，此时，才可以重新被写入数据。举例来说，当逻辑地址A（假设对应物理地址1）数据需要被修改，无法直接对A地址的数据修改，需要将A地址数据读取到cache中进行修改，然后将修改好的数据写入新的物理地址（假设物理地址6），同时将逻辑地址A对应到物理地址6，TRIM将物理地址1标为无效页，当可用页越

4、来越少时，就会启动垃圾回收（GarbageCollection）,将无效页进行Erase，重新变成可用页，此时，问题就来了：由于Erase是以Block为单位，如果需要擦除的Block中仍然包含有效页，那么就需要先将有效页进行搬迁，然后才能擦除，那么，是对包含有效页最少的Block进行擦除还是对虽然包含有效页较多但擦除次数较少的Block进行擦除？是否考虑有效块冷数据所在Block的擦除次数？还是有他条件的对某些Block进行擦除？由于这些垃圾回收直接关系到Block的擦除次数，因此，如何做到每个Block都能够被平均的擦除，而不是对某些包含热点数据的Block经常被

5、擦除，而另一些Block则极少被擦除，磨损平衡算法正是在此背景下产生。2垃圾回收策略所谓的磨损平衡是指在执行垃圾回收的过程中，对哪些Block执行垃圾回收，用什么样的机制进行回收才能保证每个Block被擦除的次数接近均衡。简单的回收策略可以缩短计算回收Block所需的时间，但会导致每个Block磨损的不均衡。复杂的回收策略均衡了算法，但导致系统效能降低，因此，好的回收策略需要平衡系统效能和磨损次数之间的微妙关系。垃圾回收策略从最基本的Greedy算法（选择包含最少有效页的Block来回收）到逐步演进的cost-Benefit算法（考虑的Block的擦除频率，也就是冷热

6、数据的影响），公式如下：再到CAT回收算法，在cost-benefit的基础上考虑了Block的擦除次数因素，需要回收的Block由决定，选择所得值最小的Block来回收）。公式如下：进而CICL算法则更进一步进行了优化，需要回收的Block由Block中的有效page数与所有Block擦除次数是否平均两个因素来决定，l为决定这两个因素的权重，如果所有Block的平均擦除次数相同，则l为0，选择需要回收的Block时只需要考虑Block中的有效page数即可，否则，就需要考虑此两种因素。公式如下：基于上述垃圾回收策略的基础思想，各家Controller厂商演变出多种多

7、样的各不相同垃圾回收算法，以及冷热数据的分析方法。被动回收策略和主动回收策略3垃圾回收有两个重要的问题需要考虑：回收无效Block的时机以及每次回收的数量。因此，又关系到两种回收策略：主动回收策略与被动回收策略。被动回收策略是当接收到写入请求时，系统根据目前状况判断是否执行垃圾回收，此策略模式下，系统通常会对可用空间设定一个临界值，当可用空间小于临界值时开始执行垃圾回收。每次需要回收多少空间则有Firmware工程师自己定义。这种磨损的弊端在于：当执行垃圾回收时，写入请求会被延迟，每次需要执行回收的Block数量越多，延迟的时间就越长，外在表现为写入