performance: fork and delete amplify metadata reads with live sibling branch count #642

Activity

1. ragnorc

   added

   needs-triageAwaiting maintainer triageAwaiting maintainer triage

   featureFeature proposalFeature proposal

   on Sep 5, 2026
2. azimafroozeh

   added

   acceptedTriaged and validated; open for a PRTriaged and validated; open for a PR

   P-lowLow priorityLow priority

   performanceCorrect result, wrong cost: work scales with the table, not with the delta or the queryCorrect result, wrong cost: work scales with the table, not with the delta or the query

   and removed

   needs-triageAwaiting maintainer triageAwaiting maintainer triage

   on Oct 1, 2026
3. azimafroozeh

   self-assigned this

   on Oct 1, 2026
4. ragnorc commented on Oct 18, 2026

   

   ragnorc

   on Oct 18, 2026 – with Cursor

   ContributorAuthor

   More actions

   Summary

   On current main, a fork and a delete do not add object-store requests as the number of live sibling branches grows. The 0.10.0 report measured that growth. Two later changes removed the two reads that caused it. Fork lists branch-ref names and reads only the refs that share the new name's Lance path. Delete retires one __manifest ref. It does not open the other branches. Cleanup, not delete, reclaims unused table forks.

   Reproduction

   Verdict: not reproduced.

   main is be031fea766fc8b280137f9ad9f34d4d2b3087bc (feat(query): the ranked binding roots its component (#1069), 2026-10-18). The cited 9f0bac0387ea is an ancestor of this commit. The cited a09176d7 is also an ancestor. OmniGraph 0.14.0. Lance 11.0.0 from Cargo.lock. rustc 1.97.1. Linux.

   The report used a 0.10.0 HTTP server, a fixed 121-table catalog, and local MinIO with 17 ms added to each physical request. This run uses GQT --measure under DST. The store is the in-memory object store. The model is unit (the default). Seed 0. Both DST runs of that seed agreed, because each case passed. This counts the same object-store verbs the report counted (list, head, get, put, delete). It does not add 17 ms, and it does not use MinIO.

   Schema: one node type, Person { name: String @key, age: I32 }, one seed row. Each case creates and deletes warmup, then creates N idle branches, then creates and deletes victim on the warm handle. A restart follows. The case then creates and deletes victimcold. N is 0, 8, and 32.

   cargo run -p omnigraph-gqt --bin omnigraph-gqt --locked --offline -- \
     /tmp/issue642/sib0.gqt /tmp/issue642/sib8.gqt /tmp/issue642/sib32.gqt \
     --measure --target omnigraph-engine-dst \
     --storage in-memory-object-store --seed 0 \
     --artifacts /tmp/issue642/artifacts

   3 of 3 cases passed (sib32 in 0.98 s).

   Live siblings	Fork requests here	Fork in the report	Delete requests here	Delete in the report
   0	11	84	40	153
   8	11	212	40	697
   32	11	596	40	2,329

   The slope here is 0. The reported fork slope is 16 requests per sibling: (212 - 84) / 8 = 16 and (596 - 84) / 32 = 16. The reported delete slope is 68: (697 - 153) / 8 = 68 and (2329 - 153) / 32 = 68.

   The same 11 and 40 hold for every create in the 32-sibling case, from the first branch through victim, and for the create and delete after restart. Warm and cold match. bytes_read is 2,709 on every create and 16,813 on every warm delete. A four-type catalog (A B C D) gives the same 11 and 40 at 0 and at 8 siblings, and the step has no table_* request.

   The 32-sibling fork log has 11 requests and no path that contains a sibling name. It lists __manifest/_refs/branches twice, reads the new ref's absence, and writes that one ref plus the shallow-clone manifest and transaction. The delete log has 40 requests and no sibling path. It lists _refs/branches twice and _refs/tags once. The 12 heads and 7 gets are all the victim ref file. The 9 data gets are the victim __manifest data files.

   What differs from the report: the version, the transport, the store, the catalog width, and the counts. The report's slope is absent. I did not run the 121-table MinIO fixture. The four-type control has no table I/O on these two steps, and current branch writes do not create a table fork, so catalog width does not multiply this path.

   Root cause of the reported slope, and the current path

   The report's fork arithmetic matches Lance Branches::fetch on the cited commit. That function lists _refs/branches, then reads every ref with BranchContents::from_path. from_path opens the object, calls size (a HEAD), then get_range (a GET). Eight such listings at 32 siblings are 256 HEADs and 256 GETs, which is the report's +16 requests per sibling. The report's delete also opened each surviving branch __manifest to prove that no survivor still used the deleted branch's table forks.

   On this commit those two reads are gone.

   Fork. ManifestCoordinator::create_branch calls ensure_manifest_branch_create_namespace, then create_branch_recoverably. The namespace check lists ref names and reads contents only for the source branch and for names that would share the new branch's Lance path. create_branch_recoverably lists names again. It reads the new ref only to see that it is absent. It does not call Dataset::list_branches.

   • create_branch
   • ensure_manifest_branch_create_namespace and list_branch_ref_names
   • branch_create_as

   Delete. delete_branch_with_expected resolves the one native ref, settles that branch's own buffered commits, and retire_branch_recoverably reads that ref, lists tags, writes retirement metadata, archives BranchContents, and unlinks the ref. No loop opens another branch.

   • delete_branch_with_expected
   • retire_branch_recoverably
   • delete_captured_branch_storage

   The scan left in #695 (merged 2026-09-10). That PR defers table-fork reclamation to explicit cleanup and keeps the ancestry a descendant needs. The full ref materialization left the create and resolve path in #706 (merged 2026-09-13). A later write-path change stopped creating a table fork for a graph branch. A branch write stages a detached commit on the dataset the registration already names. Branch writes states that contract. A pre-v11 table fork stays valid, and cleanup reclaims one that no registration still names.

   Dataset::list_branches still reads every ref. Callers that need a full inventory still use it. Those callers include logical enumeration, cleanup, and the commit lookup in #972. Fork and delete are not in that set.

   Fix

   Invariant 11 says hot-path work scales with the working set, not with accumulated history. The 0.10.0 fork and delete scaled with unrelated live branches. The working set of a fork is the source ref and the new name. The working set of a delete is the one branch being retired. The affected class was every fork and every delete on a graph that had idle siblings, at any table count. The table-width cost closed in #310 was a different class.

   The shape that removes that class is the one already on main. One directory list names the refs. Content reads stay on the refs the operation must check. Delete does not open survivors. cleanup is the pass that reads retained manifests and proves which old forks are unused. That keeps dependency safety off the delete acknowledgement, which matches the issue's own rule: do not drop the safety check, and do not cache a mutable ref without an authority rule.

   I would not add a process-local cache of branch refs for this slope. The issue already refuses that cache. Invariant 12 keeps __manifest as the authority. A cache that can disagree with a retired ref is a second record.

   I would not put the survivor manifest scan back on delete. The scan answered a question the current delete does not need. A new graph branch has no per-table fork for a sibling to borrow. Restoring the scan would spend one or more __manifest opens per live branch on every delete, which is the reported delete slope, in exchange for a check cleanup already owns.

   One test gap remains. branch_delete_manifest_reads_bounded_per_surviving_branch allows one __manifest read per surviving branch, plus slack of 2. The measured slope is 0, so that upper bound stays green if a one-manifest-per-survivor scan returns. A gate that requires a flat slope, next to that test, is the check that matches the contract in writes.md. I did not change the test.

   A constant remains inside one delete. The victim ref is read 12 times by HEAD and 7 times by GET. That cost does not grow with siblings. It is outside the slope this issue reports.

   The directory list still returns every ref name. One list page holds 1,000 keys. The measured range, 0 to 32, stays on one page, so the request count does not move. The list response grows by one key per sibling. This counter records 0 bytes for a list, so that growth is not in bytes_read. Past 1,000 live refs, the list adds one request per extra page. That is the remaining term, and it is not the 16-and-68 slope.

   Lance

   Pinned Lance is 11.0.0. BranchContents::from_path is open, then size (HEAD), then get_range (GET), in rust/lance/src/dataset/refs.rs. The same function is in Lance 12.0.0 (released 2026-09-17) and on Lance main at ac705611ddee6df27a90e334cabb6e8218893120 (2026-10-18). Branches::fetch still lists the directory and then calls from_path for every name. Lance's own open_with_size can skip the HEAD when the size is already known. from_path does not use it. The branch metadata layout stores one JSON file per branch under _refs/branches/ and does not define a single-object read of that file.

   No open Lance PR replaces that two-request read with one GET. The open branch work that touches listing is lance#9198, which fixes lance#9197 (a slash in a branch name is omitted from a one-level list on some stores). That PR still reads each branch's contents after the list. It does not remove the per-ref HEAD and GET. It also does not change OmniGraph's name-only list. A Lance release that only switches from_path to one GET would cut the cost of a full list_branches. Fork and delete on this main do not call that full read, so that release would not move the 0 slope measured here.

   Related work

   • #972 is open. A commit id that misses the current branch buffer and __history is found by record_in_live_branches, which calls list_live_manifest_branch_contents and therefore Dataset::list_branches. The reproduction on 9575b044 measured +4 requests per idle branch on one diff (2 HEAD and 2 GET per branch, because the diff lists twice). Fork and delete do not call that function. The slopes, the operations, and the code differ. See the supersession note below.
   • #641 is closed. It is merge metadata and a fragmented historical base. It is not fork or delete.
   • #643 is open. Independent merge targets serialize on graph-wide guards.
   • #644 is open. It asks to reclaim old physical __manifest versions. That is cleanup, not the delete acknowledgement.
   • #647 is open. It asks for safe deletion of unmerged work and a recovery window. That is a correctness rule for what delete may drop. It is not the request slope.
   • #969, #970, and #971 are open. They are diff reads, change-page replanning, and ordered-cursor hydration.
   • #1068 is open. A cold commit list reads merged history blocks one branch at a time. That is history read order, not fork or delete.
   • #310 is the table-width issue this report already separates from the sibling slope.
   • #662 and #638 are merged. Both name this issue and both say they do not close it. #695 and #706 are the merges that removed the two measured reads.
   • RFC 0057 records this issue as separate from merge preparation.
   • Open #677 is draft RFC 0060, branch operations v2. It does not change runtime behavior. Open #1016 adds branch create at a commit. It does not claim to change the sibling slope. Open #1012 adds a detailed branch listing that reads each listed branch on purpose. That cost belongs to the listing, not to fork or delete.

   Supersession

   #972 does not supersede this issue. #972 is a commit-id lookup that still lists every live ref. This issue is fork and delete, and those two operations no longer do that list. I am not closing this issue.

   Limitations

   I did not rebuild the 121-table HTTP fixture or the MinIO proxy. I did not run --model s3-like or a release binary on disk. The reported signal is the request slope, and the request count is flat, so a per-request delay cannot add a sibling slope. I did not measure concurrent fork and delete, a descendant branch, delete and recreate, or a retained snapshot. The cases above cover the reported 0, 8, and 32 sibling points, warm and cold, on one type and on four types.