Flash Translation Layer

Fundamental theorem of software engineering:

"We can solve any problem by introducing an extra level of indirection."

你在手機上刪除一個 App，系統顯示多了 2 GB 可用空間。但在 NAND flash 的層面，那些資料並沒有被「清除」，舊的 page 還原封不動躺在那裡。你的手機用了半年之後，這種「已刪除但還佔著位置」的幽靈資料散落在整顆晶片上，SSD 內部的地址對照表已經被改寫了幾十萬次。負責管理這一切的就是 Flash Translation Layer（FTL）。它是 SSD controller 韌體中最核心的咚咚 ...

作業系統看到的是一排連續編號的 block device：LBA 0, 1, 2, 3, ...。它假設寫入 LBA 100 就是覆寫那個位置的資料。但 NAND flash 不能覆寫，只能寫到新的空白 page。這個矛盾就是 FTL 存在的原因。

為什麼需要 address translation

主機對 SSD 發出的指令都是以 LBA（Logical Block Address）為單位。但 NAND flash 內部的實體位置會不斷變動：同一筆資料可能因為 garbage collection 被搬到不同的 physical page。如果沒有 FTL，主機每次讀取都需要知道資料目前在哪個 physical page，這顯然不切實際。

FTL 維護一張 mapping table，記錄每個 LBA 對應到哪個 PBA（Physical Block Address，更準確地說是 physical page address）。主機寫入 LBA 100 時，FTL 找到一個空白的 physical page，把資料寫進去，然後更新 mapping table：LBA 100 現在指向新的 PBA。主機讀取 LBA 100 時，FTL 查表找到目前對應的 PBA，從那個 physical page 讀出資料。

Out-of-place write：寫入永遠找新位置

這是 FTL 運作的核心原則。當主機要更新 LBA 100 的資料時，FTL 不會去找 LBA 100 目前對應的 physical page 然後覆寫它（因為 NAND flash 不允許）。取而代之的流程是：

從 free page pool 取得一個空白的 physical page
把新資料寫入這個 page
更新 mapping table：LBA 100 指向新的 PBA
將舊的 physical page 標記為 invalid

這個 invalid page 佔據的空間不會立刻被回收，而是等 garbage collection 來處理。這也是為什麼 SSD 用了一段時間後，NAND flash 上會散佈大量 invalid page。

out-of-place write 有一個重要的副作用：不管你寫的是 sequential write 還是 random write，在 NAND flash 層面都變成了 sequential write（因為每次都寫到下一個空白 page）。這就是為什麼 SSD 的 random write 效能遠優於 HDD。HDD 的 random write 需要 seek，但 SSD 的「random write」其實在物理上是 sequential 的。

Page-level mapping vs block-level mapping

Mapping table 的粒度是 FTL 設計中最關鍵的取捨。

Page-level mapping：每個 logical page 獨立映射到一個 physical page。

優點：完全的靈活性。任何 LBA 可以映射到任何 physical page，random write 效能最好。
缺點：mapping table 巨大。以一顆 1 TB SSD 為例，假設 page size 為 4 KB，共有 1 TB / 4 KB = 256M 個 page。每個 entry 需要 4 bytes（32-bit PBA），mapping table 總共需要 256M x 4 bytes = 1 GB 的 SRAM。SRAM 極其昂貴，1 GB 的 SRAM 成本可能比 SSD 本身還高。

Block-level mapping：以 block 為單位做映射。一個 logical block 內的所有 page 按照 offset 對應到 physical block 內的相同 offset。

優點：mapping table 極小。如果每個 block 有 256 個 page，table 只需要 256M / 256 = 1M 個 entry，約 4 MB 的 SRAM。
缺點：靈活性極差。如果你只更新 block 內的一個 page，必須把整個 block 的有效資料讀出來，寫到新的 block，再更新 mapping。這等於把 random write 變成了整個 block 的 read-modify-write，效能很差。

這裡有一個數字值得記住：page-level mapping 的 SRAM 需求大約是 SSD 容量的 0.1%。1 TB 的 SSD 需要約 1 GB 的 mapping table。這個比例隨著 SSD 容量增長而線性增加，但 SRAM 的價格和面積限制讓它不可能無限擴大。

DFTL 與混合式 mapping

既然 page-level 太貴，block-level 太慢，實際的 SSD 怎麼做？答案是 hybrid 方案，其中最具代表性的是 DFTL（Demand-based FTL）。

DFTL 的核心想法借鑑了 virtual memory 的 demand paging：

完整的 page-level mapping table 存在 NAND flash 上（稱為 Global Translation Directory）。容量不是問題，因為 NAND flash 很便宜。
SRAM 中只快取一部分 mapping entry（稱為 Cached Mapping Table, CMT）。典型大小可能只有幾 MB。
當主機存取一個 LBA 時，先查 CMT。如果 hit，直接使用。如果 miss，就從 NAND flash 上的 translation page 讀入這個 entry（類似 page fault）。
CMT 滿了就用 LRU 之類的 eviction policy 淘汰不常用的 entry。如果被淘汰的 entry 有被修改過（dirty），需要寫回 NAND flash。

DFTL 的效能取決於 CMT hit rate。如果 workload 有良好的 locality（大多數存取集中在少數 LBA），CMT hit rate 高，效能接近 page-level mapping。但如果 workload 是完全 random 的，大量 CMT miss 會產生額外的 NAND flash 讀取（讀 translation page），嚴重影響效能。

除了 DFTL，還有其他混合策略。例如把 NAND flash 空間分成 data block 和 log block：data block 用 block-level mapping，random write 先寫到少量的 log block（用 page-level mapping），等 log block 滿了再 merge 回 data block。這類設計的目標都是一樣的：用有限的 SRAM 預算，在盡可能多的 workload pattern 下提供接近 page-level mapping 的效能。

Mapping table 的持久化

Mapping table 存在 SRAM 中代表它是 volatile 的。如果突然斷電，mapping table 就掰了，SSD 無法知道每個 LBA 的資料在哪裡。因此 FTL 必須有機制把 mapping table 持久化到 NAND flash 上。常見的做法包括：

定期把整張 table checkpoint 到 NAND flash
每次更新 mapping 時寫一筆 log，開機時 replay log 重建 table
結合以上兩種：定期 checkpoint + 增量 log

這也是為什麼 SSD 通常有一顆大電容（power-loss protection capacitor）：斷電時提供足夠的電力讓 controller 把 SRAM 中的 dirty mapping entry flush 到 NAND flash，確保不會掉資料。

自問自答

一顆 2 TB SSD，page size 為 16 KB。如果採用 page-level mapping 且每個 entry 佔 4 bytes，mapping table 需要多少 SRAM？如果改用 block-level mapping（每個 block 有 512 個 page），又需要多少？
為什麼 out-of-place write 讓 SSD 的 random write 在物理層面變成 sequential write？這個特性對 SSD 與 HDD 的效能差距有什麼影響？
DFTL 的 CMT miss 會導致什麼額外開銷？在什麼樣的 workload pattern 下，DFTL 的效能會明顯退化？
假設一個混合式 FTL 使用 log block 方案，當 log block 滿了需要與 data block merge 時，最壞情況下需要多少次 NAND flash 讀寫操作？請用具體的 block/page 數量來說明。
如果 SSD 沒有 power-loss protection，突然斷電後重新開機時會發生什麼事？FTL 如何恢復 mapping table 的一致性？