§43.9–43.13LFS Garbage Collection, Recovery, and Summary

Efficient sequential writes have a cost: LFS keeps writing new versions and leaves the old ones behind as garbage.

43.9 A New Problem: Garbage

Because LFS never overwrites in place, old versions of blocks and inodes pile up across the disk. Whether an old block is dead depends on the operation:

You could keep the old versions and let users restore them — that’s a versioning file system versioning file system A file system that keeps old versions of files rather than reclaiming them — letting users restore accidentally overwritten or deleted data. LFS could be one (the old versions are already there as 'garbage'); NetApp's WAFL turns LFS's cleaning problem into this feature via snapshots. defined in ch. 43 — open in glossary (NetApp’s WAFL does this via snapshots). But LFS keeps only the latest live version, so a background cleaner must reclaim the dead space. Crucially, cleaning works segment-by-segment — freeing whole segments so there’s always a big contiguous region for the next sequential write:

This cleaning cleaning LFS's garbage collection: since LFS never overwrites in place, old (dead) versions of blocks/inodes accumulate as garbage. The cleaner works segment-by-segment — reading M partly-dead segments, keeping only the live blocks, and writing them into N < M new segments — freeing whole segments for future sequential writes. defined in ch. 43 — open in glossary raises two questions: a mechanism (which blocks are live?) and a policy (when and what to clean?).

43.10 Mechanism: Determining Liveness

To tell live from dead, LFS records — at the head of each segment, in a segment summary block segment summary block A small structure at the head of each LFS segment recording, for every data block in the segment, which file (inode number) and offset it belongs to. Cleaning uses it to test liveness: a block at address A is live iff, following its (inode#, offset) through the imap and inode, the inode's pointer still equals A. defined in ch. 43 — open in glossary — the (inode number, offset) of every data block. A block at address A is live iff, following that inode through the imap, the inode’s pointer still equals A:

(N, T) = SegmentSummary[A];   // block at A belongs to file N, offset T
inode  = Read(imap[N]);        // find that file's current inode
if (inode[T] == A)
    // block at A is LIVE  (the inode still points here)
else
    // block at A is dead  (the inode moved on)

(A shortcut: on truncate/delete, LFS bumps a version number in the imap and records it in the segment, so a version mismatch flags whole dead blocks without the full check.)

43.11 Policy: When and What To Clean

When is easy — periodically, when idle, or when the disk fills. What is harder: the original paper segregates hot segments (rapidly over-written — wait, since more blocks will soon die on their own) from cold ones (mostly stable — clean sooner). Getting this right has been the subject of much research.

43.12 Crash Recovery

What if a crash hits mid-write? LFS organizes its segments as a log, with the checkpoint region pointing at the log’s head and tail. Two hazards:

• A torn CR write. LFS keeps two checkpoint regions (one at each end of the disk), written alternately, each with a timestamped header and footer. A crash mid-update leaves mismatched timestamps, so recovery just uses the most recent consistent CR.
• Lost recent writes. Since the CR is only written ~every 30 s, a plain recovery would lose the last many seconds. So LFS rolls forward:

Roll forward roll forward An LFS crash-recovery technique (from databases): after reading the last checkpoint region, start at the end of the log it records and scan forward through the following segments, applying any valid updates written since the last checkpoint — recovering data that would otherwise be lost between periodic CR writes. defined in ch. 43 — open in glossary starts from the last checkpoint, finds the end of the log it recorded, and scans forward through the following segments, applying any valid updates — recovering most of the data written since the last checkpoint.

43.13 Summary

LFS never overwrites in place: it gathers updates into large in-memory segments and writes them sequentially to unused space — a form of copy-on-write copy-on-write COW (from TENEX): to 'copy' a page, map it read-only into both address spaces; only when someone writes does a trap allocate a real private copy. Makes fork()+exec() affordable and shared libraries cheap. defined in ch. 23 — open in glossary (shadow paging). This makes writes excellent on disks, on parity RAID (it sidesteps the small-write problem entirely), and even on flash SSDs. The price is garbage and the complexity of cleaning — which limited LFS’s initial impact, but whose ideas live on in WAFL, ZFS, and btrfs.