The Circular Log: Head, Tail, and the Distance Between Them

An append-only log on a finite volume must eventually reuse space, and the only space available is the space its own past occupies. The structure that makes this possible is a circular buffer of segments: the write head advances through segment numbers in increasing order, wrapping from the last to the first, while a reclaim frontier advances behind it. A segment is writable only after the frontier has passed it, and the frontier advances only when the cleaner has established that every block in the segment is dead.

The distance between the two pointers is the resource that determines what the filesystem can do. If the head is far ahead of the frontier, there is plenty of writable space, cleaning can be lazy, and writes never stall. If the head is close, every write requires a cleaning pass to be completed first, and the filesystem’s throughput collapses to the cleaner’s rate.

The three states a segment can occupy

The invariant that makes wrapping safe is that a segment is never written while any of its previous contents might still be live. Enforcing that requires tracking each segment’s state explicitly.

A free segment has been cleaned and contains no live data. It is available to the write head.

A partial segment is currently being filled. Its contents are live by definition, because nothing in it has been superseded yet. Several partial segments may exist at once, one per write stream.

A full segment is closed and immutable. Its blocks may be live or dead, and its live byte count decreases over time as writes elsewhere supersede its contents. It is a candidate for cleaning.

A fourth state is needed in practice: cleaning, meaning the collector has selected the segment, is copying its live contents to the head, and the segment must not be written or re-selected until the copy is complete. Without this state, a crash between the copy and the state transition would leave the filesystem unable to decide whether the segment’s old contents or the copies are authoritative.

The transitions are one-way within a cycle: free becomes partial when the head enters it, partial becomes full when it is closed, full becomes cleaning when selected, and cleaning becomes free when the last live byte has been copied. A segment that is freed returns to the end of the free queue, which is the front of the circular order.

Head, tail, and the invariant that keeps them apart

Let the volume have N segments numbered 0 to N−1. The write head is a segment number h plus an offset within it. The reclaim frontier, usually called the tail, is a segment number t. The filesystem’s central invariant is that the head never enters a segment that is not free, which means the head’s advance is bounded by the tail’s advance.

The number of segments between head and tail, counted in the direction of travel, is the volume’s available write space. It is not a fixed number: it fluctuates as the head advances and the cleaner catches up. The design target is to keep it above a threshold, because a small gap has two effects. It removes the cleaner’s own staging space, since the cleaner writes copies to the head and needs room to do so. And it removes the filesystem’s ability to absorb a burst, since a burst of writes advances the head faster than the cleaner can advance the tail.

/* Free segments strictly between the head and the tail, counted forward.
 * Zero means the head sits in the segment immediately before the tail. */
static uint32_t gap(const struct lfs *fs)
{
    uint32_t h = fs->head_seg, t = fs->tail_seg;
    return (t + fs->nsegs - h - 1) % fs->nsegs;
}

/* The write head may only enter a free segment. */
static int advance_head(struct lfs *fs)
{
    uint32_t next = (fs->head_seg + 1) % fs->nsegs;
    if (fs->seg_state[next] != SEG_FREE)
        return -ENOSPC;              /* caller must wait for the cleaner */
    fs->head_seg = next;
    fs->seg_state[next] = SEG_PARTIAL;
    return 0;
}

A gap of zero means the head is in the segment immediately before the tail, and every segment is either full or partial. That is a full volume, and the filesystem can only make progress by cleaning. A gap of one means exactly one free segment remains, which is enough for the cleaner to write into but not enough to absorb any burst. Sizing the reserved gap is the central capacity decision in a log-structured design, and it is the reason such filesystems report less usable capacity than their raw size.

Why the cleaner needs room to work

The cleaner’s operation is: read segment t, write its live blocks to the head, then free t. If the head is in the segment immediately before t, there is no free segment for the head to write into, so the cleaner cannot begin. It has nothing to write into and nothing to free. The filesystem is deadlocked in the precise sense: no operation can proceed.

The minimum viable gap is therefore one free segment plus whatever the cleaner’s copy occupies, and the copy can be as large as the whole segment in the worst case. If the cleaner must copy a full segment to free it, it needs an entire segment of space to copy into, so freeing one segment requires two: one to write into and one to free. That is why a log-structured volume cannot be run at 100 percent and why the reserved fraction is not merely a safety margin but a functional requirement.

The worst case is worth stating precisely. If every segment has live fraction u, cleaning one segment frees (1 − u)·S net bytes after copying u·S. To sustain a foreground write rate of W, the cleaner must free W bytes per second, so it must process W / ((1 − u)·S) segments per second and copy u·W / (1 − u) bytes per second. At u = 0.5 the cleaner’s write traffic equals the foreground’s, and the device must deliver twice the foreground rate to keep up. At u = 0.8 it must deliver five times. This is the same arithmetic as the write amplification decomposition, seen from the capacity side rather than the bandwidth side, and it is set out in Decomposing Write Amplification.

Wrapping and the write pointer’s persistence

The head position is not durable. It is written into the checkpoint, but the checkpoint is taken at intervals, so after a crash the recovered head is the position at the last checkpoint, and every segment written since then must be scanned to find where the valid data actually ends.

That scan is a forward walk from the checkpoint’s head, examining each segment’s summary to determine whether it was fully written. The walk stops at the first segment whose summary is invalid or whose timestamp is older than the one before it, which detects the wrap: a segment with an older timestamp that appears after a newer one is a segment from a previous cycle that was never overwritten, and its contents are not part of the current log’s tail.

The timestamp check is the only thing that distinguishes “the log ended here” from “the log wrapped and this is stale data”. Without it, recovery reads old segments as if they were new, and installs map entries pointing at data from before the crash. This is a concrete instance of the general rule that recovery must validate rather than assume, discussed in Checkpoint Regions and Tail Recovery.

Segment numbering and the modulo hazard

The segment number used to address the device is a physical block address, so the mapping from circular position to physical location is a modulo operation. If the segment size is not a power of two, or if the number of segments is not, the modulo is a division, and the cost of that division on the write path is measurable but small.

The real hazard is not arithmetic but aliasing. Two segments that are adjacent in circular order are adjacent physically only if the volume’s segment count divides evenly into the address space; otherwise the wrap point introduces a discontinuity where consecutive log positions map to distant physical addresses. Writes that cross the wrap therefore become two transfers rather than one, and the sequentiality that the design depends on is broken for exactly one segment per cycle.

The fix is to align the volume so that the number of segments is a power of two and the segment size is a multiple of the device’s erase or transfer granularity. Then the wrap is a single bit flip in the segment number, and the physical discontinuity is confined to the volume’s own boundary, which the device handles as a normal seek between two regions rather than as a pathological jump.

Where the circular model breaks

Two situations escape the model.

The first is a workload that writes faster than the cleaner can reclaim, permanently. The head advances to within the reserved gap and stays there, and every write blocks until the cleaner completes a pass. The filesystem is then operating in a degraded mode where its throughput is the cleaner’s throughput, and no amount of scheduling improves it, because the binding constraint is the live fraction of the data being cleaned. This is the space-pressure regime examined in Garbage Collection Under Space Pressure.

The second is a volume with immovable data. If a large fraction of the volume consists of blocks that are never superseded, those blocks are copied on every cleaning pass and never become free. The live fraction u has a floor equal to the immovable fraction, and if that floor is high enough, cleaning costs more than it frees regardless of policy. The circular model still functions, but the achievable write rate is bounded by the excess of device bandwidth over the copy cost, which can be arbitrarily small.

Neither failure is a defect in the circular structure. Both are consequences of the same conservation law: space is freed only by copying live data, and copying live data consumes the space that was freed. The gap between head and tail is the buffer that lets the filesystem absorb the mismatch between when space is consumed and when it becomes available again, and its size is the only lever that separates a smooth system from one that stalls.