Streaming Checkpoint Copy

bcmr implements a Streaming Checkpoint Copy (SCC) algorithm that unifies three capabilities no existing cp-class tool provides together: inline integrity hashing at zero extra I/O, crash-safe resumable state, and constant-time resume verification.

This document describes the algorithm design with formal analysis, presents ablation experiments across macOS and Linux validating each design decision, and compares with prior art.

Problem Statement

File copying with integrity verification faces a fundamental I/O trade-off. Let $S$ denote the source file of size $n$ bytes and $D$ the destination.

The verification tax is steep: confirming a copy doubled is a whole-file re-read. For a 100 GB file on a 500 MB/s drive, that is 200 extra seconds purely for re-reading.

Resume after interruption is worse. Existing tools verify the written prefix by re-hashing it entirely:

$T_{\text{resume-verify}} = \mathcal{O}(k) \quad \text{where } k = \text{bytes already written}$

For a 90% complete 100 GB transfer, this means re-reading 90 GB just to confirm the prefix is intact.

Algorithm Design

Core Insight

BLAKE3 achieves 1--5 GB/s on modern hardware (NEON / AVX-512), which exceeds the throughput of most storage devices. Hashing is no longer the bottleneck --- disk I/O is. This means we can compute the source hash during the copy at effectively zero marginal cost.

Data Flow

The two hashers run in lockstep: src_hasher accumulates a single BLAKE3 over the whole file (used for -V and for cross-run resume detection); block_hasher is reset every 4 MiB so the session file can record per-block hashes. See Experiment 10 for when the source hasher is skipped.

Session File

The session file persists the copy state across crashes. It uses a compact binary format:

For a file of $n$ bytes with block size $b = 4\,\text{MB}$:

$|\text{session}| = 256 + 32 \cdot \lceil n / b \rceil \quad \text{bytes}$

The overhead converges to $32/b \approx 7.6 \times 10^{-6}$ as metadata becomes negligible.

Crash Safety Invariant

The write ordering ensures a strict invariant:

Let $S$ be the session and $B_k$ the $k$-th block on disk. After each checkpoint:

$\forall\, k < S.n: \quad B_k \text{ is durable on disk} \;\wedge\; H(B_k) = S.\text{hashes}[k]$

The ordering is:

1. write(dst, block_data) --- block in page cache
2. fdatasync(dst) --- block durable on media
3. session.save() via atomic write-fsync-rename --- session updated

If a crash occurs at any point:

• Before step 2: Block not on disk. Session unchanged. Block is recopied.
• Between steps 2 and 3: Block on disk, session old. Block is recopied (redundant but correct).
• After step 3: Both durable. Resume from $B_{k+1}$.

No state can be reached where the session claims a block is complete but the block is not on disk.

The two recovery branches that recopy a block are wasteful but correct; the only forbidden state ("session says k is durable, but k isn't on disk") is unreachable.

Resume: Tail-Block Verification

On resume, we exploit the invariant. All blocks except possibly the last are guaranteed by the checkpoint ordering. We only verify the tail block --- the one that was being written when the crash occurred:

$T_{\text{resume}} = T_{\text{hash}}(b) = \mathcal{O}(1) \quad \text{independent of } k$

versus full prefix rehash:

$T_{\text{old-resume}} = T_{\text{hash}}(k) = \mathcal{O}(k)$

2-Pass Verified Copy

Since the source hash is computed inline during the copy, the -V verification mode needs only one additional pass (re-read destination to hash it), not two:

Durable Sync

On macOS, fsync() only flushes data from the OS buffer cache to the drive's write cache --- it does not issue a cache flush command to the drive controller. Data can be lost on power failure. F_FULLFSYNC via fcntl() issues a full barrier.

bcmr uses F_FULLFSYNC on macOS and fdatasync() on Linux (where data=ordered mode on ext4/XFS provides sufficient ordering guarantees). After every atomic rename, the parent directory is also fsynced to ensure the directory entry is durable.

Page Cache Management

Large copies pollute the page cache, evicting unrelated cached data. On Linux, bcmr calls posix_fadvise(FADV_DONTNEED) at each checkpoint interval to evict already-copied pages from both source and destination file descriptors.

Ablation Experiments

All experiments use median of 3--5 runs. File data is pseudo-random ((i*7+13) mod 256) to prevent compression and deduplication artifacts.

Test environments:

• macOS: Apple Silicon, APFS SSD
• Linux: Intel Xeon Gold 6238R (AVX-512), NVMe SSD (Samsung), ext4

Experiment 1: Inline BLAKE3 Hash Overhead

Hypothesis: BLAKE3 throughput exceeds storage I/O, so inline hashing adds negligible wall-clock time.

Method: Copy files of size $n \in \{16, 64, 256, 512, 1024\}$ MB in three modes: (A) copy only, (B) copy + hasher.update(), (C) copy + hash + hasher.clone() per block.

On Linux, BLAKE3 at 5.4 GB/s exceeds NVMe peak (~3.5 GB/s). Inline hashing is truly free --- the CPU finishes hashing before the next disk read completes.

On macOS, BLAKE3 at ~1 GB/s is comparable to SSD speed, so warm-cache tests show 8--56% overhead. In cold-cache (real-world) scenarios, disk latency dominates and the overhead shrinks toward the Linux numbers.

Experiment 2: 2-Pass vs 3-Pass Verification

Hypothesis: Eliminating one full-file read from verification saves $n / (3n) \approx 33\%$ of total I/O.

Warm-cache results show 5--14% savings (page cache masks the eliminated read). With cold cache, the savings converge toward the theoretical 33%.

Experiment 3: Tail-Block vs Full Prefix Rehash

Hypothesis: $T_{\text{tail}} = \mathcal{O}(1)$ while $T_{\text{full}} = \mathcal{O}(k)$.

Tail-block verification is constant at ~5 ms (macOS) / ~1.8 ms (Linux) regardless of file size. The speedup grows linearly with $k$ as predicted.

Experiment 4: Sync Interval Overhead

Hypothesis: There exists an interval $I$ where the fsync overhead is acceptable ($<20\%$) and worst-case rework on crash is bounded.

64 MB (16 blocks) is the chosen default: $\leq 16\%$ overhead on both platforms, at most 64 MB of rework (~0.1s on NVMe).

Experiment 5: F_FULLFSYNC vs fsync on macOS

Hypothesis: F_FULLFSYNC costs negligibly more than fsync on Apple Silicon.

Differences are within noise. F_FULLFSYNC provides correct durability guarantees at no measurable performance cost. SQLite, RocksDB, and PostgreSQL all use F_FULLFSYNC on macOS.

Experiment 6: copy_file_range with Offset (Linux)

Hypothesis: The kernel fast path supports non-zero offsets for resume, avoiding userspace buffer copies.

8--24% faster on NVMe. The benefit would be larger on slower media or network filesystems where zero-copy matters more.

Comparison with Prior Art

Key differentiators:

• Constant-time resume verification --- no other cp-class tool achieves $\mathcal{O}(1)$.
• Always-on source hash --- verification is a byproduct of copying, not a separate pass.
• Formal crash safety --- write ordering invariant with F_FULLFSYNC / fdatasync + directory fsync.

Summary