nordisk/skade

Time-travel — reasoning

Class: reasoning · Function: time-travel. The descriptive what is in time-travel-design.md.

Why a static search tree (STree64), not a B-tree lookup on redb

Snapshot ids are i64, immutable, and globally unique. Time-travel is, at its core, "map this id to a location." redb can do that — it's the fallback — but a redb point lookup pays begin_read() + open_table() + a B-tree descent through a general-purpose on-disk structure. For a hot historical read path that a query planner hits repeatedly, that's wasteful.

The Ragnar STree64 (znippy-zoomies) is a cache-line-packed implicit B-tree built over the sorted ids. A lookup is a handful of cache-line probes with no hashing (the ids are already integers), no lock, and no redb access. We reuse it verbatim, so the catalog inherits that crate's AVX2 and hugepage tuning for free on each dependency bump. Building our own index structure would have been slower and more code.

Why not just hash the ids? A hash map answers point lookups but loses the batch win below, and would still need locking or an immutable-swap wrapper. The sorted tree gives both point and pipelined-batch lookup from one structure.

Why the batch path (lookup_many / resolve_many) is the real prize

Query planners don't ask for one historical snapshot — they fan out over many (scan a range of history, diff snapshots, plan a time-window). Doing that as N independent lookups pays N tree walks and, worse, N redb transactions for the uncovered tail. resolve_many instead does one pipelined STree64 pass (batch_stream::<16>, which overlaps the cache-line misses across queries — the specific win Ragnar's structure was built for) and one redb read transaction for everything the index doesn't cover. One tree walk, one txn, N answers. This is the difference between time-travel being a novelty and being usable in a planner.

Why an immutable swap + a live tail, instead of an incrementally-updated index

The index could be mutated in place on every commit. We deliberately don't:

• A mutable concurrent index needs locking or a lock-free structure with far more subtlety than "build a fresh immutable one and ArcSwapOption::store it." Reads must never block, and the immutable-swap model guarantees that trivially — a reader either sees the old whole index or the new whole index, never a torn one.
• Rebuilds are correct by immutability: snapshot ids never change, so a rebuild drops nothing a covered id still needs; a stale-but-covered lookup can't be wrong, only absent (and absence routes to the live tail).

The cost of not updating in place is that recent commits (above the cutoff) aren't in the tree yet — so we keep the redb commits live tail as the fallback for ids above the cutoff. Routing id <= cutoff → tree, else → redb gives lock-free speed for the bulk of history and correctness for the fresh tail, and the background compactor moves the cutoff forward. Reads pay one atomic load to check the cutoff; writes pay one atomic increment to drive the trigger.

Why compaction is background, single-flight, threshold-triggered

• Background + fire-and-forget so no write ever waits on an index rebuild.
• Single-flight (a compacting AtomicBool CAS) so a burst of writes past the threshold spawns at most one rebuild, not one per commit.
• Threshold = 1024 commits — small enough that real workloads compact promptly and the live tail stays short, large enough that bursty writers don't thrash the rebuild. It's a deliberate middle; the commit_seq / update_counter are persisted so the trigger survives restarts and a reopen warm-starts the index from the durable log rather than starting cold.