Why Do SSDs Need Garbage Collection Before Overwriting?

NAND flash solid-state drives cannot overwrite existing data in place due to the physical and electrical properties of floating-gate and charge-trap transistors. Instead, drives must write new data to empty pages, mark old pages as invalid, and rely on garbage collection to consolidate valid data and erase entire blocks before those physical locations can be reused.

The Physics of NAND Flash Memory

NAND flash stores data by trapping electrons inside an insulated floating gate or charge-trap layer. The presence or absence of electrons shifts the transistor's threshold voltage, which the drive reads as binary values.

Programming a cell (typically changing a bit from \(1\) to \(0\)) requires applying a high positive voltage to the control gate, which pulls electrons into the floating gate via Fowler-Nordheim tunneling or hot-electron injection. However, removing those electrons to reset a cell back to \(1\) requires applying a high voltage in the opposite direction to the substrate. Because of how NAND flash arrays are wired, this erase voltage cannot be applied to a single bit or a single page; it must be applied to an entire block at once.

Pages vs. Blocks: The Read-Write-Erase Asymmetry

NAND flash memory is organized into a strict hierarchy that creates an asymmetry between reading, writing, and erasing:

  • Pages: The smallest unit that can be read or programmed (written), typically \(4\text{ KB}\) to \(16\text{ KB}\) in size.
  • Blocks: Groups of dozens or hundreds of pages, typically \(128\) to \(512\) pages per block, totaling several megabytes. A block is the smallest unit that can be erased.

Because you can program individual pages but must erase entire blocks, an SSD cannot simply overwrite a single \(4\text{ KB}\) page with new data. If a page already contains programmed bits (\(0\)s), attempting to program it again without erasing can only turn remaining \(1\)s into \(0\)s—it cannot turn \(0\)s back into \(1\)s.

Out-of-Place Writes and the Flash Translation Layer

To hide this hardware limitation from the operating system, SSDs use an internal controller running a Flash Translation Layer (FTL). The FTL maintains a mapping table that translates Logical Block Addresses (LBAs) used by the host computer into Physical Block Addresses (PBAs) on the NAND flash.

When the operating system modifies a file and requests an overwrite of an existing LBA, the SSD performs an out-of-place write:

  1. The controller writes the updated data to a different, already-erased physical page.
  2. The FTL updates its mapping table so the LBA points to the new physical page.
  3. The old physical page is marked as invalid (stale), meaning it still holds old charge patterns but is no longer referenced by the file system.

How Garbage Collection Works

Over time, out-of-place writes leave blocks fragmented with a mix of valid pages (current data) and invalid pages (stale data). If the drive never cleaned up these blocks, it would eventually run out of empty pages to write to, even if the drive is not full of active user data.

Garbage collection resolves this by reclaiming space from partially invalid blocks:

  1. Block Selection: The SSD controller identifies a block containing a high ratio of invalid pages.
  2. Valid Data Migration: The controller reads the remaining valid pages from that block and writes them to empty pages in another block.
  3. Mapping Update: The FTL updates its address table to point to the new locations of the migrated pages.
  4. Block Erasure: Once all valid data has been moved out, the entire source block is erased, resetting all of its pages to the \(1\) state so they are ready for future writes.

Write Amplification and Performance Impact

Moving valid pages during garbage collection introduces write amplification, where the physical amount of data written to the NAND flash exceeds the amount of data the host computer actually requested to write. Write amplification can be expressed as:

\[\text{Write Amplification Factor (WAF)} = \frac{\text{Data Written to NAND Flash}}{\text{Data Written by Host}}\]

If a block is mostly full of valid data, garbage collection must copy many pages just to free up a few invalid ones, driving up the WAF. This extra internal activity consumes NAND bandwidth, increases latency for incoming host writes, and accelerates wear on the flash cells, which only survive a finite number of program/erase (P/E) cycles.

The Role of TRIM

Operating systems help reduce garbage collection overhead using the TRIM command (or UNMAP in SCSI/NVMe). When a user deletes a file, the OS normally just removes the file's entry from its own file system table without telling the SSD. Without TRIM, the SSD still considers those pages valid and will waste time copying them during garbage collection.

When TRIM is enabled, the OS notifies the SSD controller which LBAs are no longer in use. The controller immediately marks the corresponding physical pages as invalid, allowing garbage collection to skip copying them and erase the block more efficiently.