performance: merges into independent targets serialize behind graph-wide guards #643

Activity

1. ragnorc

   added

   needs-triageAwaiting maintainer triageAwaiting maintainer triage

   featureFeature proposalFeature proposal

   on Sep 5, 2026
2. ragnorc

   added a commit that references this issue on Sep 25, 2026

   rfc: shared schema gate and the write critical section

   ...

   1af2323
3. ragnorc commented on Sep 30, 2026

   

   ragnorc

   on Sep 30, 2026

   ContributorAuthor

   More actions

   Measured this issue's shape before and after #783 (the shared schema gate):

   • RustFS through toxiproxy at +30 ms per round trip, release builds;
   • N concurrent merges into N independent, diverged targets, with completion times measured from the batch start;
   • as in the original report, a control: one merge on a graph with the same branch count.

   N	Before #783 (b14c22c5): completions, s	Last ÷ single	After (main c6f24757): completions, s	Last ÷ single
   1	4.36	1.01	4.15	0.99
   2	4.41, 8.61	1.99	5.16, 5.16	1.23
   4	4.54, 8.72, 12.88, 17.06	3.98	6.38, 6.92, 7.40, 7.88	1.86
   8	4.79, 8.97, 13.16, 17.35, 21.52, 25.71, 29.90, 34.04	7.88	10.06, 10.06, 10.06, 10.22, 10.74, 11.21, 11.71, 12.21	2.89

   Before #783, the staircase in the report reproduces exactly: each merge waits out the whole previous one. Since #783, a merge takes the schema gate's shared side, and merge_exclusive is gone, so independent merges overlap: eight finish in 2.9 times one merge instead of 7.9. Some serialization remains, a tail of about 0.5 s per additional merge. I have not attributed it yet.

   The acceptance criteria are pinned in #822 (tests only):

   • independent targets overlap;
   • same-target merges serialize;
   • deleting a merge's source or target waits for the merge;
   • a schema apply waits for a parked merge, then refuses on its branches;
   • same-source merges both land.

   Same-source merges currently serialize on the source's branch gate, even though a merge only reads its source. #822 leaves that unpinned, because whether they should overlap is a design question for this issue.

   Still open here:

   • the residual tail above;
   • memory/RSS and explicit admission limits (not measured);
   • cancellation (a failpoint test needs an async parking primitive);
   • failure/recovery and branch recreation during a merge.

   Harness (a local ignored test, not committed)

   //! Local, uncommitted instrument for issue 643: N concurrent merges into N
   //! independent targets, completion times from batch start, plus a matched
   //! single-merge control on a graph with the same branch count.
   mod helpers;
   
   use std::sync::Arc;
   use std::time::Instant;
   
   use helpers::{MUTATION_QUERIES, TEST_DATA, TEST_SCHEMA, mixed_params, session};
   use omnigraph::db::{MergeOutcome, Omnigraph};
   use omnigraph::loader::LoadMode;
   
   async fn graph_with_pairs(uri: &str, pairs: usize) -> Arc<helpers::Session> {
       let db = session(Omnigraph::init(uri, TEST_SCHEMA).await.unwrap());
       db.load_jsonl(TEST_DATA, LoadMode::Overwrite).await.unwrap();
       for i in 0..pairs {
           for (branch, age) in [(format!("s{i}"), 51), (format!("t{i}"), 52)] {
               db.branch_create(&branch).await.unwrap();
               db.mutate(
                   &branch,
                   MUTATION_QUERIES,
                   "insert_person",
                   &mixed_params(&[("$name", &format!("On-{branch}"))], &[("$age", age)]),
               )
               .await
               .unwrap();
           }
       }
       Arc::new(db)
   }
   
   #[tokio::test(flavor = "multi_thread", worker_threads = 8)]
   #[ignore = "instrument: issue 643 concurrent merges (local scratch)"]
   async fn instrument_concurrent_merges() {
       let base = std::env::var("MERGE_URI_BASE").expect("MERGE_URI_BASE");
       let tag = std::env::var("MERGE_TAG").unwrap_or_else(|_| "run".into());
       for n in [1usize, 2, 4, 8] {
           let db = graph_with_pairs(&format!("{base}/{tag}-n{n}"), n).await;
           let start = Instant::now();
           let handles: Vec<_> = (0..n)
               .map(|i| {
                   let db = Arc::clone(&db);
                   tokio::spawn(async move {
                       let outcome = db.branch_merge(&format!("s{i}"), &format!("t{i}")).await;
                       (outcome, start.elapsed().as_secs_f64())
                   })
               })
               .collect();
           let mut done = Vec::new();
           for handle in handles {
               let (outcome, secs) = handle.await.unwrap();
               assert_eq!(outcome.unwrap(), MergeOutcome::Merged);
               done.push(secs);
           }
           done.sort_by(|a, b| a.partial_cmp(b).unwrap());
   
           let control = graph_with_pairs(&format!("{base}/{tag}-control{n}"), n).await;
           let control_start = Instant::now();
           assert_eq!(control.branch_merge("s0", "t0").await.unwrap(), MergeOutcome::Merged);
           let single = control_start.elapsed().as_secs_f64();
           let fmt: Vec<String> = done.iter().map(|s| format!("{s:.2}")).collect();
           eprintln!(
               "MERGES tag={tag} n={n} single_control_s={single:.2} completions_s=[{}] last/single={:.2}",
               fmt.join(", "),
               done.last().unwrap() / single
           );
       }
   }

   Run with MERGE_URI_BASE=s3://<bucket>/<prefix> RUSTFLAGS= cargo test --release -p omnigraph-engine --test zz_merge_instrument -- --ignored --nocapture and the AWS_* environment of the S3 suites.
4. ragnorc commented on Sep 30, 2026

   

   ragnorc

   on Sep 30, 2026

   ContributorAuthor

   More actions

   Follow-up on the residual tail (about 0.5 s per additional merge at +30 ms). Most likely it is merge_authority_cache:

   • On the local filesystem the same run takes 20–30 ms per merge (eight concurrent merges: last ÷ single = 2.27, in milliseconds). So the S3 tail is serialized storage round trips, not CPU: 0.48 s is about 16 round trips at 30 ms.
   • Every capture on a branch other than the handle's bound one goes through Omnigraph::validated_cached_coordinator (db/omnigraph.rs). That is a single-entry cache (merge_authority_cache: tokio::sync::Mutex<Option<(String, GraphCoordinator)>>) whose mutex is held across the latest-incarnation probe and, on a different key, across open_coordinator_for_branch. Concurrent merges on distinct branches therefore evict each other's entry and each reopen a coordinator while holding the mutex, one at a time. A merge captures twice (open_merge_write_txns resolves source and target), so it can also evict itself.
   • perf(writes): reuse captured authority for unchanged branches #813 measured a skipped __manifest open and scan as 16 storage calls (75 → 59 on the DST BranchWrite fixture). At 30 ms that is about 0.48 s, the observed tail.
   • The field's comment still justifies the mutex with "the schema serial queue already serializes merges and branch controls at capture time". Since engine: shared schema gate and the write critical section (RFC 2026-09-18) #783 that no longer holds: the schema gate is shared for merges, so this mutex has become their remaining serialization point.

   Not verified with a per-phase timer yet, so treat this as the leading explanation rather than a measurement.

   A fix is a trade-off the field's comment already names: the single entry exists so that retained lineage is not multiplied by live branches. Options:

   • a small per-branch LRU with a single-flight open per branch, so no mutex is held across I/O;
   • extending perf(writes): reuse captured authority for unchanged branches #813's captured-authority reuse to merge captures, so an unchanged branch skips the reopen.
5. ragnorc commented on Sep 30, 2026

   

   ragnorc

   on Sep 30, 2026

   ContributorAuthor

   More actions

   Confirmed by measurement: the tail is the authority-cache mutex. #825 releases it while a miss reopens the branch's coordinator, and keeps the single-entry cache, so there is no memory trade-off. With the same harness and setup (RustFS, +30 ms per round trip), the last completion over one merge alone:

   N	Before #783	main	#825
   2	1.99	1.23	1.13
   4	3.98	1.86	1.23
   8	7.88	2.89	1.27
6. ragnorc commented on Oct 1, 2026

   

   ragnorc

   on Oct 1, 2026

   ContributorAuthor

   More actions

   Status against the acceptance criteria, with the work in three draft PRs.

   Independent pairs overlap. #783 put merges on the schema gate's shared side; #825 removes the remaining tail (the authority-cache mutex held across a coordinator reopen). Measured with the instrument in #835 (RustFS, +30 ms per round trip, last completion over one merge alone):

   N	main	#825
   2	1.20	1.14
   4	1.76	1.22
   8	2.60	1.28
   16		1.40
   32		1.68

   Same-target, same-source and shared-table cases (#822): same-target merges serialize, and the second merges on top of the first; same-source merges both land and today serialize on the source's branch gate; two independent targets both write node:Person and still overlap, since table gates are keyed by (table, branch).

   Boundaries (#822, failpoint tests):

   • schema apply: a parked merge holds its shared permit, so an apply waits, then refuses on the non-main branch;
   • delete: deleting a merge's source or target waits for the merge, then succeeds;
   • recreate: another process deletes the target and creates a branch of the same name while the merge is parked after its table effects; the merge refuses with ReadSetChanged on the target's branch identifier, and the new branch keeps only its own rows;
   • failure/recovery: a merge failing before its manifest commit while an independent merge is parked leaves its target unmoved, the other merge publishes, and the same handle retries it;
   • cancellation: aborting a parked merge's task leaves the target untouched or merged whole, the same handle keeps working, and cleanup succeeds afterwards;
   • source advance is unreachable in one process (the merge holds the source's branch gate). A cross-process probe that recreated the source mid-merge saw the merge publish the source snapshot it captured.

   Measurement (#835): per-merge completion and service time, controls before and after, peak RSS, exact contents and publication receipts verified on every run. Queue wait inside the engine is not separated from work; that needs engine-side instrumentation.

   Open decisions:

   1. Admission limits. There is no cap today. With perf(merge): open a branch's coordinator outside the authority-cache lock #825, process peak RSS after the batch rises from a 70 MB pre-batch peak to 99, 113 and 128 MB at N = 8, 16 and 32, with 50-row merges; real payloads will cost more per merge.
   2. Whether same-source merges should overlap. A merge only reads its source, and the cross-process probe above suggests the source's branch gate is not what keeps it correct. Dropping that gate for merges would change the source arm of the delete-waits test.
7. pronskiy

   added a commit that references this issue on Oct 1, 2026

   rfc: shared schema gate and the write critical section (ModernRelay#754)

   ...

   24da4f5