跟著兵哥撿垃圾（1）

作者： SSD攻城獅

想要和作者還有《大話存儲》作者冬瓜哥、《PCI Express體系結構導讀》作者王齊、《蛋蛋讀NVMe》作者蛋蛋等全世界的大牛討論SSD及存儲相關技術？加nanoarch為微信好友，拉你進ssdfans微信群。

平時看兵哥的文章學到不少東西，最近終於見到活人了。

兵哥曾經發過一篇文章《壽增三倍的磨損平衡演算法思想》，裡面介紹了不少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為，選擇需要回收的Block時只需要考慮Block中的有效page數即可，否則，就需要考慮此兩種因素。公式如下：

基於上述垃圾回收策略的基礎思想，各家Controller廠商演變出多種多樣的各不相同垃圾回收演算法，以及冷熱數據的分析方法。

喜歡就請分享轉發！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！