OS Study 33. FileSystem: LFS, Log-Structured File System

There are many different types of file systems.

In this post, Let’s focus on one in particular: the Log-Structured File System(LFS)

Why Log-Structured File Systems were proposed

Log-structured file systems were introduced to address several trends and limitations in storage systems.

1️⃣ Growth in memory capacity and increased caching

As main memory capacity increased, more data could be cached in memory.

• Many read requests began to hit in the page cache rather than going to disk.
• Disks were increasingly used for write operations.
• As a result, overall file-system performance became dominated by write performance(the file system still has to persist data on disk)

2️⃣ Widening gap betweeen random and sequential I/O performance

Over time, disk characteristics evolved unevenly:

• Transfer bandwidth improved rapidly, by roughly 50–100% per year.
• Seek time and rotational latency improved very slowly, by only about 5–10% per year.

Therefore, if a file system can use the disk with mostly sequential I/O, it can significantly improve performance.

The relationship between transfer bandwidth and I/O performance can be seen from the basic breakdown of I/O time:

I/O time = seek time + rotational latency + transfer time

• Transfer time is the time required to read data from disk sectors and send it to the controller or memory.
• Transfer bandwidth is the maximum speed when data is read continuously (sequentially), and is directly related to transfer time.

As transfer bandwidth increases, the time for sequential disk I/O decreases, while random I/O remains relatively slow due to seek and rotational delays.

3️⃣ Poor performance of traditional file systems under common workloads

4️⃣ Lack of RAID-awareness in traditional file systems

Traditional file systems generally do not take RAID behavior into account.

For example, RAID 4 and RAID 5 suffer from the small write problem:

• Even when a single logical block is updated, up to four physical I/O operations may be required.

What does an Ideal file system look like?

An ideal file system:

• Focuses on write performace.
• Operates efficiently not only when writing user data, but also under workloads that frequently update on-disk metadata structures.
• Performs well both on a single disk and on RAID configurations.

The LFS was designed with these goals in mind.

Core Idea of LFS

LFS records all updates, including metadata, into a segment data structure.

• When a segment becomes full, the file system finds free space on disk and writes the entire segment in a single large I/O.
• Existing data is never overwritten in place; segments are always written to previously unused (free) regions of the disk.
• Because segments are large, disk writes become highly efficient, allowing the file system to exploit the full sequential bandwidth of the disk.

To improve file-system performance, the key remaining point is to turn writes into sequential writes.

Why Focus on writes, Not reads?

• Read operations cannot be arbitrarily rearranged or transformed; they are determined by the access pattern of applications.
• Write operations, however, allow the file system to choose where on disk to place new data. By carefully choosing write locations, the file system can convert many small, random writes into large, sequential writes.

1. Writing sequentially to disk

How can all file-system-modifying writes be issued to disk as sequential writes?

• When a data block is written, both the data and the corresponding metadata(inode) must be updated.
• The file system must write the inode to disk and ensure that the inode points to the new data block.
• To achieve this, the data block and its inode are laid out consecutively on disk

2. Writing sequentially and efficiently

Sequential writes alone are not enough to fully exploit disk performance.

To achieve high write throughput, the file system must send many sequential writes(or one large write) to the disk in a single operation

This is because of the following issue:

• Suppose the file system writes to logical addresses A and A+1 for sequential I/O.
• In practice, the disk may perform: write at A → disk rotation → write at A+1, incurring additional rotational delay between the two writes.

To avoid this kind of overhead, a classic technique called write buffering is used.

In LFS, write buffering works as follows:

• Updates are first kept in memory instead of of being written immediately to disk.
• Once enough updates have accumulated, they are flushed to disk in one large write.
• The unit written to disk in one shot is called a segment.
• In other words, when the file system records data, it keeps the pending writes in a segment buffer; when the buffer is full, the entire segment is written to disk with a single write operation.
• If the segment size is sufficiently large, these writes become very efficient.

3. choosing an appropriate segment buffer size

The appropriate size for the segment buffer depends on:

• The physical characteristics of the disk and the balance between positioning overhead (seek+rotational latency) and data transfer time

🔥Tip, The details matter more than you think

Most systems are built from a few general concepts + many detailed mechanisms.

When studying a system, it’s easy to stop at “I kind of get the idea; the rest is just details” (which is where I am right now).

Buf if you stop there, you’ve only learned about half of how the real system actually works.

In many cases, the details are the core of the system, and the high-level concepts are almost too easy to understand.

To build a real, working system, you have to handle all kinds of tricky edge cases and subtle behaviors.

🔥Tip, In computer science, understanding the “flow” matters more than memorization

Computer science is a field where you need to understand things logically, not just memorize facts.

If you understand the underlying flow and reasoning, you can reapply that understanding when new technologies, tools, or frameworks appear.