The Log-Structured File System (LFS)

Motivation

Traditional file systems (FFS, ext2) optimise for read performance by clustering related data (files in the same directory, inodes near their data). Write performance suffers because small writes must seek to scattered locations: update the inode, update the data block, update the free-block bitmap, update the directory entry — each in a different location.

The Log-Structured File System (LFS) takes the opposite approach: optimise for writes by treating the disk as an append-only log. All writes — data blocks, inodes, bitmaps, directories — are buffered in memory and written to the end of the log in large, sequential segments. Reads still require random access, but reads can be cached; writes are the bottleneck for many workloads.

The log structure

The disk is divided into fixed-size segments (e.g., 512 KB or 1 MB). The LFS accumulates pending writes in an in-memory segment buffer. When the buffer is full, LFS writes the entire segment to the next free segment on disk in one sequential transfer.

Each segment contains segment summary information at the start, which maps each block in the segment to the inode and offset it belongs to. This allows the recovery process (after a crash) to reconstruct the file system by scanning the log.

Garbage collection: the cleaner

As files are overwritten or deleted, old log entries become garbage — they refer to blocks that are no longer part of any live file. But the disk does not overwrite them in place; the log only appends. Eventually, the disk fills up, and the cleaner must reclaim segments:

1. Read a segment from disk.
2. Determine which blocks are still live (by consulting the inode map, which points to the most recent version of each block).
3. Copy the live blocks into a new segment (at the end of the log).
4. Mark the old segment as free.

Cleaning is the main performance challenge for LFS. If the cleaner must move many live blocks, it competes with the normal write stream for disk bandwidth. The choice of which segment to clean (based on utilisation — a segment with mostly garbage is cheap to clean) is critical.

The inode map

LFS inodes do not have fixed locations on disk — they move each time they are updated (since all writes go to the end of the log). LFS maintains an inode map (or “imap”) that tracks the current log location of each inode. The imap itself is logged — the very last block of the log points to the imap, enabling recovery to find the current state of the file system.

Advantages and disadvantages

Advantages:

• Write performance is excellent — all writes are large, sequential, and aligned to segment boundaries. This is especially beneficial on magnetic disks where seek time dominates.
• Crash recovery is conceptually simple: scan the log forward from the last checkpoint, replaying completed segments.
• Supports snapshots cheaply (just preserve old log entries).

Disadvantages:

• The cleaner is complex and must run efficiently to avoid degrading write performance.
• Reads may require following a chain of log entries to find the latest version of a block (mitigated by caching the inode map).
• Performance degrades as the disk fills — fewer clean segments means the cleaner must work harder.
• Modern SSDs use a similar log-structured approach internally (flash translation layer, FTL), which interacts oddly with a log-structured file system on top — write amplification can compound.

Summary

• LFS treats the disk as an append-only log; all writes are sequential and batched into segments.
• The cleaner reclaims garbage segments by copying live blocks forward.
• An inode map tracks current inode locations since inodes move on each update.
• Excellent for write-heavy workloads; complex cleaner logic is the main challenge.