Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 43, Arpaci-Dusseau & Arpaci-Dusseau

Log-structured File Systems

Berkeley LFS [RO91] (Rosenblum & Ousterhout) aims for write performance by turning updates into large sequential transfers.

Motivation

Bigger memories → more reads hit cache → disk traffic is write-heavy
Sequential bandwidth ≫ random (seeks/rotations lag transfer rates)
FFS still pays many small seeks for create/metadata updates
Classic FSes ignore RAID small-write pain (RAID-4/5)

Crux: how can a file system make all writes sequential?

Segments and write buffering

LFS buffers data and metadata in memory, then writes a segment (a few MB) to free space in one long I/O. It never overwrites in place (copy-on-write / shadow paging).

Sequential addresses alone aren’t enough — if you wait between block writes, the platter rotates. You need a large contiguous write to amortize positioning:

Reffective = D / (Tposition + D/Rpeak). For fraction F of peak: D = F · Rpeak · Tposition / (1 − F).

Example: 10 ms position, 100 MB/s, F = 0.9 → about 9 MB per flush.

Finding inodes: imap and CR

Inodes are no longer at fixed offsets — each update moves them. LFS adds an inode map (imap): inode number → disk address of the latest inode. imap chunks are written next to the segment contents (not a fixed hot spot).

A fixed checkpoint region (CR) points at the latest imap pieces. CR is updated periodically (~30 s) so the write path stays sequential.

Read path (cold): CR → load imap → inode → (in)direct blocks — same I/O count as a classic FS once imap is cached.

Quiz

Rank the sequence

1 / 1

Order the cold-start read path LFS uses to locate a file’s data (top = first).

OrderDrag the handle to rearrange — top should be first.

1Read the data block
2Read the checkpoint region (CR)
3Read the inode to get (in)direct block pointers
4Load the relevant imap chunk to find the inode’s disk address

Drag items into the correct order (or use ↑↓), then check.

Directories still store (name, inum). When an inode moves, only the imap changes — this avoids the recursive update problem up the directory tree.

Garbage collection (cleaning)

Old versions left behind are garbage. Cleaning runs segment-by-segment: read M segments, compact live blocks into N < M new segments, free the old — keeps large free regions for future sequential writes.

Liveness: segment summary stores (inum, offset) per block; live iff current inode still points at that address. Version numbers in imap short-circuit truncate/delete checks.

Policy: clean cold segments sooner; wait on hot ones (more blocks die). Cleaning cost was controversial early on [SS+95]; later work improved policies [MR+97].

Quiz

Rank the sequence

1 / 1

Order the steps of LFS segment cleaning (top = first).

OrderDrag the handle to rearrange — top should be first.

1Read M candidate segments into memory
2Compact the live blocks into N < M new segments
3Write the N compacted segments to new free space
4Free the M old segments
5Check each block’s segment-summary entry against the current inode to determine liveness

Drag items into the correct order (or use ↑↓), then check.

Crash recovery

Two CRs (ends of disk), updated alternately with timestamped header/body/trailer → detect partial CR writes
Roll forward from the last good CR along the log to recover recent segments

Interactive

Try: why LFS · segment write path · imap/CR · cleaning · crash recovery.

Check your understanding

Quiz