25 Years The Log-Structured File System

An Implementation of a Log-Structured File System for UNIX on USENIX 1993 by Seltzer.

The LFS Storage Manager published on Proceedings of the 1990 Summer Usenix.

The Log-Structured File System is 25 years old now, 3 years older then The Log-Structured Merge-Tree which is published in 1996 on Springer by O’Neil. The Log-Structured File System mentioned here do not manipulate a tree data structure.

See the review written on 2010 by Murat:

The LFS idea is simple: focus on write performance and utilize sequential bandwidth of disks. Here is how it works. LFS buffers all writes into a segment in main memory. (Even though the writes may be for different files, they are appended into the segment.) When the segment is full, LFS writes the segment to unused place on disk sequentially again.

Different to LSM-tree, the main memory caching of the Log-Structured File System is used as a segment to aggregate the writes rather than a B-tree. The write logs then directly append to disks when the segment is full. No merge operation is required.

Checkpoint

The checkpoint region is very like a superblock in BTRFS. The checkpoint points to the inode map and the inode map then points to the data region. Both inode map and data are stored in a log structure manner, while the checkpoint region is write to fixed place periodically. Checkpoint is widely used by storage systems to support fault recovery, such as Tachyon – The memory-centric distributed storage system.

Garbage Collection

This Log-Structured File System use garbage collection to reclaim the unused data space. It is amazing to see that the garbage collection exist far more earlier than the emerging of NAND Flash based SSDs. The garbage collection in Log-Structured File System is like the merge operation in LSM-Tree. It redo the write logs to the old data and then write to a new region.

While the garbage collection in SSDs are content independent. It merges the data pages from different blocks and write to a new block as well as update the mapping table. The architecture of Log-Structured File System is very similar to the firmware design of SSDs. However, the design of Log-Structured File System and LSM-Tree seems to be much better, because the garbage collection/merge operation are data/data structure aware.