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

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

圖1-1 虛構的小小SSD空間

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

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

圖1-2 主機寫入4個邏輯頁數據后

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

用戶繼續順序寫入，固件則把數據交錯寫入到各個Die上，直到寫滿整個SSD空間（主機端看到的）。如下：

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

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

繼續拷入小電影。

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

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

繼續順序寫入，紅色方塊越來越多（垃圾數據越來越多）。所有閃存空間都寫滿后，小SSD世界就是下面這個樣子：

圖1-5 閃存空間寫滿

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

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

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

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

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

圖1-6 垃圾回收示例

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

圖1-7 擦除垃圾數據塊變成可用數據塊

回到我們的小小SSD系統中來。

上例中，由于我們是順序寫入，垃圾集中在Block 0上，上面沒有任何有效數據，我們把它們擦除就可以騰出新的寫入空間。用戶就可以把新的數據寫入到垃圾回收完成的Block 0上了。 從這個例子中，我們可以看到：順序寫，即使是閃存空間寫滿后的寫（Full Drive寫），性能也是比較好的，因為垃圾回收可以很快完成（也許僅僅只要一個擦除動作）。

但現實是殘酷的：用戶寫入數據，更多的可能是隨機寫入數據。下面是一個閃存空間經歷隨機寫滿后的樣子：

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

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

對上面每個閃存塊的垃圾數（紅色方塊）做個統計：

表1-1 每個閃存塊上垃圾數據統計

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

圖1-9 做完垃圾回收后的BLOCK0可以繼續寫入數據

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

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