Decomposing Write Amplification in Log-Structured Filesystems

Write amplification is the ratio of bytes the device must write to bytes the application asked to store. In a log-structured filesystem the ratio is never one, and the reasons are distinct enough to be counted separately. Treating the total as a single number hides which part is a design choice, which part is a consequence of the workload, and which part is a fixed tax that can only be reduced by changing the segment geometry.

The decomposition below uses a volume with segment size S, block size B, steady-state live fraction u across reclaimable segments, and an application write rate W. The live fraction is the collector’s central input rather than a constant, and maintaining it exactly is treated in Segment Liveness Accounting.

Term one: cleaning copies

The collector must copy the live contents of every segment it frees. In steady state, space is reclaimed at exactly the rate it is consumed, so the number of segments cleaned per unit of time equals the number of segments written. If a fraction u of each cleaned segment is live, cleaning writes u·S bytes for every segment freed, and the foreground writes S bytes into each new segment.

So per byte of foreground data, cleaning contributes u / (1 − u) additional bytes. At u = 0.5 that is one extra byte per byte written; at u = 0.8 it is four. This is the dominant term, and it is the one that responds to placement policy rather than to any constant in the code. Which segments the collector chooses, and therefore what value of u it faces, is the subject of Choosing What to Clean.

The formula also shows why u cannot be allowed to approach one. A volume at u = 0.95 writes nineteen bytes for every byte of user data, which exceeds the endurance budget of any flash device and the bandwidth budget of any disk. The system does not fail cleanly at that point; it simply slows until the write rate matches the available bandwidth, and the free-space level stops moving. The design target is usually to keep u low enough that cleaning contributes less than one additional byte per byte, which means u below about 0.5.

Term two: checkpoints

Every checkpoint rewrites the inode map index and the segment usage table. Both scale with the volume, not with the write rate: the index has one entry per map block, and the usage table has one record per segment. Let C be the checkpoint size and T the interval between checkpoints. The contribution is C / (W·T) bytes per byte written.

The shape of that expression is worth noting. A larger volume makes C larger, so the same interval costs more; a higher write rate makes W·T larger, so the same interval costs less. A checkpoint interval tuned for a slow workload is wasteful on a fast one, and a volume that grows without the interval being adjusted develops a checkpoint tax that was not present when it was smaller.

For a volume of a few hundred gigabytes with a checkpoint in the low megabytes and an interval of tens of seconds, the term is small, on the order of a few thousandths of a byte per byte at a sustained rate of tens of megabytes per second. It becomes visible when the write rate is low, because the checkpoint keeps being written whether or not anything else is happening. An idle filesystem still writes checkpoints if the interval is a timer rather than a dirty-state trigger, and that is pure cost with no benefit.

Term three: summaries and headers

Every segment carries a summary block describing its contents, and every block may carry a small header identifying its kind and owner. The summary is one block per segment, so its contribution is B / S: with 4 KiB blocks and 1 MiB segments that is one part in 256, or under 0.4 percent. Per-block headers of eight or sixteen bytes on 4 KiB blocks cost 0.2 to 0.4 percent.

These are the smallest terms and the easiest to overlook, and they are the ones that scale badly if the geometry is chosen poorly. A filesystem using 256 KiB segments pays four times the summary overhead of one using 1 MiB segments, and a filesystem using 512-byte blocks pays eight times the header overhead of one using 4 KiB blocks. Neither cost is large in absolute terms, but both are unconditional: they are paid even for a workload that never triggers cleaning, unlike the first term.

Term four: slack at segment boundaries

Segments are written as whole units. If the buffer that fills a segment runs dry before the segment is full, the filesystem has three options: write the partial segment and waste the remainder, hold the segment open and delay durability, or pad it with something useful.

Writing a partial segment wastes (S − filled) / S of the segment’s capacity, and that waste is charged against the volume’s usable space rather than against the write bandwidth. The effect on write amplification is indirect but real: wasted space lowers the effective capacity, which raises the live fraction u for a given amount of data, which raises the first term.

Holding segments open avoids the waste but converts it into a durability delay and into memory pressure, since the unfilled buffer cannot be reused. The original design kept a small number of segments open, one per write stream, and closed them when a timer expired even if they were not full. That is the standard compromise: bounded waste, bounded delay, and the number of streams bounded so that the waste is bounded too.

The padding option is to write dead blocks deliberately, which is what some designs do when a segment must be closed early: fill the remainder with a known-invalid pattern so that the segment’s summary accounts for the space and the cleaner can treat the padding as immediately dead. This does not reduce the write cost, since the bytes are still written, but it keeps the accounting honest and avoids a special case in the cleaner.

Adding the terms, and what dominates

The total is

A = 1 + u/(1-u) + C/(W*T) + B/S + h/B + slack

where h is the per-block header size and slack is the fraction of segment capacity wasted at boundaries. The leading one is the user’s data itself.

At u = 0.4, S = 1 MiB, B = 4 KiB, h = 16 bytes, and a checkpoint term of 0.005, the sum is roughly 1 + 0.67 + 0.005 + 0.004 + 0.004 ≈ 1.68. The cleaning term is over fifty times everything else combined. That ratio is the central fact about log-structured write cost: geometry choices and checkpoint tuning move the total by a fraction of a percent, while the live fraction moves it by multiples.

/* Amplification estimate; all inputs are ratios except sizes in bytes. */
static double amplification(double u, double ckpt_bytes, double write_rate,
                            double interval, double seg, double blk, double hdr)
{
    double clean = u / (1.0 - u);                 /* dominant term */
    double ckpt  = ckpt_bytes / (write_rate * interval);
    double sumry = blk / seg;                     /* one summary block per segment */
    double hdrs  = hdr / blk;                     /* per-block header */
    return 1.0 + clean + ckpt + sumry + hdrs;
}

Why the naive comparison with journaling misleads

A journaling filesystem is often described as writing everything twice, and a log-structured filesystem as writing everything once. Both descriptions are wrong in opposite directions.

Journaling writes metadata twice and data once in the common ordered mode, so its amplification for a metadata-heavy workload approaches two and for a data-heavy one approaches one. It has no collector, so it has no u term, and its amplification does not depend on how full the volume is.

The log-structured filesystem writes everything once in the foreground, then writes a fraction of it again during cleaning. On a volume with low utilization and a workload that rewrites data quickly, the second write is small and the total is close to one. On a full volume with long-lived data, the total can exceed two and keep climbing. So the comparison depends entirely on the fill level, which the single-number framing conceals.

The endurance consequence

On flash, each device page can be programmed a limited number of times, and the amplification multiplies the program count the workload imposes. A workload writing a terabyte per year at amplification 1.7 consumes 1.7 terabytes of program budget, and the device’s rated endurance is expressed in total bytes written rather than in bytes stored. This is why the cleaner’s efficiency is a reliability parameter and not merely a performance one, and why collectors are usually tuned to a free-space target rather than to a fixed cleaning rate.

The relationship also explains a counterintuitive behavior: adding capacity to a log-structured volume can reduce its write amplification more than proportionally, because a larger volume lowers the steady state u for the same data set. The benefit comes from having more room to let garbage accumulate before it must be reclaimed, not from the extra bandwidth.

The terms above are the complete accounting for the foreground-plus-cleaner path. What they do not capture is when the writes happen, which matters as much as how many there are: a collector that issues its copies during a foreground burst competes for the same queue, and the latency consequence is the subject of Cleaner Interference and Foreground Latency.