[RFC] check_connected: toward incoming-proportional cost

Hi!

The connectivity check (check_connected()) used by both fetch
and receive-pack (and a few other call sites) can be expensive
for repositories with many refs or large active trees, and I
think that is worth optimizing.  I have a couple of ideas for
how to approach that, but before I start sending patches I
want to discuss the high-level need and align on the direction.

This follows up on Patrick Steinhardt's 2021 series [1], which
explored a faster connectivity check.  I found that thread
after independently trying a similar approach (and the thread
was helpful for making me pivot away from it).

My key takeaway from that discussion was that making the
check faster would be useful, but we need to preserve the
connectivity invariant, and I think I found a way to
achieve that.

A few definitions I will use throughout:

  Trusted object (in the context of connectivity check):
    an object whose complete transitive closure is known to
    be present for the purposes of the connectivity check.
    For an object with traversed references, this requires
    those referenced objects to be trusted.  Objects
    reachable from current tips are implicitly trusted by
    the existing connectivity invariant.

  Boundary commit: a trusted commit at the edge between
    already-trusted and newly introduced history.  More
    precisely, a trusted commit reached while walking
    parents from an incoming tip, where the adjacent
    commit toward the incoming tip is not itself reachable
    from any current tip.


Problem statement
-----------------

The current implementation delegates to a rev-list
subprocess:

    rev-list --objects --stdin --not --all --quiet

feeding the incoming tips on stdin.  This reuses the existing
traversal machinery, which is nice, but it performs work that
depends on the existing repository size rather than the size
of the incoming set.

The rev-list operation can be modeled as two steps.

  1. Find the set of boundary commits, using graph traversal
     seeded by all current tips and all the incoming tips.

     The cost here comes both from the number of current tips
     and the overall graph distance from the seeds to the
     boundary.  As Patrick noted in the previous thread, this
     becomes very slow with 880k refs.

  2. Verify the objects reachable through the trees of the
     incoming commits.  This is implemented by first walking
     the complete tree closure of the boundary commits,
     marking all visited objects as trusted (UNINTERESTING
     in the rev-list semantics).  This ensures that walking
     the tree closure of the incoming commits can be pruned
     efficiently and thus becomes cheaper.

     The cost here is the initial marking, which effectively
     visits all active objects.

Since the cost is approximately proportional to both the
number of local tips and the size of the active object tree,
it can slow down local fetch operations and server-side
receive-pack -- and I have observed this being one of the
bottlenecks for servers with very frequent pushes.

The recent --skip-connectivity-check addition [2] lets server
operators bypass the check entirely when they have external
validation, which suggests the cost is a meaningful pain point
for some server operators.

Ideally the connectivity check should be proportional to only
the incoming set.  I am not sure if we can fully reach that
for all scenarios, but it is possible for simple cases such
as:

  * pushing new commits on top of an existing branch
  * force-pushing new commits that have been rebased on a
    more recent origin/master.

If we manage to optimize the check for most scenarios, we can
reduce the overall load on git servers even if edge cases will
still exist.

The two steps (finding the boundary, and verifying commit
trees) have independent scaling problems and I believe they
can be optimized mostly independently.

I start with step 2 because it seems like the simplest one to
reason about, and I also need it to simplify the solution for
the other problem (step 1).


Proposal for opportunistic trusted-tree discovery (for step 2)
--------------------------------------------------------------

The current implementation eagerly walks the tree closure of
the boundary commits and marks the visited objects as trusted
before verifying the incoming commits.  Instead, I propose
maintaining a cache of trusted objects while verifying the
incoming commits.  A cached object does not need to be
verified again; for a tree, this also lets us prune its
entire closure.

The cache is populated in two ways with different goals:

First, every object verified during the walk is cached, so
we never need to verify the same object twice.

Second, we can introduce a heuristic for opportunistically
populating the cache based on doing a parallel tree walk
against trusted parent commits.

Ignoring details like missing entries and type-changing paths,
the core idea is roughly:

    global trusted_objects = {}
    def visit_tree(candidate_tree, parent_trees):
      for parent_tree in parent_trees:
        for (_, obj) in entries(parent_tree):
          trusted_objects += obj
      for (name, obj) in candidate_tree:
        if obj in trusted_objects: continue
        if obj is a tree:
          parent_subtrees = parent_trees.map(_.get(name))
          visit_tree(obj, parent_subtrees)
        // verify obj itself
        trusted_objects += obj

This heuristic prunes verification to roughly the changed
entries, as long as there are no cross-directory moves.  If
there are moves, such subtrees would be verified instead of
skipped -- we may lose some pruning opportunities, but that
affects performance rather than correctness.

This heuristic relies on parent-before-child processing
order: all parents must already be known to be trusted before
processing the child, otherwise entries from the parent side
cannot safely be added to the cache.


Proposal for finding the boundary (step 1)
------------------------------------------

This part is harder, but I think there are approaches that can
speed up the common case.

The simplest option: seed the traversal with a small set of
likely-useful refs (the old values of the refs being updated,
possibly together with a few other likely tips) and a bounded
walk budget.  If every ancestry path from each incoming tip
reaches a trusted commit within the budget, the boundary is
closed and we are done.  Otherwise fall back to --not --all
as today.  This should cover many common push workflows and
is straightforward to reason about.

If this finds a solution, it is not necessarily minimal.
Walking from other refs could tighten the boundary, but this
is still valid for correctness.  A non-minimal boundary means
more candidate commits to verify, but with opportunistic
discovery (Proposal 1) that extra work is typically cheap --
those commits share most of their trees with their parents.

A more ambitious follow-up could interleave lazy iteration of
the refs with the graph walk, rather than enumerating all refs
up front.  Each newly loaded ref adds its tip to a shared
priority queue, and the walk budget is charged globally
regardless of which ref's ancestry is being explored.  Refs
would ideally be loaded in an order likely to close the
boundary quickly, with a fallback to full ref enumeration if
the budget runs out.

One possible ordering mechanism would be a user-configured
priority list of ref prefixes, though I have not explored that
enough to argue for it yet.  The point is mostly that I think
this is solvable, but I do not know exactly what the best
solution would look like.

For the prototype I used the simple option, but I am less
sure that hard-coding that heuristic is the right upstream
interface, and I would be happy to either flesh out the
follow-up idea or hopefully arrive at an even better approach
through the discussion here.


Preliminary results
-------------------

It's too early for proper benchmarks, but I think it's useful
to get a sense of what is possible.  My local prototype for
both proposals speeds up the connectivity check for a large
repository (3M commits, 200K refs, ~600K tree and blob
objects reachable from the boundary).  Numbers are
intentionally rounded to one significant digit since this is
not scientific, purely intended as guidance for knowing if
it's worth exploring further.

  5-commit push, 45 changed files:

  Current (rev-list --not --all):               1     s
  Opportunistic discovery + bounded traversal:  0.03  s

  1-commit push, trivial change:

  Current (rev-list --not --all):               1     s
  Opportunistic discovery + bounded traversal:  0.007 s


On this workload, the opportunistic discovery is much less
impactful than the boundary walk, but it is included here
because I never attempted to combine the existing rev-list
--objects mechanism with the new boundary search.

The bounded traversal (seeded with the old branch value)
avoids loading the full ref set, and opportunistic discovery
reduces the object verification: around 100 objects walked
instead of the full 600 000 tree and blob objects.


Other approaches considered
---------------------------

I also explored using commit-graph membership as evidence of
past trust: if a commit is in the commit-graph and in the odb,
treat it as trusted and stop the walk there.  I initially
hoped that GC's treatment of reachable closures might make
this safe as well.  However, it turns out to still
be hard to reason about what it means for an object to exist
in the odb -- it may still exist in a pack that is retained
because other objects inside are reachable.

I gave up on that approach for now, but I am honestly not
certain if it's fully a dead end or not.

Feedback requested
------------------

I am primarily interested in feedback on whether this problem
is worth solving and if the proposed solution is going in the
right direction, but any useful insights or gotchas that break
the idea are of course appreciated.

I tried to keep this as high-level as possible and avoided
discussing some of the edge cases -- some of my earlier
email drafts were much too long and it was a struggle to
condense it. That said, I included an appendix to present
how my prototype handles those cases if anyone is curious.

Thanks,
Kristofer


Appendix: special cases
-----------------------

Non-commit tips: tags are peeled iteratively until reaching
a non-tag object.  Blob tips are verified for existence by
the peel step itself.  Tree tips get full closure verification
(no parent diff, since there is no parent commit to diff
against).  This is correct but not optimized -- and tree tips
are uncommon in practice (I think).

Shallow clones: when a temporary shallow file is in effect,
the listed commits are treated as roots with no parents.
Their trees get full closure verification rather than a
parent diff.  The parent-diff heuristic only applies above
the shallow boundary, which is where incoming commits are in
practice.

Deepening fetches: the entire deepened ancestry becomes
candidates, so there is no small incoming set to optimize
for.  The implementation falls back to the current rev-list
path to avoid the memory overhead of tracking millions of
candidate commits in-process.  This could be optimized later
if needed.

Promisor remotes: the existing fast path that checks whether
all wanted tips are present in promisor packs runs first,
unchanged.  If that fast path does not cover all tips, the
optimized verification path accepts any missing object
(tree, blob, or tag target) that is a promisor object,
matching the --exclude-promisor-objects semantics.

Replace objects: the optimized path assumes the physical
commit graph is acyclic.  Replace objects can violate that, so
the implementation falls back to the current rev-list path
when any replace objects are configured.


[1] https://lore.kernel.org/git/cover.1621451532.git.ps@pks.im/ (local)
    (Speed up connectivity checks via quarantine dir,
    Patrick Steinhardt, 2021)
[2] https://lore.kernel.org/git/20250507030249.4802-1-jltobler@gmail.com/ (local)
    (builtin/receive-pack: introduce option to skip connectivity checks,
    Justin Tobler, 2025)