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

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

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

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

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

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

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

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

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

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

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

圖1-4 刪除4個(gè)邏輯頁后再次寫入4個(gè)邏輯頁

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

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

圖1-5 閃存空間寫滿

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

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

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

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

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

圖1-6 垃圾回收示例

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

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

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

上例中，由于我們是順序?qū)懭耄性贐lock 0上，上面沒有任何有效數(shù)據(jù)，我們把它們擦除就可以騰出新的寫入空間。用戶就可以把新的數(shù)據(jù)寫入到垃圾回收完成的Block 0上了。 從這個(gè)例子中，我們可以看到：順序?qū)懀词故情W存空間寫滿后的寫（Full Drive寫），性能也是比較好的，因?yàn)槔厥湛梢院芸焱瓿桑ㄒ苍S僅僅只要一個(gè)擦除動(dòng)作）。

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

圖1-8 隨機(jī)寫滿閃存空間后的SSD

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

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

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

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

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

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

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