垃圾回收（Garbage Collection，GC）是FTL的一個重要任務(wù)。我們虛構(gòu)一個小小的SSD空間，來講垃圾回收原理，以及與之緊密聯(lián)系的WA（Write Amplification，寫放大）和OP (Over Provisioning，預(yù)留空間)等概念。

麻雀雖小五臟俱全。翠花，上麻雀。

圖1-1 虛構(gòu)的小小SSD空間

我們假設(shè)該SSD底層有4個通道（Channel，CH0-CH3），連接著4個Die （每個Channel上的Die可并行操作），假設(shè)每個Die只有6個閃存塊（Block0-Block5），所以一共24個閃存塊。每個閃存塊內(nèi)有9個小方塊，每個小方塊的大小和邏輯頁大小一樣。24個閃存塊中，我們假設(shè)其中的20個閃存塊大小為SSD容量，就是主機端看到的SSD大小；另外4個閃存塊是超出SSD容量的預(yù)留空間，我們稱之為OP （Over Provisioning）。

好，一個SSD擺在我們面前，蛋蛋開始寫小電影了。

圖1-2 主機寫入4個邏輯頁數(shù)據(jù)后

我們順序?qū)懭?個邏輯頁，分別寫到不同通道上的Die上，這樣寫的目的是增加底層的并行性，提升寫入性能。

用戶繼續(xù)順序?qū)懭耄碳t把數(shù)據(jù)交錯寫入到各個Die上，直到寫滿整個SSD空間（主機端看到的）。如下：

圖1-3 用戶空間寫滿后的SSD

整個盤寫滿了（從用戶角度來看整個用戶空間寫滿了，但在閃存空間，由于OP的存在，并沒有寫滿），如果蛋蛋想放入更多的小電影，怎么辦？不能怎么辦，只能把看過的小電影割愛刪除了，騰出空間放新的小電影。

繼續(xù)拷入小電影。

圖1-4 刪除4個邏輯頁后再次寫入4個邏輯頁

假設(shè)還是從邏輯頁1開始寫入。這個時候，SSD會把新寫入的邏輯頁寫入到所謂的OP空間。對SSD來說，不存在什么用戶空間和OP空間，它只看到閃存空間。主機端來數(shù)據(jù)，SSD就往閃存空間寫。上面有人紅了，怎么回事？因為邏輯頁1-4的數(shù)據(jù)已更新，寫到新的地方，那么之前那個位置上的邏輯頁1-4數(shù)據(jù)就失效了，過期了，變垃圾了。用戶更新數(shù)據(jù)，由于閃存不能在原位置覆蓋寫，固件只能另找閃存空間寫入新的數(shù)據(jù)，因此導(dǎo)致原閃存空間數(shù)據(jù)過時，形成垃圾。

繼續(xù)順序?qū)懭耄t色方塊越來越多（垃圾數(shù)據(jù)越來越多）。所有閃存空間都寫滿后，小SSD世界就是下面這個樣子：

圖1-5 閃存空間寫滿

等所有Die上的Block 5寫滿后，所有Die上的Block 0也全紅了（這些數(shù)據(jù)都是垃圾）。

現(xiàn)在不僅整個用戶空間都寫滿，整個閃存空間都滿了。如果用戶想繼續(xù)寫入后續(xù)的邏輯頁(36之后的) ，怎么辦？

這個時候，就需要垃圾回收了。我們暫時從之前的SSD系統(tǒng)中走出來，看看什么是垃圾回收。

這里需要說明的是，實際中是不會等所有閃存空間都寫滿后才開始做GC的，而是在滿之前就觸發(fā)GC，這里只是為描述GC而做的假設(shè)。

垃圾回收，就是把某個閃存塊上的有效數(shù)據(jù)（圖4-19中綠色的）讀出來，重寫，然后把該閃存塊擦除，就得到新的可用閃存塊了。

圖1-6 垃圾回收示例

圖中，Block x上面有效數(shù)據(jù)為A,B,C，Block y上面有效數(shù)據(jù)為D,E,F,G，紅色方塊為無效數(shù)據(jù)。垃圾回收機制就是先找一個可用Block z，然后把Block x和Block y的有效數(shù)據(jù)搬移到Block z上面去，這樣Block x和Block y上面就沒有任何有效數(shù)據(jù)，可以擦除變成兩個可用的閃存塊。

圖1-7 擦除垃圾數(shù)據(jù)塊變成可用數(shù)據(jù)塊

回到我們的小小SSD系統(tǒng)中來。

上例中，由于我們是順序?qū)懭耄性贐lock 0上，上面沒有任何有效數(shù)據(jù)，我們把它們擦除就可以騰出新的寫入空間。用戶就可以把新的數(shù)據(jù)寫入到垃圾回收完成的Block 0上了。 從這個例子中，我們可以看到：順序?qū)懀词故情W存空間寫滿后的寫（Full Drive寫），性能也是比較好的，因為垃圾回收可以很快完成（也許僅僅只要一個擦除動作）。

但現(xiàn)實是殘酷的：用戶寫入數(shù)據(jù)，更多的可能是隨機寫入數(shù)據(jù)。下面是一個閃存空間經(jīng)歷隨機寫滿后的樣子：

圖1-8 隨機寫滿閃存空間后的SSD

用戶如果繼續(xù)往SSD上寫入數(shù)據(jù)，那么SSD怎么處理？當(dāng)然需要做垃圾回收。 可世道變了，SSD內(nèi)部狀況比之前看到的復(fù)雜多了，垃圾數(shù)據(jù)分散在每個閃存塊上，而不是集中在某幾個閃存塊上。這個時候，如何挑選需要回收的閃存塊呢？是的，挑垃圾比較多的閃存塊來回收，因為有效數(shù)據(jù)少，要搬移的數(shù)據(jù)少，這樣騰出空閃存塊的速度快。

對上面每個閃存塊的垃圾數(shù)（紅色方塊）做個統(tǒng)計：

表1-1 每個閃存塊上垃圾數(shù)據(jù)統(tǒng)計

由于我們是同時往4個通道上寫，我們需要每個通道都有一個空閑的閃存塊，因此，我們做垃圾回收時，不是回收某個閃存塊，而是所有通道上都要挑一個。一般選擇每個Die上塊號一樣的所有閃存塊做垃圾回收。上例中，Block 0上的垃圾數(shù)量最多（24個紅色方塊，最多），因此我們挑Block 0作為垃圾回收的閃存塊（這里忽略PE count等因素，只看垃圾數(shù)）。 回收完畢，我們把之前Block 0上面的有效數(shù)據(jù)（綠色方塊）重新寫回到這些閃存塊（這里，我們假設(shè)回收的有效數(shù)據(jù)和用戶數(shù)據(jù)寫在同一個閃存塊，實際，它們可能是分開寫的）。

圖1-9 做完垃圾回收后的BLOCK0可以繼續(xù)寫入數(shù)據(jù)

這個時候，有了空閑的空間（白色方塊），用戶就可以繼續(xù)寫入數(shù)據(jù)了。

江湖傳言：SSD越寫越慢。沒錯，其實這是有科學(xué)依據(jù)的：可用閃存空間富裕時，SSD是無需做GC的，因為總有空閑的空間可寫。SSD使用早期，由于沒有觸發(fā)GC，無需額外的讀寫，所以速度很快。慢慢的會發(fā)現(xiàn)SSD變慢了，主要原因是SSD需要做GC。