SSD Garbage Collection

你可能有過這種經驗：一邊工作一邊用 Steam 裝遊戲，寫入大量資料的時候，系統突然頓了一下，滑鼠移動不太順，或是正在存檔的程式卡了半秒鐘。那個短暫的卡頓，很可能就是你 SSD 內部的 garbage collection（GC）正在跟你的工作搶頻寬。

FTL 的 out-of-place write 策略解決了「不能覆寫」的問題，但製造了一個新問題：隨著寫入持續進行，NAND flash 上會累積越來越多的 invalid page（舊版本的資料），而這些 page 所在的 block 無法直接重新使用，因為一個 block 裡通常同時包含 valid page 和 invalid page。如果不處理，SSD 最終會耗盡所有空白 page 而無法寫入。GC 就是 SSD 韌體中負責回收這些空間的機制，它的設計直接決定了 SSD 的寫入效能、延遲一致性、以及使用壽命。

GC 的基本流程

GC 的運作可以分成三個步驟：

1. 選擇 victim block：從所有包含 invalid page 的 block 中，依據某種策略選出一個 block 來回收。
2. 搬移 valid page：把 victim block 中仍然有效的 page 讀出來，寫到其他有空白 page 的 block 中，同時更新 FTL mapping table。
3. 抹除 victim block：整個 block erase，變成可以重新寫入的 free block。

這裡的核心開銷在步驟 2：搬移 valid page。每搬移一個 page 就需要一次 read 和一次 write，而這些 read/write 與使用者的 I/O 共享 NAND flash 的頻寬。如果一個 block 裡有 200 個 valid page（總共 256 個），那回收這個 block 需要 200 次額外的 read + write，但只換來 256 個空白 page。效率不高。反之，如果一個 block 裡只有 10 個 valid page，那只需 10 次搬移就能換來 256 個空白 page，效率很好。

這就引出了 victim block selection 的策略問題。

Greedy policy vs cost-benefit policy

Greedy policy 是最直覺的策略：挑選 invalid page 數量最多的 block 作為 victim。邏輯很簡單，invalid page 越多代表需要搬移的 valid page 越少，回收的成本最低、效率最高。

Greedy 在大多數情況下表現不差，但它有一個盲點：它不考慮資料的「年齡」。假設有兩個 block：

• Block A：50% invalid page，但 valid page 裡的資料是「冷資料」（很久沒被更新）
• Block B：60% invalid page，但 valid page 裡的資料是「熱資料」（頻繁被更新）

Greedy 會選 Block B（invalid 比例高）。但 Block B 的 valid page 很快就會被更新而變成 invalid，如果我們等一下，Block B 可能自然地累積更多 invalid page，到時候回收成本更低。相比之下，Block A 的冷資料可能永遠不會被更新，如果不主動回收，這些 valid page 會一直霸佔空間。

Cost-benefit policy 就是考慮這個因素的策略。它的選擇公式大致是：

benefit = (1 - utilization) * age / (2 * utilization)

其中 utilization 是 block 中 valid page 的比例，age 是 block 中資料的平均年齡（距離上次被寫入的時間）。這個公式傾向選擇那些「utilization 低且資料老舊」的 block，因為老舊資料不太可能自己變成 invalid，不主動清理就會一直浪費空間。

實務上，許多 SSD 使用 greedy 的變種或更複雜的 heuristic，因為 cost-benefit 需要追蹤每個 block 的年齡資訊，增加了實作複雜度。

Over-provisioning：給 GC 留的緩衝空間

SSD 的實際 NAND flash 容量比使用者看到的容量大。例如一顆標示為 1 TB 的 SSD，內部可能有 1.12 TB 的 NAND flash。多出來的 12% 就是 over-provisioning（OP），使用者無法存取這些空間。

OP 的主要用途就是讓 GC 有足夠的「週轉空間」。想像一個類比：你有一個書架，所有格子都塞滿了書。如果你想整理某一格（把不要的書丟掉），你需要一個暫時放書的地方。如果書架完全滿了，連一個暫放的空間都沒有，整理就無法進行。OP 就是那個暫放空間。

OP 比例直接影響 GC 的效率：

• OP 越高：free block 越多，GC 不需要在空間極度緊張時才運作，可以從容地選擇最佳 victim block。搬移的 valid page 比例較低，write amplification 較小。
• OP 越低：free block 稀缺，GC 經常在「快沒空間了」的緊急狀態下運作，被迫選擇 valid page 比例較高的 block 來回收，write amplification 增加。

企業級 SSD 的 OP 通常為 28%（標示 800 GB 但內部有 1024 GB NAND），而消費級 SSD 通常只有 7%（標示 1 TB 但內部有 1074 GB NAND）。這也是企業級 SSD 在持續寫入下效能更穩定的原因之一。這就是為什麼企業級 SSD 比消費級貴好幾倍：你買的不只是更高的耐久度，更是那多出來 20% 的「隱藏容量」帶來的 GC 效率優勢。資料中心為了穩定的 tail latency，願意花三倍的錢買只多了一點 OP 的 SSD。

OP 還有另一個用途：當某些 block 的 P/E cycle 耗盡或出現壞 cell 時，OP 區域的 block 可以作為替換，延長 SSD 的可用壽命。

Wear leveling：平衡 P/E cycle 使用

每個 block 的 P/E cycle 有上限（例如 TLC 約 3,000 次）。如果某些 block 被頻繁地 erase 而其他 block 幾乎不動，那些高使用率的 block 會先壞掉。即使其他 block 還很健康，SSD 的有效容量也會因為壞 block 的累積而縮小，最終影響可靠性。

Wear leveling 的目標是讓所有 block 的 P/E cycle 使用量盡量平均。這分為兩種策略：

Dynamic wear leveling：在 GC 選擇 victim block 時，優先選擇 P/E cycle 較低的 block 作為搬移目的地。這種方式只影響被 GC 處理過的 block，對於一直存放冷資料而從未被 GC 動過的 block 沒有效果。

Static wear leveling：主動把存放在低 P/E cycle block 上的冷資料搬到高 P/E cycle 的 block 上，然後把低 P/E cycle 的 block 釋放出來給 GC 使用。這樣冷資料不會一直霸佔「年輕」的 block，讓所有 block 的磨損更加均勻。

Static wear leveling 的開銷比 dynamic 大（需要額外搬移本來不需要動的資料），但對延長 SSD 整體壽命更有效。實際的 SSD 韌體通常會結合兩種策略，在效能和壽命之間取得平衡。

值得注意的是，wear leveling 和 GC 的 victim selection 策略有時會衝突。Greedy GC 想回收 invalid page 最多的 block（效率最高），但 wear leveling 可能要求對低 P/E cycle 的 block 做更多操作。SSD 韌體需要在這些目標之間做適當的權衡。

自問自答

1. 一個 block 有 256 個 page，其中 200 個是 valid。GC 回收這個 block 需要多少次額外的 NAND flash read 和 write 操作？回收後得到多少個空白 page？

2. 為什麼 greedy policy 在冷熱資料混合的 workload 下可能不是最佳策略？請用具體的 block 狀態舉例說明 cost-benefit policy 會做出什麼不同的決策。

3. 一顆企業級 SSD 有 28% OP，一顆消費級 SSD 有 7% OP。在持續 random write workload 下，哪顆 SSD 的 write amplification 會比較低？為什麼？

4. 如果一顆 SSD 只使用 dynamic wear leveling 而沒有 static wear leveling，在什麼情境下會出現部分 block 提早耗盡 P/E cycle 的問題？

5. GC 的 victim selection 和 wear leveling 的目標可能會衝突。請描述一個具體的情境，說明 SSD 韌體在這兩個目標之間需要做什麼取捨。