Log-structuring made the FTL fast, but — exactly as with LFS — it brings two costs: garbage, and a big mapping table.
44.8 Garbage Collection
Overwriting a logical block writes a new page and leaves the old one as garbage. The FTL runs garbage collection garbage collection Reclaiming dead pages left behind by a log-structured device/FS: find a block with garbage (overwritten) pages, copy its still-live pages elsewhere, then erase the block for reuse. In SSDs it's a key FTL job (the FS-level version is LFS cleaning). It adds write amplification, mitigated by overprovisioning. defined in ch. 44 — open in glossary to reclaim it: find a block with dead pages, copy its still-live pages to the log, then erase the block:
1After overwriting 100 and 101
Logical blocks 100 and 101 were rewritten (c1, c2) into block 1 (pages 4, 5). Their OLD copies (a1, a2 at pages 0, 1) are now garbage — valid on the flash, but no longer pointed to by the map.
The ideal victim is a block that is entirely dead — it can be erased with no data migration at all. Two things help:
Aside: The trim Command
Because a log-structured SSD keeps a flexible logical→physical map, it helps to know when a block is truly unneeded. The trim trim A storage command by which the file system tells the SSD that a block range is no longer in use (e.g. after a delete). Because a log-structured FTL keeps a flexible logical→physical map, knowing a block is dead lets it drop the mapping and reclaim the space in garbage collection — a case of the implementation shaping the interface. defined in ch. 44 — open in glossary command lets the file system tell the SSD “this block range is deleted” — so the FTL can drop the mapping and reclaim the space at GC time. Here the implementation (flexible mapping) shapes the interface (a new command).To cut GC’s cost further, SSDs use overprovisioning overprovisioning Building an SSD with more physical flash than its advertised capacity. The spare space lets garbage collection be delayed and run in the background (when the device is idle) and adds internal bandwidth for cleaning — reducing the performance hit of GC. defined in ch. 44 — open in glossary : build in more physical flash than the advertised capacity. The slack lets GC run lazily in the background (when the device is idle) and adds internal bandwidth for cleaning — so it barely dents the performance the client sees.
44.9 Mapping-Table Size
The second cost is memory. A page-level map needs one entry per 4 KB page — about 1 GB of RAM for a 1 TB SSD. Too much. The alternatives trade table size against write flexibility:
| mapping memory | write behavior | |
|---|---|---|
| page-level | one entry per PAGE — huge | fully flexible: any page anywhere; fast writes |
| block-level | one entry per BLOCK — tiny (÷ pages-per-block) | a sub-block ("small") write forces read-modify-write of the WHOLE block → high write amplification |
| hybrid | per-page log table (small) + per-block data table | flexible writes go to a few log blocks, merged back periodically |
| page-map + cache | cache only the hot mappings in RAM | great if the working set fits; a miss costs an extra flash read (and maybe a write) |
Block-level mapping (one pointer per block, like using bigger pages in VM) is compact but murders small writes — a write smaller than a block forces reading the whole block and rewriting it elsewhere.
The popular compromise is hybrid mapping hybrid mapping An FTL scheme that balances mapping-table size against write flexibility: keep a few erased log blocks with per-PAGE mappings (a small log table) for flexible writes, plus per-BLOCK mappings (a data table) for everything else. Log blocks are periodically merged back into block-mapped form — a switch merge (best), partial merge, or full merge (costliest). defined in ch. 44 — open in glossary : keep a few erased log blocks with per-page mappings (a small log table) for flexible writes, plus per-block mappings (a data table) for everything else. Reads check the log table first, then the data table. The trick is keeping log blocks few, so the FTL periodically merges them back into block-mapped form:
- switch merge (best): a log block was filled exactly like a data block, so it simply becomes one, replacing all its per-page pointers with a single block pointer — no copying.
- partial merge: only some pages were rewritten; the FTL reads the rest from the old block and appends them, then switches. Extra I/O.
- full merge (worst): the log block’s pages belong to many different data blocks; the FTL must gather scattered pages to rebuild each — lots of extra work, best avoided.
Check yourself: flash GC and mapping tables
1.In a log-structured FTL, what creates garbage, and what does garbage collection do about it?
2.How does the FTL decide whether a page is live or dead during GC?
3.Why does garbage collection contribute to write amplification?
4.What is the trim command, and why is it useful for SSDs?
5.Why is a pure page-level mapping table impractical, and why is pure block-level mapping also problematic?
6.How does hybrid mapping balance the two, and what is a switch merge?