nordisk/skade

Time-travel — design

Class: design · Function: time-travel · Uses: store. Only the shape that runs; the why (why STree64, why immutable-swap, why a live tail) is in time-travel-reasoning.md.

f0 — resolve a table as of a snapshot

Time-travel resolves (table, snapshot_id) → metadata_location through the Ragnar static index when the id is covered by the cutoff, else the redb commits live tail. Routing rule (catalog.rs:149 resolve_location_at): probe the ArcSwapOption<StaticIndex>; on a covered hit whose table_key matches, return it; otherwise open a redb read txn and point-lookup the commits table.

The public entry points:

f1 — the commit log (store.rs)

COMMITS (store.rs:77) is append-only: key {table_key}\x1f{snapshot_id:u64_be} → metadata_location. The big-endian id (commit_key, store.rs:99) makes redb's lexicographic order equal ascending snapshot order within a table, so per-table scans and cutoffs are contiguous. Snapshot ids are immutable and globally unique in Iceberg, so a row is never rewritten. record_commit (store.rs:111) appends only when a commit carries a snapshot id, and bumps META_COMMIT_SEQ + META_UPDATE_COUNTER.

f2 — the Ragnar STree64 index (static_index.rs)

StaticIndex (static_index.rs:42) is an immutable projection of the commit log: sorted ids: Arc<[i64]> parallel to entries: Arc<[Entry]>, with a STree64 — Ragnar Groot Koerkamp's cache-line-packed implicit B-tree — built over the ids.

• build(read) (static_index.rs:66) scans every commits row, decodes the key (decode_commit_key, static_index.rs:154), sorts + dedups on id, builds the tree. Empty log → None.
• lookup(sid) (static_index.rs:122) is tree.find_exact → index into the parallel arrays: a handful of cache-line probes, no hashing, no lock, no redb.
• lookup_many(&[sid]) (static_index.rs:132) rides STree64::batch_stream::<16> — a software-pipelined pass that overlaps the cache-line probes (Ragnar's batch win). This is what makes resolve_many pay one tree walk + one redb txn for N ids instead of N of each.

f3 — the compactor (store.rs)

The index is built at open (warm-start from the durable log, store.rs:201) and rebuilt in the background as history grows:

• maybe_trigger_compaction (store.rs:342) increments writes_since_compaction; once it crosses COMPACT_THRESHOLD (1024, store.rs:93) and no rebuild is in flight (single-flight via a compacting AtomicBool), it spawns a fire-and-forget thread.
• compact_with_db (store.rs:313) opens a redb read snapshot, builds a fresh STree64, ArcSwapOption::stores it in wholesale, advances the cutoff AtomicI64, resets the persisted + in-memory counters.

Reads never block on compaction; the only write-path cost is one atomic increment. Correctness rests on immutability: the compactor swaps a whole new immutable index in — it never mutates one in place, and it drops nothing a covered id still needs.