Log-Structured File Systems

For decades, file systems were designed around a simple assumption: update data in place. When you modify a file, the file system finds the existing blocks on disk and overwrites them. When you delete a file, the file system marks those blocks as free. This "in-place update" model seemed natural—after all, it mirrors how we think about editing a document.

But what if this fundamental assumption was wrong? What if, instead of updating data where it lives, we always wrote new data sequentially to the end of a log? This radical insight forms the foundation of Log-Structured File Systems (LFS)—one of the most influential innovations in storage system design.

The log-structured approach doesn't just change how we write data; it fundamentally transforms file system performance, crash recovery, and optimization strategies. Understanding LFS is essential for any systems engineer working with storage, databases, or distributed systems.

To appreciate the log-structured approach, we must first understand why traditional file systems struggle with writes. Consider a typical update-in-place file system like ext4 or NTFS:

The Write Amplification Problem:

When you write a single byte to an existing file, the file system must:

1. Read the entire block containing that byte (typically 4 KB)
2. Modify the byte in memory
3. Write the entire block back to its original location
4. Update metadata (modification time, possibly size)
5. Update the inode to reflect changes
6. Possibly update directory entries

A single logical write becomes multiple physical writes scattered across the disk. This is called write amplification, and it devastates performance.

The Seek Time Domination:

For traditional hard disk drives (HDDs), the real performance killer isn't the data transfer itself—it's the seek time. Moving the disk head to the right track takes approximately 5-15 milliseconds on average. Once positioned, data transfer is relatively fast.

But scattered writes force the disk head to constantly seek between:

• Data blocks (where file content lives)
• Inode tables (metadata about files)
• Bitmap areas (free space tracking)
• Directory structures (file naming)

Each seek costs milliseconds. A workload with thousands of small, scattered writes can reduce a disk capable of 100+ MB/s sequential throughput to mere kilobytes per second of random I/O.

Small Write Syndrome:

Many real-world workloads are dominated by small writes:

• Databases: Transaction logs append sequentially, but row updates are scattered
• Email servers: Each incoming message creates a new small file
• Version control: Commits modify many small files across directories
• Virtual machines: Guest OS writes create unpredictable patterns
• Build systems: Compilation generates thousands of object files

Traditional file systems handle these workloads poorly. They're optimized for large, sequential operations—reading entire files, streaming media, copying large datasets. The small, random write workloads that dominate interactive computing expose their worst-case behavior.

This fundamental mismatch between workload characteristics and file system design created the opportunity for a radical rethinking: What if we made the file system itself sequential?

In 1992, Mendel Rosenblum and John K. Ousterhout published a groundbreaking paper: "The Design and Implementation of a Log-Structured File System." Their insight was deceptively simple yet revolutionary:

Treat the entire disk as an append-only log. Never update data in place. Always write new data (including metadata) to the end of the log.

This single principle transforms file system behavior completely.

How Log-Structured Writing Works:

Imagine the disk as a tape that only moves forward during writes. When the user wants to:

1. Create a new file: Append the file data, then append the inode, all sequentially
2. Modify existing data: Append the new version of the data blocks, then append the updated inode
3. Delete a file: Simply append a new directory version without that file (old data becomes garbage)
4. Update metadata: Append the new metadata (old version becomes obsolete)

Notice that we never go back to modify existing data. Old versions remain on disk until we garbage collect them later.

The Segment Buffer:

LFS doesn't write every small operation immediately. Instead, it collects writes in a memory buffer called the segment buffer. When the buffer fills (typically 512 KB to several megabytes), the entire segment is written sequentially to disk.

A segment contains:

• Data blocks from multiple files
• Inodes for those files
• Inode map updates pointing to the new inode locations
• Segment summary describing the segment contents

By batching writes into large segments, LFS achieves near-disk-bandwidth write performance even for workloads composed entirely of small random writes.

Understanding the complete LFS architecture requires examining several interconnected components. Each solves a specific problem introduced by the append-only design.

The Fundamental Challenge:

If we always append new data and never update in place, how do we find the current version of a file? In traditional file systems, the inode number tells us exactly where the inode lives (it's a simple calculation from the inode table location). In LFS, the inode could be anywhere in the log—its location changes every time we modify the file.

This is solved by the inode map.

The Inode Map:

The inode map is the critical indirection layer that makes LFS work. It's a simple data structure: given an inode number, return the current disk address of that inode.

In traditional file systems:

inode_address = inode_table_start + (inode_number × inode_size)

In LFS:

inode_address = inode_map[inode_number]

The inode map itself is also written to the log. After each segment write, a portion of the inode map (the parts that changed) is appended. The complete inode map is reconstructed by reading these scattered pieces.

To find the current inode map, we use the checkpoint region—one of the few fixed locations on disk. The checkpoint region contains a pointer to the most recent inode map blocks, plus metadata about the file system state.

Segment Structure:

Segments are the fundamental unit of LFS operation. Each segment contains:

1. Segment Summary Block: Describes what's in the segment

   • For each block: which inode owns it, offset within file
   • Used during garbage collection to identify live vs. dead blocks
   • Enables forward traversal of the log

2. Data Blocks: Actual file content

   • May contain blocks from multiple files
   • Blocks from the same file often grouped together

3. Inodes: File metadata

   • Placed near their data blocks in the same segment
   • Reduces seeks when reading file (data + metadata adjacent)

4. Inode Map Blocks: Updates to the inode map

   • Only the changed portions
   • Enables reconstruction of complete imap

This segment structure is optimized for both write performance (one large sequential write) and garbage collection (summary enables quick liveness checking).

While LFS revolutionizes write performance, reads involve a different set of trade-offs. Understanding the read path illuminates both the elegance and the costs of the log-structured design.

Read Path for Opening a File by Path:

Consider reading /home/user/document.txt:

1. Start from checkpoint region (fixed disk location)
2. Load inode map from checkpoint pointers (or use cached copy)
3. Look up root directory inode (inode 2 by convention)
4. Read root inode from log using imap[2]
5. Read root directory data blocks to find "home" entry → inode number
6. Look up /home inode using imap
7. Read /home directory to find "user" → inode number
8. Look up /home/user inode using imap
9. Read /home/user directory to find "document.txt" → inode number
10. Look up document.txt inode using imap
11. Read file data blocks using pointers from inode

Read Performance Characteristics:

LFS reads have different performance properties than traditional file systems:

Advantages:

• Inode map cached in memory: After initial load, inode lookups are O(1) in-memory operations
• Data locality: Files written together tend to be in adjacent segments
• No metadata seeks during sequential reads: Data blocks for a file are often contiguous within segments

Disadvantages:

• Fragmentation over time: As files are updated, their blocks scatter across different segments
• Extra indirection: Inode map lookup adds latency (though cached)
• Cold start overhead: First access after mount requires loading inode map from disk

Mitigation Strategies:

Modern LFS implementations address read performance through:

1. Aggressive caching: Keep frequently-accessed inodes and inode map in memory
2. Read-ahead: Prefetch contiguous data blocks within segments
3. Directory caching: Cache directory contents to avoid repeated lookups
4. Segment-aware placement: Group related files in same segment during writes

One of the most compelling advantages of log-structured file systems is simplified crash recovery. Traditional file systems face a fundamental challenge: how do you ensure consistency when a crash interrupts a multi-step operation?

The Crash Consistency Problem:

Consider creating a new file in a traditional file system. This requires:

1. Allocate an inode
2. Write data blocks
3. Update the inode with block pointers
4. Add directory entry pointing to inode
5. Update free block bitmap
6. Update free inode bitmap

If the system crashes between steps 3 and 4, we have an allocated inode with no directory entry—a space leak. If it crashes between steps 4 and 5, we have a file that appears valid but uses blocks still marked as "free"—potential data corruption.

Traditional solutions include:

• fsck: Scan entire file system to detect and repair inconsistencies (slow, hours for large disks)
• Journaling: Write operations to a log first, replay after crash (adds write overhead)
• Copy-on-write: Never modify existing data (similar to LFS but without sequential optimization)

Why LFS Recovery is Fast:

1. Checkpoint provides consistent snapshot: We always have a known-good state to fall back to

2. Log is append-only: No in-place modifications means no partial updates to repair

3. Segment summaries enable validation: Each segment is self-describing; we can verify its integrity

4. Roll-forward is optional and bounded: We only need to scan segments written since last checkpoint, not the entire disk

5. Atomic segment writes: Modern disks guarantee atomic sector writes (512 bytes or 4 KB). Segment summaries include checksums to detect partial writes.

The Trade-off: Checkpoint Frequency

Checkpoints must be written periodically to bound recovery time and limit data loss. But checkpoints themselves cost performance (they force sync to disk). LFS implementations balance:

• Frequent checkpoints: Faster recovery, less data loss, more overhead
• Infrequent checkpoints: Lower overhead, longer recovery, more potential data loss

Typical values: checkpoint every 30 seconds or after N segments written.

Understanding where LFS came from helps appreciate its significance and ongoing influence.

The 1992 Breakthrough:

Rosenblum and Ousterhout's LFS was developed at UC Berkeley as part of the Sprite distributed operating system project. Their key observations:

1. Memory was getting cheaper: More RAM meant larger buffer caches, making reads faster and allowing write batching

2. CPU was getting faster: Processing overhead of log management became negligible

3. Disk capacity grew faster than speed: More data to manage, same (or slower) random I/O

4. Workloads were write-heavy: Increasing use of databases, version control, and interactive applications

They demonstrated that LFS could achieve up to 10x the write performance of BSD FFS (the contemporary state-of-the-art) for small file workloads.

Beyond File Systems: The Log-Structured Idea Spreads:

The log-structured principle proved so powerful that it escaped file systems entirely:

Log-Structured Merge Trees (LSM Trees):

• Used by LevelDB, RocksDB, Apache Cassandra, Apache HBase
• Writes go to in-memory buffer, periodically merged to disk
• Powers most modern key-value and NoSQL databases
• Same insight: convert random writes to sequential

Write-Ahead Logging (WAL):

• PostgreSQL, MySQL, and other databases log changes before applying
• Essentially a mini-LFS for transaction recovery
• Combines log-structured writes with in-place data for reads

Distributed Systems:

• Apache Kafka: Distributed commit log for event streaming
• Event sourcing architecture: Log as source of truth
• Blockchain: Append-only ledger for transactions

The LFS insight—that appending is fundamentally more efficient than updating in place—has become a foundational principle of systems design.

Several production file systems embody log-structured principles today:

NILFS2 (Linux):

• Continuous snapshotting: every checkpoint creates a snapshot
• Useful for live backup and versioning
• Native Linux kernel support
• Suited for archival and write-once workloads

F2FS (Flash-Friendly File System):

• Developed by Samsung for NAND flash storage
• Adapts LFS for SSD characteristics
• Uses multiple logs (hot/cold data separation)
• Default on many Android devices

Btrfs and ZFS (COW file systems):

• Not pure LFS but share append/COW philosophy
• Never overwrite existing blocks for data integrity
• Enable snapshots and self-healing

WAFL (NetApp):

• Write Anywhere File Layout for storage appliances
• Log-structured for consistency, optimized for RAID
• Powers enterprise storage systems

We've explored the revolutionary concept of log-structured file systems. Let's consolidate the key insights:

What's Next:

Now that we understand the core LFS concept, we'll dive deeper into its implications. The next page explores sequential writes in detail—how LFS achieves near-optimal disk utilization, the role of segment size, and the engineering trade-offs in write batching.