The First Transaction and 260,000 Crash Replays---Writing a COW Filesystem from Scratch, Part 5

The red leaves at the SAIJOU mountain spend the whole summer getting ready before they bloom. After that it happens every year: spring, summer, autumn, winter.

This is a file system written from scratch. It stands on the shoulders of giants, but it doesn't simply copy them, so it has to solve some problems of its own.

1. Where do the decisions behind the code come from?
2. What should each stage implement?
3. How do we prove that nothing is wrong right now?

1　Where do the decisions behind the code come from?

For about three weeks, not a single line of code was written in crates/. The repository had no crates/ directory and no root Cargo.toml. Every day went into research and testing under research/, which piled up some ninety-odd model binaries.

Beyond the twenty-one ground rules, the project started from these decisions: keep a reverse index (D1); variable-width full stripes (D2); no split between data and metadata, one unified allocator (D3); accounting with birth txg plus deadlists (D5); stay out of the Linux mainline for the first few years (D7).

On top of that, after many rounds of the agents' three-way process, a first version of the following was settled:

• Format: device identity bits, every byte in the unit header, tree types, the records that carry generation identifiers.
• Root record: its byte width and what goes into it.
• Journal: data types and how records are written.
• Tree table: byte width, height, and organization.

And, of course, the format constants. All decisions live in .claude/kb/decisions/ and all experiments in .claude/kb/experiments/; the experiment rigs, the three-way materials, and the verdicts live in research/.

The last gate before coding was a full review of the decisions. The 28 decision documents were split across eleven review legs (eight Opus, three Sonnet), with a single criterion: if two people each implemented "new pool, new file" from today's text, would they write different bytes? The review produced 31 items that needed a ruling, and the user decided them one by one.

Turning decisions into bytes was the job of experiment E142 (a dry run of "new pool, new file"): an independent rig under research/ writes the byte table out exactly as specified, then recovers from every crash state in the crash model. It ran seven times, and every run forced out a few gaps where the byte table could not actually be written.

So by the time crates/ was written, there was already a working answer in hand.

2　What should each stage implement?

Because this is a COW file system built from zero, there is no existing standard to verify against and no reference implementation whose output we could compare. And because we get to enjoy the advantages of our time, there was no need to build FUSE first and verify by mounting. So we committed to a staged plan built around transactions: every feature is a new kind of transaction, and no feature is accepted without the transaction layer.

What should each stage implement? There is no answer yet. But the first transaction is not in doubt: create the disks, then do one COW write.

Milestone one is called "new pool, new file": run mkfs on two disks, write a 3000-byte file, commit once, throw away everything in the process, cold-start, and read the file back. It is split into eight steps, and every step's acceptance test must first prove that it can fail:

Step	What it does
0	Scaffolding: four crates (format constants, core, harness, pool-level checker), a block-device abstraction, a recorder
1	mkfs: system configuration, three root-ring regions, the journal ring, the instance table, an empty tree table, the generation-0 root
2	Allocate one 32 KiB data unit, write the file contents into it, one copy on each disk
3	The inode tree, extent tree, allocation-record tree, and accounting tree
4	The central mapping: logical identity → location
5	One publish
6	Cold-start recovery, read the file back
7	Layer-0 crash-point replay

3　How do we prove that nothing is wrong right now?

With nothing to compare against, the implementation has to prove itself. Building crash recovery alongside it was also a goal. So crash replay testing is the top priority. Put simply: record the on-disk state at every crash point, run recovery, and check the result with the judges.

There are other tests too:

• Mixing the two address types fails to compile;
• If the recorder misses one write, the write-count gate fails;
• Two mkfs runs with the same parameters produce byte-identical images;
• The segment sequences of the five write paths match the E142 output exactly, and the journal back chain matches the experiment's back_chain=628216162 exactly;
• Eight probes that corrupt the root slot, the journal, a data unit, or the system configuration each end exactly as the experiment's output says;
• Subset enumeration within segments, three judges, and so on.

One more word on the back chain: the experiment rig and crates/ were written separately from the same set of clauses and share no code. When both arrive at the same number for the same quantity, the byte table, the clauses, and the implementation agree on that quantity. If either side gets one thing wrong, the comparison fails.

Code and implementation: the first transaction and 260,000 replays

The code below comes from two places: experiment code from the E77 rig under research/, and implementation code from crates/. Lines unrelated to the first transaction were removed from the excerpts and marked with // ….

1　The first transaction

After mkfs, the full write sequence is made of three paths:

• Instance acquisition: write instance generation 1 into the system configuration on each disk, 2 writes.
• Two empty warm-up publishes: move checkpoint_txg 0 → 1 → 2, 10 writes.
• The real publish at txg 3: 21 writes — 8 units written to both disks (16), 2 journal records, 1 root slot, and 2 system configuration writes.

The warm-up comes from D16, settled item 8: on the first mount, this instance's root must reach both disks before fsync returns.

Every publish reaches the disk in the same order:

units and index nodes (one copy on each disk)
  → barrier
  → journal record (one copy on each disk)
  → barrier
  → root slot FUA write (region txg mod 3, slot (txg div 3) mod 8)
  → system configuration slot rotation (once per disk, tail = jsn counter)

E77 measured this order before any code was written: data integrity needs only the barrier before the root slot; the barrier between the record and the root slot is there to keep the record stream complete.

Instance acquisition, warm-up, and publish all reach the disk through one closed enum. The design rule is "one transaction layer, shared by every structure"; fsync does not get a second one:

Implementation　crates/singlefs-core/src/transaction.rs

// No wildcard arm: leave one out and it does not compile.
pub enum CommitStep<'publish> {
    WriteUnitToEveryDevice { slot: SlotNumber, unit: &'publish [u8], identity: TransactionUnit },
    WriteJournalRecordToEveryDevice { counter: u64, record: &'publish [u8] },
    /// Root slot FUA write: region `txg mod 3`, slot `(txg div 3) mod 8`, on the disk that owns that region.
    WriteRootRecordForceUnitAccess { checkpoint_txg: CheckpointTxg, root_slot: &'publish [u8] },
    /// One in-place system configuration slot write per disk: generation = highest self-verified
    /// generation of the two slots on this disk + 1, slot = generation mod 2.
    RotateSystemConfigurationSlots { journal_tail: u64, journal_instance: InstanceGeneration },
    Barrier,
}

pub fn perform_commit_step(&mut self, step: CommitStep<'_>) -> Result<(), BlockDeviceError> {
    // …
    match step {
        CommitStep::WriteUnitToEveryDevice { slot, unit, .. } => {
            for (_, device) in self.devices.iter_mut() {
                device.write_at(slot.to_device_offset(), unit, WriteDurability::Plain)?;
            }
        }
        CommitStep::WriteJournalRecordToEveryDevice { counter, record } => {
            let offset = record_offset(counter, self.parameters.geometry.journal_ring_bytes);
            for (_, device) in self.devices.iter_mut() {
                device.write_at(offset, record, WriteDurability::Plain)?;
            }
        }
        CommitStep::WriteRootRecordForceUnitAccess { checkpoint_txg, root_slot } => {
            let target = target_for_publish(checkpoint_txg, self.parameters.geometry.root_ring_slots_per_region);
            let region_device = self.parameters.region_devices[usize::try_from(target.region).expect("region number")];
            let (_, device) = self.devices.iter_mut()
                .find(|(identity, _)| *identity == region_device)
                .expect("mkfs's check_geometry has verified region ownership");
            device.write_at(
                slot_offset(target, self.parameters.geometry.fixed_structure_slot_spacing),
                root_slot,
                WriteDurability::ForceUnitAccess,
            )?;
        }
        CommitStep::RotateSystemConfigurationSlots { journal_tail, journal_instance } => {
            for index in 0..self.devices.len() {
                self.write_system_configuration_slot(index, journal_tail, journal_instance, /* … */)?;
            }
        }
        CommitStep::Barrier => {
            for (_, device) in self.devices.iter_mut() {
                device.barrier()?;
            }
            // …
        }
    }
    Ok(())
}

A publish hands its bytes to it in order. All three paths share this one place:

Implementation　same file

/// Hand one publish's bytes to the devices in durability order. All three publish paths share
/// this one place — separate copies would drift apart, and "root slot before system configuration
/// slot" is exactly the premise of those few cells in the crash window.
fn persist_publish_writes<Device: BlockDevice>(
    writer: &mut PoolWriter<'_, Device>,
    writes: &PublishWrites,
) -> Result<(), BlockDeviceError> {
    for unit in &writes.units {
        writer.perform_commit_step(CommitStep::WriteUnitToEveryDevice {
            slot: unit.slot, unit: &unit.bytes, identity: unit.identity,
        })?;
    }
    writer.perform_commit_step(CommitStep::Barrier)?;
    for record in &writes.records {
        writer.perform_commit_step(CommitStep::WriteJournalRecordToEveryDevice {
            counter: record.counter, record: &record.bytes,
        })?;
    }
    writer.perform_commit_step(CommitStep::Barrier)?;
    // In the original, these two steps live in a small helper; inlined here.
    writer.perform_commit_step(CommitStep::WriteRootRecordForceUnitAccess {
        checkpoint_txg: writes.checkpoint_txg, root_slot: &writes.root_slot,
    })?;
    writer.perform_commit_step(CommitStep::RotateSystemConfigurationSlots {
        journal_tail: writes.journal_tail, journal_instance: writes.journal_instance,
    })
    // …
}

Journal records are linked by a back chain: each record stores the CRC-32C of the previous record's header.

Implementation　crates/singlefs-core/src/journal.rs

/// Back chain: over the previous record's whole header, with the 32 bytes of `header_csum` taken as 0.
pub fn back_chain_of(previous_record_bytes: &[u8]) -> u32 {
    let mut header =
        previous_record_bytes[..usize::try_from(JOURNAL_HEADER_BYTES).expect("487")].to_vec();
    header[JOURNAL_HEADER_CHECKSUM_OFFSET
        ..JOURNAL_HEADER_CHECKSUM_OFFSET + usize::try_from(WIDE_CHECKSUM_BYTES).expect("32")]
        .fill(0);
    crc32_castagnoli(&header)
}

The kinds of steps are registered in exactly one place: the segment-sequence table in section 8 of the byte table. The gate compares the recorded stream's segment sequence and kind string against that table character by character; both the experiment rig and the implementation must match it.

2　The crash-point design

The crash model is D13, settled item 4: the stream of write requests is cut into segments at barriers. A crash state is: every earlier segment fully durable, any subset of writes in the current segment durable, every later segment not durable at all. Locations that are not durable hold the bytes they had before the crash, and the resulting images are fed to the judges.

Earlier segments	Current segment	Later segments
all durable	any subset of writes durable	none durable

The first transaction's 33 writes split into ten segments at the barriers:

Segment	1	2	3	4	5	6	7	8	9	10
Path	Acquire	Warm-up 1	Warm-up 1	Warm-up 1	Warm-up 2	Warm-up 2	Warm-up 2 + publish	Publish	Publish	Publish
Writes	2	2	1	2	2	1	18	2	1	2
What	Sys config	Record	Root slot	Sys config	Record	Root slot	Sys config 2 + units 16, no barrier between them	Record	Root slot	Sys config

Segment sequence 2+2+1+2+2+1+18+2+1+2. Which step each segment belongs to is inferred from two lines in the records: "the acquisition writes and the first warm-up's barrier form the opening segment" and "the second warm-up's system configuration writes share a segment with the transaction's unit writes".

Code: cutting at barriers and enumerating crash states

Experiment code　E77: one publish scaled down to 6 units, 3 records, and 1 root slot — 10 writes — under four barrier placements

/// The segments that barriers cut 0..TOTAL_WRITES into. No `_ =>` wildcard arm.
fn segments(self) -> Vec<Vec<usize>> {
    let units: Vec<usize> = (0..UNITS).collect();
    let records: Vec<usize> = (UNITS..UNITS + RECORDS).collect();
    let root = vec![ROOT_SLOT_WRITE_INDEX];
    match self {
        Arm::BothBarriers => vec![units, records, root],
        Arm::BarrierAfterUnitsOnly => vec![units, [records, root].concat()],
        Arm::BarrierBeforeRootOnly => vec![[units, records].concat(), root],
        Arm::NoBarriers => vec![[units, records, root].concat()],
    }
}

/// Enumerate every crash state of one arm (as a bitmap of the durable set).
/// Barrier semantics: any write durable in segment f ⇒ every write in segments < f is durable.
fn crash_states(arm: Arm) -> BTreeSet<u16> {
    let segments = arm.segments();
    let mut states = BTreeSet::new();
    for frontier in 0..segments.len() {
        // segments < frontier: all durable
        let mut base_state: u16 = 0;
        for segment in segments.iter().take(frontier) {
            for &write_index in segment {
                base_state |= 1 << write_index;
            }
        }
        // current segment: any subset
        let current_segment = &segments[frontier];
        for subset_mask in 0u32..(1 << current_segment.len()) {
            let mut crash_state = base_state;
            for (position_in_segment, &write_index) in current_segment.iter().enumerate() {
                if subset_mask & (1 << position_in_segment) != 0 {
                    crash_state |= 1 << write_index;
                }
            }
            states.insert(crash_state);
        }
    }
    states
}

A BTreeSet collects them because adjacent segments overlap at the boundary: "all of the previous segment" equals "none of the next one". Only after deduplication do you get the number of distinct states.

3　Recovery model and independent audit

Every crash state gets one recovery run. If the root slot is there, walk the tree, verifying checksums along the read path. If not, fall back to the old root, take the journal prefix with strictly consecutive jsn, apply it only if the commit mark is present, and verify each named unit before applying.

Experiment code　E77

/// Recovery outcomes. Three states are not enough — "partial transaction" must be its own cell;
/// folding it into old or new would hide violations.
enum Outcome { StateOld, StateNew, BrokenRoot, Corrupt }

fn recover(state: u16, replay: Replay) -> Outcome {
    // Verify every candidate first, then pick the newest by generation (D22's settled read order).
    if persisted(state, ROOT_SLOT_WRITE_INDEX) {
        // Walk: the read path always verifies checksums; a non-durable unit reads stale bytes ⇒ mismatch.
        for unit_index in 0..UNITS {
            if !persisted(state, unit_index) {
                return Outcome::BrokenRoot;
            }
        }
        return Outcome::StateNew;
    }
    // Old root S0 chosen: replay. Prefix = strictly consecutive jsn (from R0, stop at the first gap).
    let mut prefix_record_count = 0;
    for record_index in 0..RECORDS {
        if persisted(state, UNITS + record_index) {
            prefix_record_count = record_index + 1;
        } else {
            break; // stop at the first gap
        }
    }
    // Transaction filter: the commit mark is on the last record; no mark in the prefix ⇒ incomplete, drop it all.
    if prefix_record_count != RECORDS {
        return Outcome::StateOld;
    }
    match replay {
        Replay::Validating => {
            // Verify each named unit before applying; any mismatch ⇒ drop the whole transaction (old state).
            for record_index in 0..RECORDS {
                for unit_index in units_named_by_record(record_index) {
                    if !persisted(state, unit_index) {
                        return Outcome::StateOld;
                    }
                }
            }
            Outcome::StateNew
        }
        // No verification: graft directly and claim success. Whether it was wrong is for audit to decide, not itself.
        Replay::Naive => Outcome::StateNew,
    }
}

/// Independent audit: re-judge the outcome recovery claims against the physical truth.
/// Without this step, silent corruption from "replay without verification" would be counted as success.
fn audit(state: u16, claim: Outcome) -> Outcome {
    if claim == Outcome::StateNew && (0..UNITS).any(|unit_index| !persisted(state, unit_index)) {
        return Outcome::Corrupt;
    }
    claim
}

/// Falling back to the old state after the root slot is durable (fsync may have returned) = losing promised data.
fn is_violation(state: u16, outcome: Outcome) -> bool {
    match outcome {
        Outcome::BrokenRoot | Outcome::Corrupt => true,
        Outcome::StateNew => false,
        Outcome::StateOld => persisted(state, ROOT_SLOT_WRITE_INDEX),
    }
}

Recovery only reports the outcome it believes in; audit re-judges it against the durable set. The auditor and the audited never share code — a rule later carried over into crates/ as is. Results for the four barrier placements:

Barrier placement	States	Violations (verified replay)	Violations (no verification)
[units][records][root]	72	0	0
[units][records+root]	79	0	0
[units+records][root]	513	0	63
[no barriers]	1024	504	567

Remove the verification before applying, and the placement with only the barrier before the root slot immediately shows 63 silent grafts. So "each item a record names carries its own checksum" is not a nice-to-have — it is the price of dropping a barrier.

Closed form for the number of states

Each segment contributes all of its proper subsets, plus one more for "everything durable":

states = 1 + Σ (2^|segment| − 1)

After mkfs, "new pool, new file" has the segment sequence 2+2+1+2+2+1+18+2+1+2, 33 writes in total. Plugging in:

3 + 3 + 1 + 3 + 3 + 1 + 262,143 + 3 + 1 + 3 + 1 = 262,165

The 16 writes of 8 units to both disks, plus the second warm-up's two system configuration slot writes, have no barrier between them and fall into the same segment. 2^18 = 262,144. So the 260,000 figure is essentially the power set of one 18-write segment. The number of states grows exponentially with segment length.

This number grew step by step. E142's first run enumerated only the transaction's 21 writes, segments 16+2+1+2, 65,543 states; the fourth run, once the warm-up wrote real bytes, 262,162; the sixth, after the two acquisition writes joined the opening segment, 262,165.

4　The checker

The pool-level checker (crates/singlefs-checker) shares only the format-constants module with the implementation: CRC-32C is written again bit by bit, and the parsing of the three slot kinds and of units is written twice. If the runtime and the checker used the same code, they would be the same computation, and the cross-check would be worth nothing.

The checker computes the same back chain itself, with a bitwise CRC, not the implementation's:

Implementation　crates/singlefs-checker/src/lib.rs

/// Bitwise CRC-32C (reflected polynomial 0x82F63B78): no table, no call into the implementation's version.
pub fn crc32_castagnoli_bitwise(bytes: &[u8]) -> u32 {
    const POLYNOMIAL_REFLECTED: u32 = 0x82F6_3B78;
    let mut remainder = !0u32;
    for byte in bytes {
        remainder ^= u32::from(*byte);
        for _bit in 0..8 {
            remainder = if remainder & 1 == 1 {
                (remainder >> 1) ^ POLYNOMIAL_REFLECTED
            } else {
                remainder >> 1
            };
        }
    }
    !remainder
}

/// Back chain: CRC-32C of the previous record's header, with the 32 bytes of `header_csum` taken as 0.
pub fn back_chain_of_record_header(record: &[u8]) -> u32 {
    let mut header = record[..usize::try_from(JOURNAL_HEADER_BYTES).expect("487")].to_vec();
    header[JOURNAL_HEADER_CHECKSUM_OFFSET..JOURNAL_HEADER_CHECKSUM_OFFSET + 32].fill(0);
    crc32_castagnoli_bitwise(&header)
}

/// Self-verifying checksum of a slot or unit: over the covered range with the checksum field as 0;
/// the first 4 bytes are the CRC, the rest all 0.
pub(crate) fn checksum_field_holds(bytes: &[u8], cover_end: usize, field_offset: usize) -> bool {
    let field_width = usize::try_from(WIDE_CHECKSUM_BYTES).expect("32");
    if bytes.len() < cover_end || field_offset + field_width > cover_end {
        return false;
    }
    let mut covered = bytes[..cover_end].to_vec();
    covered[field_offset..field_offset + field_width].fill(0);
    let expected = crc32_castagnoli_bitwise(&covered).to_le_bytes();
    let stored = &bytes[field_offset..field_offset + field_width];
    stored[..4] == expected && stored[4..].iter().all(|byte| *byte == 0)
}

/// Choose the system configuration slot: checksum valid and highest generation.
pub fn choose_system_configuration(slots: &[&[u8]]) -> Option<(usize, SystemConfigurationView)> {
    slots
        .iter()
        .enumerate()
        .filter_map(|(index, slot)| check_system_configuration_slot(slot).ok().map(|view| (index, view)))
        .max_by_key(|(_, view)| view.slot_generation)
}

The entry point takes a single image and reports each invariant as holds, violated, or not applicable:

Implementation　crates/singlefs-checker/src/walk.rs

/// Entry point of the pool-level checker: every invariant is reported; ones not evaluated are
/// reported "not applicable" with a reason.
pub fn check_pool_image(reader: &dyn ImageReader) -> Vec<(&'static str, InvariantVerdict)> {
    let system_configurations = chosen_system_configurations(reader);
    // … choose the root, scan the journal, walk the trees, judge each invariant
}

Every crash state goes to three judges:

Judge	What it checks
Recovery + oracle	Recover twice, with and without the journal. A file that is read must be byte-for-byte correct; once the root slot is durable there is no going back to the old state; the walk must not fail
Pool-level checker	Entry point walk::check_pool_image, 23 invariants
Record checker	Root on disk but journal record missing; recovery claims the new state but a unit is missing

The record checker is separate because D13, settled item 7, limits the pool-level checker to a single image. Any check that needs a second input (the pre-crash image, the record stream) is not its job.

A judge must be able to fail, or zero violations means nothing. There are 26 corrupted images, at least one per invariant, and each one makes its invariant fail. With the root slot durable, removing each of the 8 units in turn fails 8 times out of 8; removing the barrier between the journal record and the root slot makes the record checker fail.

Results

The first disk creation and write succeeded. mkfs on two disks, write 3000 bytes, commit, throw away everything in the process, cold-start, read back: byte-for-byte identical.

260,000 crash replays, zero errors. All 262,165 crash states enumerated, no sampling; zero violations from all three judges; 22.7 seconds in release mode on the local machine.

That does not mean the code has no problems. Crash replay covers only the crash states enumerated in the model; edges outside the model are not covered:

• There is only one workload, "new pool, new file". Overwrite, reuse after free, repeated mounts, and rollback have never been replayed.
• The model assumes every write before a barrier is durable. A disk that does not honor FLUSH is outside it.
• A torn write that happens to fool the 32-bit CRC32C is an accepted risk.
• Of the 66 invariants in use, the checker judges 23.
• Functional differential testing against an ideal model does not exist yet.

The story is long. Spring, summer, autumn, winter.