壽增三倍的固態硬碟磨損平衡演算法思想

6 人贊了文章

【原創】瑞耐斯技術兵哥

本文前面部分介紹磨損平衡產生的背景以及常用的演算法思想，後半部分介紹了一種可以壽增三倍的磨損平衡演算法：Non-Blance演算法，高手可以直接跳過前面部分。

為了讓快閃記憶體擁有更長久的生命周期，避免一些塊（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對應到物理地址6，TRIM將物理地址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演算法則更進一步進行了優化，需要回收的Block由Block中的有效page數與所有Block擦除次數是否平均兩個因素來決定，l為決定這兩個因素的權重，如果所有Block的平均擦除次數相同，則l為0，選擇需要回收的Block時只需要考慮Block中的有效page數即可，否則，就需要考慮此兩種因素。公式如下：

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

被動回收策略和主動回收策略

垃圾回收有兩個重要的問題需要考慮：回收無效Block的時機以及每次回收的數量。因此，又關係到兩種回收策略：主動回收策略與被動回收策略。

被動回收策略是當接收到寫入請求時，系統根據目前狀況判斷是否執行垃圾回收，此策略模式下，系統通常會對可用空間設定一個臨界值，當可用空間小於臨界值時開始執行垃圾回收。每次需要回收多少空間則有Firmware工程師自己定義。

這種磨損的弊端在於：當執行垃圾回收時，寫入請求會被延遲，每次需要執行回收的Block數量越多，延遲的時間就越長，外在表現為寫入性能急速下降。對於普通用戶而言，會感覺系統卡頓或者假死現象，對於數據採集用戶而言，在執行垃圾回收過程中將會出現大量的丟幀現象。

下圖：被動垃圾回收機制下的性能表現：

主動回收策略則是利用系統空閑時間執行垃圾回收，通過固件設定周期性任務，定時檢查可用塊的剩餘情況，如有需要就執行垃圾回收。主動回收策略等同於利用空閑時間提前進行垃圾回收，避免了被動策略所造成的性能波動。

單一利用系統空閑時間執行主動垃圾回收同樣存在弊端，假設系統一直沒有空閑時間，垃圾回收同樣無法有效執行，例如：城市道路視頻監控，快閃記憶體會一直有文件寫入，此種情形下垃圾回收與被動策略基本雷同。

（以下內容涉及商業機密，僅做大體介紹，請各位讀者不要諮詢具體實現方法）瑞耐斯在主動回收策略中採用了更加優化的方式：PR-Latency技術，同時，根據不同的應用場景，配合自動可調的OP空間，可以使SSD即使在100%寫/讀負荷的情況下都可以保持同樣的性能，使用IOMeter設置2MB pattern，100%寫模式進行不間斷的測試，一周後直接測試性能曲線，仍然可以表現為一條直線。

靜態磨損平衡和動態磨損平衡

動態磨損平衡是指當需要更改某個page中的數據時，將新的數據寫入擦除次數較少的物理頁上，同時將原頁標為無效頁，動態磨損平衡演算法的缺點在於，如果剛剛寫入的數據很快又被更新，那麼，剛剛更新過的數據塊很快又變成無效頁，如果頻繁更新，無疑會讓保存冷數據的Block極少得到擦除，對快閃記憶體整體壽命產生不利影響。早期的SSD主控多用動態磨損平衡演算法，現在則更多是研究動態和靜態共同使用。

靜態磨損平衡則是考慮了那些更新頻率很低的Block（冷數據），例如：系統數據所在的Block，或者某些只讀數據，這些冷數據所在的Block被更新的頻率比熱數據所在的Block明顯低很多，靜態磨損平衡演算法就是把這些冷數據所在的Block也加入磨損平衡中，增加了快閃記憶體的總體壽命。

靜態磨損平衡的演算法非常多，沒有那種演算法是絕對的完美，後人的演算法總是在前人演算法的基礎上更進一步，不同應用場景、不同需求都會導致不同的演算法產生。

一種壽增三倍的演算法：瑞耐斯Non-Blance磨損平衡演算法

目前垃圾回收演算法基本都是圍繞如何更加平均的擦除每個Block這種思想進行設計，這些演算法是基於Block耐磨度完全一致的「假設」基礎之上，但事實上，每個page和Block的耐磨狀態是不同的，當對一個快閃記憶體上的所有Block進行平均擦除時，必然會有一些Block先成為Bad Block，而另一些Block則會有更長時間的耐磨度。這是由晶圓設計工藝所決定的，在目前的工藝條件下，尚無法確保每個Block完全一致，而且晶圓一定會存在一些錯誤，不可控制的是這些錯誤是隨機分布的。

下圖為全新Nand Flash（型號：JS29F16B08CCME2，Intel 16GB MLC）做10次P/E後的情形，結果顯示每個Block的Erase時間是不同的，不同的操作時間反應了每個Block的原始狀態不同，操作時間短的Block健康狀態理論上好於操作時間長的Block。

如果每個Block的耐磨度本來是不均衡的，人為通過演算法保持每個Block擦除一致的結果，不是延長了快閃記憶體整體壽命，恰恰是損害了快閃記憶體最佳使用壽命。

Renice Non-Blance演算法思想是：能者多勞。打破前人假設「每個Block壽命一致」基礎上的平衡演算法，在使用過程中對每個page和Block真實耐磨度進行評估，讓耐磨度強的Block得到更多的擦寫次數，而耐磨度差的則得到相應的保護。只有每個Block都不成為壞塊，才能最大程度上減少對每個Block的擦除次數，舉例來說：100個Block寫入1TB數據和1000個Block寫入1TB數據，假設100個Block寫入1TB數據需要被擦除10次，那麼，1000個Block只需要被擦除1次。

Non-Blance演算法的另一個精要是：當Block的不可糾正誤碼率（UBER，Uncorrectable Bit Error Rate）達到一定的閾值時，將MLC模式轉自動換為SLC模式。

Non-Blance演算法涉及到重要的技術難題是：如何判斷快閃記憶體的真實耐磨度（如：page1為3000P/E cycle，page3為5000P/E cycle）。

測試page真實耐磨度的方法有很多，可以通過某個關鍵指標或者多個指標綜合判斷，也可以通過高溫或者低溫條件下的加速測試事先做好某一型號Nand Flash的耐磨度關鍵指標測試，具體做法有如下思路：

通過對某一個型號的Nand Flash做破壞性測試，對Nand Flash做最徹底的P/E測試，記錄原始誤碼率變化、不可糾正誤碼率和操作時間的精準數據，建立三者之間的數學模型，定義不同誤碼率（原始誤碼率及低強度ECC下的誤碼率）及操作時間對應page真實的耐磨度，通過高溫條件下的加速測試修正此數學模型。

儘管從實際的操作過程上看，會增加很高的複雜度（測試是個非常耗費時間的過程，且需要對數學模型不斷的修正使其更加精準），但實際的效果會遠遠好於不考慮page實際耐磨度的做法，技術的進步往往是從細節和耐心開始。

SSD是木桶理論的最佳踐行者，SSD的整體壽命取決於最差的那片快閃記憶體，因此，如何篩選出耐磨度一致的快閃記憶體才決定了SSD到底可以使用多久，否則，無論多麼優秀的演算法，終究會敗給最孱弱的那片快閃記憶體。

「瑞耐斯存儲技術」為純凈原創技術文章的公眾號平台，歡迎關注