Garbage Collection and Where Write Amplification Comes From

Every write to a flash device consumes a free page, and no write returns a page to the free pool. The only operation that creates free pages is erasing a block, and a block can be erased only when none of its pages is still referenced by the mapping table. Reclaiming a block therefore requires moving its live pages somewhere else, which costs writes. Garbage collection is the accounting and scheduling of that cost, and write amplification is the number that measures how badly the accounting is going.

The invariant

Define the device’s physical capacity in pages as C, the number of pages currently holding live data as L, and the number of free pages as F, so that C = L + F plus the pages in blocks currently being erased or written. Over-provisioning is the difference between the device’s physical capacity and the logical capacity it advertises to the host; a drive with 256 GiB of NAND presenting 240 GiB of logical capacity has roughly 6 percent over-provisioning, and the host can never fill L to C.

Garbage collection operates on a block with u valid pages out of n pages per block. To erase it, the collector must copy u pages to free space and then erase the block, gaining n free pages minus the u it just consumed elsewhere. The net gain is n − u free pages, and the cost is u writes.

Write amplification WA is bytes programmed to the medium divided by bytes requested by the host. Host writes fill pages; the collector’s copies also fill pages. In steady state, every host page written eventually becomes invalid and must be reclaimed, so the total program traffic per host page is 1 + (copies per host page). If the collector always picks a block with u valid pages, the copies per reclaimed block are u and the free pages gained are n − u, so the copying per unit of free space produced is u/(n − u). Host writes consume free space at one page each. In equilibrium:

$$ WA = \frac{1}{1 - u/n} $$

with u/n the fraction of valid pages in the blocks being reclaimed. A collector that reclaims blocks that are 25 percent valid copies one page per three gained and reaches WA = 1.33. At 50 percent valid, WA = 2. At 80 percent valid, WA = 5. The relation is the whole economics of the device in one line: amplification is governed by how empty the victim blocks are, and how empty they can be is governed by how much free space the drive has to work with.

The reason over-provisioning matters follows directly. A drive whose logical capacity equals its physical capacity has, when full, no free pages at all, and the collector must reclaim blocks that are nearly all valid. A drive with 7 percent over-provisioning keeps about 7 percent of its pages free at full host capacity, and the collector can choose among blocks whose valid fraction is bounded away from 1. Vendors quote endurance against a stated over-provisioning level for this reason; the same NAND with more reserved space lasts longer under the same host workload.

Choosing a victim

The greedy choice, lowest valid count first, is optimal for a single collection step and is what most controllers approximate with a small sample. Sampling a handful of candidate blocks and picking the emptiest is cheap and close to the greedy optimum, and the cost of scanning every block’s valid count is avoided by keeping the count in the block’s metadata, updated as pages are invalidated.

Greedy has a failure mode. It always reclaims the coldest blocks, which are the ones holding data that has not been rewritten and probably will not be. The blocks holding hot data, which are constantly being rewritten and are therefore the emptiest, get reclaimed immediately and then filled again. The result is that cold data is copied repeatedly while hot data is copied once. Age-aware policies weigh the time since a block was last written against its valid count, preferring to reclaim blocks whose live pages are old enough that they are unlikely to be invalidated soon after being copied. Copying a page that will be invalidated a second later is pure waste, and only the age signal distinguishes that page from one that will live for months. The same reasoning governs how the controller distributes erases across the device, which is the wear leveling problem.

A second refinement separates data by update frequency. If the controller writes incoming data into blocks grouped by expected lifetime, then blocks holding cold data accumulate few invalid pages and can be left alone, while blocks holding hot data become almost entirely invalid and are cheap to reclaim. This is the same insight the log-structured filesystem applies at the filesystem level, where it is called hot/cold data separation, and the effect on amplification is larger than any improvement in victim selection.

Foreground and background collection

Collection triggered by a host write is foreground collection: the write cannot complete until free space exists, so the copy traffic is on the critical path and the host sees the latency. Collection done when the drive is otherwise idle is background collection, which spends the device’s idle time and hides the copy cost entirely. A controller that can keep enough free space ahead of the host runs almost entirely in the background; one that cannot has host writes serialized behind erases.

The latency of a foreground collection is not the copy traffic alone but the erase. An erase operation takes on the order of a millisecond to several milliseconds depending on the part, against a page program in the tens of microseconds and a page read in the tens of microseconds. An erase cannot be interrupted, and the die performing it is unavailable for the duration. A write that arrives when all dies are erasing waits for one to finish. This is why steady-state write latency on a nearly full drive is not the same distribution as on an empty one, and why sustained random write throughput on a consumer drive degrades once its free pool is exhausted and recovers only after idle time.

struct block_meta {
    uint32_t valid_pages;
    uint64_t last_write_ns;   /* age signal for the victim policy */
    uint8_t  erase_count;     /* coarse; see wear leveling */
};

/* Pick the reclaim victim: cheapest copy cost, with an age tiebreak.
 * The block table is the collector's own bookkeeping. */
static struct block_meta *pick_victim(struct block_meta *blocks, size_t n)
{
    struct block_meta *best = NULL;
    for (size_t i = 0; i < n; i++) {
        struct block_meta *b = &blocks[i];
        if (b->valid_pages == 0) return b;          /* free erase, no copying */
        if (!best) { best = b; continue; }
        if (b->valid_pages < best->valid_pages ||
            (b->valid_pages == best->valid_pages &&
             b->last_write_ns < best->last_write_ns))
            best = b;
    }
    return best;
}

The zero-valid case is worth calling out because it is the one case where collection costs nothing beyond the erase. A collector that can keep a supply of fully invalid blocks has amplification of exactly 1 for the pages it reclaims. The difficulty is producing them: they arise from sequential overwrites of whole blocks, which is to say from workloads whose writes are larger than an erase block and aligned to it.

Alignment and the amplification multiplier

A host write that does not cover a whole erase block cannot invalidate a whole erase block. Writing 4 KiB into a block that holds 256 other pages leaves those 256 valid, and if the workload rewrites that same 4 KiB repeatedly, each write invalidates one page and leaves 255. The collector then copies 255 pages to reclaim 1 useful free page, and the measured amplification for that workload is bounded by the block size divided by the write size. On a 1 MiB block and a 4 KiB write that bound is 256, independent of any victim policy, because the policy has no emptier block to choose.

This is not a theoretical worst case. Random 4 KiB overwrites of a small region are the standard stress workload for exactly this reason, and drives quote sustained random write performance far below their sequential figure. The filesystem can avoid it by allocating and rewriting in larger, aligned units, by writing sequentially, and by telling the device which regions are free, which is what discard does.

Where the model stops

The steady-state formula assumes uniform random writes over the whole logical address space and a collector that can always find a block at the average valid fraction. Real workloads are skewed: a small set of addresses receives most of the writes, and those addresses’ blocks are easy to reclaim while the rest are not touched at all. Amplification measured over a skewed workload can be far below the formula, which is why a drive’s endurance rating depends on the workload definition rather than the capacity alone.

The model also ignores the interaction with error correction and retention. A block that has been erased many times, or one whose neighbours were programmed with a disturb-inducing pattern, may return read errors and need relocation even though its pages are still valid. That relocation is another source of unrequested writes, and it is proportional to the medium’s condition rather than to the host’s behaviour. Both effects mean the amplification a host observes can exceed what the space accounting predicts, and neither is visible from the logical block interface. The one lever the host holds directly is free-space signalling, and it is the next mechanism in the cluster. A more drastic answer is to remove the device-side collector altogether and give the placement decision to the host, which is what zoned block devices do; the copy cost does not disappear, it moves.