Log-structured File Systems

Forces That Motivated LFS

Larger memories satisfy most reads from cache, leaving disks occupied almost exclusively by writes. Areal density has raised sequential bandwidth sharply while mechanical seek and rotation lag, so random I/O stays costly. Classic file systems issue many tiny writes even for a one-block file (inode, bitmaps, directory), incurring short seeks inside a group. RAID-4/5 turns a logical small write into four physical I/Os. LFS converts every update into a large sequential transfer to overcome these limits.

Turning Writes Sequential with In-Memory Segments

Consecutive addresses alone still lose time to rotation between successive small writes. LFS therefore gathers data blocks together with inodes and other metadata inside an in-memory segment; when full the whole segment is issued as one long sequential write onto unused disk space, never overwriting live data. A large enough segment amortizes positioning cost so effective bandwidth approaches the drive peak. Data and metadata travel together, completing related updates in a single transfer.

How Large a Buffer Makes Sense

Buffer size is set by positioning overhead T_position versus peak rate R_peak. To obtain fraction F of peak bandwidth the data volume D must satisfy D = [F/(1-F)] × R_peak × T_position. Bigger segments hide mechanical delay more completely and therefore come closer to sequential-transfer limits.

Pitfalls

• Thinking sequential addresses by themselves reach peak bandwidth, forgetting a single large contiguous transfer is required.
• Buffering only data while still scattering inode and bitmap updates randomly.
• Assuming reads become sequential as well; LFS primarily accelerates the write path.

Minimum C11 · complete program · Download .c

#include <stdio.h>

int main(void) {
    double t_pos = 0.01;
    double r_peak = 100.0;
    double f = 0.9;
    double d = (f / (1.0 - f)) * r_peak * t_pos;
    printf("Needed buffer: %.1f MB\n", d);
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-43-lfs.c -o example && ./example

Expected result

Needed buffer: 9.0 MB

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

With 8 ms positioning, 50 MB/s peak rate and a 90 % peak-bandwidth target, how many MB should LFS buffer?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.