Checkpoint Regions and Tail Recovery in an Append-Only Log

An append-only log has no natural consistency point. There is no transaction boundary, no commit record, and no moment at which the on-disk state is known to be self-consistent, because writes are continuous and the write pointer is always in motion. A crash leaves the log with an arbitrary tail: some suffix of the most recent segments may have reached the platter, some may be partially written, and the block layer may have reordered writes that the filesystem issued in a particular sequence. Recovery must nonetheless produce a mountable volume and must not resurrect data that a completed operation had replaced.

The mechanism that makes this tractable is the checkpoint, a region of the volume written at a known location whose contents describe a complete, self-consistent state of the log. Recovery reads the checkpoint, reconstructs the metadata structures it describes, and then rolls forward through whatever was written after it.

Why the write pointer cannot be trusted

The naive recovery is to read the write pointer from a fixed location and continue from there. The difficulty is that the pointer is updated after every segment, so its own write is one of the small scattered writes the log exists to avoid, and it is not atomic with respect to the data it points past. If the pointer is written before the segment it names, a crash in between leaves a pointer into a segment that was never written. If it is written after, a crash in between leaves the pointer lagging, and the blocks beyond it are invisible.

Neither ordering is safe, and a single pointer word is not enough to distinguish the two cases because a torn write of that word is possible. The fix is to make the fixed location hold not a pointer but a checkpoint: a structure that carries the timestamp of its own writing, a version counter, and enough redundancy that a partial write can be detected.

A checkpoint is written by quiescing the filesystem, flushing the buffer cache, writing the current inode map index and the current segment-usage state to a checkpoint region, and then atomically publishing the checkpoint’s location. The original implementation wrote two checkpoint regions at opposite ends of the volume and alternated between them, so that a torn write to one left the other intact; the timestamp inside each is compared at mount time to select the newer valid one.

What a checkpoint must contain

The checkpoint’s job is to eliminate all the state that cannot be reconstructed by scanning. Anything that is only in memory and not derivable from the log must be written into the checkpoint region.

The inode map index is the largest item. Without it, recovery would have to scan the entire log to find every map block, because map blocks are not identifiable from their contents alone. With it, the map is immediately available and every inode is reachable.

The segment usage table is the second. It records, per segment, how many live bytes the segment contains and when it was last modified. This is what the cleaner consults to decide what to clean, and it cannot be rebuilt without reading every block in the log and resolving each against the current inode map, as the accounting discussion in Segment Liveness Accounting sets out. That is a full-volume scan, which is precisely what a checkpoint is meant to avoid.

The last is the write pointer itself, plus the identity of the open segments and the position within them. With those, recovery knows where valid data ends.

A checkpoint therefore has a size proportional to the number of segments plus the number of map blocks, which for a large volume is on the order of a few hundred kilobytes to a few megabytes. Writing it is a real cost, which is why checkpoints are taken at intervals measured in tens of seconds rather than after every segment. The interval is the bound on how much roll-forward work recovery must do, and it is the design knob that trades write overhead against recovery time.

Roll-forward from the checkpoint

Everything after the checkpoint’s recorded position is a suffix of segments whose contents are not described by any durable metadata. Recovery must read them and rebuild the segment summaries they carry.

The key insight is that the log can be scanned in the forward direction and that each block is self-describing enough to be interpreted. A segment contains a summary at a known position within it, listing every block in that segment: its kind (inode, data, indirect block, directory entry, map block), the inode it belongs to, and its offset within that file. The summary is written as part of the segment and is covered by the same write, so a segment that is present at all has a summary that describes it.

/* Rebuild state by walking forward from the last checkpoint. */
int recover_tail(struct lfs *fs, uint64_t start_seg)
{
    for (uint64_t s = start_seg; s != fs->write_seg; s = next_seg(fs, s)) {
        struct summary *sm = read_summary(fs, s);
        if (!summary_valid(sm, s)) {
            /* Torn or missing: nothing after this point can be trusted. */
            fs->write_seg = s;
            break;
        }
        for (int i = 0; i < sm->nblocks; i++) {
            struct dentry *e = &sm->blocks[i];
            switch (e->kind) {
            case BLK_INODE:
                imap_install(fs, e->ino, addr_of(s, i));  /* map now points here */
                break;
            case BLK_IMAP:
                imap_index_install(fs, e->blk, addr_of(s, i));
                break;
            case BLK_DATA:
                break;   /* accounted for by the inode that references it */
            }
        }
        segusage_update(fs, s, sm);
    }
    return 0;
}

The order matters. Map blocks must be installed before the inodes they describe are considered reachable, and inodes must be installed before the data they point to is counted as live. Walking forward and installing as it goes gives the correct final state, because a later summary that supersedes an earlier entry for the same inode simply overwrites the map entry, and the earlier copy of that inode is thereby dead.

A block whose summary entry is valid but whose inode was superseded later in the scan is dead space in its segment. That is not an error; it is ordinary garbage, and the cleaner will reclaim it on the next pass. The scan’s purpose is to establish what is live, not to make every block live.

The torn-write problem inside a segment

The summary is a single block within a segment, and the segment is written as one large transfer, but the transfer is not atomic. A device may complete some portion of it and lose the rest, and modern devices with internal caches may reorder the writes within the transfer unless the filesystem issues a flush at the right point.

The original design handled this by writing the summary twice, at the beginning and at the end of the segment, with a checksum over the summary’s contents and a timestamp. A segment whose head summary validates but whose tail does not was partially written, and the valid prefix of the summary tells recovery exactly how many blocks are present. A segment whose head summary does not validate is treated as empty and its space is immediately available for reuse.

The checksum is essential and is the part most easily omitted in a reimplementation. Without it, a block of stale data from an earlier use of the segment can be mistaken for a valid summary, and recovery installs map entries pointing into garbage. The failure is silent: the volume mounts, files appear, and their contents are wrong. The checksum converts that into a clean truncation of the log.

Idempotence and repeated crashes

Recovery itself writes, because installing the rebuilt inode map and segment usage into memory and then checkpointing them produces new log traffic. A crash during recovery must not leave the volume in a worse state than the crash that triggered it.

Two properties are required. Recovery must be idempotent: running it twice from the same checkpoint must produce the same state, which holds as long as the scan is purely a function of the log’s contents and the checkpoint. And the recovery process must not overwrite anything that a later recovery needs. Since recovery’s writes go to the head of the log, beyond the point it is scanning, and its checkpoint is published only at the end, a crash mid-recovery leaves the original checkpoint intact and the scan simply repeats.

The exception is the checkpoint write itself. Publishing a checkpoint is the one non-idempotent step, which is why the two-region alternation matters: the new checkpoint goes to the region not currently in use, and the old one remains valid until the new one’s checksum verifies.

What the interval costs

Checkpointing every ten seconds on a volume writing at tens of megabytes per second means up to a few hundred megabytes of log must be scanned after a crash, since the scan must read every block in that range. That is bounded and predictable, and it is far less than a full-volume consistency check, which reads every block in the filesystem regardless of when it was written.

The comparison with journaling is instructive. A journal bounds recovery by the size of the journal, which is typically a few tens of megabytes, and recovery replays only the transactions it contains. The log-structured checkpoint bounds recovery by the write rate times the checkpoint interval, which is larger and variable. In exchange, the log-structured design never writes anything twice: the journal of a journaling filesystem is pure overhead, while the log here is the filesystem’s only copy of the data.

The residual exposure is the interval itself. Any data written and acknowledged but not covered by a checkpoint is recoverable only if its segment reached the device, and the filesystem cannot promise more than that without a synchronous flush. Shortening the interval is not free: every checkpoint rewrites the inode map index and the segment usage table, and that recurring cost is one of the terms counted in Decomposing Write Amplification. What recovery guarantees is narrower and stronger than durability of the last few seconds: the volume always mounts, the structures it contains always satisfy their invariants, and no superseded version of any object is ever presented as current.