Read The Design and Implementation of a Log-Structured File System, by Rosenblum and Ousterhout (reading #14).

This paper presents the design of a file system, the part of an operating system that manages how files are written to a disk. The UNIX paper presented the design of a file system for UNIX; that file system is (including a few changes) still in use today. LFS is proposed as a higher performance replacement for that file system.

LFS is structured around the idea of a append-only log. You can think of a log as a flat file which can be modified only by appending new data to the end of the file. We'll be studying logs in greater detail in the reading for L22, for more information consult the sidebar on page 8-22 of your textbook. LFS stores all file data in the log. As 6.033 considers the topic of reliable systems, we'll see logs used to achieve reliability, here a log is used to improve performance.

To understand why appending to a log is a high-performance operation, it is necessary to understand how disks are constructed (a more complete description of hard disk operation appears on page 3-33 of your text). Data on a disk is stored on a constantly spinning platter and read by a head that floats above the platter. The platter is broken down into concentric rings called tracks; each track is divided into sectors. The time required to read or write data to a disk can be broken down into three components: moving the head to the correct track, waiting for the correct sector to rotate under the head, and transferring the data off the disk. The first two operations (known collectively as a "seek") are very expensive (and aren't getting cheaper very fast): they are likely to take around 5ms. Once the disk head is at the correct location, data can be transferred quickly (at around 40 MB/s on modern disks).

The goal of LFS is to minimize expensive seeks by treating the disk as an infinite append-only log. For example, new files are simply appended to the end of the log. For the LFS's strategy to translate into higher performance LFS needs to:

• Write in large batches to amortize the cost of a seek (if any).
• Always start writing from the last place you stopped writing.
• Avoid reading; reads are likely to cause a seek.