Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 44, Arpaci-Dusseau & Arpaci-Dusseau

Flash-based SSDs

Solid-state storage has no moving parts — NAND flash transistors that retain charge across power loss. Fujio Masuoka’s flash (1980s) has quirks that make SSD design hard:

Crux: how to build a flash SSD despite expensive erase and wear out from repeated program/erase?

Raw flash: bits → pages → blocks​

Term (flash)Typical sizeRole
Cell1–3 bits (SLC / MLC / TLC)Charge level encodes value
Page~2–4 KBUnit of read / program
Erase block~128–256 KBUnit of erase (many pages)

Ops

  • Read(page) — tens of μs, roughly location-independent (true random access vs disk)
  • Erase(block) — milliseconds; sets bits to 1; destroys all pages in the block
  • Program(page) — ~100s μs; can only change 1→0 after erase; once VALID, must erase block to rewrite

States: INVALID → erase → ERASED → program → VALID. You cannot re-program a VALID page in place.

Quiz

Rank the sequence

1 / 1

Order a flash page’s lifecycle from unwritten to holding data, then back (top = first).

OrderDrag the handle to rearrange — top should be first.

  1. 1Program the page
  2. 2ERASED (bits set to 1, ready to program)
  3. 3VALID (holds programmed data)
  4. 4Erase the containing block
  5. 5INVALID / stale (overwritten logically, still physically VALID until reclaimed)

Drag items into the correct order (or use ↑↓), then check.

Reliability: wear out (~10k P/E MLC, ~100k SLC); read/program disturb on neighbors. Program pages low→high within a block to reduce disturb.

From chips to a block device: the FTL​

An SSD exposes a normal logical block interface. Internally: flash chips + SRAM (cache/maps) + controller. The flash translation layer (FTL) maps client reads/writes to read/erase/program, aiming for:

  • Low write amplification (bytes written to flash / bytes from client)
  • Wear leveling (spread P/E across blocks)
  • Parallelism across chips

Direct-mapped FTL (bad)​

Logical N ↔ physical N. Every write: read whole erase block, erase, reprogram → terrible amp and hot-spot wear. Don’t do this.

Log-structured FTL (common)​

Append each write to the next free page; update an in-memory LBA → physical map. Erases happen when opening a new block; overwrites leave garbage.

Garbage collection: find blocks with dead pages, relocate live pages to the log, erase the old block. Ideal reclaim target: all-dead. Overprovisioning delays GC and hides cleaning bandwidth.

Quiz

Rank the sequence

1 / 1

Order the steps of FTL garbage collection on a block (top = first).

OrderDrag the handle to rearrange — top should be first.

  1. 1Find a block with dead (stale) pages
  2. 2Erase the reclaimed block
  3. 3Relocate any still-live pages by appending them to the log
  4. 4Mark the block free for future writes

Drag items into the correct order (or use ↑↓), then check.

TRIM: host tells the device LBAs are unused → drop maps, reclaim earlier.

Map persistence: OOB metadata per page (slow full scan on boot) or logging/checkpoints (faster recovery).

Mapping table size​

Page-level maps need too much DRAM (e.g. ~1 GB for 1 TB @ 4 KB). Options:

SchemeMemoryWrite pain
Page mapHugeFlexible
Block mapSmallSmall write → copy whole block
HybridLog blocks page-mapped; data blocks block-mappedSwitch / partial / full merges
Cached page map (DFTL)Only hot entriesMisses cost extra flash I/O

Wear leveling​

Log + GC help, but cold long-lived data never frees its block. FTL must periodically migrate cold live data so every block gets write traffic — more write amp for fairness.

Performance vs cost​

SSDs crush HDDs on random IOPS; sequential gap is smaller. Log FTLs turn random client writes into sequential flash programs. HDDs still win $/GB → hybrid “hot on SSD, cold on disk” tiers remain common.

Interactive​

Try: raw ops · bad direct FTL · log FTL + GC · mapping schemes · wear/cost.

Check your understanding​

Quiz

Flash-based SSDs

1 / 6

Before programming a flash page that was already written, the device must…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: ssd.py​

Use the OSTEP file-ssd homework (ssd.py).

Lab

Homework: ssd.py

0/3 started

Loading lab…

Summary​

IdeaTakeaway
Erase before programPage write ≠ disk overwrite
FTLBlock API atop weird flash ops
Log FTLAppend + map; GC + TRIM + wear leveling
Map spaceHybrid or cached page maps
MarketSSD for latency/IOPS; HDD for $/GB

Previous: Log-structured File Systems

Next: Data Integrity — LSEs, checksums, scrubbing.

Further Reading​