In the previous page, we established that log-structured file systems convert random writes to sequential writes. But why is sequential access so powerful? And how does LFS actually achieve this transformation?

The answer lies in understanding the fundamental physics of storage devices—and how LFS exploits that physics to deliver performance that seems almost magical: taking workloads that would cripple traditional file systems and running them at near-disk-bandwidth speeds.

This page dives deep into the mechanics of sequential writes in LFS: how segment buffers work, why size matters, how LFS handles different types of data, and the engineering decisions that determine real-world performance.

To understand why sequential access dominates random access in performance, we need to examine how storage devices physically operate.

Hard Disk Drives (HDDs):

An HDD consists of magnetic platters spinning at 5,400 to 15,000 RPM, with read/write heads mounted on actuator arms. To access data, the drive must:

1. Seek: Move the head to the correct track (radial position)
2. Rotate: Wait for the correct sector to spin under the head
3. Transfer: Read or write the data

The time for each phase:

• Seek time: 2-15 ms (average ~8 ms for consumer drives)
• Rotational latency: Half a rotation on average = 4.2 ms at 7,200 RPM
• Transfer time: Negligible for small blocks (0.01-0.1 ms for 4 KB)

For a 4 KB random read: Total ≈ 12 ms = ~83 IOPS (I/O operations per second)

For 4 KB sequential reads (no seek, no rotational delay between blocks): Transfer rate ≈ 150 MB/s = ~37,500 4KB blocks/second

Solid State Drives (SSDs):

SSDs have no moving parts, eliminating seek and rotational latency. However, they have their own characteristics that favor sequential access:

1. Read/Write Asymmetry: Writes are more complex than reads
2. Page vs. Block Granularity:
   • Reads: Per-page (4 KB typical)
   • Writes: Require erasing entire block first (128-512 KB)
3. Write Amplification: Random writes cause internal copying and garbage collection
4. Channel Parallelism: SSDs have multiple channels; sequential writes utilize all channels efficiently

While the sequential advantage is smaller for SSDs (~5-10x vs. 400x for HDDs), it remains significant—especially for write-heavy workloads.

The Fundamental Insight:

Storage devices are optimized for sequential access at every level:

• HDDs: Mechanical design requires forward motion
• SSDs: Flash translation layer, wear leveling, and parallelism optimization
• Controllers: Prefetching, write combining, queue optimization
• Operating systems: Read-ahead, write-back caching

LFS aligns with this reality by never asking the storage device to do what it does poorly: scattered random writes. Instead, LFS accumulates writes in memory and issues them in large, sequential bursts—exactly what storage devices do best.

The segment buffer is the central mechanism that transforms scattered application writes into sequential disk writes. Understanding its operation is key to understanding LFS performance.

How the Segment Buffer Works:

1. Accumulation Phase: Application writes (data blocks, inodes, directory updates) are collected in a memory buffer

2. Segment Construction: When the buffer is full (or a sync is requested), all pending writes are organized into a segment

3. Sequential Write: The entire segment is written to disk in one contiguous operation

4. Imap Update: The inode map is updated to reflect new block locations

This batching converts what might be hundreds of scattered 4 KB writes into a single multi-megabyte sequential write.

Segment Buffer Contents:

A segment isn't just a random collection of blocks. It's carefully organized for both write efficiency and future read performance:

1. Segment Summary Block (beginning):

   • Lists every block in the segment
   • For each block: owning inode, offset within file
   • Checksum for integrity verification
   • Enables garbage collection without reading inodes

2. Data Blocks:

   • File content from multiple files
   • Grouped by file when possible (locality)
   • May include partial file updates

3. Inode Blocks:

   • Updated inodes for files in this segment
   • Placed after their data blocks (read locality)

4. Inode Map Updates:

   • Changes to the imap since last segment
   • Only the portions that changed (incremental)

5. Segment Trailer (optional, some implementations):

   • Duplicate checksum for validation
   • Write completion marker

The choice of segment size profoundly affects LFS performance. There's no universally optimal size—the right choice depends on workload characteristics, hardware, and system requirements.

The Trade-offs:

Mathematical Analysis:

To achieve a target percentage of maximum disk bandwidth, segment size must exceed a threshold. Consider an HDD with:

• Seek time (T_seek): 10 ms
• Maximum sequential write rate (R_max): 100 MB/s

To achieve 90% of maximum throughput:

Efficiency = Segment_Size / (Segment_Size + T_seek × R_max)
0.90 = S / (S + 0.01 × 100 MB)
0.90 = S / (S + 1 MB)
S = 0.90 × (S + 1 MB)
S = 0.90S + 0.9 MB
0.10S = 0.9 MB
S = 9 MB

For 90% efficiency on this HDD, segments must be at least 9 MB.

For 99% efficiency: approximately 99 MB segments required.

Common Segment Sizes in Practice:

• Original LFS (1992): 512 KB - 1 MB (limited by memory availability)
• NILFS2: 8 MB default (configurable)
• F2FS: 2 MB sections, 6 sections per zone = 12 MB effective units
• Most modern implementations: 4-16 MB

Dynamic Segment Sizing:

Some advanced implementations adjust segment size dynamically based on:

• Current write rate (more data = larger segments)
• Available memory (can buffer more)
• Sync frequency requirements
• Disk utilization (fuller disk = smaller segments for GC efficiency)

Writing data sequentially sounds simple, but ensuring consistency requires careful attention to write ordering. LFS must guarantee that the file system remains valid even if a crash interrupts a segment write.

The Ordering Problem:

Consider what's in a segment:

1. Data blocks
2. Inodes pointing to those data blocks
3. Inode map entries pointing to those inodes
4. Segment summary describing the segment

If the disk reorders these writes and crashes mid-segment:

• Inode map might point to an inode that doesn't exist yet
• Inode might reference data blocks not yet written
• Segment summary might be incomplete

Any of these could corrupt the file system.

Checkpoint Atomicity:

The checkpoint region is updated only after a segment is completely written. This creates an atomic commit point:

• Before checkpoint update: Old file system state (valid)
• After checkpoint update: New file system state (valid)
• Never: Inconsistent state

Handling Disk Write Reordering:

Modern disks may reorder writes for performance. To ensure ordering, LFS uses:

1. Barriers/Flushes: Force all pending writes to complete before proceeding
2. Cache flush commands: FUA (Force Unit Access) or write-through
3. Journaling within segment: Write-ahead of critical metadata

F2FS Approach:

F2FS (Flash-Friendly File System) uses a sophisticated technique:

• Writes node (inode) blocks to a separate "node log"
• Writes data blocks to "data log"
• Uses checkpointing to ensure cross-log consistency
• Enables parallel writes to different flash channels

Modern LFS implementations often use multiple logs rather than a single append point. This enables separation of data with different characteristics and better optimization for specific access patterns.

Why Multiple Logs?

Not all data is created equal:

• Hot data: Frequently modified (e.g., database indices)
• Cold data: Rarely changed (e.g., archived files)
• Metadata: Small, frequent updates (directories, inodes)
• Large files: Sequential streaming writes

Mixing hot and cold data in the same segment leads to inefficient garbage collection: cleaning a segment with 10% live data still requires moving that 10%.

Data Classification Techniques:

File systems use various heuristics to classify data:

1. Access frequency tracking: Count reads/writes per file or block
2. File extension/type: Media files likely cold, database files likely hot
3. Directory location: /tmp is hot, /archive is cold
4. Size heuristics: Small files often hot (metadata-like), large files often cold
5. Age: Recently created/modified data is hot; old data is cold
6. Explicit hints: Applications can specify expected access patterns (fadvise())

NILFS2 Approach:

NILFS2 uses a single log but with a different strategy:

• All writes go to the segment at the log head
• Continuous snapshots capture every state
• Cleaning is deferred and batched
• Simpler architecture, suitable for archival workloads

LFS's segment buffering creates a tension with applications that require durability guarantees. When an application calls fsync(), it expects data to be safely on disk—not lingering in a memory buffer.

The Sync Challenge:

If we wait for the segment buffer to fill before writing, fsync() could take arbitrarily long. But if we write partial segments on every sync, we lose the sequential write advantage.

Solutions:

1. Partial Segment Writes: Write whatever is in the buffer immediately

   • Loses some efficiency but maintains correctness
   • Next segment starts where this one ended

2. Dedicated Sync Log: Maintain a separate small log for sync-heavy workloads

   • Main log gets batched writes
   • Sync log handles durability requirements
   • ZFS uses this with the ZIL (ZFS Intent Log)

3. Segment Aggregation: Combine sync requests

   • Multiple syncs within a short window share one segment write
   • Improves efficiency for bursty sync patterns (e.g., databases)

Database Workload Optimization:

Databases issue frequent fsync() calls for transaction durability. This is particularly challenging for LFS:

• Each transaction commit may trigger fsync()
• Transactions can be small (single row update)
• Batching is limited by commit latency requirements

Group Commit:

Many databases implement "group commit"—collecting multiple transaction commits and issuing a single fsync() for all. This aligns perfectly with LFS:

1. Transaction 1 commits → wait in queue
2. Transaction 2 commits → wait in queue
3. Transactions 3, 4, 5 commit → queue
4. Short delay expires → flush all 5 with one fsync()

Combined with LFS segment batching, this achieves high transaction throughput with durability.

Let's examine how LFS sequential write strategy performs under different workloads compared to traditional file systems.

Workload Categories:

1. Small random writes: Many small files, scattered updates (email, metadata-heavy)
2. Large sequential writes: Big files, streaming writes (video, backup)
3. Mixed workloads: Combination of both patterns
4. Sync-heavy: Frequent fsync() calls (databases)

SSD Performance Characteristics:

On SSDs, the performance landscape changes:

• Sequential advantage is smaller (5-10x vs 100x+)
• But SSD internal garbage collection benefits from LFS alignment
• Write amplification reduction significant for SSD lifespan
• Multi-queue NVMe can exploit LFS parallel log writes

Real-World Benchmarks:

From Samsung F2FS paper (2015), on mobile devices:

• SQLite random insert: 2x faster than ext4
• App installation: 1.5x faster
• Boot time: 10% reduction

From NILFS2 evaluations:

• Mail server workload: 4x throughput improvement
• Backup workloads: Near-disk-bandwidth writes
• Snapshot creation: Instant (no copy required)

These results demonstrate that LFS's sequential write strategy delivers substantial real-world benefits, particularly for write-intensive workloads on both HDDs and SSDs.

We've explored the mechanics of sequential writes in LFS and how this fundamental design decision transforms file system performance.

What's Next:

Sequential writes solve the performance problem but create a new one: garbage collection. Since we never update in place, old versions of data accumulate and consume space. The next page explores how LFS reclaims this space through garbage collection—a critical and challenging aspect of log-structured storage.