Every file system so far overwrites structures in place. The log-structured file system (LFS) log-structured file system LFS (Rosenblum & Ousterhout): a file system that turns ALL writes into sequential writes. It buffers updates (data AND metadata) in memory, then writes them to an unused part of the disk as one big segment — never overwriting in place (copy-on-write). Optimizes write performance (most traffic is writes; sequential ≫ random) and sidesteps RAID's small-write problem. defined in ch. 43 — open in glossary , built by Rosenblum and Ousterhout, does something radical instead: it turns every write into a sequential write, never overwriting in place. Four observations drove it:
| observation | why it favors a log-structured design | |
|---|---|---|
| memory | System memories keep growing | bigger caches absorb most reads → disk traffic becomes mostly WRITES → write performance dominates |
| gap | Sequential I/O ≫ random I/O | transfer bandwidth rises fast, but seek/rotation improve slowly — so using the disk sequentially is a huge win |
| ffs | FFS scatters small writes | creating a one-block file = ~6 writes (inode, inode bitmap, dir data, dir inode, data, data bitmap) → many short seeks, far below peak |
| raid | File systems aren't RAID-aware | they ignore RAID-4/5's small-write problem (4 physical I/Os per logical write) |
The Crux: How To Make All Writes Sequential Writes
How can a file system transform all writes into sequential writes? (Reads are hopeless — a block may be anywhere on disk — but for writes, the file system always gets to choose where the data goes.)43.1–43.2 Writing Sequentially, and Effectively
The core idea: append all updates — data and metadata — to a log, at unused disk locations. But sequential order alone isn’t fast: if you write to A, wait, then write to A+1, the disk has rotated past A+1 and you eat almost a full rotation. The fix is to issue one large write. So LFS buffers updates in memory and flushes them together as a segment lfs segment In LFS, a large (a few MB) chunk of buffered updates that LFS writes to disk in one long sequential transfer. Large segments are what make writes efficient (amortizing positioning cost) and are also the unit of cleaning. (A different meaning from the memory 'segment' of virtual-memory segmentation.) defined in ch. 43 — open in glossary (a few MB):
1Write the data block D
Say we write a data block D to a file. LFS places it at the next free spot in the log — here disk address A0.
Because segments are large, the disk (or RAID) is used efficiently, and write performance approaches the drive’s peak. (This is just write buffering and amortization — the same idea as FFS’s large-file chunks, pushed to cover all writes.)
43.3 How Much To Buffer?
How big should a segment be? Enough to amortize the fixed positioning cost. Writing D MB costs the positioning time plus the transfer time:
so the effective write rate is the data over that total:
To reach a fraction F of peak bandwidth (set R_effective = F · R_peak and solve for D):
With a 10 ms positioning time, 100 MB/s peak, and a 90% target (F = 0.9): D = (0.9 / 0.1) × 100 MB/s × 0.01 s = 9 MB. Want 95% or 99% of peak? The buffer must grow fast — exactly the amortization trade-off from the disk and FFS chapters, now governing LFS’s segment size.
Check yourself: LFS sequential writing
1.What is the core idea of a log-structured file system?
2.Why did the LFS designers argue that WRITE performance matters most?
3.When LFS writes a data block, what else goes into the log alongside it?
4.Why isn't writing in sequential ORDER (block A, then A+1, then A+2…) enough for good performance?
5.What is a segment in LFS?
6.Using D = F/(1−F) × R_peak × T_position, how much must LFS buffer for 90% of peak on a disk with 10 ms positioning and 100 MB/s peak?