chadtmiller.com/knotless

Switch repository

Loading…

What changes

Refs name their packs. dev.knotless.ref gains an optional pack: the record key of the pack holding its target. A push sets it to its own pack, or, for a commit some ref already points at (a base the push's pack left out), to the pack that ref names.

A fetch reads those packs by key. For each ref whose target is still missing, it reads the named pack with getRecord, all at once, then repeats for bases that are other refs' targets. It walks the pack pages as before only for what that leaves missing: a pointer gone stale because a compaction folded its pack, a ref written by an older client, or a base no ref points at (a branch deleted since, or earlier commits of a branch the client is behind on).

No snapshot lists the packs, but a fetch's reads the newest few. Remote::snapshot reads the repo record and refs, two parallel reads, and heads() goes, since every snapshot is now one. Push, ls-remote, commit, the gateway, queue landings and manage stop waiting on the pack page. Remote::snapshot_to_fetch also reads the newest 4 packs beside the refs; the helper uses it for git's list before a fetch, not list for-push. What was pushed last is among those, so a fetch of it needs no read after the refs. A clone, into a repository with no refs yet, wants every pack, so reads a whole page of 100 there instead, as every snapshot did before.

A fetch looks in three places. fetch takes the snapshot: the newest packs, if it read them; then the packs the refs name; then the walk, going on from the newest packs. The runner, forge and mirrors pass their snapshot, which reads no packs, so they start with the named packs. A pack's tips being here no longer proves its parents are, once packs come in out of order, so a walk that runs out of pages with something still missing walks once more taking every pack it has not indexed.

The compaction count moves out of the push. The owner's push used the snapshot's page to count packs. It now starts knotless compact --due after every push that lands, which reads the packs itself and folds only at KNOTLESS_COMPACT_THRESHOLD. Run detached by default, so git does not wait for the count.

Why

The snapshot read the newest page of pack records alongside the refs, and small packs ride inline in their records. On prod the knotless repository's page was 1.6 MB (1.2 MB gzipped) at 27 packs, growing until each fold. Timed from a laptop against prod, 25 rounds interleaved:

	p50
the helper's git ls-remote	1.15 s
the snapshot's three reads, replayed	1.24 s
the same without the pack page	0.56 s
the pack page alone	1.17 s
the refs page alone	0.51 s

Every snapshot waited on the slowest of its reads, which was always the pack page. A few newest packs cost little more than the refs (3 packs: 0.64 s; 8: 0.91 s; 100: 1.04 s), so a fetch's snapshot reads 4, and a fetch of the last few pushes still takes one round trip. The ref pointers cover a client further behind, and the mirrors, with one more read of exactly the packs needed instead of a page. Pointers alone would have made a fetch of new commits a round trip longer: about 1.1 s on prod (refs 0.53 s, then a pack's getRecord 0.54 s), against 0.56 to 1.24 s before.

Expected on prod, from the timings above: git push and ls-remote about 0.56 s, a fetch about 0.64 s, each against 0.56 to 1.24 s before, depending on how many packs since the last fold.

Considered and measured against this: leveled compaction (pays only for large repositories, grain's 67 MB fold absorbing 0.75 MB of pushes), packing pushes against trunk only (2.3x the bytes, most pushes then over the inline limit), and having knotless-serve choose the packs (clones are bandwidth-bound; serve's HTTPS clone was already only 10 to 20% faster).

How it was checked

• refs_name_the_packs_holding_their_targets (library): a push's ref names its pack, whose tips and bases are as expected; a branch made at main's commit names main's pack; a fresh fetch reads the named pack and walks for its base; compact_due only counts under the threshold and folds over it; after the fold the pointer is stale and a fresh fetch walks to the fold.

• The same test hands fetch a page of only the older pack: the walk indexes it, and the refs then name main's pack. snapshot_to_fetch reads the newest packs.

• compaction_keeps_the_bases_young_packs_name now reaches the base on a deleted branch through the named pack and then the walk; the walk's restart after a failed download is reached through a stale page of newest packs, as before.

• The CLI test runs compact --due under the threshold and refuses an unknown flag.

• oauth's private_repositories caught git ls-remote outside any repository, where the helper cannot read local refs: it reads the newest few packs then.

• agents_fork_review_and_merge (MCP) failed on two runs reading show_item straight after an assignment and a dismissal, before the appview heard of them: the race 73afe073 fixed in two forge tests. It now waits for them.

• just bench 50, main and this branch alternately, twice each, on an idle laptop (p50, ms):

  	main	branch
  push	208, 225	223, 205
  fetch	179, 188	221, 170
  commit	475, 466	513, 423
  clone, 31 packs	350, 516	357, 310
  clone, compacted	174, 322	207, 191
  16 agents, own branches	632, 665	595, 591
  16 agents, one branch	14.0 s, 11.5 s	12.9 s, 11.9 s

  Level within the noise: the reference PDS's pack page is small and local, so the saving shows only on a PDS where that page is slow, as prod's. performance.md's table takes the branch's second run.

• Build, clippy and the test suite ran in CI.

Shortcomings

• A client more than 4 pushes behind, on a fast PDS with small pages, takes one round trip more than before, for the named packs.
• A ref moved back to an older commit no other ref points at names the push's own pack, which does not hold it. The fetch downloads that pack, finds the commit still missing, and walks: correct, but wasted work. Rare enough to leave.
• The saving was measured from a laptop only, not from the runner or serve, which already read snapshots without packs for mirror syncs.
• Every owner's push now starts a detached knotless compact --due, which reads one page of packs, where before only a push at the threshold did.
• Refs written by older clients carry no pointer until they next move, and a fold leaves every pointer stale until its ref moves. Both fall back to the walk, so cost no more than before.

Review

The design first: the pointer's meaning in push::holding, and the fallback order in fetch::fetch. Then compact_due and the helper's after_push.

🤖 Generated with Claude Code

This adds an optional pack to dev.knotless.ref, set by push::holding. The fetch reads the packs the refs name by key before it walks the pack pages. The snapshot no longer lists packs, and compact --due takes over counting them after each push. I found nothing that blocks merging. I did not read the checks, so I can't say whether CI passes.

• Ref writes: push_by is the only place that builds a RefRecord (I searched for RefRecord {). Every writer therefore gets the pointer, including commits and gateway pushes.
• fetch::fetch: A pack that is gone, or fails to download, goes into tried and the loop falls through to walk, so a stale pointer cannot loop. Each round's missing is rechecked against git after the bases are added, which is correct.
• holding: One case can name the wrong pack. A ref created at a commit that is an ancestor of an existing ref's target, when no ref points at it exactly, falls to pushed. The push's pack excludes everything reachable from the bases, so it may not contain that commit. The fetch then spends one extra getRecord and download before it walks. The result is correct, and the pointer stays wrong until the ref next moves. If it is cheap, name no pack there rather than the push's; otherwise the shortcomings note could mention it.
• compact_due: It reads the snapshot and then the pack page, and compact reads the snapshot again when it folds. That is one redundant read only on the fold path, which is fine.

The new commit makes a snapshot read for a fetch (snapshot_to_fetch) also list the newest 4 packs beside the refs. fetch then tries those packs first, then the packs the refs name, then the walk, which carries on from where the 4 end. A push's list for-push, the runner, the forge and serve still read no packs. I found nothing that blocks merging, and I did not read the checks.

• Fetch order: I traced it and it holds. by_name runs at most once, either before the walk when there is no recent page, or after the first walk round when there is one. The restart and cursor paths still work from a 4-item page, because full is computed against n, so next is set. Every call site passes the snapshot now, and the library tests cover the stale-pointer and partial-recent cases.
• Extra downloads: A recent pack is indexed if any of its tips is missing locally, even when the wanted object is elsewhere. A client behind on an unrelated branch can download up to 4 packs it didn't need before reaching the named ones. This is bounded and the old walk behaved the same way, so I'm only noting it.
• Earlier holding note: holding is unchanged, so the case I raised is still there. A ref created at an ancestor of another ref's target, where no ref points at that exact commit, falls through to the push's pack and can name a pack that lacks the commit. The cost is one wasted getRecord and download, then the walk. It stays correct, and I don't ask for a change.
• Description: The body is out of date. It still says no snapshot lists the packs, that Remote::snapshot is two reads, and that a fetch of new commits costs one more round trip than before. A fetch's snapshot now makes three parallel reads, and the common case is back to one round trip. The docs in the diff are correct. The benchmark table doesn't cover the fetch snapshot with 4 packs, so it is worth a line saying that was not measured.

The new commit only changes the test refs_name_the_packs_holding_their_targets. It uses std::slice::from_ref instead of cloning the commits, which is behavior-neutral and reads correctly. I found nothing that blocks merging, and I did not read the checks. The earlier holding note about a ref created at an ancestor of another ref's target is unchanged and still not worth blocking on. The description is still out of date. It says no snapshot lists packs and that Remote::snapshot is two reads, but the pull now has snapshot_to_fetch, which also reads the newest 4 packs. It would help to update it.

The new commit changes the fetch walk. It now tracks the packs it has indexed by key (seen). When the pages run out with something still missing, it walks once more and takes every pack not yet indexed, whatever its tips. This covers a pack that holds a commit while the parents sit in an older pack whose tip is already present. I traced it and it holds. by_name and the walk share seen, and seen keeps a pack from being downloaded twice. The fetch's count is now seen.len(). The failed-download path still returns before it extends seen. The docs describe the new pass. I found nothing that blocks merging. CI was still running when I looked, so I can't say whether it passes.

One thing to be aware of: restarted now means two things. A download that fails mid-walk because a compaction deleted the pack also sets it. The fresh walk after that failure then indexes every pack it hasn't seen, not just those with a missing tip. That is correct, but in that rare race it can download more than before, up to the whole repository on a large one. If it matters, use a separate flag for the take-everything pass. I don't ask for that.

The description is still out of date, as I noted in earlier rounds. It says no snapshot lists packs, that Remote::snapshot is two reads, and that a fetch of new commits costs one more round trip. The snapshot_to_fetch part is also unmeasured. Please update it before merging.

The new commit makes a fetch's snapshot read a full page of packs (100) when the local repository has no refs yet, which is a clone, and 4 otherwise. snapshot_to_fetch takes the count, RECENT and PAGE are used in helper.rs, and the storage doc is updated. This avoids a clone paying the extra walk rounds. The test now also checks that compact_due counts 0 packs before the first push. I found nothing that blocks merging. I did not read the checks.

The description is still out of date, and I've said so in earlier rounds. It says no snapshot lists packs and that Remote::snapshot is two reads. It leaves out snapshot_to_fetch, both the 4-pack read and now the 100-pack read on a clone. It also says a fetch of new commits costs a round trip more than before. Neither new read is covered by the timings. Please update it before merging.