School of Computer Science & Engineering
University of New South Wales
Advanced Operating Systems
COMP9242 2002/S2
Next: LFS Performance: Comparison with
Up: 09-fs
Previous: Limitations of Traditional File
Subsections
- Only write to end of log.
- 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 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 (%).
- 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