為了讓閃存擁有更長(zhǎng)久的生命周期，避免一些塊（Block）被頻繁擦除而迅速成為壞塊，而另一些塊則因極少擦除這樣不均衡的擦寫(xiě)而導(dǎo)致SSD整體生命周期縮短的弊端，閃存從業(yè)者提出了多種磨損平衡算法（Wear-Levelling）和垃圾回收（Garbage Collection）策略來(lái)規(guī)避這些問(wèn)題的產(chǎn)生。

磨損平衡算法產(chǎn)生的背景

磨損平衡算法是基于閃存的基本特征而產(chǎn)生：

1、不支持本地更新（outplace-update，即不能在原數(shù)據(jù)位置進(jìn)行覆蓋寫(xiě)入或者直接更改，更改數(shù)據(jù)需要將更改后的數(shù)據(jù)搬遷至新的可用的page，原有位置的page被標(biāo)示為無(wú)效頁(yè)，必須要先擦除無(wú)效頁(yè)才能在原位置重新寫(xiě)入數(shù)據(jù)）；

2、以page為單位寫(xiě)入，以Block為單位擦除，擦除Block需要先將可用page中的數(shù)據(jù)搬遷，那么，當(dāng)有大量的Block可以被選擇擦除時(shí)，搬遷哪些Block中的page并重新利用就關(guān)系到對(duì)不同Block的擦除次數(shù)；

3、每個(gè)Block有擦除次數(shù)限制，經(jīng)常被擦除的Block會(huì)很快成為“壞塊（bad block）”因此，只有均衡每個(gè)Block的擦除次數(shù)，才能讓閃存具有更長(zhǎng)的使用壽命。

FTL通常將page分為三種類型：有效頁(yè)（valid page）、無(wú)效頁(yè)（Invilid page）、可用頁(yè)（Free page）,若物理頁(yè)有邏輯地址相對(duì)應(yīng)則表明該頁(yè)的數(shù)據(jù)是有效的，稱為有效頁(yè)，反之，稱為無(wú)效頁(yè)，當(dāng)垃圾回收運(yùn)行后，無(wú)效頁(yè)被Erase，成為可用頁(yè)，此時(shí)，才可以重新被寫(xiě)入數(shù)據(jù)。

舉例來(lái)說(shuō)，當(dāng)邏輯地址A（假設(shè)對(duì)應(yīng)物理地址1）數(shù)據(jù)需要被修改，無(wú)法直接對(duì)A地址的數(shù)據(jù)修改，需要將A地址數(shù)據(jù)讀取到cache中進(jìn)行修改，然后將修改好的數(shù)據(jù)寫(xiě)入新的物理地址（假設(shè)物理地址6），同時(shí)將邏輯地址A對(duì)應(yīng)到物理地址6，TRIM將物理地址1標(biāo)為無(wú)效頁(yè)，當(dāng)可用頁(yè)越來(lái)越少時(shí)，就會(huì)啟動(dòng)垃圾回收（Garbage Collection）,將無(wú)效頁(yè)進(jìn)行Erase，重新變成可用頁(yè)，此時(shí)，問(wèn)題就來(lái)了：

由于Erase是以Block為單位，如果需要擦除的Block中仍然包含有效頁(yè)，那么就需要先將有效頁(yè)進(jìn)行搬遷，然后才能擦除，那么，是對(duì)包含有效頁(yè)最少的Block進(jìn)行擦除還是對(duì)雖然包含有效頁(yè)較多但擦除次數(shù)較少的Block進(jìn)行擦除？是否考慮有效塊冷數(shù)據(jù)所在Block的擦除次數(shù)？還是有他條件的對(duì)某些Block進(jìn)行擦除？由于這些垃圾回收直接關(guān)系到Block的擦除次數(shù)，因此，如何做到每個(gè)Block都能夠被平均的擦除，而不是對(duì)某些包含熱點(diǎn)數(shù)據(jù)的Block經(jīng)常被擦除，而另一些Block則極少被擦除，磨損平衡算法正是在此背景下產(chǎn)生。

垃圾回收策略

所謂的磨損平衡是指在執(zhí)行垃圾回收的過(guò)程中，對(duì)哪些Block執(zhí)行垃圾回收，用什么樣的機(jī)制進(jìn)行回收才能保證每個(gè)Block被擦除的次數(shù)接近均衡。簡(jiǎn)單的回收策略可以縮短計(jì)算回收Block所需的時(shí)間，但會(huì)導(dǎo)致每個(gè)Block磨損的不均衡。復(fù)雜的回收策略均衡了算法，但導(dǎo)致系統(tǒng)效能降低，因此，好的回收策略需要平衡系統(tǒng)效能和磨損次數(shù)之間的微妙關(guān)系。

垃圾回收策略從最基本的Greedy算法（選擇包含最少有效頁(yè)的Block來(lái)回收）到逐步演進(jìn)的cost-Benefit算法（考慮的Block的擦除頻率，也就是冷熱數(shù)據(jù)的影響），公式如下：

再到CAT回收算法，在cost-benefit的基礎(chǔ)上考慮了Block的擦除次數(shù)因素，需要回收的Block由決定，選擇所得值最小的Block來(lái)回收）。公式如下：

進(jìn)而CICL算法則更進(jìn)一步進(jìn)行了優(yōu)化，需要回收的Block由Block中的有效page數(shù)與所有Block擦除次數(shù)是否平均兩個(gè)因素來(lái)決定，l為決定這兩個(gè)因素的權(quán)重，如果所有Block的平均擦除次數(shù)相同，則l為0，選擇需要回收的Block時(shí)只需要考慮Block中的有效page數(shù)即可，否則，就需要考慮此兩種因素。公式如下：

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

被動(dòng)回收策略和主動(dòng)回收策略

垃圾回收有兩個(gè)重要的問(wèn)題需要考慮：回收無(wú)效Block的時(shí)機(jī)以及每次回收的數(shù)量。因此，又關(guān)系到兩種回收策略：主動(dòng)回收策略與被動(dòng)回收策略。被動(dòng)回收策略是當(dāng)接收到寫(xiě)入請(qǐng)求時(shí)，系統(tǒng)根據(jù)目前狀況判斷是否執(zhí)行垃圾回收，此策略模式下，系統(tǒng)通常會(huì)對(duì)可用空間設(shè)定一個(gè)臨界值，當(dāng)可用空間小于臨界值時(shí)開(kāi)始執(zhí)行垃圾回收。每次需要回收多少空間則有Firmware工程師自己定義。

這種磨損的弊端在于：當(dāng)執(zhí)行垃圾回收時(shí)，寫(xiě)入請(qǐng)求會(huì)被延遲，每次需要執(zhí)行回收的Block數(shù)量越多，延遲的時(shí)間就越長(zhǎng)，外在表現(xiàn)為寫(xiě)入性能急速下降。對(duì)于普通用戶而言，會(huì)感覺(jué)系統(tǒng)卡頓或者假死現(xiàn)象，對(duì)于數(shù)據(jù)采集用戶而言，在執(zhí)行垃圾回收過(guò)程中將會(huì)出現(xiàn)大量的丟幀現(xiàn)象。

下圖：被動(dòng)垃圾回收機(jī)制下的性能表現(xiàn)：

主動(dòng)回收策略則是利用系統(tǒng)空閑時(shí)間執(zhí)行垃圾回收，通過(guò)固件設(shè)定周期性任務(wù)，定時(shí)檢查可用塊的剩余情況，如有需要就執(zhí)行垃圾回收。主動(dòng)回收策略等同于利用空閑時(shí)間提前進(jìn)行垃圾回收，避免了被動(dòng)策略所造成的性能波動(dòng)。單一利用系統(tǒng)空閑時(shí)間執(zhí)行主動(dòng)垃圾回收同樣存在弊端，假設(shè)系統(tǒng)一直沒(méi)有空閑時(shí)間，垃圾回收同樣無(wú)法有效執(zhí)行，例如：城市道路視頻監(jiān)控，閃存會(huì)一直有文件寫(xiě)入，此種情形下垃圾回收與被動(dòng)策略基本雷同。

領(lǐng)存在主動(dòng)回收策略中采用了更加優(yōu)化的方式：PR-Latency技術(shù)，同時(shí)，根據(jù)不同的應(yīng)用場(chǎng)景，配合自動(dòng)可調(diào)的OP空間，可以使SSD即使在100%寫(xiě)/讀負(fù)荷的情況下都可以保持同樣的性能，使用IOMeter 設(shè)置2MB pattern，100%寫(xiě)模式進(jìn)行不間斷的測(cè)試，一周后直接測(cè)試性能曲線，仍然可以表現(xiàn)為一條直線。

靜態(tài)磨損平衡和動(dòng)態(tài)磨損平衡

動(dòng)態(tài)磨損平衡是指當(dāng)需要更改某個(gè)page中的數(shù)據(jù)時(shí)，將新的數(shù)據(jù)寫(xiě)入擦除次數(shù)較少的物理頁(yè)上，同時(shí)將原頁(yè)標(biāo)為無(wú)效頁(yè)，動(dòng)態(tài)磨損平衡算法的缺點(diǎn)在于，如果剛剛寫(xiě)入的數(shù)據(jù)很快又被更新，那么，剛剛更新過(guò)的數(shù)據(jù)塊很快又變成無(wú)效頁(yè)，如果頻繁更新，無(wú)疑會(huì)讓保存冷數(shù)據(jù)的Block極少得到擦除，對(duì)閃存整體壽命產(chǎn)生不利影響。早期的SSD主控多用動(dòng)態(tài)磨損平衡算法，現(xiàn)在則更多是研究動(dòng)態(tài)和靜態(tài)共同使用。

靜態(tài)磨損平衡則是考慮了那些更新頻率很低的Block（冷數(shù)據(jù)），例如：系統(tǒng)數(shù)據(jù)所在的Block，或者某些只讀數(shù)據(jù)，這些冷數(shù)據(jù)所在的Block被更新的頻率比熱數(shù)據(jù)所在的Block明顯低很多，靜態(tài)磨損平衡算法就是把這些冷數(shù)據(jù)所在的Block也加入磨損平衡中，增加了閃存的總體壽命。靜態(tài)磨損平衡的算法非常多，沒(méi)有那種算法是絕對(duì)的完美，后人的算法總是在前人算法的基礎(chǔ)上更進(jìn)一步，不同應(yīng)用場(chǎng)景、不同需求都會(huì)導(dǎo)致不同的算法產(chǎn)生。

一種壽增三倍的算法：領(lǐng)存Non-Blance磨損平衡算法

目前垃圾回收算法基本都是圍繞如何更加平均的擦除每個(gè)Block這種思想進(jìn)行設(shè)計(jì)，這些算法是基于Block耐磨度完全一致的“假設(shè)”基礎(chǔ)之上，但事實(shí)上，每個(gè)page和Block的耐磨狀態(tài)是不同的，當(dāng)對(duì)一個(gè)閃存上的所有Block進(jìn)行平均擦除時(shí)，必然會(huì)有一些Block先成為Bad Block，而另一些Block則會(huì)有更長(zhǎng)時(shí)間的耐磨度。這是由晶圓設(shè)計(jì)工藝所決定的，在目前的工藝條件下，尚無(wú)法確保每個(gè)Block完全一致，而且晶圓一定會(huì)存在一些錯(cuò)誤，不可控制的是這些錯(cuò)誤是隨機(jī)分布的。

下圖為全新Nand Flash（型號(hào)：JS29F16B08CCME2，Intel 16GB MLC）做10次P/E后的情形，結(jié)果顯示每個(gè)Block的Erase時(shí)間是不同的，不同的操作時(shí)間反應(yīng)了每個(gè)Block的原始狀態(tài)不同，操作時(shí)間短的Block健康狀態(tài)理論上好于操作時(shí)間長(zhǎng)的Block。

如果每個(gè)Block的耐磨度本來(lái)是不均衡的，人為通過(guò)算法保持每個(gè)Block擦除一致的結(jié)果，不是延長(zhǎng)了閃存整體壽命，恰恰是損害了閃存最佳使用壽命。

領(lǐng)存 Non-Blance算法思想是：能者多勞。打破前人假設(shè)“每個(gè)Block壽命一致”基礎(chǔ)上的平衡算法，在使用過(guò)程中對(duì)每個(gè)page和Block真實(shí)耐磨度進(jìn)行評(píng)估，讓耐磨度強(qiáng)的Block得到更多的擦寫(xiě)次數(shù)，而耐磨度差的則得到相應(yīng)的保護(hù)。只有每個(gè)Block都不成為壞塊，才能最大程度上減少對(duì)每個(gè)Block的擦除次數(shù)，舉例來(lái)說(shuō)：100個(gè)Block寫(xiě)入1TB數(shù)據(jù)和1000個(gè)Block寫(xiě)入1TB數(shù)據(jù)，假設(shè)100個(gè)Block寫(xiě)入1TB數(shù)據(jù)需要被擦除10次，那么，1000個(gè)Block只需要被擦除1次。

Non-Blance算法的另一個(gè)精要是：當(dāng)Block的不可糾正誤碼率（UBER，Uncorrectable Bit Error Rate）達(dá)到一定的閾值時(shí)，將MLC模式轉(zhuǎn)自動(dòng)換為SLC模式。Non-Blance算法涉及到重要的技術(shù)難題是：如何判斷閃存的真實(shí)耐磨度（如：page1為3000P/E cycle，page3為5000P/E cycle）。測(cè)試page真實(shí)耐磨度的方法有很多，可以通過(guò)某個(gè)關(guān)鍵指標(biāo)或者多個(gè)指標(biāo)綜合判斷，也可以通過(guò)高溫或者低溫條件下的加速測(cè)試事先做好某一型號(hào)Nand Flash的耐磨度關(guān)鍵指標(biāo)測(cè)試，具體做法有如下思路：

通過(guò)對(duì)某一個(gè)型號(hào)的Nand Flash做破壞性測(cè)試，對(duì)Nand Flash做最徹底的P/E測(cè)試，記錄原始誤碼率變化、不可糾正誤碼率和操作時(shí)間的精準(zhǔn)數(shù)據(jù)，建立三者之間的數(shù)學(xué)模型，定義不同誤碼率（原始誤碼率及低強(qiáng)度ECC下的誤碼率）及操作時(shí)間對(duì)應(yīng)page真實(shí)的耐磨度，通過(guò)高溫條件下的加速測(cè)試修正此數(shù)學(xué)模型。

盡管從實(shí)際的操作過(guò)程上看，會(huì)增加很高的復(fù)雜度（測(cè)試是個(gè)非常耗費(fèi)時(shí)間的過(guò)程，且需要對(duì)數(shù)學(xué)模型不斷的修正使其更加精準(zhǔn)），但實(shí)際的效果會(huì)遠(yuǎn)遠(yuǎn)好于不考慮page實(shí)際耐磨度的做法，技術(shù)的進(jìn)步往往是從細(xì)節(jié)和耐心開(kāi)始。

SSD是木桶理論的最佳踐行者，SSD的整體壽命取決于最差的那片閃存，因此，如何篩選出耐磨度一致的閃存才決定了SSD到底可以使用多久，否則，無(wú)論多么優(yōu)秀的算法，終究會(huì)敗給最孱弱的那片閃存。

fqj