The snapshot I couldn't reorder

I imported four years of notes out of another app in one shot. Sixty-odd thousand blocks, a couple hundred thousand operations, all landing at once.

That import turned out to be the best fuzzer I’ve ever run, and I didn’t run it on purpose. I just wanted my own notes in outl. But dumping four years of history into a system in one go does something no amount of hand-testing does: it drags every latent bug into daylight at the same time. I’d built the move op and the p2p sync against workspaces I typed by hand, dozens of operations, a few hundred at most. They worked. Then I handed them four years of real data across two devices, and a pile of problems that had been sitting there the whole time, invisible for lack of volume, all surfaced in the same week. This post is one of them, and it’s the scariest.

Three things broke at once, and underneath they were the same thing: the app did work proportional to my whole history when it should have done work proportional to my current state. O(history) where it wants to be O(state). The outline you see is just a projection of the log, and I was rebuilding the entire projection on every open.

The clients got slow to open. Opening the app meant replaying the whole op log from the first byte, every single time, and on the desktop it stuttered doing it. This is the one that bothers me most, and not as an engineer. I open a note app to get something out of my head before I lose it. That’s the whole job. If it makes me wait to do that, it’s already broken, no matter how correct the sync underneath is.

The mobile app didn’t get slow, it crashed. It didn’t even open. Replaying that many ops built up around a gigabyte of resident state, and iOS doesn’t negotiate: it saw the number and killed the process before the first frame ever painted. Not slow. Gone.

Sync was big and slow. A fresh device paired by pulling the entire log and replaying it, and moving that much data device to device the way I’d built it dragged badly, then timed out over and over under the volume. The thing that’s supposed to feel like magic felt like watching a progress bar lie.

The fix is the first thing anyone would reach for: cache the materialized tree to disk, and on boot load the cache instead of replaying. And once you have that, pairing gets an obvious upgrade too. When a fresh device joins, why ship it a 200k-op log and make it replay the whole thing? Ship it the tree the other device already built. Adopt your peer’s snapshot, apply whatever it hasn’t seen on top, done.

It forked the tree.

Two devices, the same set of operations, two different outlines. This wasn’t a race or a lost write. Both devices were internally consistent, both had every operation, both had converged. They’d converged to different trees. One said a page lived under a, the other said it lived under b, and neither was wrong by its own accounting.

I’d seen the shape of this before. Last week I wrote about a title that converged to exactly the wrong string, where “it converges” was true and told you nothing about to what. This is the same lesson wearing a scarier coat, because this time the wrong answer wasn’t a doubled string in one field. It was two devices that would never agree again.

the setup, in one paragraph

outl is a local-first outliner. Every change is an operation appended to a per-device log, and the outline is that log replayed through a tree CRDT, Kleppmann, Mulligan, Gomes & Beresford’s move operation. The move op is what makes the tree highly available: any device can move any node at any time, offline, and the replicas still converge. It buys that with a specific trick. Operations carry a hybrid logical clock timestamp, and when an operation arrives out of order, with an older timestamp than something already applied, the algorithm doesn’t just append it. It undoes every operation newer than the newcomer, applies the newcomer in its correct causal position, then redoes the ones it undid:

apply(new_op):
    if new_op.ts > log.last().ts:
        do_op(new_op); append
    else:
        undo every applied op with ts > new_op.ts
        do_op(new_op); append
        redo the undone ops, in order

Convergence rests entirely on that undo/redo. It’s how a late operation slots into the right place in history instead of getting stapled to the end. Hold onto that, because it’s the whole post: the tree converges by reordering the log.

what’s the paper’s, what’s ours

The algorithm above is the paper’s, unchanged. The undo/redo, the transitive cycle check that walks all the way to the root, the old parent stashed on each op so it can be undone, the five invariants the code exists to hold (convergence, commutativity under reordering, idempotency, the tree stays a tree, no op ever silently lost). All of that is Kleppmann et al., down to matching the authors’ reference implementation. I didn’t touch the move op. I couldn’t have made it better and I had no reason to try.

What I did touch is everything the paper doesn’t model, and that turned out to be a lot. The paper carries one quiet assumption: your state is the log, replayed. Clean on paper, O(history) in production, and four years of notes imported at once is where O(history) goes to die. The snapshot is the fix, and the snapshot is also the thing that fights the move op, which is the rest of this post.

The snapshot dragged three smaller departures in with it. The paper orders ops with one total-order timestamp. To replay the right ops on top of a snapshot, and to catch a peer missing ops below its own watermark, I needed a per-actor vector clock instead. The paper’s timestamp is an abstract Lamport clock. outl uses an HLC, so the order tracks wall-clock time too. And the paper hands every node a fresh unique id, where outl derives a page’s id from its slug so two offline devices create the same node and converge instead of splitting. The same do/undo machinery got stretched over ops the paper never mentions: setting a property, collapsing a node, editing text.

That last one is the biggest thing living outside the paper. The paper is entirely about the tree’s shape, never a node’s contents. A block’s text is a whole separate CRDT, a Yrs sequence, sitting inside each node the tree moves around. Two CRDTs composed, and the seam between them is where a different family of bugs lives, including a title that doubled itself. None of this is a correction to the paper. It’s the layer you build on top of a correct algorithm to ship it as a product, and the lesson of the fork is that the layer can break the algorithm’s guarantees even while the algorithm stays perfect.

the operation that depends on history

Most operations don’t care what came before them. Create a node, set a property, apply it, done, the result is the same no matter the surrounding history. Move is the exception, and it’s the exception that matters.

Moving a node has to refuse to create a cycle. You can’t move a under b and b under a. One of those has to lose, or the tree stops being a tree. So do_op(Move) checks the current tree for a cycle and no-ops if the move would form one:

do_op(Move { node, new_parent }):
    if new_parent is a descendant of node in the CURRENT tree:
        no-op          // this move would form a cycle
    else:
        detach node, reattach under new_parent

Read that “current tree” carefully. Whether a given Move cycles or not depends on the shape of the tree at the moment it’s applied, which depends on every operation that came before it. Move is history-sensitive. That’s fine, better than fine, as long as you can always reorder the history around it. Undo the later ops, and the “current tree” the Move sees is the correct one for its timestamp. Redo them after, and everything lands where causality says it should.

The move op is safe because it can always be reordered. Now take reordering away.

a snapshot is history thrown away

A snapshot is the materialized tree: node x is under node y, this block’s text is that string. It is not the log. That’s the entire point. It exists so you can skip the log. The ops that produced it are gone, folded into a settled shape.

Which means a snapshot is the one thing the CRDT can’t reorder against. If an operation you still have to apply sorts before something already baked into the snapshot, the algorithm wants to undo that something and redo it around the newcomer, but it’s not an operation anymore. It’s a fact in an opaque tree. There’s nothing to undo.

Here’s where it bit. Set up two nodes, a and b, both under root. Then:

• Y = Move(a under b), timestamp 200, on the desktop
• D = Move(b under a), timestamp 100, on the phone

Replay the full log and it’s unambiguous. D (ts 100) applies first: b goes under a, tree is root → a → b. Then Y (ts 200): moving a under b would form a cycle, because b is already a descendant of a, so Y no-ops. Final tree: root → a → b. Every device that replays these two operations gets that, every time. That’s the CRDT holding up its end.

Now do it with a snapshot. The desktop writes its snapshot before the phone’s op exists. Its snapshot folds in Y with no D to stop it, so the desktop’s cached tree is root → b → a. The phone pairs, adopts that snapshot, and then its own D (ts 100) arrives on top. But D is being applied against the snapshot’s tree, root → b → a, not against a replay. In that tree, moving b under a forms a cycle, because a is already under b, so D no-ops. The phone keeps root → b → a.

Desktop says root → a → b. Phone says root → b → a. Same two operations, opposite trees. The move op resolved the cycle one way on a replay and the other way on top of a snapshot, because the snapshot is the one context where it couldn’t reorder D back to its rightful position. I wrote the smallest test that would pin it, and its assertions are the bug stated as an expectation:

// Mobile boots: adopts snap-desk, the guard sees D below the body's max
// HLC → full replay. Tree must match the full-replay result.
assert_eq!(
    ws.tree().parent(a),
    Some(NodeId::root()),
    "a stays under root (full-replay result), not under b (divergent snapshot result)"
);
assert_eq!(ws.tree().parent(b), Some(a), "b under a (full-replay result)");

the guard is one line

Once you can say the failure precisely, the fix writes itself. Adopting a snapshot equals a full replay only when the operations it hasn’t seen form a pure temporal suffix, every one of them newer than everything folded into the snapshot. The instant one delta op sorts at or below the snapshot’s high-water mark, you’re in reorder territory, and reorder is the thing a snapshot can’t do.

So boot checks exactly that, and bails if it can’t guarantee the shortcut is honest:

// CONVERGENCE GUARD (invariant #1). The snapshot body is an opaque
// MATERIALIZED tree, not a reorderable log, so applying the delta on
// top equals a full replay ONLY when the delta is a pure temporal
// SUFFIX — every delta op newer than every op folded into the body.
// If a delta op sorts at/below a body op, the CRDT would need to
// reorder it against ops that live only in the (opaque) tree, so a
// cycle-forming `Move` can resolve the opposite way and the tree
// diverges from a full replay. [...] Bail to a full replay:
// correct over fast. (No-silent-loss #5 holds regardless — the op is
// always in the log; this only decides the materialization order.)
if let Some(max_body_hlc) = body.cutoff.values().max().copied() {
    if delta.iter().any(|op| op.ts <= max_body_hlc) {
        return Ok(false); // -> boot_from_full_replay
    }
}

delta.iter().any(|op| op.ts <= max_body_hlc). That’s the whole defense. If any operation the snapshot missed is older than the snapshot’s newest fact, throw the shortcut away and replay the log. In the fork above, the phone’s D (ts 100) is below the snapshot’s max (ts 200), the guard trips, the phone full-replays, and both devices land on root → a → b. The parenthetical at the end is the part I keep coming back to: the operation is always in the log. The snapshot never decides what the tree is, only whether this particular boot gets to take the fast path. A snapshot is a performance cache that is structurally forbidden from changing correctness. When it can’t prove it’s identical to a replay, the replay wins.

why per-actor, not one clock

The guard leans on body.cutoff, and the shape of that cutoff is its own small lesson. My first instinct was a single high-water-mark HLC, the newest timestamp the snapshot had seen, one number. That’s wrong in a way that’s invisible until a second device with a slow clock shows up.

HLCs are only monotonic within one device. Across devices they’re merely comparable, not ordered by anything real. A phone that’s been offline can author an operation with a lower HLC than a desktop wrote hours earlier. A single global cutoff tracks only the snapshotting device’s clock, so an operation from another device, with a legitimately lower timestamp, delivered after the snapshot, sorts below the global mark and gets silently skipped on replay. It’s on disk. It’s just not in the tree. That’s the worst kind of bug: durable, invisible, and perfectly consistent.

So the cutoff is a per-actor vector clock, the high-water mark of each device, separately:

/// This must be a per-actor vector clock, not a single global HLC: a
/// single cutoff tracks only the high-water mark of the snapshotting
/// actor, so a legitimately-low-HLC op from a *different* actor
/// delivered after the snapshot (offline device, lagging clock) would
/// fall below it and be silently dropped from the tree even though
/// it's durably in storage (#156).
pub cutoff: BTreeMap<ActorId, Hlc>,

Boot replays, for each device A, every operation with hlc > cutoff[A], plus every operation from any device absent from the map entirely, a device the snapshot had never heard of when it was written. This is also what makes adopting a peer’s snapshot safe in the good case: your own local edits, the note you typed on the phone that the desktop’s snapshot never saw, sit above your own cutoff and get replayed on top of the adopted tree. Nothing local is lost. The snapshot is a floor. The log is the truth built on top of it.

the same bug, on the wire

Here’s the part that made me trust the diagnosis: the identical mistake was hiding somewhere else, and I only recognized it because the snapshot bug had taught me its shape.

Delta sync, the thing that decides which operations to send a peer, worked off a per-device high-water mark. You tell me your newest HLC per device, I send you everything above it. Clean, until you remember that operations arrive out of order by design, which is the whole reason the move op exists. If a high-HLC op lands on a peer ahead of a still-pending backlog, that peer’s high-water mark jumps past the gap, and my “send everything above your mark” fast path never resends what’s underneath. The ops below the gap become permanently invisible. Mac and iPhone that would not converge, for exactly the snapshot reason in a different costume: a bare max HLC lies about what’s underneath it the moment delivery isn’t gapless.

The fix is the same move as the per-actor cutoff: stop trusting the max, count what’s below it. Each side now sends max plus a distinct-op count per device, and if I hold more distinct ops at or below your mark than your count says you have, I resend that device’s whole log and let your ingest dedup absorb the overlap:

let full_resend: HashSet<ActorId> = census.iter()
    .filter_map(|(actor_id, hlcs)| match peer_clock.get(actor_id) {
        None => Some(*actor_id),                    // peer never saw this actor
        Some(peer) => {
            let below = hlcs.range(..=peer.max).count() as u64;
            (below > peer.count).then(|| {          // gap under the watermark
                info!(actor = %actor_id, below, peer_count = peer.count,
                      "gap below peer watermark detected; resending full actor log");
                *actor_id
            })
        }
    })
    .collect();

The count is distinct HLCs, not a raw line count, because historic duplicated lines on disk would otherwise inflate it and hide a real gap. One conceptual bug, the max-HLC watermark lying under out-of-order delivery, showed up in two places, the snapshot cutoff and the sync wire, and both fixes are the same sentence: don’t trust the max, count what’s beneath it.

the door I’d left open

One more, because it’s the kind of bug that only exists in the seams between two correct pieces.

Peer sync writes incoming operations straight to disk (it appends them to the per-device .jsonl files) and never routes them through the normal Workspace::apply path. Good reasons for that: it’s a bulk ingest, not an interactive edit. But the background snapshot writer, the thing that keeps the boot cache fresh, only fires from inside apply when the op count crosses a threshold. So on a device that mostly receives, a second machine syncing down a big vault, the snapshot writer never ran. No fresh snapshot ever got written. And every reload full-replayed the entire log, forever, a few seconds apart, pinning the CPU while the journal painted and then kept stuttering.

It got worse in combination with the guard I’d just added. Two devices actively syncing constantly hand each other low-HLC operations, so the convergence guard correctly rejects the snapshot on nearly every reload, which is it doing its job. But a stale gate in the reload path only re-persisted a snapshot once the log passed 10,000 ops, so any smaller workspace whose snapshot got rejected once would never write a fresh one and would full-replay on every single incremental reload, indefinitely. The two safe behaviors composed into a permanent slow path.

The fix is to re-persist whenever a reload had to full-replay, no size floor:

// Re-persist a fresh snapshot whenever this reload FULL-REPLAYED
// (snapshot absent, stale, or rejected by the convergence guard) so
// the next boot adopts one instead of replaying. [...] A gate here
// used to require `log().len() >= 10_000` before re-persisting, which
// meant any workspace under that size whose snapshot got rejected once
// by the convergence guard (the routine case for two actively-syncing
// actors) [...] full-replayed on *every* subsequent incremental
// reload, forever.
if !workspace.booted_from_snapshot() {
    if let Err(e) = workspace.save_snapshot() {
        tracing::warn!("reload: could not persist boot snapshot: {e}");
    }
}

The fast path and the sync path took different doors into storage, and only one of them knew to refresh the cache. Writing around apply skipped the bookkeeping apply was quietly responsible for. That’s a class of bug worth naming: whenever you add a second way into a data store, audit everything the first way did on the side.

what I’d take from this

The move op is beautiful because it can reorder. Any device, any move, any time, offline, and it all converges, because a late operation can always be undone-into-place and the rest redone around it. That flexibility is the feature.

A snapshot is the one place that flexibility doesn’t reach. It’s history with the reordering thrown away, kept precisely because throwing the log away is what makes it fast. So the optimization and the invariant are in direct tension: the thing that makes the tree correct is the thing the snapshot can’t offer, and if you adopt a snapshot naively you hand a history-sensitive Move a context it was never meant to resolve in. It resolves anyway, cleanly and deterministically, into the wrong tree.

The resolution isn’t cleverness, it’s humility encoded as one comparison. The log is the truth. The snapshot is a hint. Adopt the hint only when you can prove it equals the truth, and when you can’t, replay. That one line, delta.iter().any(|op| op.ts <= max_body_hlc), is the whole argument, and everything else in this post is a footnote to it: the per-actor cutoff so the proof isn’t fooled by a slow clock, the distinct-op count so the wire isn’t fooled by a gap, the write-through re-persist so proving it wasn’t safe doesn’t cost you forever.

“It’s a CRDT, so it converges” got me the forked tree last week’s lesson had warned me about. The follow-on lesson is narrower and I think more useful: a CRDT converges by doing something, reordering in this case, and any optimization that takes that ability away has to prove it wasn’t needed before it’s allowed to skip it.

The guard, the cutoff, and the gap detector are in the outl repository, across crates/outl-core/src/workspace.rs, snapshot.rs, and crates/outl-sync-iroh/src/engine_sync.rs.