Flash Translation Layers: Mapping Tables, Garbage Collection, and Write Cost

The host writes to logical block addresses and expects each one to hold the last thing written there. The flash array cannot honour that expectation directly: a page that has been programmed cannot be programmed again, and the only way to clear space is to erase a whole block. Between the two sits a table that says, for each logical address, which physical page currently holds its data. Everything else in a flash controller — garbage collection, wear levelling, over-provisioning, power-loss recovery — exists to keep that table consistent and to make the cost of maintaining it small.

Two mappings with very different table sizes

The simplest mapping is at block granularity. Logical block i maps to physical block j, and the offset within the block is preserved: logical page 3 of block i lives in physical page 3 of block j. The table has one entry per logical block, so a drive with a million blocks needs a million entries — a few megabytes at four bytes per entry, small enough to live in the controller’s SRAM.

The cost is on writes. Overwriting logical page 3 means the physical page 3 cannot be rewritten, so the controller must copy the other pages of the block somewhere, write the new page 3, and remap the block. That is a block-level read-modify-write for a single page, and for random writes it is catastrophic: every write moves a whole block. The classic mitigation is a log block — a spare block that receives the new pages while the original stays in place — but a log block can absorb only as many writes as it has pages, and when it fills, the merge is the same full-block copy.

Page-level mapping removes the offset constraint. Each logical page has its own entry pointing at any physical page, so an overwrite writes a fresh page anywhere and updates one entry. The table is now one entry per logical page: a terabyte of storage with 4 KiB pages has about 268 million entries, and at four bytes each the table is roughly a gibibyte. That does not fit in SRAM, so it lives in DRAM, and the DRAM cost is on the order of one gigabyte per terabyte of capacity — the term that dominates a page-mapped controller’s memory budget.

Hybrid designs split the difference: data blocks keep block-level mapping so their entries are cheap, while a small set of log blocks uses page-level mapping so that random overwrites are absorbed cheaply. The log blocks are merged into data blocks periodically, and the merge policy determines how much of the random-write benefit survives. Demand-based schemes go further and keep only a cache of hot mapping entries in SRAM, storing the full table on flash and fetching entries on a miss — trading a second indirection on cold accesses for a much smaller RAM requirement.

Garbage collection is a copying collector

Because pages are invalidated rather than freed, free space is created by copying the still-valid pages out of a block and erasing it. The unit of reclamation is a block, and the cost is the number of valid pages that must be moved.

A block with many invalid pages is cheap to reclaim; a block with few is expensive. The greedy policy, picking the block with the fewest valid pages, minimises the immediate copying cost. It also has a perverse long-run effect: blocks containing cold data, which never gets invalidated, are never selected, so they sit occupied forever while the hot region churns. That is acceptable for space, but it is bad for wear, because the blocks that are reclaimed repeatedly are the ones that wear out. Wear levelling therefore overrides the greedy choice periodically, forcing cold blocks to be relocated so that erases are spread across the whole array.

The copy-out has a second consequence: the pages being moved are written again, so the physical bytes written exceed the host bytes written. That ratio is write amplification, and it is the number that determines how long the drive lasts, because endurance is consumed per physical program, not per host write. The per-program cost itself — and the erase that must precede any reuse of a block — is described in page program and block erase.

The utilisation term

For a workload of uniformly random writes over the whole address space, with greedy victim selection and no over-provisioning, the steady-state write amplification is approximately 1/(1−u), where u is the fraction of the drive’s pages that hold valid data. The derivation is an occupancy argument: when a block is reclaimed, the expected fraction of its pages that are still valid equals u, so each host page written forces u/(1−u) pages of copying in the long run.

The formula is worth internalising because it makes the value of free space explicit. At 50 percent utilisation, amplification is about 2. At 80 percent it is about 5. At 90 percent it is about 10. The curve is not linear; the last ten percent of capacity costs as much endurance as the first fifty.

Over-provisioning is the deliberate withholding of capacity to keep u low. A drive that exposes 800 GiB of a 1 TiB array runs at a nominal 80 percent utilisation and can use the remainder as a working area for garbage collection, so the instantaneous utilisation during a collection cycle stays lower than the nominal figure. The same effect is available at the host level: a filesystem that keeps ten percent free is buying endurance it cannot otherwise recover, and a discard command that tells the controller which logical ranges are no longer in use lets the mapping table mark those pages invalid instead of preserving them as live data. Without that signal, a deleted file’s pages remain valid from the controller’s point of view, and the drive copies them during every collection cycle that touches their block.

# Steady-state write amplification for random writes under greedy collection.
def amplification(utilisation):
    return 1.0 / (1.0 - utilisation)

for pct in (50, 60, 70, 80, 90, 95):
    print(f"{pct:2d}% valid -> {amplification(pct/100):5.2f}x physical writes per host write")

# Bytes of endurance consumed by a workload, given host bytes and the drive's rating.
def endurance_years(host_tbw_per_year, wa, rated_pe, blocks, block_bytes):
    total = rated_pe * blocks * block_bytes
    return total / (host_tbw_per_year * 1e12 * wa)

The first function is the model; the second is the arithmetic a capacity planner needs. Neither accounts for sequential writes, which can achieve an amplification near 1 because a block’s pages are invalidated in the order they were written, so the victim block is entirely dead when it is reclaimed.

Sequential and random are different regimes

The 1/(1−u) model assumes random writes. A purely sequential write stream behaves very differently: pages are written in order, whole blocks are filled, and when the stream wraps around, the oldest block is entirely invalid and can be erased with no copying at all. Amplification approaches 1, and the drive’s endurance is consumed at exactly the rate the host writes.

Mixed workloads land in between, and the ratio of sequential to random traffic is often a better predictor of drive life than the total bytes written. It also explains why the same drive can carry very different endurance ratings depending on the workload class it is certified for: the rating is a statement about a workload model, not an intrinsic property of the silicon.

Keeping the table across a power cut

The mapping table is the drive’s only record of where data lives. If it is lost, the data is unreachable even though the pages still hold it. Page-level mapping changes on every write, so the controller cannot rewrite the whole table on each update; it journals the changes and checkpoints the table periodically. The journal entries must be ordered against the data writes they describe, or a crash can leave a mapping entry pointing at a page whose program never completed.

That ordering requirement is what makes power-loss protection a controller-level problem rather than a host-level one, and it is treated separately in power-loss protection and mapping table persistence. The relevant point here is that garbage collection multiplies the exposure: a collection cycle writes many pages and updates many entries, and a crash in the middle of a cycle leaves both the source and the destination blocks in partially valid states that recovery must reconcile.