Log-Structured Filesystem

A log-structured filesystem is a novel disk storage management technique developed in the late 1980's by John K. Ousterhout and Fred Douglis. It stores data sequentially on the disk rather than scattering blocks all over the disk as most other filesystems do.

Overview

Figure 1: Layout of classic inode-based filesystems (simplified)

Modern inode-based filesystems store inode and data blocks seperately in fixed regions on the disk. Figure 1 shows a simplified disk layout of classic inode-based filesystems. This layout induces a substantial seek overhead when writing files (with read operations this overhead can be cached away). When writing a file the data blocks are written first, then the inode of the file, then the corresponding directory block is updated, then its associated inode is updated. All these operations are preceded by seek operations to locate the on-disk position of the block that is to be accessed. With workloads like those found in office applications that work on many, small files the seek operations consume up to 80% of the raw disk bandwidth.

The log-structured filesystem tries to remove this overhead by eliminating all seeks and thus reclaiming almost 100% of the disk bandwidth for write operations.

LFS in Detail

Figure 2: Layout of a log-structured filesystem (simplified)

The basic idea of a log-structured filesystem is to store all information sequentially on disk in a log structure. This includes all data blocks, inode blocks, directory blocks, indirect blocks, etc.

Links

• Citeseer: Mendel Rosenblum, John K. Ousterhout - The Design and Implementation of a Log-Structured File System
• Wikipedia article about log-structured filesystem
• NILFS Homepage - A log-structured filesystem for linux
• Sun's ZFS development page