Log-Structured File System (LFS)

Idea: Whole disk is a log[RO92].

Only write to end of log.
- Eliminates most seeks.
Write in large chunks, called segments (64kB-1MB).
- Amortises costs of any seeks.
Include in segments updated data block as well as metadata.
- Can control write order by location within segment.
- Ensures consistency of updates (like delayed writes).
Keep track of live data in previously written segments.
- Segments without live data can be reclaimed.
- Partially live segments can be compacted.
- Uses garbage collector process, called cleaner.
Occasionally checkpoint metadata (using shadow paging).
- Avoids processing whole log on restart.

In segments:
- inodes (as in FFS, but pointers change frequently),
- directories (as in FFS),
- inode map, giving locations of inodes (changes frequently),
- log of directory changes (to avoid multiple updates),
- segment summary:
  - number of next segment,
  - summary of contents,
  - checksums of contents (to verify successful write).
In checkpoint:
- timestamp,
- address of last segment written,
- segment usage table,
- address of inode map.

lfs

LFS allows fast restart from crash:
- Segment usage table allows locating unused segments to write.
- Last segment pointer, and next pointer in segment summary allow recovery.
- Imap pointers allow finding inode maps.
- Time stamp allows locating last successful checkpoint.
LFS provides transaction semantics on metadata updates.

Cleaning is critical:
- LFS can only operate fast if plenty free segments available
- Segments utilisation drops over time as files get modified.
- Most segments will not become totally empty.
- Need garbage collection to compact partially-used segments.
Cleaning is tricky:
- Normal log use is dominated by writes and minimises seeks.
- Cleaning is dominated by reads, and requires many seeks.
- Cleaner potentially destroys performance[SBMS93,SSB$^+$95].
Basic approach:
- Try cleaning at times of low disk activity;
- Try keeping disk utilization low ( $<80$ %).
- Preferably clean lowly utilised segments.
- Group files of similar age.

Next: LFS Performance: Comparison with Up: 09-fs Previous: Limitations of Traditional File

Gernot Heiser 2002-10-11