CSE Roadmap

Common tier · about 3 hours · 7 parts

Part 4 of 7 · 3 min read

Cleaning

Think of a notebook where each correction goes on a new page. After a while, most pages are crossed out, and a few lines on each are still good. To get a clean page back, you copy the good lines to a new page and discard the old one. The analogy stops in one place: a notebook has an unlimited supply of paper, while a disk is fixed in size.

In plain words: When data is overwritten or deleted, the old copy in an earlier segment becomes dead. To reuse a segment, the cleaner reads it, copies the blocks that are still live to the end of the log, and then frees the whole segment. If a share u of the segment is still live, then cleaning reads one segment, writes u of a segment of live data, and so frees (1 - u) of a segment. The new data then fills that free space, which costs (1 - u) of a segment of writes. In total, to write (1 - u) segments of new data, the system reads 1 and writes u + (1 - u) = 1 segment, which is 2 segments of I/O. The write cost is 2 / (1 - u) segments of I/O for each segment of new data.

A worked example. The table gives the cost for four values of u (made up to show the idea).

Live share u Write cost 2 / (1 - u)
0.2 2.5
0.5 4.0
0.8 10.0
0.9 20.0

If the segments that the cleaner picks are half live, every byte of new data costs the I/O of 4 bytes. If they are 90% live, the cost is 20. The system therefore wants to clean segments that are mostly dead. Files that are deleted or rewritten at about the same time make such segments, and a workload that spreads changes evenly makes them rare.

The key lines. Compare with page 3 of Level 8. A flash drive collecting a block with a live share u has a write amplification of 1 / (1 - u), which counts only the writes. The LFS formula has a factor 2 because it also counts the reads of the segment that is cleaned. Both come from the same idea, never overwrite, and both depend on how empty the victims are. This is also why the cleaner prefers cold segments, the ones that will not be changed soon.

Segment cleaning

Segment cleaning is the process by which a log-structured file system reclaims space. It reads a segment, copies the still-live blocks to the end of the log, and marks the whole segment free. Its cost grows quickly as the live share of the cleaned segments approaches 1.

Example: cleaning a segment that is 50% live costs a write cost of 4: four segments of I/O for each segment of new data.

Check yourself: 1. What is the write cost when u = 0.5? 2. Why does the cleaner prefer segments with little live data? 3. Why is the LFS formula 2 / (1 - u) and the flash formula 1 / (1 - u)?