Log-Structured File Systems: Maximizing Disk Write Bandwidth via Pure Append Layouts

Traditional Unix file systems (such as FFS / ext2) organize storage into fixed, in-place structures: separate bitmap blocks, inode tables, data blocks, and indirect pointers. Modifying a file or creating a small directory entry requires multiple random writes across different physical disk locations to update data blocks, parent directory blocks, and inode metadata synchronously.

Introduced by Mendel Rosenblum and John Ousterhout in 1991, the **Log-Structured File System (LFS)** is built on the realization that growing system RAM caches absorb almost all read traffic, leaving storage devices primarily write-bound. To eliminate random I/O bottlenecks, LFS buffers all file modifications—both data blocks and metadata—and writes them sequentially to disk in continuous, large **Segments**, completely replacing in-place updates with an append-only log.

The Wandering Tree Problem & Inode Map (imap) Solution

In an append-only file system, updating data block $D$ means writing a new version $D'$ to the end of the log. Because $D'$ now has a new physical block address, its parent **Inode** (which holds pointers to the file's data blocks) must also be updated and written to a new location in the log.

This creates the **Wandering Tree (Recursive Update) Problem**: writing a new inode changes its address, which forces its parent directory data block to update, which forces the directory's inode to move, propagating modifications all the way to the file system root.

The Inode Map (imap) Level of Indirection

LFS halts this recursive propagation using a dynamic routing structure called the **Inode Map (imap)**:

• Indirection Table: An array indexed by an invariant file identifier (`inode_number`) that returns the current physical on-disk address of that inode.
• Piecewise imap Updates: The imap itself is broken into small chunks. When an inode moves, only the specific chunk of the imap containing that inode is appended to the log next to the inode.
• Fixed Checkpoint Region (CR): A single known physical location on disk (the Checkpoint Region) stores pointers to all active chunks of the imap. The CR is updated periodically (every 30 seconds or during clean unmounts), avoiding recursive writes on individual file operations.

Segment Cleaning: Freeing Space and Garbage Collection

Because data is never overwritten in place, obsolete versions of data blocks and inodes ('dead blocks') accumulate throughout the log, eventually exhausting available disk space. LFS reclaims free contiguous space through a background process called **Segment Cleaning**:

1. Read Segment: The cleaner reads a batch of old segments into memory.
2. Identify Live Blocks: Every segment includes a **Segment Summary Block** listing the file number and block offset for every data chunk in that segment. The cleaner consults the current Inode Map: if the inode's pointer still points to this block, the block is **live**; if the inode points to a newer block, this block is **dead**.
3. Compact & Re-append: The cleaner packs all surviving live blocks into a fresh, compact segment and writes it sequentially to the end of the log.
4. Free Segments: The old, processed segments are marked as completely free for future writes.

Cost-Benefit Cleaning Policy

To prevent wasting I/O cleaning segments that are actively changing, Rosenblum and Ousterhout established the **Cost-Benefit Cleaning Formula**:

Cold segments with high dead data are prioritized immediately; hot segments are allowed to age so more blocks can become dead before incurring compaction costs.

Crash Recovery: Checkpoints and Roll-Forward

When an LFS machine crashes or loses power, recovery does not require a full file system consistency check (like Unix `fsck`):

• Checkpoint Recovery: The system reads the Checkpoint Region (CR) to reconstruct the consistent Inode Map state as of the last checkpoint.
• Roll-Forward Logging: The recovery engine scans forward through the sequential log blocks written *after* the checkpoint up to the point of failure. It detects valid newly written inodes/data blocks and applies them to the in-memory imap, minimizing lost work down to sub-second windows.

C++ Conceptual Simulation Blueprint (LFS Inode Map & Segment Append)

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

struct Inode {
    uint32_t inodeNumber;
    uint32_t size;
    std::vector<uint64_t> directBlockPointers;
};

struct BlockSummary {
    uint32_t inodeNumber;
    uint32_t blockOffset;
};

class LFSStorageSimulation {
private:
    uint64_t currentDiskOffset = 0;
    // Inode Map (imap): Inode Number -> Physical Disk Offset of Inode
    std::unordered_map<uint32_t, uint64_t> imap;
    
    // Simulated disk storage log
    std::vector<std::string> diskBlocks;
    std::unordered_map<uint64_t, BlockSummary> segmentSummaries;

public:
    uint64_t appendDataBlock(uint32_t inumber, uint32_t offset, const std::string& data) {
        uint64_t blockAddr = currentDiskOffset++;
        diskBlocks.push_back(data);
        segmentSummaries[blockAddr] = {inumber, offset};
        return blockAddr;
    }

    void writeInode(Inode inode) {
        // Inode itself is written sequentially to the log
        uint64_t inodeAddr = currentDiskOffset++;
        diskBlocks.push_back("__INODE_META__");
        
        // Update Inode Map with new physical location of the inode
        imap[inode.inodeNumber] = inodeAddr;
    }

    bool isBlockLive(uint64_t blockAddr, const Inode& currentInode) const {
        if (!segmentSummaries.count(blockAddr)) return false;
        BlockSummary summary = segmentSummaries.at(blockAddr);
        
        if (summary.blockOffset < currentInode.directBlockPointers.size()) {
            return currentInode.directBlockPointers[summary.blockOffset] == blockAddr;
        }
        return false;
    }

    uint64_t getInodeAddress(uint32_t inumber) const {
        return imap.count(inumber) ? imap.at(inumber) : 0;
    }
};

Real-World Storage Systems & Industrial Applications

1. Flash Translation Layers (FTL in SSDs & NVMe): Modern solid-state drives cannot overwrite NAND flash blocks in place without expensive block-erase cycles. FTL firmware implements LFS principles (out-of-place logging, logical-to-physical mapping tables, and background garbage collection wear leveling).
2. Copy-on-Write (CoW) File Systems (ZFS & Btrfs): Uses trees of pointers and transaction groups to write all block updates out-of-place, guaranteeing transactional snapshotting and instant crash recovery.
3. NetApp WAFL (Write Anywhere File Layout): Proprietary enterprise storage architecture treating NVRAM and disk arrays as log-structured buffers to eliminate random write delays.
4. Log-Structured Databases (RocksDB, Cassandra SSTables): Direct software descendants applying LFS segment compaction and immutable log concepts to application-level key-value storage.