Part 3 of 7 · 2 min read
Log-structured file systems
Think of a diary in which you never erase anything. You write each change at the end, and to know the present state you read the latest entry for each topic. An index at the front says where the latest entry for each topic is. The analogy stops in one place: a diary grows forever, and a file system must reclaim the space of entries that are out of date.
In plain words: A log-structured file system (LFS) treats the whole disk as a log. It collects all changes, data blocks, inodes and directory blocks alike, in memory, and writes them together in one large piece called a segment, at the end of the log. Because inodes move, an inode map records the current disk address of each inode, and the inode map pieces are also written to the log. A fixed place on the disk, the checkpoint region, holds the addresses of the latest inode map pieces and is updated rarely. To read a file the system finds the inode through the inode map, and then reads the data as usual. After a crash it starts from the last checkpoint and rolls forward through the newer part of the log.
A worked example. To read file 7, the system looks up inode 7 in the inode map (usually cached in memory), gets the disk address of its inode, reads the inode, and then reads the data blocks it names. This costs about as many reads as in an ordinary file system, once the map is in memory. Writes are the difference. In the test of section 1, the 300 blocks of 100 file creations became one segment write. The old copies of the inodes and directory blocks are now out of date, and the file system will not use them again.
The key lines. The design needs the disk to be mostly written sequentially, so it suits a disk with a big seek cost. It also writes new copies of a block each time, so the space of the old copies must be recovered. That is the subject of the next section.
Log-structured file system
A log-structured file system is a file system that writes all updates, data and metadata together, sequentially at the end of a log in large segments, and finds the current location of each inode through an inode map. The earlier copies in the log become garbage that must be reclaimed.
Example: LFS buffers the data blocks, inodes and directory changes of 100 new files and writes them in one segment.
Check yourself: 1. What does the inode map record, and why is it needed? 2. What does the checkpoint region hold? 3. Why is reading a file in an LFS not much slower than in an ordinary file system?