4.4. ADR-004: Binary WAL Format for Crash-Safe Storage Transactions

4.4.1. Status

Accepted

Date: 2026-05-19

4.4.2. Context

The cda-storage crate provides a crash-safe, transactional storage backend for diagnostic data (MDD files, configuration). Mutations are journaled to a Write-Ahead Log (WAL) before being applied to the filesystem. The WAL must:

  • Record operations durably before they are applied.

  • Support crash recovery: detect incomplete transactions and roll back partial commits.

  • Minimize I/O overhead on flash-based storage where write amplification matters.

The key decision is the WAL’s on-disk encoding: binary (e.g., rkyv, wincode) vs text-based (e.g., JSON, TOML).

4.4.3. Decision

Use a binary WAL format with rkyv (zero-copy deserialization) for operation payloads and CRC32 checksums per entry.

4.4.3.1. Commit Strategy

The WAL uses a one-phase commit with checksums (1PC+C) strategy:

  1. Operations are appended to the WAL during the transaction without fsync.

  2. Before applying, the header status is flipped from RECORDING to COMMITTING via an in-place write to the file header.

  3. A single fsync makes both the status change and all entries durable.

  4. Operations are applied to the filesystem.

  5. The WAL file is deleted (point of no return).

4.4.3.2. On-Disk Format

[u8 magic][u8 status][u16 reserved][u32 header_crc32] [u32 crc32][u32 len][payload] ...
|-------------- 8-byte file header -----------------| |------ per-entry data -----|

  • File header (8 bytes): magic 0xCA, status byte (0x00 = recording, 0x01 = committing), 2 bytes reserved padding, CRC32 over the header fields.

  • Entry envelope (8 + N bytes): CRC32 checksum of the payload, u32 payload length, followed by the rkyv-serialized Operation enum.

  • All fields are little-endian. The 8-byte header and 8-byte entry headers maintain 4-byte alignment as required by rkyv deserialization.

4.4.3.3. Recovery

On startup, LocalStorage::new() inspects the WAL:

  • No WAL: clean state, nothing to do.

  • RECORDING: transaction never reached commit. discard WAL and staging.

  • COMMITTING: commit was in progress. read entries, undo applied operations via .bak file restoration and new-artifact removal.

  • Truncated COMMITTING WAL with no evidence of application: discard WAL, no operations were applied.

  • Truncated COMMITTING WAL with evidence of partial application: return StorageError::Corruption so the caller can decide how to handle it.

4.4.4. Rationale

4.4.4.1. Why Binary over Text

  1. Zero-copy deserialization. rkyv deserializes directly from the memory-mapped / read buffer without parsing or allocating. Text formats (JSON, TOML) require a full parse pass and allocate intermediate structures.

  2. Simple deserialization. The serialized bytes are the payload directly. No text encoding layer (escaping, quoting, base64) sits between the raw operation data and its on-disk representation.

  3. Compact. Typical Operation payloads are < 1 KiB. A JSON equivalent with escaped strings, keys, and formatting would be 2-5x larger, increasing flash write amplification for no benefit.

  4. Checksumming is simpler. CRC32 over raw bytes. With text, checksums would need to account for encoding differences (line endings, whitespace normalization).

4.4.4.2. Why u32 Payload Length

The payload length field is u32:

  • The WAL is an on-disk format. Using usize would make files non-portable between 32-bit and 64-bit targets.

  • u32 fits the 4-byte alignment rkyv requires. u16 would need 2 bytes of padding for no benefit.

  • u64 (and usize on 64-bit) would waste 4 bytes per entry as with the current operation sizes, the length will never even reach u16::MAX.

  • Actual payloads are well under 1 KiB (the largest variant, Operation::Write, contains three short strings bounded by filesystem NAME_MAX). u32 provides ~6 orders of magnitude of headroom.

4.4.4.3. Why rkyv over Other Binary Formats

  • Zero-copy: unlike bincode or postcard, rkyv does not need a deserialization pass. The archived data is accessed in-place. Bincode was a contender, but is discontinued and should not be used for new projects.

  • Derive-based: #[derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)] on the Operation enum. No manual codec.

  • Deterministic layout: same input always produces the same bytes, making CRC32 checksums reliable.

  • Alignment-aware: produces 4-byte aligned output, matching the WAL entry header layout without additional padding logic.

4.4.5. Consequences

4.4.5.1. Positive

  • Single fsync per transaction commit minimizes flash wear.

  • CRC32 per entry detects partial writes and corruption during recovery.

  • Zero-copy deserialization keeps recovery fast even with many entries.

  • Fixed-size headers simplify sequential reading and offset arithmetic.

4.4.5.2. Negative

  • The WAL is not human-readable. Debugging requires tooling (e.g., a wal-dump utility or logging during recovery).

  • rkyv’s archive format is not stable across major versions. A rkyv version upgrade may require a WAL migration or version field in the header. The reserved header bytes can be used for this purpose.

4.4.6. References

  • rkyv documentation

  • cda-storage/src/wal.rs: WAL implementation

  • cda-storage/src/recovery.rs: startup recovery logic