nordisk/znippy

znippy's custom tables as git indexes — design note (lane gitidx, 2026-10-31)

znippy-plugin-git serves a git repository out of an append-only archive of verbatim packs plus a set of custom tables: the object index, the exploded object table, the commit graph, the reachability bitmaps, the ordinal space, the ref log and the push log. This note is the answer to one question: are those tables good git indexes — what does each one answer, what does it cost to build and keep, what is persisted and what is rebuilt, and where does it beat a plain graph walk? Every number is measured; the method is at the end.

The occasion was GUN-PERF (gunnar, 2026-10-31): with real clients on oden, a git.git clone answered from the reachability index took 65 s of server CPU against 19 s for gunnar's plain walk, the index took 85 to 150 s to build after every start or push, and OrdinalSpace::ordinal_of_hex was 51 % of the profile. gunnar reverted the index path for blob-tagged repositories (18c10860) and handed the fix to znippy.

1. The operations and the tables they touch

Files in a store directory: objects.pack (truth), objects.pack.journal, objects.tail (redb), objects.index (persisted Arrow projection), objects.exploded (eager table: commits and tags) and objects.exploded.c<N> (lazy segments), objects.graph, objects.reach (new), refs.log, and repository[.gN].znippy (sealed generations).

2. What each table answers, and what it costs

2.1 The object index (objects.index + objects.tail)

Answers: oid → (archive offset, length, entry type, uncompressed size), has, sizes, batch lookups for emission. Build: the indexer drain writes rows into redb as a pack is resolved; the projection fold rewrites objects.index when the tail outgrows its ratio (read_stack.rs, ~136 folds / ~51 GB written for the kernel at ratio 1.0). Persisted: both layers. Measured: 80/221 ns per projection lookup against 463/937 ns for the tail; batch-of-100 161 ns per oid. This is the one table every operation uses and it is as fast as a .idx. Nothing to fix here.

2.2 The exploded object table (objects.exploded*)

Answers: oid → (kind, payload) with no delta chain. Build: commits and tags eagerly at push (the default policy), everything else lazily on first read, under a disk budget. Persisted: yes, evictable. It is what makes a tree read in the reachability builder cost a lookup instead of a chain inflate, and what makes "which of the pushed objects are commits" a lookup (exploded.content) instead of a resolve (§3.3).

2.3 The commit graph (__gunnar_graph__, objects.graph, OrdGraph)

Answers: commit → parents, root tree, committer time, generation; the commit set; tips. Build: parse every commit payload out of the exploded table and run one Kahn pass (assign_generations). Persisted: objects.graph, validated by a blake3 token over the sorted oid list of the whole store, so any push invalidates it. Until this lane the fold then re-read every commit after every push (git.git: 83 932 commit payloads parsed per one-commit push) and load_persisted_graph decoded the whole stale file before comparing the token. Now the token is compared first, and after a push the graph is extended: the previous rows stand, the exploded table says which of the appended oids are commits, and only those are parsed. The hex CommitNode rows are kept for the sealed section and graph_snapshot; the serving form is OrdGraph — rows, ordinals and parent rows, with the commit set as a bitmap and row_of(ordinal) by rank — built with one hex decode per node per fold.

2.4 The ordinal space (OrdinalTable)

Answers: oid ⇄ ordinal, the bitmap position space. Before: the sorted concatenation of every oid, binary-searched (19 probes over 411 105 oids of 20 bytes). A sorted space renumbers on every push — every oid above a new one shifts — so every stored bitmap had to be rewritten bit by bit after every push (carry_reach). Now: append-only. A sorted base is laid down once; later arrivals are appended in arrival order and found through a sorted index of their own; the base gets a 16-bit fanout (git's .idx idea, two bytes), so a lookup is one table read and about six probes. The space is re-sorted only when the appended part exceeds a quarter of the base (and 4096 objects), or at seal, through one remap table — one lookup per object, one array index per bit.

2.5 The reachability table (__gunnar_reach__, objects.reach, ReachTable)

Answers: for a selected commit, the closed set of objects reachable from it; want − have as OR(bitmaps of want) ANDNOT OR(bitmaps of have); a commit without a bitmap by the bounded walk (accumulate: commits down to the first bitmapped one, then its trees with the skip rule). Selection: tips first, then an even sample, 512 by default.

Build, before: per distinct tree a memoised closure bitmap keyed by a hex String, hex::encode per tree entry, ordinal_of_hex per edge, a HashMap<String, RoaringBitmap> over every object. git.git on dwarf: 151 s (oden: 85 to 150 s). Build, now: git's own shape — parents before children, each commit's bitmap starts from its parents' (moved when the parent's last child takes it, cloned otherwise) and is completed by fill_tree with the skip rule, so a tree already in the parents' closure is never opened. Work is O(objects + commits); memory is the frontier, not one bitmap per tree. No hex anywhere below the sealed builder.

After a push: before, the table was carried (every bit of every entry renumbered) while the push stayed under a tenth of the history, else dropped and rebuilt from scratch on the next read. Now nothing is renumbered; the fold gives each new tip (and every 64th commit of a long pushed branch) an entry by the bounded walk, inside the fold, so the first fetch after the push pays nothing. At start: before, nothing was persisted for a live store — the first read after every start walked every tree. Now objects.reach holds the space (base + appended, raw) and the entries (Arrow IPC through znippy-common's ipc_guard); a load follows the store's current oid list, so a persisted table also survives pushes it never saw (they append, and the fold extends). It is written after every full build and compaction, every 16th extension, and on drop.

Query, before: select built the answer, then computed the closure of have a second time for client_has, then probed a HashSet<Vec<u8>> once per selected object to name the commits (the 18 % SipHash in GUN-PERF's profile), and every tag or sampled commit among 1 006 wants walked its trees with hex::encode per entry. Now: one read guard, integers end to end, the have closure computed once and handed back, commits = delta AND commits.

3. Measured: real repositories, store level

examples/reach_real_repo.rs (§5): one process, no server, the repository's one pack fed to a fresh GitStore, then every step a clone, a fetch, a push and a restart pay. Wall and CPU of the process, VmHWM peak, 1-minute load at the step's start. dwarf, 12 threads, 61 GB, shared with other lanes (load 12 to 13 during the after runs, 2 to 6 during the before runs — the CPU column is the one to compare). 2026-10-31. before = znippy master 6ecb049 (znippy-plugin-git 0.2.2), after = this lane (0.2.3).

git.git (hist.git from GUN-PERF): 411 105 objects, 83 932 commits, 1 007 refs, 1 006 commit tips (the blob-tagged junio-gpg-pub is dropped, as gunnar drops it), 292 MB pack.

The 83 s warm clone was the cost gunnar saw as 65 s of server CPU: 1 006 wants, most of them tags on old commits with no bitmap of their own (512 entries), each walked down to a sampled entry with its root tree opened and a hex string made per entry — and then every selected object probed through a HashSet<Vec<u8>> to name the commits. After: the bitmapped tips are ORed first, a tag whose commit is already in the (closed) union walks nothing, and the commits are one bitmap AND.

The build's remaining 20 s is 330 535 tree reads out of delta chains (11.6 s, 2.4 GB of tree payloads, after the chain memo; 27 s before it) and 57 M tree entries resolved to ordinals. It is paid once per repository now.

A second baseline run of git.git on the same box (load 5 to 12, 2026-10-31, 0.2.2) gave: build 175.3 s / 168.0 s CPU / 1 757 MB; warm select of all tips 55.8 s; fetch-shaped select 0.91 s; push 1.54 s; first select after the push 54.1 s; reopen 84.5 s. The before column above is the first run; the two together are the spread of the old code on a shared box. The after column was reproduced within 10 % across four runs (bench/after2..after6 in the lane's folder).

gunnar (git clone --bare of the gunnar repository, one pack): 28 251 objects, 2 916 commits, 9 refs, 34 MB pack. dwarf, 2026-10-31, load 5 (before) and 12 (after).

On a small repository the index was never the problem; what the lane buys it is the restart (nothing rebuilt) and a cheaper fold.

4. Where the tables beat a plain walk, and where they do not

• A clone or a fetch of a commit tip — bitmaps win outright: want − have is a set operation over the whole closure with no object opened; a bitmapless tip costs the trees of the commits since the nearest entry. The walk costs one read per object in the closure (gunnar: 19 s of CPU for git.git's 402 k objects).
• A fetch of a few new commits — both are cheap once the table is current; the index path wins only because the have closure (the repository) is one bitmap OR instead of a walk of the repository.
• A tip that is a blob or a tree (a partial clone's lazy fetch, a blob tag wanted outright) — the table cannot add to an answer; fill_tree covers a tree tip, a blob tip is itself. gunnar's select declines these before asking; it can stop declining now (GP-7).
• Filters, shallow boundaries, deepening — membership is decided per object by facts no bitmap carries; the walk serves them.
• gc's live set — the union of every tip's closure is one bitmap OR per tip here; the walk is the whole repository. (live_set still hands the answer out as hex strings; that is the maintenance path and is left for a later lane.)
• A repository whose pushes remove objects (retain) — the space is rebuilt and the table dropped; the first read after a gc walks every tree once (the fast builder now).

4b. The sweep of the other operations (hex in hot loops, rebuilds at start)

5. Method, and the command to run on a schedule

Store level (any box; the numbers above are from dwarf):

# a bare repository packed into ONE pack (a fresh `git clone --bare`, or `git gc`)
cargo build --release --locked -p znippy-plugin-git --example reach_real_repo
ZNIPPY_REACH_TIMING=1 target/release/examples/reach_real_repo /seed/git.git /tmp/work 3

It prints one markdown row per step — ingest, put-refs, refs, first-select (the build), warm select (p50 of N), fetch-select, push, post-push-select, reopen — with wall, CPU, VmHWM and the 1-minute load at the step's start, plus a header naming the repository, its size, the host, its threads and the date. The README rows come straight out of it; a run is about 2 minutes for git.git after the ingest.

Server level (oden): gunnar's crates/gunnar-perfbench, GUN-PERF's method (~/plan/handback/gun-perf.md): GUNPERF_ONLY=clone,fetch GUNPERF_ENGINES=znippy against a release gunnar built with --features engine-gix, seeded with the same git.git.

• Store-level: plugins/native/znippy-plugin-git/examples/reach_real_repo.rs on dwarf (12 threads, 61 GB), the same seed (git.git as GUN-PERF's hist.git, one pack of 292 MB), before = master 6ecb049, after = this lane.
• Server-level: gunnar's crates/gunnar-perfbench on oden, method and baseline in ~/plan/handback/gun-perf.md (lane GUN-PERF); see the lane's handback for the server numbers.
• Correctness: every existing test of the crate, plus property tests in reach.rs (the_full_table_equals_a_graph_walk_on_random_dags, an_extended_table_equals_a_graph_walk_on_random_dags: 24 random DAGs each with merges, shared blobs, nested trees and gitlinks, every entry and every bounded walk against a plain object walk, at caps 1, 3, 7 and unbounded, and across an append-extended space, and through the seal remap), the ordinal table's follow/replay/refusal test, the hostile-bytes tests for the persisted table, and the store-level tests a_push_carries_the_reach_table_across_the_fold, a_push_of_any_size_extends_the_reach_table_and_rebuilds_nothing, a_hostile_persisted_reach_table_is_rebuilt_not_trusted.