平时看兵哥的文章学到不少东西，最近终于见到活人了。
兵哥曾经发过一篇文章《寿增三倍的磨损平衡算法思想》，里面介绍了不少GC相关的内容，值得好好学习。
背景
磨损平衡（Wear Leveling）和垃圾回收（Garage Collection）都是基于闪存的基本特征而产生：
1、不支持本地更新（outplace-update，即不能在原数据位置进行覆盖写入或者直接更改，更改数据需要将更改后的数据搬迁至新的可用的page，原有位置的page被标示为无效页，必须要先擦除无效页
才能在原位置重新写入数据）；
2、以page为单位写入，以Block为单位擦除，擦除Block需要先将有效数据进行搬迁，那么，当有大量的Block可以被选择擦除时，搬迁哪些Block并重新利用就关系到对不同Block的擦除次数；
3、每个Block有擦除次数限制，经常被擦除的Block会很快成为”坏块（bad block）”因此，只有均衡每个Block的擦除次数，才能让闪存具有更长的使用寿命。
FTL通常将page分为三种类型：有效页（valid page）、无效页（Invalid page）、可用页（Free page）,若物理页有逻辑地址相对应则表明该页的数据是有效的，称为有效页，反之，称为无效页，当GC运行后，无效页被Erase，成为可用页，此时，才可以重新被写入数据。
于谦老师有三大爱好：抽烟，喝酒，烫头
兵哥捡垃圾有三大步骤：圈地，拆迁，登记
圈地：决定什么时候开始GC，对哪些Block进行GC；
拆迁：扫描待回收的Block，把Valid Page复制到新的Block里，然后整个Block擦除；
登记：搬迁的Valid Page，以及新释放出来的Free Page，更新Mapping Table。
跟拆迁和登记比起来，圈地是比较有技术含量的，在执行垃圾回收的过程中，对哪些Block执行回收，用什么样的机制进行回收才能保证每个Block被擦除的次数接近均衡。
简单的回收策略可以缩短计算回收Block所需的时间，但会导致每个Block磨损的不均衡。复杂的回收策略均衡了算法，但导致系统效能降低，功耗增加，因此，好的回收策略需要平衡系统效能和磨损次数之间的微妙关系。
垃圾回收策略各家算法不同，但基本都是前人的算法基础上逐步完善和发展起来的。
最基本的Greedy算法（选择包含最少有效页的Block来回收）
然后逐步演进的Cost-Benefit算法（考虑的Block的擦除频率，也就是冷热数据的影响），公式如下：
再到CAT回收算法，在cost-benefit的基础上考虑了Block的擦除次数因素，需要回收的Block由决定，选择所得值最小的Block来回收）。公式如下：
进而CICL算法则更进一步进行了优化，需要回收的Block由Block中的有效page数与所有Block擦除次数是否平均两个因素来决定，L为决定这两个因素的权重，如果所有Block的平均擦除次数相同，则L为0，选择需要回收的Block时只需要
考虑Block中的有效page数即可，否则，就需要考虑此两种因素。公式如下：
基于上述垃圾回收策略的基础思想，各家Controller厂商演变出多种多样的各不相同垃圾回收算法，以及冷热数据的分析方法。
