The Log as the Filesystem: Segments, Sequential Writes, and the End of the Free-Space Map

A conventional filesystem treats the disk as an array of addressable blocks and maintains a map of which ones are free. An update to a file is an overwrite: the block already has an address, so the new contents go to the same place. A log-structured filesystem rejects that premise. Every write, whether it is file data, an inode, a directory entry, or a piece of allocation metadata, is appended to a single monotonically advancing position. Nothing is ever modified in place. The block that held the old version is simply left behind, still intact, and becomes garbage the moment the new version is durable.

That one decision propagates through the entire design. Free-space management becomes a question about the past rather than a bitmap of the present, locating a file requires an indirection layer because addresses no longer persist, and the filesystem must eventually run a collector to recover the space occupied by superseded data. The layout and the motivation come first; the indirection, the recovery, and the collector are each large enough to deserve their own treatment.

What a small write actually costs

The argument begins with a measurement that has nothing to do with filesystems. On a rotating disk, servicing a request requires the head to move to the right cylinder and then wait for the platter to rotate under it. A typical full-stroke seek takes several milliseconds and rotational delay averages half a revolution, which at 7200 rpm is about four milliseconds. Transferring a 4 KiB block at a sustained rate of 100 MB/s takes roughly 40 microseconds. The transfer is therefore two orders of magnitude smaller than the positioning, and the positioning cost is paid once per request rather than once per byte.

This is why the throughput of a workload is governed by how many requests it issues, not by how many bytes it moves. A workload of independent 4 KiB writes at random offsets can achieve on the order of a hundred requests per second on such a device, which is well under a megabyte per second, while the same device streams over a hundred megabytes per second when the requests arrive in ascending order and can be merged. The gap is roughly three orders of magnitude, and it exists because the second workload amortizes one seek over a very large transfer.

A filesystem that updates in place is forced into the first pattern by its own metadata. Creating a single small file touches an inode, a directory entry, the directory’s data block, an allocation bitmap, and the file’s data block, and those five structures live in different regions by design, because spreading them apart is what keeps the directory from fragmenting. The blocks are also written at unpredictable times, since the ordering between them is dictated by crash-consistency rules rather than by locality. The result is a sequence of small writes to scattered addresses, and no amount of caching at the block layer can turn that into a stream unless the writes are held long enough to be sorted, which delays durability.

Batching into segments

The log-structured answer is to accept the delay deliberately and to make the batching explicit. Writes accumulate in a memory buffer. When the buffer reaches a fixed size, or when a timer expires, or when a caller demands durability, the whole buffer is written to one contiguous run of blocks at the current end of the log. The unit of this transfer is a segment: a fixed-size, aligned region, large enough that a single segment write is dominated by transfer rather than by positioning. Segment sizes in use range from a few hundred kilobytes to several megabytes, bounded above by the fact that a larger segment holds more data hostage when it is only partly filled.

Inside a segment, blocks are packed in the order they were created, with no gaps for future growth. Because the destination address is simply the current write pointer, the allocator reduces to an addition. There is no search for a free block, no bitmap to consult, and no possibility of choosing a bad address: the next block in the log is always the correct one. The kernel keeps a small number of segments open for writing at once, so that unrelated streams of updates do not have to interleave in the same buffer, but the destination of every one of them is still the head of the log.

/* Reserve n blocks at the log head. seg is the segment currently being filled;
 * off is the next free block index within it. */
static uint64_t log_reserve(struct lfs *fs, uint32_t n)
{
    if (fs->off + n > fs->blocks_per_seg) {
        segment_close(fs);              /* flush and seal the current segment */
        fs->seg = segment_alloc(fs);    /* next free segment, from the tail */
        fs->off = 0;
    }
    uint64_t blk = fs->seg * fs->blocks_per_seg + fs->off;
    fs->off += n;
    return blk;                         /* the caller never chooses an address */
}

The absence of choice is the point. Because the filesystem never decides where a block goes, it also never creates the fragmentation that an allocator would have to undo later. A file written in one pass occupies a contiguous range of the log, and reading it back sequentially is as fast as reading a freshly formatted region. The layout is optimal for the write that created it and for the read that immediately follows.

What the free-space map becomes

The cost of that simplicity is that the filesystem loses the notion of a block being free. Every block ever written is either live, meaning some file’s current version points at it, or dead, meaning it holds a superseded copy. Which one it is cannot be determined from the block itself; it depends on what the current inode and indirect blocks say, and those are also in the log and also subject to change.

Two consequences follow immediately. First, space is reclaimed only by a cleaner, a process that reads the live blocks out of a segment, appends them to the head of the log, and then declares the whole segment free. Second, the filesystem cannot run at full capacity. Cleaning requires space to write into while it is recovering space, so a fraction of the volume must remain unallocated at all times. The usable fraction is a design parameter, and the cleaning policy discussed in Choosing What to Clean exists to keep the reclaimable fraction high enough that cleaning does not become the dominant cost.

The reclamation also changes the meaning of an address. In a filesystem that updates in place, an inode number plus a block offset is a stable name for a location. Here the inode itself moves whenever it is modified, so a fixed pointer to it would go stale on the first write. The mapping from file to current block must therefore be stored somewhere that is itself updated by appending, which leads to the inode map described in Inode Maps and Block Indirection. Every read in the system passes through that map, so its cache hit rate is the single largest determinant of read performance.

The alternative that was rejected

It is worth being precise about what update-in-place buys, because the log-structured design gives it up. Fixed addresses mean that an inode is found by arithmetic: the inode number indexes directly into a table at a known offset. A block is found by following a pointer that was written once and never changes. Read amplification is one, and no lookup structure stands between the file offset and the disk block.

The price is paid on the write side. To keep the on-disk structures consistent across a crash, an update-in-place filesystem must either journal the changes (writing them twice), or order them with synchronous writes (paying a rotation per dependency), or use soft updates with its intricate dependency tracking. Each of those is a mechanism for imposing order on writes that the log gets for free, because in a log the order of the bytes is the order of the operations.

So the trade is not “fast writes versus fast reads” in the abstract. It is: the log-structured design converts a stream of small scattered writes into large sequential ones, and in exchange it adds one indirection on the read path, a collector on the write path, and a permanent space reserve. On media where positioning dominates, that exchange is heavily favorable for write-heavy workloads and mildly unfavorable for read-only ones. On media where positioning is nearly free, the exchange loses most of its value, which is why the design’s fortunes have tracked the cost of a random write rather than the cost of a random read.

Where the layout breaks down

Three failure modes are intrinsic rather than accidental.

The first is that the log is finite and the cleaner is not free. If the rate at which new data is appended exceeds the rate at which the cleaner can reclaim space, the head of the log catches the tail and the filesystem must stall writes. The stall is not a bug in the cleaner; it is the steady state of a system whose write amplification exceeds the bandwidth left over after serving the foreground. The arithmetic is worked out in Decomposing Write Amplification, and the extreme case, where the volume is nearly full and the cleaner has nowhere to stage its output, is the subject of Garbage Collection Under Space Pressure.

The second is that a crash can lose the end of the log. Everything after the last durable checkpoint is a candidate for loss, and reconstructing it requires reading the segment summaries that describe what each block in the log was. This is the roll-forward problem covered in Checkpoint Regions and Tail Recovery.

The third is temporal. Data written at the same time tends to die at the same time, so the age distribution of live bytes within a segment is not uniform. A segment holding a mixture of hot metadata and cold file data cannot be reclaimed cheaply, because cleaning it requires copying the cold half. Segregating writes by expected lifetime is the only defense, and it is why a log-structured filesystem maintains several open streams rather than one.

The layout itself is a single idea with a long tail of consequences: append everything, never overwrite, and pay for the past with a collector. Everything that follows is the accounting that idea demands.