Re: [PATCH v2 01/19] Documentation: describe incremental MIDX format

From: Jeff King <peff@peff.net>
Date: Aug 1, 2024, 09:19 UTC
Message-ID: <20240801091952.GA1159276@coredump.intra.peff.net>
In-Reply-To: <014588b3ecf2e32a6ab1af8e77234dfb2f9ea75a.1721250704.git.me@ttaylorr.com>

On Wed, Jul 17, 2024 at 05:11:58PM -0400, Taylor Blau wrote:

Show 31 quoted lines

> +Each individual component of the chain need only contain a small number
> +of packfiles. Appending to the chain does not invalidate earlier parts
> +of the chain, so repositories can control how much time is spent
> +updating the MIDX chain by determining the number of packs in each layer
> +of the MIDX chain.
> +
> +=== Design state
> +
> +At present, the incremental multi-pack indexes feature is missing two
> +important components:
> +
> +  - The ability to rewrite earlier portions of the MIDX chain (i.e., to
> +    "compact" some collection of adjacent MIDX layers into a single
> +    MIDX). At present the only supported way of shrinking a MIDX chain
> +    is to rewrite the entire chain from scratch without the `--split`
> +    flag.
> ++
> +There are no fundamental limitations that stand in the way of being able
> +to implement this feature. It is omitted from the initial implementation
> +in order to reduce the complexity, but will be added later.
> +
> +  - Support for reachability bitmaps. The classic single MIDX
> +    implementation does support reachability bitmaps (see the section
> +    titled "multi-pack-index reverse indexes" in
> +    linkgit:gitformat-pack[5] for more details).
> ++
> +As above, there are no fundamental limitations that stand in the way of
> +extending the incremental MIDX format to support reachability bitmaps.
> +The design below specifically takes this into account, and support for
> +reachability bitmaps will be added in a future patch series. It is
> +omitted from this series for the same reason as above.

It is nice that you added a bit of a roadmap here about what is implemented and what is not, and that the design takes into account future directions (especially incremental bitmap generation).

It does feel a little funny to say "this series" in text that will go into the repository (i.e., somebody reading the checked out file will say "huh? which series?"). I'm not sure how to word it better, except to maybe just say "in the future" and "it is omitted for now" (and obviously it's a pretty minor point).

Show 8 quoted lines

> +In brief, to support reachability bitmaps with the incremental MIDX
> +feature, the concept of the pseudo-pack order is extended across each
> +layer of the incremental MIDX chain to form a concatenated pseudo-pack
> +order. This concatenation takes place in the same order as the chain
> +itself (in other words, the concatenated pseudo-pack order for a chain
> +`{$H1, $H2, $H3}` would be the pseudo-pack order for `$H1`, followed by
> +the pseudo-pack order for `$H2`, followed by the pseudo-pack order for
> +`$H3`).

OK, that makes sense. It's how I'd have intuitively assumed it to be, and most importantly, it should allow appending to the chain without regenerating (or even translating) earlier bitmaps.

Show 27 quoted lines

> +=== File layout
> +
> +Instead of storing a single `multi-pack-index` file (with an optional
> +`.rev` and `.bitmap` extension) in `$GIT_DIR/objects/pack`, incremental
> +MIDXs are stored in the following layout:
> +
> +----
> +$GIT_DIR/objects/pack/multi-pack-index.d/
> +$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-chain
> +$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H1.midx
> +$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H2.midx
> +$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H3.midx
> +----
> +
> +The `multi-pack-index-chain` file contains a list of the incremental
> +MIDX files in the chain, in order. The above example shows a chain whose
> +`multi-pack-index-chain` file would contain the following lines:
> +
> +----
> +$H1
> +$H2
> +$H3
> +----
> +
> +The `multi-pack-index-$H1.midx` file contains the first layer of the
> +multi-pack-index chain. The `multi-pack-index-$H2.midx` file contains
> +the second layer of the chain, and so on.

Makes sense. How does the chained multi-pack-index.d interact with a singular multi-pack-index? Generally we should not have both at the same time, but I'd imagine they both exist for a brief period when moving from one to another.

I assume the rules are the same as for commit-graphs, which use the same on-disk structure. I can't think of a reason to prefer one over the other but this might be a good place to document what does/should happen.

Show 7 quoted lines

> +=== Object positions for incremental MIDXs
> +
> +In the original multi-pack-index design, we refer to objects via their
> +lexicographic position (by object IDs) within the repository's singular
> +multi-pack-index. In the incremental multi-pack-index design, we refer
> +to objects via their index into a concatenated lexicographic ordering
> +among each component in the MIDX chain.

How do duplicate objects work here? I guess there aren't any duplicates in the midx itself, only in the constituent packfiles. So from the perspective of this section, I guess it doesn't matter? And from the perspective of bitmaps (where the duplicate issue came up before), it is business as usual: the midx revindex gives the bit order, and we'd presumably concatenate the individual revindexes in chain order.

(Mostly just thinking out loud; I'm not sure there's much for you to answer there).

Looking good so far...

-Peff