1. 关于SSD特性

    磨损平衡(Wear Leveling)和垃圾回收(Garage Collection)都是基于闪存的基本特征而产生:

1、不支持本地更新(outplace-update,不能在原数据位置进行覆盖写入或者直接更改,更改数据需要将更改后的数据搬迁至新的可用的page,原有位置的page被标示为无效页,必须要先擦除无效页才能在原位置重新写入数据);
2、以page为单位写入,以Block为单位擦除,擦除Block需要先将有效数据进行搬迁,当有大量的Block可以被选择擦除时,搬迁哪些Block并重新利用就关系到对不同Block的擦除次数;
3、每个Block有擦除次数限制,经常被擦除的Block会很快成为”坏块(bad block)”因此,只有均衡每个Block的擦除次数,才能让闪存具有更长的使用寿命。
page分为三种类型:有效页(valid page)、无效页(Invalid page)、可用页(Free page),若物理页有逻辑地址相对应则表明该页的数据是有效的,称为有效页,反之,称为无效页,当GC运行后,无效页被Erase,成为可用页,此时,才可以重新被写入数据。
SSD卡内部需要不停的扫描待回收的Block,把Valid Page复制到新的Block里,然后整个Block擦除;搬迁的Valid Page,以及新释放出来的Free Page,更新Mapping Table。这个搬迁和重映射的动作,相比SSD何时回收如何回收(回收策略)是要简单一些的。
回收策略需要平衡系统效能和磨损次数之间的微妙关系。
  1. 垃圾回收策略

    垃圾回收策略各家算法不同,基本都是前人的算法基础上逐步完善和发展起来的。最基本的Greedy算法(选择包含最少有效页的Block来回收)
    然后逐步演进的Cost-Benefit算法(考虑的Block的擦除频率,也就是冷热数据的影响),
    再到CAT回收算法,在cost-benefit的基础上考虑了Block的擦除次数因素,需要回收的Block由决定,选择所得值最小的Block来回收)。
    进而CICL算法则更进一步进行了优化,需要回收的Block由Block中的有效page数与所有Block擦除次数是否平均两个因素来决定,L为决定这两个因素的权重,如果所有Block的平均擦除次数相同,则L为0,选择需要回收的Block时只需要考虑Block中的有效page数即可,否则,就需要考虑此两种因素。
    基于上述垃圾回收策略的基础思想,各家Controller厂商演变出多种多样的各不相同垃圾回收算法,以及冷热数据的分析方法。

  2. 参考

    跟着兵哥捡垃圾:http://www.sohu.com/a/148665668_505795 openwall项目: http://lists.openwall.net