nordisk/edda

Server storage — why three traits, and why there is no database

Class: reasoning. Why the server's storage layer is shaped the way it is, and what the alternatives cost. What Gunnar is: design.md. The protocol: wire-design.md. The no-OS case: appliance-design.md.

Scope: the server only. gunnar-client opens gix::Repository on a real path and none of this applies to it.

Status, 2026-08-03. The traits, the mem backend, the Arrow IPC log and the fs backend are built and run one conformance suite. The znippy cold tier and repack() are not built. Every figure below is labelled with where it came from; the stree number is znippy's own bench, not a Gunnar measurement.

The problem a naive approach cannot solve

The server must run where there is no filesystem: a single Rust binary as PID 1 in a distroless appliance image. The obvious approach is to take gix, the Rust git implementation, and put a storage abstraction under it.

That does not work, and the reason is not the one most people expect. The assumption is that a git library is filesystem-bound all the way through, so abstracting it is a large and diffuse job. It is not diffuse. It is concentrated in one place, and that place has no seam.

The finding

gix is filesystem-dependent in exactly one layer:

Keys were never the problem. Refs are. Key material is bytes and goes into a store like anything else. But every ref update in git is atomically replace this small file, and gix implements that once, against POSIX, with no trait in front of it.

The second half of the finding is what makes the job small. Because a git server never checks anything out (see design.md), everything else that binds gix to a filesystem is out of scope: the index, the worktree, status, smudge and clean filters, CRLF handling, attributes, ignore rules, pathspec globbing, .git/config, repository discovery, credential helpers, prompts.

So refs and objects are not two of many things to abstract. They are the whole list — plus secrets, which have no git equivalent at all but have exactly the same "where does this live when there is no home directory" problem.

What we compute

The Gunnar server does not go through gix::Repository. It goes through the gix plumbing crates and its own three traits. The client does the opposite, and should.

/// Immutable, content-addressed, write-once, read-random.
pub trait ObjectStore: Send + Sync {
    fn hash_kind(&self) -> gix_hash::Kind;   // sha1 AND sha256, per repository
    fn contains(&self, id: &gix_hash::oid) -> bool;
    fn read<'a>(&self, id: &gix_hash::oid, buf: &'a mut Vec<u8>) -> Result<Option<Data<'a>>>;
    fn header(&self, id: &gix_hash::oid) -> Result<Option<Header>>;
    fn write(&self, kind: Kind, bytes: &[u8]) -> Result<ObjectId>;
}

/// Small, mutable, needs compare-and-swap. NOT an archive's shape.
pub trait RefStore: Send + Sync {
    fn read(&self, name: &FullName) -> Result<Option<Target>>;
    fn iter(&self, prefix: Option<&str>) -> Result<Vec<(FullName, Target)>>;
    /// ALL-OR-NOTHING across the batch, with per-ref old-value CAS.
    /// This is what makes a push atomic. It is the hard one.
    fn transaction(&self, edits: Vec<RefEdit>) -> Result<Vec<RefEdit>>;
}

/// The SSH host key and the admin bootstrap material.
pub trait SecretStore: Send + Sync {
    fn get(&self, key: &str) -> Result<Option<Vec<u8>>>;
    fn put(&self, key: &str, value: &[u8]) -> Result<()>;
    fn delete(&self, key: &str) -> Result<()>;
    /// Atomic get-or-create — the host key must never be regenerated by a race.
    fn get_or_create(&self, key: &str, mk: &mut dyn FnMut() -> Result<Vec<u8>>) -> Result<Vec<u8>>;
}

ObjectStore gets a blanket implementation of gix_object::{Find, Exists, FindHeader} through the GixObjects adapter. That single wrapper is what makes every gix plumbing algorithm run over any backend unmodified, including one that is an archive file rather than a directory.

RefStore::transaction is the hard method and the one the conformance suite is built around. All-or-nothing across the batch, with a per-ref old-value compare-and-swap, is what makes a push atomic.

get_or_create takes &mut dyn FnMut, not impl FnOnce as the specification writes it. impl Trait in a trait method is not object-safe, and every consumer of SecretStore holds it as a trait object.

Why the traits have opposite shapes

Objects and refs are opposite kinds of data, and treating them alike is the mistake that would sink the design:

An archive format satisfies the left column exactly and cannot satisfy the right column at all. So there are separate traits, with different backends, and no attempt to unify them.

Backends

The off-filesystem configuration is the znippy object tier plus arrow_log for refs and secrets. The specification's §4 table attributes __gunnar_refs__ to the znippy backend; that is the same thing seen from the archive's side. The live log is a refs.arrow sidecar, and repack() folds its compacted state into the archive as a reserved section. The RefStore implementation is arrow_log's either way.

The fs feature is off by default because it assumes a filesystem. What it does not assume, since 2026-08-03, is a worktree, a shell or a .git/config worth parsing: it goes through git's plumbing, gix-odb for objects and gix-ref for references, and links none of gix's porcelain.

That change was not cosmetic. gix::Repository reaches its object and ref stores through gix-discover, gix-config, gix-worktree, gix-index, gix-filter, gix-attributes, gix-ignore and, via blob-diff, gix-command, which exists to spawn subprocesses. This module used to open gix::ThreadSafeRepository, and that alone was why all eight were in the appliance build.

Nothing is reimplemented that git already implements: objects go through gix-odb's implementation of the same gix_object traits the adapter targets, and refs go through gix-ref's loose-plus-packed store with its gix-lock rename atomicity, exactly what gix::Repository delegated to. The one thing the porcelain did that had to be replaced rather than called is creating a bare repository: gix::create builds one out of gix-config and gix-discover, and a bare repository is four directories and two files, so init_bare writes them. tests/real_git_reads_what_we_wrote.rs checks the result with the real git binary, including git rev-parse --show-object-format, which is the only honest proof that the config written there says what it must.

fs is what a server runs on today, because it is the only object backend that survives a restart. gunnar-cli/src/server/stores.rs is where the backend choice is made, and it is the one line that changes when gunnar-store-znippy lands.

tmpfs plus the fs backend fakes a filesystem, and it stays as a backend: the honest fast path for an appliance with RAM to spare. It is not the design, and it must not become the excuse not to build the traits.

There is no database (D18)

redb was in this design and is gone. It was carrying two jobs and neither survived scrutiny.

The object tier. A push arrives as a packfile, which is already an immutable indexed container. Converting it into key-values only to convert it back at repack() is work for its own sake. Git's own answer is many immutable containers plus a periodic merge, and that is now the design: incoming packs, folded into a znippy archive by repack(). No database between two archive formats.

The ref store. Refs turned out to be a better fit for an Arrow IPC log than for a B-tree. See below.

The dependency argument for D18 was wrong

An earlier version of this reasoning claimed the change left "one storage technology and no libc". Both halves were wrong and the arithmetic went the other way. Measured on gunnar-store's tree:

• libc already arrives through gix-features and gix-utils, whatever the storage is.
• Roughly a quarter of the crate's dependency tree exists only because of arrow. The specification records 21 of 87. Re-measured 2026-08-03 on cargo tree -p gunnar-store -e normal with default features, subtracting everything also reachable without arrow: 19 of 81, among them arrow-*, chrono, iana-time-zone, num-bigint, num-complex, half, flatbuffers, ahash, zerocopy. The two counts differ by measurement method and tree drift; the ratio is the point. redb's closure is one.

The design reasons for D18 stand: batch atomicity from the IPC frame instead of a transaction manager, and the reflog for free. The dependency justification does not. Keep the decision, drop the bad argument.

The cost is acceptable in the configuration that matters because arrow is already paid for by the cold tier: znippy's index is Arrow IPC, so any build with znippy has arrow regardless, and the ref log's marginal cost there is zero. That is not true of the plain fs configuration, where gix-ref handles refs and arrow arrives only because fs.rs reuses the arrow-log secret store. A plain-file SecretStore for fs would confine arrow to the configuration that has already paid for it; it is an open item and is small.

Refs as an Arrow IPC log

Refs are a log-structured table. One push writes one RecordBatch, appended to an Arrow IPC stream.

Why atomicity is free here

An Arrow IPC stream frames every message as a continuation marker (0xFFFFFFFF) plus a 4-byte length, then metadata and body; end-of-stream is 0xFFFFFFFF 0x00000000. Verified against arrow-ipc 58, and against real bytes the crate produced. The constant is private to arrow-ipc, so Gunnar names it itself and the tests prove the two agree.

A push that updates three refs writes one length-prefixed message. Either that message is complete on disk or it is not. All-or-nothing is a property of the framing, not of a transaction manager. That is a fix by construction, and it is why there is no crash-injection proof of a bespoke transaction layer: there is no transaction layer.

The schema, and where it deviates from the specification

Specification §4.5 writes it as refname: Utf8 · old_oid: FixedSizeBinary · new_oid: FixedSizeBinary(nullable) · actor: Utf8 · at_unix_ms: Int64. Three things did not survive contact with the trait it has to store:

• old_oid must be nullable too. A create has no old value. The alternative is git's all-zeros oid, which encodes "absent" as a legal oid.
• Symbolic targets do not fit a FixedSizeBinary. HEAD is normally ref: refs/heads/main, and Target::Symbolic is part of RefStore, so two nullable Utf8 columns, old_symref and new_symref, carry them. A row with both new_oid and new_symref null is a delete.
• refname: Utf8 cannot hold every legal git ref name, which is bytes. Rather than corrupt one lossily, this backend rejects a non-UTF-8 name with InvalidRefName. mem and fs accept such names, so the backends genuinely differ; the conformance suite pins that difference explicitly rather than leaving it to be discovered.

Single writer, which is not an Arrow limitation

Compare-and-swap means "read current, compare, write if unchanged", which is only correct if nothing writes in between. redb had the same constraint, one writer and many readers, so nothing was lost by dropping it. Git works this way too: <ref>.lock plus rename, packed-refs.lock.

• Within a process, a per-store Mutex serialises writers.
• Across processes, an O_EXCL lock file is taken at open, so a second Gunnar refuses to start rather than corrupting the log. Two appenders at the end of a stream would interleave and destroy the frame boundaries; Arrow IPC has no reservation protocol.
• Readers take neither. They read the replayed map behind an RwLock.

The lock file does not self-clear after a hard kill. flock was unusable: the crate is unsafe_code = "forbid" with no libc or rustix, and File::try_lock is Rust 1.89 against a 1.85 MSRV. Recovery is therefore at startup rather than an operator verb (S-019, 2026-08-03): the lock records <pid> <start-time> — field 22 of /proc/<pid>/stat, so a recycled pid is detected rather than obeyed — and open reclaims a lock whose owner is provably gone, logging a warn when it does. Anything undecidable (a live owner, no /proc, an unreadable owner line, a lock written by an older Gunnar that recorded no start time) still refuses, and ArrowLogStore::force_unlock is what exists for those.

The lock also propagates. FsStore reuses the arrow-log secret store, so two FsStore handles on the same git directory cannot exist at once, which is why gunnar-cli/src/server/stores.rs caches one handle per repository for the life of the process rather than opening one per request.

Three things that had to be got right

Each has a test that was seen to fail before it was trusted, and each of those tests has a companion that deliberately breaks the mechanism and asserts the guard catches it.

1. fsync before acknowledging. transaction does not return Ok until every byte it wrote is on the platter. One test asserts the durable byte count equals the file length; its companion turns the fsync off and asserts the first test would have failed.
2. A partial trailing message is truncated, never merely skipped. If it were only skipped, the next append would land after the garbage and every later read would stop there — silent data loss that looks exactly like an empty repository. The tests assert the file length after reopening, then append and reopen again, which is where "skipped" would show.
3. The cross-process lock is load-bearing. A test starts a real second process and asserts it is refused, then asserts the same process is admitted once the lock is released, so it cannot pass by refusing everything.

Secrets ride the same mechanism

__gunnar_secrets__ is the same shape: a small Arrow IPC log, last-wins per key, holding the SSH host key and the bootstrap admin material. The SecretStore trait is unchanged; only its backend is. Reusing the log means the atomic get-or-create is proven by the same conformance run rather than written twice.

Layout, symmetric with objects

incoming/*.pack   →  objects.znippy      immutable content · folded at repack
refs.arrow (live) →  __gunnar_refs__     mutable pointers  · compacted at repack

Live appends go to a sidecar stream so they never touch the sealed archive. repack() folds the compacted state in as a reserved section. Same format in both places.

Objects: incoming packs, cold znippy — planned

Neither tier below is built. This is the design they are being built to.

• Incoming is the pushed packfile, kept as it arrived. It is already an immutable indexed container, and gunnar-pack's indexer writes it. Cost is O(new objects).
• Cold is znippy. One archive per repository. Objects are keyed by their oid hex as the archive's relative_path. Immutable, queryable, blake3-verified.
• repack(), exposed as gunnar gc, folds incoming into cold and removes the packs.

Reads check incoming first, then cold. This is git's own loose → pack → repack design. It was not copied from git; it fell out of znippy's constraints independently, and that it lands on the same shape is the strongest signal available that the shape is right.

The write cost that forces the tiering

znippy does support append. ArrowIpcSinkAppend::open_existing reopens a sealed archive, computes blob_end as the lowest index_offset across all sub-index entries, truncates the rebuildable metadata tail, and accepts new blobs at that offset.

But finish() re-sorts the merged old and new row set and rebuilds the whole trie, manifest and footer. That is O(total objects), not O(new objects). A three-object push into a repository holding two million objects would rebuild a two-million-key index.

So: never append the object archive per push. Pushes stay packs, where the cost is proportional to what was pushed. The archive is written by repack(), where an O(total) cost is amortised and expected. The tiering is not an optimisation on top of the archive design. Without it the archive design is not usable at all.

The __gunnar_refs__ log is a different matter. It has hundreds of rows, not millions, so appending it per push is cheap.

Why the objects go in an archive rather than in packfiles

Three properties of znippy's index suit git object storage:

1. A sorted, seekable keyspace. The lookup sub-index is the base columns re-sorted by (relative_path, chunk_seq), so a file's chunks land contiguous and keys land in byte-lexicographic order. That ordering is the substrate the oid index stands on.
2. Per-chunk blake3 verification on every read. get_file verifies each chunk against its stored 32-byte checksum before returning bytes. Git object integrity checking, always on, at no additional cost.
3. Objects become queryable from outside. The lookup sub-index is a valid Arrow IPC stream. Slice it by the manifest's index_offset and index_len and hand it to DuckDB, Polars or DataFusion. That costs Gunnar no code.

Chunking is already handled: a file over file_split_block_size (10 MB) spans several rows sharing a relative_path, ordered by chunk_seq. Large blobs need no special handling.

Packs-in-znippy is rejected. Storing git packfiles as archive members discards the sorted lookup, the SQL surface and the per-chunk checksums, and forces a second hand-written index layer on top to find an object inside a pack. Wrapping one indexed container in another is worse than either.

Refs-in-znippy is rejected and must not be attempted. An archive cannot compare-and-swap a 41-byte value by rewriting a sealed object archive. Refs go to their own small Arrow IPC log. Same technology, different granularity.

Why stree and not the fst trie

znippy builds a sorted lookup sub-index and an fst::Map trie for every archive, at finalize, in meta_sink.rs::write_lookup_and_trie. Both are core znippy, not a plugin, and both index relative_path generically. Using the trie that is already there would be the path of least effort.

It is the wrong structure for these keys. The mismatch is not with znippy's design but with git oids specifically. Oids are fixed-width and uniformly random, so they share no prefixes. An fst over such keys gets no prefix compression, still walks its automaton byte by byte per lookup, and, decisively, has no batch path.

The right structure is already in the tree: stree, in znippy-zoomies/src/stree.rs (STree64, STree64Mmap). A static search tree over sorted i64 keys: one cache-line node, branchless SIMD comparison (_mm256_cmpgt_epi64), prefetched batch traversal. znippy's own benches put it around 40× binary search. That is znippy's number on znippy's workload, not a Gunnar measurement, and no Gunnar claim rests on it until Gunnar measures its own. The structure is built for uniform fixed-width keys, which is what an oid is.

The sign bit

Key derivation is the first 8 bytes of the oid, mapped to an i64, then find_exact, then verify the full oid on the candidate.

i64::from_be_bytes(oid[..8]) is not order-preserving with respect to oid byte order. Any oid whose first byte is 0x80 or higher becomes negative and sorts before every oid starting 0x00..0x7f:

Roughly half of all oids start with a high bit set, so half the keyspace lands on the wrong side. Flip the top bit — (u64::from_be_bytes(first8) ^ (1 << 63)) as i64 — which maps unsigned order onto signed order exactly. With that, the stree key rank equals the sorted-lookup row order, so no parallel rows/ordinals array is needed.

The znippy implementation currently carries explicit parallel arrays instead, because it took an earlier, literal wording of the specification. Both are correct; the XOR form is smaller. Align them before the index is consumed.

Two stree facts the API does not advertise

• STree64Mmap::find_exact returns a member of a duplicate-key run, not provably the first, and its leaf scan only walks at most B+1 records forward. Expand the equal-key run in both directions; do not trust either end.
• STree64::new and new_with_stride assert count > 0, so an empty index carries no tree at all. Handle that as a clean miss, not a panic.

Eight-byte collisions are vanishingly rare but not impossible, and must be handled as a short candidate run rather than assumed away. A test constructs a deliberate 8-byte-prefix collision and must be seen to fail before the verify step is trusted.

The batch path is what actually decides it

Serving a pack means hundreds to thousands of object lookups at once, and stree has lookup_batch_pipeline::<P> and batch_stream::<P>, software-pipelined and prefetched, for exactly that shape. fst has no batch path at all. Git's hot path is a batch path.

stree cannot do inserts. That is not a limitation here: the cold tier is immutable and written once by repack(). A static index for a static store, the same property that makes the tiering work.

The three reserved indexes

The git archive carries three reserved modules. The base columns already supply object type and size, so listing, quota gates and type filtering need no object reads at all.

All three are in scope. 1 and 2 land together; 3 gets its own wave because of its cost, and no speedup is claimed for it until it is measured on a real repository with real merge history. In scope is not the same as earned.

The bitmap structures exist in znippy already and nothing in Gunnar reads them. Until gunnar-store-znippy exists there is nothing to wire them to.

This is what gix-commitgraph and git's .bitmap files are, done natively, and module 2 is readable by anything that reads Arrow.

Why git is a native znippy package format

The alternative was a gunnar-side plugin against znippy's generic extension points. It was rejected in favour of making git a first-class znippy package format, living in the znippy repository alongside the maven, python, media, rust-toolchain and skidbladnir formats, registered in builtin_handlers() and discovered through meta(). The skidbladnir format is the precedent: a nordisk-internal format already lives natively in znippy.

Going native dissolves the upstream work rather than scheduling it. As a built-in, __gunnar_oid__, __gunnar_graph__ and __gunnar_reach__ are known module names, so is_reserved_module is extended with them directly. No generalisation, no naming convention, no registration API, and no risk of a pre-existing archive being reclassified by a newly generic rule.

Two further consequences: stree already lives in znippy-zoomies, so the index code sits beside the structure it uses; and a git archive becomes queryable from DuckDB as a znippy capability rather than as a Gunnar bolt-on.

The cost to plan around is release coupling. A change to the git schema is now a znippy release before Gunnar can consume it. Both repositories are in the same hands, so this is a cadence question rather than a blocker — but Gunnar's Cargo.toml must pin a published znippy-common version and must never carry a path dependency on a sibling checkout.

wasm was rejected

The stree hot path needs AVX2 (_mm256_cmpgt_epi64), an mmap of the archive, and prefetch. wasm offers SIMD128 only, no host mmap and no prefetch, so the speed advantage evaporates and the complexity remains. The appliance server would also have to ship a wasm runtime, which spends the dependency budget on the one build that can least afford it. wasm stays where znippy already uses it: sandboxing untrusted per-file format parsers. Git object indexing is neither untrusted nor per-file-parse-shaped.

One archive per repository

znippy can hold many repositories in one archive. GroupKey { pkg_type, repo, module_name } carries a repo field and the manifest is one row per section, so sub-repositories are native, and a namespace-wide archive would be legal under znippy's "one archive is one ecosystem" rule, which is about the ecosystem and not the repository count.

Gunnar still takes one archive per repository, for one concrete reason: finish() is O(total rows in the archive). A namespace-wide archive would make every repository's repack pay for every other repository in that namespace. Per-repository also makes repository deletion a file unlink, and keeps one repository's corruption away from its neighbours.

The multi-repository capability is retained as a later option for archives of many small, rarely-written repositories, where per-archive overhead would dominate. Not now.

Why repack() writes a new archive instead of appending

repack() does not append. It writes a new .znippy from the old archive union the incoming packs, swaps it in atomically, and only then removes the packs.

It is barely more expensive than appending, because finish() already rebuilds the entire sorted lookup, trie and manifest either way. The O(total) cost is paid in both designs. What the new-archive form buys is safety:

• readers keep serving from the old archive for the whole rebuild. There is no window in which a live archive has had its metadata tail truncated;
• a crash mid-repack leaves the old archive intact and the incoming packs untouched, so the operation is retried and nothing is reconstructed;
• the swap is a rename, which is atomic on a real filesystem, and a single catalog commit where a catalog is in play.

Pack removal happens only after the swap has succeeded and the new archive has been opened and verified. Ordering it the other way round is the one way to lose objects.

repack() is not written. gunnar gc today lists the repositories it would touch and then fails with that fact, rather than exiting 0 over a no-op. An exit code that means "nothing happened" is indistinguishable from one that means "it worked".

Open, and honestly open

• The repack trigger. Loose-object count, incoming bytes, elapsed time, or explicit gunnar gc only. Starting point: explicit gunnar gc plus a count threshold, tuned on measurement.
• Compaction cadence for __gunnar_refs__, the packed-refs equivalent. Ref durability and the reflog shape are settled: the log is the reflog.
• Delta compression. Non-delta first, then measure, then decide. znippy's own zstd or lz4 chunk compression covers part of what git-style deltas buy, so whether deltas are needed at all is a measurement, not an assumption. Clone bandwidth on a large repository may force the question earlier than planned.
• A plain-file SecretStore for fs, to keep arrow's 21 crates out of a configuration that otherwise needs none of them.
• The stale O_EXCL lock after a hard kill. PID-plus-liveness, or raise the MSRV to 1.89 and use File::try_lock.
• LFS objects. Content-addressed blobs, which is the cold tier's shape. Probably the same store. Not decided.

Tests

The conformance suite is one suite, run against every backend, both hash kinds, and — this is the part that makes it worth anything — against deliberately broken backends that it is asserted to catch. Those broken implementations live in gunnar_store::conformance, in the library rather than in tests/, so the ability to report red is permanent rather than something somebody once checked by commenting a line out.

Pinned specifically:

• RefStore::transaction is all-or-nothing. A batch in which one edit's old value does not match must leave every other ref in the batch unchanged. Asserted by reading the other refs back, not by the return value.
• Durability before acknowledgement, with a companion that turns the fsync off and asserts the first test would have failed.
• Truncation of a partial trailing message, asserted on the file length and on a second append-and-reopen.
• The cross-process lock, with a real second process, and the release path so the test cannot pass by refusing everything.
• A non-UTF-8 ref name is refused, not corrupted.
• Both hash kinds. The sha256 path is exercised by a sha256 fixture. It is never inferred from a green sha1 run.
• Stock git reads what Gunnar wrote, in tests/real_git_reads_what_we_wrote.rs.

Planned, once the cold tier exists: the 8-byte oid prefix collision, seen to return the wrong object without the verify step; a repack swap serving identical bytes before, during and after; and a tiered fixture that puts objects only in cold, because a test where every object happens to be in the incoming tier cannot distinguish a working cold tier from an absent one.

Flow (plain text)

push ──▶ pack indexed ──▶ objects written                      O(new)
                          refs applied via RefStore::transaction (CAS, atomic)
                          one RecordBatch, one IPC frame, fsync, then ack

read ──▶ ObjectStore::read ──▶ incoming packs ──hit──▶ bytes
                             └─miss─▶ cold (znippy)            not built
                                        __gunnar_oid__ stree: oid[0..8] → row
                                        verify full oid on candidate
                                        chunk read, blake3 verified ──▶ bytes

gunnar gc ──▶ repack(): write NEW .znippy from (old ∪ incoming)  not built
                        ──▶ open and verify new
                        ──▶ atomic swap
                        ──▶ remove the incoming packs
              (readers serve from OLD for the whole rebuild)

See also: design.md · wire-design.md · appliance-design.md · TOTAL-PROMPT.md §4.