In progress 12 Aug 2026 · The Heddle team · 7 min read · engineering·storage·git

Smaller than the Git pack it can reconstruct

There's a function in Heddle's repack code whose only job is to flip one bit. Ask for it in a test and corrupt_if_requested XORs the middle byte of the first frame the repack writes, so we can watch the pipeline refuse to commit it. The hook exists because the whole feature hangs on one promise: after the store rewrites every tree and every commit-state into a new encoding, each object has to come back byte-for-byte identical. A verifier nobody has ever seen fail is not a verifier, so the failure is a test case.

With that constraint pinned down, here's the result. heddle#1338 landed a columnar encoding for the metadata half of the store and plugged it into the background repack. On three public repos at pinned revisions, the repacked store comes out 9 to 17% smaller than the same history's Git pack, while carrying fields Git has no place for: who wrote each state and which agent model under which session, what the test run said, where a change was cherry-picked or reverted from. And the Git side still reconstructs exactly.

corpus	revision	objects	heddle total	git pack	ratio
ripgrep	3fce3b5bb023	13,790	2,805,825 B	3,380,197 B	83.01%
curl	f5378b88a974	287,550	47,117,705 B	53,893,244 B	87.43%
semver-cli	4fea7f0d5a1c	373	107,166 B	117,623 B	91.11%

Three things at once, then: smaller than the pack, storing more than the pack, and able to give every byte back. Any one alone is unremarkable. You can beat Git's size by throwing information away; you can store richer metadata by paying for it; you can be lossless by changing nothing. The interesting part is the mechanism that gets all three, and it's mostly about admitting what the data is before you compress it.

What a pack refuses to know

A content-addressed store is structure-blind on purpose. It knows each object's hash, type, and size, and by design nothing else — the hash of version 41 of src/main.rs shares not one bit with the hash of version 42. So when a packer goes looking for delta bases, it has to guess which objects resemble each other. Heddle's pack builder does what Git does: it sorts candidates by a path hint (extension, then basename, then size descending) and runs a sliding window over the result, so successive versions of the same file end up adjacent and delta against each other.

Here's the confession that motivates everything else in this post. Until this week, our hosted production writer passed None for every path hint. Objects without hints sort into a single bucket at the end, which meant the entire sort quietly collapsed to size ordering, and deltas were being picked among size-neighbours: whatever blobs happened to be about as long as you. It worked, in the sense that packs were produced and nothing crashed, and it wasted space on every write. The fix (weft 24e13c0c, "populate production pack path hints") is three files and about sixty lines. The packer was never the problem. It just couldn't act on structure nobody told it about.

That failure is the honest version of a general rule: a size-sorted delta window is an archaeologist guessing at kinship from bone length. If the store itself knows that these twelve trees are the same directory across twelve versions, and that these nine blobs are nine revisions of one file surviving two renames, it can stop guessing.

Frames that know what they hold

The compact encoding stores trees and states not as one record per object but as frames of many, laid out column-wise. A tree frame (magic HCT1) holds a batch of trees; for each one it writes all the entry modes, then all the entry kinds, then all the names, then all the 32-byte targets. The point of the transposition is that the columns have wildly different entropy. Modes are almost all regular-file; kinds are almost all blob; names repeat across versions of the same directory almost verbatim. The hashes are the only column that's genuinely random, and now they're contiguous instead of interleaved with everything else.

A state is Heddle's commit-grade object: it points at a tree and lists parents, then keeps going. The state frame (HCS1) opens with two dictionaries — principals as name/email pairs, agents as provider/model/session/segment/policy — interned once and referenced by varint index from then on, because a repository has thousands of states and a handful of authors. After that, columns: change ids, tree hashes, parent lists, attribution indexes, intents, confidence values, verification results (tests passed and failed, coverage and its delta, lint warnings, custom keys), status bytes. Timestamps are stored as zigzag deltas from the previous state, since commit times arrive nearly sorted and the deltas fit in a byte or two; an authored-at time is stored as an offset from its own created-at. Then the Git-fidelity tail: the raw commit message, extra headers, committer, timezone offsets, provenance hash, and a lossy-import flag, so a Git projection can be rebuilt without inventing anything. Then lineage records — cherry-pick, collapse, revert, git-projection — each naming its source change and state.

One field is missing on purpose: the state id. It's recomputed from content on decode and checked, not stored. Ids you can derive are bytes you don't spend.

Each frame gets a BLAKE3 checksum, then zstd at level 19 with long-distance matching over a 128 MiB window. If compression fails to shrink a frame it's stored raw, so the reader's size check stays unambiguous. Frames are bounded at 12 MiB of payload, and in the pack file many logical objects share one physical record: the index points every tree in a frame at the same offset, and the reader decodes and verifies the whole frame before handing back the single object you asked for.

The compression is downstream of the layout

None of the above compresses anything by itself. What it does is decide what ends up adjacent, and adjacency is what a compressor can actually use. The repack walks states newest-first in topological order, then emits trees grouped by directory path in that order — version N of src/routes/ right next to version N−1 — before the frame ever meets zstd. Long-distance matching is, in effect, a delta engine: it finds repeated spans anywhere in its window. It cannot find versions of the same directory that a hash-ordered or size-ordered layout scattered across the store. Grouping by identity first is what turns a big match window into a delta chain.

The blob side runs on the same idea with more work. A lineage walk diffs each state's tree against its parents, follows files through renames (exact matches, plus similarity matches above 0.6), and writes each path's versions adjacently, newest to oldest. That layout plus the same solid compression is what the #1325 falsifier measured, and this PR re-gated those numbers against the real production compact writer for the metadata.

You can see the layout doing the work in the PR's own accounting, because the same encoder at the same level produces wildly different ratios depending on how much structure there is to exploit. Compact tree frames land at 1.85% of the same trees' native record bytes on curl — 287,550 objects, decades of history, enormous numbers of near-identical directory versions. On ripgrep it's 10%. On semver-cli, 373 objects and barely any history to repeat, it's 28%. State frames sit between 41% and 57% everywhere, because states are mostly hashes and message text and there's less redundancy to find. If the codec were the story, those numbers would cluster. They track repetition instead.

The objections, taken in order

"You're just compressing harder than zlib." Partly, and it would be silly to deny it: Git's pack is zlib over its own deltas, these frames are zstd 19, and some of the margin is simply the newer codec. But the baseline is not naive — Git's pack format has had twenty years of delta and ordering work — and the tree-frame spread above (1.85% versus 28%, same codec, same level) is a layout effect, not a codec effect. The codec can only eat the redundancy the layout hands it.

"zstd 19 is slow." It is, and nothing on the write path pays it. Compact frames are produced by a background repack: staged to the side, verified, then cut over atomically, the same maintenance slot where Git would run gc. Frames are bounded at 12 MiB so no single compression call runs away. Reads pay zstd decompression, which is the cheap direction, plus decoding a frame to serve one object from it — the standard trade every columnar system makes.

"9% isn't much." On semver-cli it's 8.9%, and taken alone that would be a boring result. The claim is not a compression record. The store is carrying strictly more than the pack it undercuts — per-state agent attribution, verification outcomes, lineage, intent — and the naive expectation is that all of that costs bytes on top. It comes out under instead, with the comparison counting Heddle's own index and excluding Git's. Notice also that the smallest corpus does worst: fixed overheads amortize with history, so the ratio improves exactly where storage starts to matter.

"Lossless how, exactly?" Mechanically, and at write time. Before any frame is committed, the repack decodes it back and compares: trees value-by-value with their hashes re-derived, states re-serialized to canonical named MessagePack and compared byte-for-byte against the originals, ids recomputed from content and checked against what the index will claim. Each frame carries a BLAKE3 checksum inside zstd's own checksum. Above all of that sits the whole-store gate the table reports: a fingerprint over every typed object before the repack and after it, which must match exactly. And the bit-flip hook from the first paragraph is the negative control — corrupt one byte of one frame and the repack must fail loudly rather than store it. It does.

What this doesn't claim

This is the local object store on disk: compact metadata plus blob frames plus index, against a Git pack, on three corpora. It says nothing about Heddle's hosted layer, which projects objects into remote storage with different trade-offs and is a different measurement for a different post. It says nothing about clone or transfer sizes. And three corpora are three corpora — all source code, where history repeats. A repo full of already-compressed assets gives neither side much to work with, and I'd expect the ratio to drift toward parity there; we haven't measured it.

The encoding lives in crates/object-model/src/compact, the shared-frame pack plumbing in crates/pack, and the repack integration in crates/objects. The corpora, revisions, and the harness that produced every number above are in the PR, if you want to re-run the arithmetic.

---

Heddle is open source at github.com/HeddleCo/heddle; the change discussed here is PR #1338.