Solid-State Drives (SSDs)

A solid-state drive stores data in NAND flash memory, arrays of floating-gate or charge-trap transistors that retain charge without power. The smallest unit the controller can read or program (write) is a page, typically 4 KB, 8 KB, or 16 KB. Pages are grouped into blocks, typically 128 to 512 pages, and the block — not the page — is the smallest unit that can be erased. This asymmetry is the defining physical fact of flash: programming pushes electrons onto a floating gate one page at a time, but removing them (erasing) requires a high-voltage pulse applied to an entire block simultaneously, because the erase circuitry is wired at block granularity. The consequence is erase-before-write: a page holding stale data cannot simply be overwritten with new data. The controller must first erase the entire block containing that page — destroying every other page in it, live or not — before any page in it can be reprogrammed. Since erasing is roughly ten to a hundred times slower than programming, and a block may contain hundreds of live pages you do not want to lose, no drive erases on every write. Instead, the Flash Translation Layer (FTL) — firmware running on the SSD's embedded controller — intercepts every logical read/write request from the OS and translates it into physical NAND operations, always directing new writes to pre-erased pages elsewhere on the chip. This is called out-of-place update (or log-structured writing), and it is the single idea that makes flash usable as a general-purpose block device. The FTL maintains a mapping table (logical block address → physical page), tracks which pages are stale after each out-of-place update, and periodically runs garbage collection to reclaim blocks whose live pages have been relocated and whose stale pages can finally be erased. Because each flash cell degrades with every program/erase (P/E) cycle and eventually fails, the FTL also performs wear leveling, deliberately migrating data so that no block is erased far more often than any other.

The FTL sits between the host interface (SATA/NVMe queue of logical reads and writes) and the raw NAND chips. Four mechanisms cooperate:

1. Address mapping. The FTL keeps a table translating each logical page number (LPN) to a physical page number (PPN). Fine-grained (page-level) mapping gives maximum flexibility at the cost of table size (~4 bytes per 4 KB page, roughly 1 GB of RAM per 1 TB of flash for pure page mapping); most real drives use hybrid mapping — block-level mapping with a small per-block log of page offsets — to shrink this table.

2. Out-of-place write. A write to LPN L never overwrites the page currently holding L's data. The FTL picks a pre-erased page in the current "open" block, writes the new data there, updates the mapping table so L now points to the new PPN, and marks the old PPN invalid (stale).

3. Garbage collection (GC). Over time, blocks accumulate a mix of valid and invalid pages. When free (erased) space runs low, the FTL selects a victim block, copies its still-valid pages to a fresh location (updating the mapping table again), and then erases the victim block, returning it to the free pool.

4. Wear leveling. The FTL tracks an erase count per block and biases victim/target selection so that cold (rarely-updated) data occasionally migrates out of lightly-worn blocks and infrequently-erased blocks are preferentially reused, keeping P/E cycle counts roughly uniform across the chip. ``` // Simplified Flash Translation Layer State: map[LPN] -> PPN // logical-to-physical page table valid[PPN] -> boolean // is this physical page still live? eraseCount[block] -> integer // wear-leveling statistic freeList // erased blocks ready to receive writes openBlock // block currently accepting new page writes function WRITE(LPN, data): if map[LPN] exists: oldPPN = map[LPN] valid[oldPPN] = false // old copy becomes stale, NOT overwritten if openBlock has no free page: openBlock = ALLOCATE_BLOCK() // pull an erased block from freeList PPN = next free page in openBlock PROGRAM(PPN, data) // physical NAND program operation map[LPN] = PPN valid[PPN] = true if freeList.size() < LOW_WATERMARK: GARBAGE_COLLECT() function READ(LPN): PPN = map[LPN] return PHYSICAL_READ(PPN) function ALLOCATE_BLOCK(): if freeList.isEmpty(): GARBAGE_COLLECT() return freeList.popLowestEraseCount() // wear leveling: prefer lightly-erased blocks function GARBAGE_COLLECT(): victim = SELECT_VICTIM_BLOCK() // e.g. block minimizing valid-page count for each PPN in victim.pages: if valid[PPN]: newPPN = write live page's data via WRITE-style relocation map[ownerLPN(PPN)] = newPPN valid[newPPN] = true ERASE(victim) // block-granularity erase eraseCount[victim] += 1 freeList.push(victim) function SELECT_VICTIM_BLOCK(): // greedy: choose block with fewest valid pages (least copying cost) return argmin over blocks not in freeList of (count of valid pages in block) ``` The read path is straightforward: look up the mapping, read one physical page. The write path is where all the complexity lives, because every write can potentially trigger, as a side effect, a garbage-collection pass that itself performs additional reads, writes, and an erase — this cascading cost is exactly what "write amplification" measures.

Time complexity of the core operations. A read is O(1): one mapping-table lookup plus one physical page read (a NAND page read costs roughly 25–100 microseconds regardless of which page is read, unlike a rotational disk where physical location matters enormously). A write is amortized O(1) mapping-table work plus one page program (~200–500 microseconds), but garbage collection is triggered periodically and its cost must be amortized across writes: each GC pass copies v valid pages (a page read plus a page program each) and performs one block erase (~2–5 milliseconds), reclaiming (pages per block − v) free pages. If a drive maintains free-space invariant by running GC whenever free blocks drop below a watermark, the amortized extra cost per host write is proportional to the write amplification factor (WAF):

WAF is never less than 1 (every host write requires at least one physical program) and grows as the fraction of valid data relocated during GC grows. A drive kept nearly full, with data updated randomly in small chunks, forces GC to relocate many still-live pages per reclaimed block, driving WAF up toward 3–6× in adversarial workloads; a mostly-empty drive receiving sequential writes can approach WAF ≈ 1.

Space complexity. The mapping table for page-level FTL requires O(N) entries where N is the number of logical pages — for a 1 TB drive with 4 KB pages that is 2.56 × 10⁸ entries, each needing roughly 4 bytes (32-bit PPN), i.e. about 1 GB of controller RAM. Hybrid or block-level mapping reduces this to O(N / pages-per-block) primary entries plus small per-block logs, trading RAM for slightly slower address translation on sequential-update blocks. Over-provisioning — reserving a fraction (commonly 7–28%) of total flash capacity that the host never sees as usable LBAs — is what gives the GC algorithm slack: it guarantees a supply of erased blocks exists even under worst-case fragmentation, directly lowering the achievable WAF.

Correctness argument. The FTL must preserve two invariants under arbitrary interleavings of reads, writes, and power loss: 1. Mapping invariant — at all times, `map[L]` points to the most recently written physical copy of logical page L, or is undefined if L was never written. 2. No data loss on erase — a block is erased only after every page in it holding still-referenced (valid) data has been copied elsewhere and `map[]` updated to point at the copy, and that update is durably committed (e.g., logged in an out-of-band area or a separate mapping journal) before the erase proceeds. Out-of-place writing preserves invariant 1 trivially: a write never destroys the old copy until the mapping is repointed, so a crash mid-write leaves the old valid copy still reachable (the new copy is simply not yet referenced, so it is treated as garbage on recovery, not committed data — this is the same idea as Interrupts and DMA completion ordering, where a transfer is not "done" until its completion is acknowledged). Garbage collection preserves invariant 2 by construction: the algorithm explicitly copies every page marked `valid` before erasing, and marks a page invalid only after its logical owner has a newer copy recorded in the map. The correctness of wear leveling is a liveness property, not a safety property: it does not affect whether data is preserved, only whether the drive's useful lifetime is maximized, since a block that reaches its rated P/E-cycle limit is retired and its capacity lost.

Tradeoffs, honestly stated. SSDs remove the mechanical seek/rotation delay entirely, so random 4 KB reads that take 5–10 ms on a rotational disk take tens of microseconds on flash — three orders of magnitude faster, a real and important win. But they introduce three costs with no rotational-disk analogue: write amplification (extra physical writes beyond what the host requested), finite endurance (each cell tolerates a bounded number of P/E cycles, typically 1,000–100,000 depending on flash type), and background GC latency spikes (a foreground write can stall behind an in-progress erase). None of these costs exist on a spinning platter, which can be overwritten in place indefinitely.

Consider a toy SSD with blocks of 4 pages (real drives use hundreds; small numbers make the trace legible) and exactly 2 blocks total, B0 and B1, both initially erased. The host issues these logical writes in order: `W(L1)`, `W(L2)`, `W(L3)`, `W(L4)`, `W(L1)` again (an update), `W(L5)`.

At this point B0 has 3 valid pages (L2, L3, L4) and 1 stale page — no free pages remain in B0, and no block is fully erased except none, since B1 still has 2 free pages. Suppose the host now issues `W(L6)`, `W(L7)` filling B1 completely. All pages are now full and no free blocks remain, so the next write must trigger `ALLOCATE_BLOCK` → `GARBAGE_COLLECT`.

GC step. `SELECT_VICTIM_BLOCK` picks the block minimizing valid-page count. B0 has 3 valid pages (L2, L3, L4) and 1 stale; B1 has 4 valid pages and 0 stale. B0 is the cheaper victim (fewer pages to copy). The algorithm: 1. Copies L2, L3, L4 to a fresh already-erased target block B2 (obtained from the free list, or — since none exists yet — GC must have reserved at least one over-provisioned erased block for exactly this purpose). 2. Updates `map[L2] = B2.p0`, `map[L3] = B2.p1`, `map[L4] = B2.p2`. 3. Erases B0 entirely (all 4 pages, including the already-stale L1 copy) — this is the physically destructive, block-granular operation. 4. Increments `eraseCount[B0]` and returns B0 to the free list.

Write amplification for this GC pass: the host originally requested 7 writes (L1..L7, counting the L1 update once as one logical write event, twice as two physical programs since it's rewritten). The GC pass added 3 extra physical page programs (copying L2, L3, L4) that the host never asked for. If we count the total physical programs (8: L1 old + L2 + L3 + L4 + L1 new + L5 + L6 + L7, then +3 GC copies = 11) against host-requested logical writes (7), WAF for this trace is 11⁄7 ≈ 1.57 — illustrating concretely how "hot" overwritten data (L1) combined with a nearly-full drive forces GC to pay a real copying cost.

Every modern laptop, phone, and cloud server relies on an FTL running inside its storage device, invisible to the operating system's block layer. Data-center flash arrays run FTLs tuned for enormous over-provisioning and aggressive wear leveling because they sustain write-heavy database and log workloads around the clock. NVMe SSDs expose many parallel command queues so the OS can issue thousands of concurrent I/Os, exploiting the fact that flash chips, unlike a single spinning platter, can service many reads and writes to different chips simultaneously — a property that reshapes how the OS scheduler and interrupt/DMA completion paths (see Interrupts and DMA) are designed for storage. File systems increasingly issue TRIM/discard commands to tell the FTL which logical pages are no longer needed, directly reducing garbage-collection work and write amplification — a cooperation between OS and device that has no equivalent on rotational media and motivates SSD-aware choices in Allocation Methods for File Storage and log-structured or copy-on-write designs discussed under File-System Implementation and Layout. Databases favor log-structured merge trees partly because their append-mostly write pattern naturally matches how the FTL itself already prefers to receive data.

Ask the tutor: How does the choice of victim-block selection policy in garbage collection (e.g., greedy least-valid-pages vs. cost-benefit heuristics) actually change the achievable write amplification under realistic workloads?