NetBSD src in Fossil form is 317,081 check-ins, 206,523 files at the tip,
and 3,649 megabytes of store. A CI runner that builds the tip, a sandbox
that makes one change and pushes it, someone who only works in sys:
none of them will read any but a sliver of that, and a Fossil clone hands
them all of it. Fossil has no shallow clone and no partial one. The only
clone is the whole repository, and that is a good default. It is a poor
only option.
zit already had half of an answer. A sparse cone keeps every structural
artifact and drops the file content outside a set of paths, so --cone=sys
gives you the files under sys and still a whole, verifiable repository.
That is the breadth half. This release adds the depth half, the horizon,
and the more interesting result is the measurement that decided which kind
of horizon was worth building.
What a horizon is
A horizon is a check-in C and a rule for which check-ins count as at or
after it. The default rule, descendants, takes C and everything descended
from it. The other, leaves, also takes in each childless check-in's
ancestry back to where it meets C's, so a merge between two live branches
finds its base inside the clone. Both rules are stated over P cards. Log
order and timestamps both disagree with ancestry wherever branches run
concurrently, and a cut defined on either would hold a check-in while
lacking a parent that happens to be newer.
What the clone does not hold it still knows by name. An artifact below the horizon is an elided phantom: known, deliberately absent, never requested unless someone asks for it. Nothing is rewritten. A manifest's name is the hash of its bytes, P cards included, so dropping a parent from a manifest would rename it and every descendant. Every artifact a horizon clone holds is the origin's artifact under the origin's name, and a check-in committed in one lands at the origin as itself.
The cut I expected to build, and the one that pays
The obvious horizon keeps every manifest and drops old file content. Call
it the content horizon. Every input the derive reads is still there, so
timeline, leaves, branches and merge ancestry come out exactly as they do
on a dense clone, against any server, with no cooperation from it at all.
It is Git's blobless partial clone, not Git's --depth.
Then I measured what it would save. pkgsrc's sub-manifest store is 632 MB dense, and 137 MB of that is file content. The rest, at least 495 MB, is manifests, tree nodes, tags, wiki, tickets and forum, and a content horizon keeps all of it. Structure outweighs content about four to one, and that is with tree manifests, which keep each check-in's manifest small. A long history is a great many small things. The content horizon can save at most a quarter of pkgsrc.
So the cut that pays has to go through the manifests. The structural horizon keeps only the manifests and tree nodes that the held set reaches through P, B and S cards, plus every control artifact at every age, since they are small and a tag below C can still change the state at C. On pkgsrc that clone is 61 MB, against 632.
The seed
Dropping the old manifests breaks the derive. Branches in Fossil are not stored anywhere. A branch tag is applied once, to the check-in that starts the branch, and propagates forward along primary parents. A clone with no ancestors of C has nowhere for propagation to start, so every check-in it holds would come out on no branch at all. Closed markers set below C would vanish, and tags applied below C would not resolve.
What stands in for the ancestry is the smallest thing that can: one control artifact the origin mints from its own derivation, the seed. Its T cards apply directly to C every tag in force there: the branch tag with its value, the other propagating tags, the closed marker, and the non-propagating tags on C. It does the same for each other check-in of the held set whose primary parent is below C. A branch forked below C that later merges C in has one of those. With the seed applied, propagation starts at each of those check-ins with the state the dense repository has there, and everything above derives exactly. The derive needs no new code to apply it, because it already knows how to apply a control artifact.
A few rules keep it honest.
- Its D card is the latest time among the tag events it summarizes, rounded up to a whole second. Fossil's rule that the later tag wins then makes it outrank what it stands in for, and minting it twice over unchanged state produces the same bytes and the same name. The clone names its seed on every pull, and the origin sends a new one only when the name differs. The origin keeps no per-client state.
- Its U card is
zit-serve, not a login. No user applied those tags. - It never leaves the clone. Pushed into a repository whose state has moved on, it would be a wrong tag application with a late date. zit holds it beside the store cone, outside the artifact store, so it is never announced or offered.
- It reaches a shared artifact in exactly one place. A check-in that starts a branch writes a cancel card for the parent's branch, and the parent's branch is what the seed said. The origin checks that card against its own derivation at push and refuses a stale one, naming the command that writes the correction.
A seed is derived state the clone did not derive, and its blast radius is the clone's local view plus that one checked card. It can be verified by deepening to wherever each tag was really applied and computing it again.
The rest of the machinery
The origin labels every boundary parent it sends, so the clone can tell a parent below the horizon from one that simply has not arrived yet. Anything that needs history below C, such as an update to an old check-in or a merge whose base is old, deepens. It moves C back, drops the old seed and pulls what the new held set adds. That is the one remedy for everything, and nothing does it on its own: Fossil verbs do not talk to the network unless asked, and neither do these.
The origin classifies once per store, not once per request. Every set the classification computes only grows as artifacts are appended, so it is kept in a sidecar keyed to the log prefix and extended over each new tail. The one arrival that breaks that is an artifact something held already cited, and it is detected by name. The references the classification reads do not depend on the horizon at all, so they are read once per store into a graph, and any horizon, including one the origin has never seen, is classified over the graph. Pulls carry a cursor, so a pull from a horizon clone announces nothing. A no-op pull on the pkgsrc structural clone moves 431 bytes up and 237 down.
Against a stock Fossil server none of this origin work happens, and the draft is written so that is a documented property, not a hope. Every new card is a pragma, and Fossil ignores pragmas it does not know. A content horizon clone of a Fossil server classifies locally and pays the bandwidth. A structural request has no seed to stand on, so it falls back to the content horizon and says so. Check-ins made in a horizon clone and pushed to stock Fossil arrive byte for byte, and a fresh Fossil clone of that server rebuilds clean.
What it measured
All on NetBSD src, the same x86 Linux host, served over loopback, every clone verified with 0 faults.
| Structural horizon | Wall |
|---|---|
--cone=usr.bin, cold |
4.6 s |
--cone=usr.bin, warm |
1.10 s |
--cone=sys |
44.5 s |
| whole tree, 182,735 artifacts | 189 s |
| Content horizon | Wall | Client RSS | Held |
|---|---|---|---|
--cone=usr.bin |
452 s | 1.87 GB | 449,113 artifacts, 359,052,984-byte store |
--cone=sys |
1611 s | 2.07 GB | 713,630 artifacts |
The ratio between those two tables is the four-to-one from pkgsrc again,
seen as time. The content horizon under usr.bin still holds every check-in
manifest of 317 thousand check-ins, and the in-cone tree nodes of each one.
The structural horizon holds one tree's worth.
The regression
The horizon work lived on a branch while trunk shipped 0.6.5 and 0.6.6,
and 0.6.5 brought the path-cone index: the classifier stopped re-reading
every artifact for every cone. After merging trunk into the branch, I timed
the plain path-only cone clone as a control, --cone=usr.bin with no
horizon, 932,336 artifacts. It had got slower:
| Build | Wall | Client user CPU |
|---|---|---|
| zit 0.6.6 | 1826 s | 1347 s |
| merged | 1943 s | 1545 s |
Two hundred seconds of client CPU had appeared from somewhere, and a total does not say where. So I ran the clone again with every phase timestamped. The transfer was level. Classification was not: 412 s merged against 201 s in 0.6.6. Of the merged build's 461 s of classification wall time, 215 s was a single step, the finalize slot walk.
The slot walk exists for sparse stores that are missing tree nodes. A path cone can elide a sub-manifest node that no S-card slot leading into the cone reaches, and finding those means walking every tree in the store. In the merged build the walk ran on this clone too, where the origin had sent every node. Every node was held, and the walk read every tree in the store a second time to find nothing.
The fix is a flag. While the classifier reads S cards, it already learns whether any of them names a node the store does not hold. It now records that, and the walk runs only when one does. A test builds the same two-level tree twice, once whole and once missing a single leaf below an inner node, and checks that the walk is skipped for the first and still finds the hole in the second.
| Build | Wall | Client user CPU | Elided | Store |
|---|---|---|---|---|
| zit 0.6.6 | 1826 s | 1347 s | 1563 | 1,244,509,552 bytes |
| final | 1713 s | 1343 s | 0 | 1,241,666,920 bytes |
The final build is faster than 0.6.6, not just back to it. The Elided column is the other half. 0.6.6's origin served a kept blob as its stored delta even when the delta's base was outside the cone. The client then had to fetch the base to expand the blob, and then drop the base. That is 1563 artifacts sent only to be thrown away. The new origin sends any delta that crosses the cone in full form, so nothing outside the cone arrives at all.
That rule has a corollary for a client newer than its origin. A 0.6.6 origin still sends crossing deltas, and a clone that writes rounds as they arrive would have written those out-of-cone bases into the store for good. What arrives after the clone sequence, the answers to the clone's own requests, is now held back and judged by the cone before it is written. A base the cone does not keep is dropped, and the blob that needed it is stored in full form.
The same change took the content-horizon usr.bin clone from 513 s to 452 s.
What is still open
- The cache derive after a clone. In both 0.6.6 and the final build, about 55% of the path-cone clone above, around seventeen minutes, is warm_cache: deriving the repository image after the transfer is done. It is the largest single cost left in a path-cone clone and is not horizon-specific.
- The origin's first time. The origin builds its cone index once and reuses it. On NetBSD src the first build is about 1,100 s of origin CPU. The structural graph has its own one-time read. A long-lived server pays each once. A front that spawns a server per request pays the load on every request.
- Content-horizon memory. The content horizon clones above peak at 1.87 and 2.07 GB of client memory. They hold every manifest of the history, and that is the price of an exact derive with no seed.
- Seed signing. The draft says an origin that holds a signing key SHOULD sign the seed, and a clone that knows the key MUST verify it. zit does neither yet. Today a seed is bound to the reply that delivered it by its hash and by nothing once it is on disk.
- The work after a push. Minting a new seed, extending the repository image and extending the classification and the graph take the origin seconds on the push and again on the next pull. Each is bounded, and none is yet as incremental as it could be.
- A default commit on a big tree. Fossil's R card is computed from every
file in the tree. With
repo-cksum offa commit in the NetBSD structural clone takes 1.8 s. With the default it reads every file.
The draft that specifies all of this, draft-fossil-horizon-00, ships in
the source package beside the other Fossil drafts.