[PATCH 0/2] connected: add incremental connectivity check

This series adds an incremental mode for the connectivity check, gated behind transfer.connectivityCheck=incremental (no expected changes unless you opt in).

The intent is to solve the problem of the connectivity check slowing down as the number of reachable objects from the boundary grows.

It relates to the RFC I sent out earlier:

[RFC] check_connected: toward incoming-proportional cost https://lore.kernel.org/git/CAL71e4Nf=-zCrfN7ghEVGq11irajJhtdxYZgKe0Ycux0qs1ZvQ@mail.gmail.com/

Design ======

The verifier runs inside the same rev-list subprocess that check_connected() already spawns, triggered by a new internal flag --verify-trees-incremental. After get_revision() collects the incoming commits, the verifier processes them in topological order (ancestors before descendants).

The idea is to keep a set of trusted objects, shared across the incoming commits, that grows over time. We visit the new/untrusted commit trees and do a comparison walk over the trees of their parents. Entries discovered on the trusted parent side are remembered as trusted, which lets later verification skip matching objects and avoid descending into unchanged subtrees.

More algorithmic details are in Documentation/technical/connectivity-check.adoc.

Benchmarks ==========

I'll just mention a short summary here, to avoid repeating what's already in the commit message. The incremental mode is faster than the full mode when there are few commits to verify and when the active object tree is large. In the happy case, the work tracks the changed paths and their comparison trees rather than the full reachable object closure, which substantially reduces the dependence on total repository size. I've seen speedups up to around 20x for the synthetic perf tests.

Running against a large real-world repo (3.4 GB boundary closure), the numbers are more dramatic. All timings use rev-list directly with --not HEADN, isolating the tree verification cost from the boundary-finding cost:

commits    full  incr.  speedup   full RSS  incr. RSS
      1    1.9s  0.01s    190x      3.4 GB     14 MB
     10    1.9s  0.04s     48x      3.4 GB    125 MB
    100    1.9s  0.37s      5x      3.4 GB    1.1 GB

The full mode takes ~1.9s regardless of commit count because it is dominated by walking the boundary closure. Incremental scales with the number of incoming commits and the paths they touch. Memory follows the same pattern: incremental uses a fraction of the full mode's RSS for small pushes, converging only when many commits are verified.

There are also regression cases in the synthetic fixtures. With long incoming histories, the extra parent-tree scans accumulate; in the synthetic fixture incremental is about 1.5x slower at 10000 commits. Per-commit changes have less impact than expected: even when every directory is touched, incremental remains competitive; bypassing the object cache for tree reads likely helps here.

I cannot establish how common these regression cases are. In the cases I have tested, however, the regression has remained modest; I have not been able to provoke a substantially larger slowdown. My feeling is that this is an acceptable tradeoff behind the opt-in config, since the target case (small pushes to large repos) sees the largest speedup, while the regression appears with long incoming histories.

A safety net for this regression could be to dynamically disable the incremental mode if the number of incoming commits is too large, but this is left out of the initial version to avoid overly speculative code.

Deepening fetches currently fall back to the full check because the full check omits --not --all for deepening -- there is no existing-reference boundary at which the walk can stop. An incremental approach is possible here too -- using the old shallow roots as the trusted boundary and walking the deepened ancestry forward -- but that is a separate change and left for future work. Deepening is also less common than regular fetch and receive-pack, where the speedup matters most.

Test coverage =============

Most correctness cases in t5412-connectivity-check.sh are run in both full and incremental modes to check semantic equivalence. Selected cases additionally assert trace2 tree/blob counts for the incremental mode, to verify that unchanged portions of the object graph are actually skipped. It covers:

 * Corruption detection: missing blobs, missing trees, type mismatches,
   malformed trees (unparseable, mid-tree corruption)
 * Tree optimization: trace2 assertions confirm unchanged subtrees are
   skipped, subtree moves, merge parent boundaries
 * Root commits (no parents -- verifies full tree closure)
 * Partial clones: missing promised blobs, missing promised trees,
   verification of local commits
 * Replacement objects (with and without GIT_NO_REPLACE_OBJECTS)
 * Shallow boundaries
 * Deepening fetches (falls back to full check)
 * Integration: real push, fetch, and clone

Most tests call git rev-list directly with the appropriate flags; integration tests exercise the full check_connected() path through push, fetch, and clone.

Alternatives considered =======================

My first prototype ran the verifier in-process inside connected.c. This required a second rev-list subprocess just for boundary finding, _nofetch variants of several object-reading functions to prevent lazy fetches in partial clones, explicit shallow-file plumbing, and careful avoidance of die() in all code paths reachable from the verifier. The result worked but was fragile and touched many files.

Moving the verifier into the rev-list subprocess eliminated all of those problems: in partial clones the existing --exclude-promisor-objects handling already disables lazy fetching, die() is isolated by the process boundary, shallow and replacement semantics are established before the verifier runs, and error routing comes for free via stderr.

So while I liked the idea of being less reliant on checking within a subprocess, making that work ended up being a lot more complex.

Next steps ==========

This series only addresses tree verification; the other significant cost is finding the commit boundary, especially for repos with many refs. I already have some prototypes for optimizing that too, and if this ends up landing, that would be something I would start polishing up.

Thanks, Kristofer

Kristofer Karlsson (2):
  Documentation: describe connectivity checking
  connected: add incremental connectivity check via rev-list

 Documentation/config/transfer.adoc            |  20 +
 Documentation/rev-list-options.adoc           |   6 +
 .../technical/connectivity-check.adoc         | 243 +++++++
 Makefile                                      |   1 +
 builtin/rev-list.c                            |  18 +
 connected.c                                   |  24 +
 meson.build                                   |   1 +
 t/meson.build                                 |   1 +
 ...enerate-repo-p5412-connectivity-check.perl |  44 ++
 t/perf/p5412-connectivity-check.sh            |  92 +++
 t/t5412-connectivity-check.sh                 | 655 ++++++++++++++++++
 tree-verify.c                                 | 306 ++++++++
 tree-verify.h                                 |  15 +
 13 files changed, 1426 insertions(+)
 create mode 100644 Documentation/technical/connectivity-check.adoc
 create mode 100644 t/perf/generate-repo-p5412-connectivity-check.perl
 create mode 100755 t/perf/p5412-connectivity-check.sh
 create mode 100755 t/t5412-connectivity-check.sh
 create mode 100644 tree-verify.c
 create mode 100644 tree-verify.h

base-commit: 47ce80527c56f462cb97db4ca8125342204d3783
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2211%2Fspkrka%2Ftree-diff-connectivity-v1-clean-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2211/spkrka/tree-diff-connectivity-v1-clean-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2211