12 · Atomicity and crash recovery: torn writes and tail detection

The power dies mid-write. What happens to the data? A DB uses WAL replay to roll back or re-apply any transaction that was in progress. Quipu-Log is built differently. Because it's append-only there's nothing to roll back, and recovery comes down to exactly one operation — trimming the broken tail. Let's look at why that's enough, and how it's done.

First, what you already know: WAL replay in a DB

When a relational DB reboots, its recovery routine walks the WAL from the beginning.

• Redo phase — re-applies anything that was committed but hadn't yet been written through to the data pages (the body).
• Undo phase — rolls back anything that had started writing to the WAL but never committed (an incomplete transaction).

Both phases are needed because a DB writes to two places — the data pages (the body) and the log. The data pages use in-place writes, scattered across the file, so a crash at the wrong moment can leave the body in a half-modified state. That mess has to be cleaned up.

torn write: a record cut short

What actually happens inside Quipu-Log when power dies in the middle of an append? Imagine the process is in the middle of tacking a new frame onto the end of the file when the lights go out.

This half-written frame is called a torn tail. The signals that say "cut here" are: the last frame's CRC doesn't match, the number of bytes present is less than the len field promises, or len exceeds MAX_RECORD (64 MiB).

skim(): finding the valid tail

In Quipu-Log, crash recovery lives entirely in one function: skim(). It walks the segment file from the beginning, accumulating the length of every frame whose CRC checks out. The moment it hits a broken frame it stops. The stopping point becomes valid_len.

crates/quipu-core/src/storage/segment.rs — skim()loop {
    if total - valid < FRAME_HEADER as u64 { break; }
    reader.read_exact(&mut header)?;
    let len = u32::from_le_bytes(header[0..4].try_into().unwrap());
    let crc = u32::from_le_bytes(header[4..8].try_into().unwrap());
    let ts  = u64::from_le_bytes(header[8..16].try_into().unwrap());
    if len > MAX_RECORD || total - valid - (FRAME_HEADER as u64) < len as u64 {
        break; // bad length → start of torn tail
    }
    buf.resize(len as usize, 0);
    reader.read_exact(&mut buf)?;
    if crc32fast::hash(&buf) != crc { break; } // CRC mismatch → torn tail
    valid += (FRAME_HEADER + len as usize) as u64;
    records += 1;
}

When the loop ends, valid holds "the file length up through the last intact frame." That value is returned as Skim::valid_len.

Cut on open: Segment::open()

Segment::open() runs skim() every time it opens a file for writing. If the file is longer than valid_len — meaning there's a torn tail — it calls file.set_len(valid_len) to cut it off cleanly. It then positions the BufWriter at valid_len and starts writing from there.

crates/quipu-core/src/storage/segment.rs — Segment::open()match skimmed {
    Some(s) => {
        if file.metadata()?.len() > s.valid_len {
            file.set_len(s.valid_len)?; // trim the torn tail
        }
        let mut writer = BufWriter::with_capacity(256 * 1024, file);
        writer.seek(SeekFrom::Start(s.valid_len))?;
        Ok(Self { /* ... start from a valid state */ })
    }
    None => {
        // Empty file or a torn header: start fresh
        file.set_len(0)?;
        /* rewrite header */
    }
}

Reading this code, you can see the whole shape of recovery. No complex replay — just validate on open, then trim the broken end. The entire recovery process fits in two functions: skim + set_len.

Why redo alone is enough

A DB needed both redo and undo. Why does Quipu-Log need neither?

Because it's append-only. Once a record has been fully written, that spot on disk is never touched again. "Something half-written" means exactly one thing: a partial frame at the very end of the file. Every record before it is intact. So there's nothing to redo — the intact records are already on disk. And there's nothing to undo — once you trim the partial frame, that record never existed.

base_index: preserving Merkle positions

Trimming the tail doesn't quite close the story. Quipu-Log commits every record to a Merkle tree Ch. 20, Merkle tree. A record's position in that tree (its leaf index) is determined by which record number it is in the overall log. Multiple segments can exist, and older ones can be deleted by retention — but the leaf index of surviving records must never change.

To guarantee this, the segment header carries a base_index — the position of this segment's first record within the full log. A record's absolute leaf index is base_index + offset within the segment. When opening an existing segment, base_index is read from the header; for a brand-new file it's supplied as an argument and written there. Trimming the torn tail leaves the header (and therefore base_index) intact, so every record that survives gets the same leaf index it had before the crash.

Confirmed by a test: does recovery actually work?

The source ships a unit test for exactly this. Write two records and sync them, then manually splice a broken half-frame onto the end of the file. Reopen the same file — the torn tail is trimmed automatically, and a third record can be appended normally.

crates/quipu-core/src/storage/segment.rs — tests// Simulate a crash: append a half-frame directly to the file
{
    let mut f = OpenOptions::new().append(true).open(&path).unwrap();
    f.write_all(&[9, 0, 0, 0, 1, 2]).unwrap(); // len=9 but no payload
}
// Reopen — the torn tail is removed automatically
let mut seg = Segment::open(&path, 0).unwrap();
seg.append(b"gamma", 3).unwrap();
seg.sync().unwrap();
// Reading back yields: alpha, beta, gamma (no torn frame)

Recap

• A DB needs both redo and undo recovery because its body (B-tree) uses in-place writes.
• Quipu-Log is append-only, so a crash produces at most one torn tail — a single partial frame. skim() computes valid_len; set_len() trims the rest. No redo, no undo.
• A CRC mismatch or an out-of-range length value is the signal that a torn tail has been reached.
• base_index lives in the segment header. It guarantees that Merkle leaf indexes stay stable across retention deletes and crashes.