Re: [PATCH v2 1/2] Documentation: describe connectivity checking

From: Kristofer Karlsson <krka@spotify.com>
Date: Oct 6, 2026, 10:03 UTC
Message-ID: <CAL71e4PzQJz16BvP=zaVoS25R1ezai1R9UBZ2XDhNSYFYEpknA@mail.gmail.com>
In-Reply-To: <asSOJVUTS3BMq6kS@pks.im>

On Tue, 6 Oct 2026 at 07:59, Patrick Steinhardt <ps@pks.im> wrote:

Show 17 quoted lines

>
> On Mon, Oct 05, 2026 at 12:17:27PM -0700, Junio C Hamano wrote:
> >
> > This is totally outside the topic of documentation updates, but it
> > makes me wonder if we should pay attention to connectivity roots
> > other than refs (like index entries) that we use when we run fsck.
>
> Hmm, I'm not sure. I guess performance of the connectivity check is
> typically an issue on the server side only, much less so on the client
> side. And the server would of course typically not even have an index
> entry at all. Same for reflogs, at least in many setups.
>
> I also wonder whether that'd really speed things up if we add more data
> sources. At GitLab we typically have the problem that we have too many
> connectivity roots with refs alone, and that is making the whole check
> painfully slow in some repositories. So adding more connectivity roots
> to it would probably be counterproductive.

I have some followup work in this area (but I want to keep focus) and it's indeed true that number of refs used as seeds is also an important part of the problem.

I see connectivity and reachability as two separate things, though the current implementation has an invariant based on reachability implying (e.g. requiring) connectivity.

I think we could build up a stronger connectivity invariant for the common case, where we can cheaply check if an object is connectivity-closed regardless of its reachability state.

One idea is to utilize the fact that MIDX maps out a very specific set of packs, so we could compute which set of packs form a connectivity closure (and cheaply update that information as the MIDX changes).

Another idea would be to dynamically load refs as seeds in parallel with walking the graph. This creates a tradeoff between how many objects we need to check and how many refs we need to load (if we load fewer refs we just need to walk further to reach common ground).

Sorry, this is a bit hand-wave:y but my point is that I think regardless of how this is followed up to solve the bigger problems, I think optimizing the object-tree traversal is a useful first step.

Thanks, Kristofer