Re: [PATCH v3 01/13] Documentation: describe incremental MIDX bitmaps

[Patrick Steinhardt <ps@pks.im>]

On Tue, Nov 19, 2024 at 05:07:19PM -0500, Taylor Blau wrote:
> diff --git a/Documentation/technical/multi-pack-index.txt b/Documentation/technical/multi-pack-index.txt
> index cc063b30bea..a063262c360 100644
> --- a/Documentation/technical/multi-pack-index.txt
> +++ b/Documentation/technical/multi-pack-index.txt
> @@ -164,6 +164,70 @@ objects_nr($H2) + objects_nr($H1) + i
>  (in the C implementation, this is often computed as `i +
>  m->num_objects_in_base`).
>  
> +=== Pseudo-pack order for incremental MIDXs
> +
> +The original implementation of multi-pack reachability bitmaps defined
> +the pseudo-pack order in linkgit:gitformat-pack[5] (see the section
> +titled "multi-pack-index reverse indexes") roughly as follows:
> +
> +____
> +In short, a MIDX's pseudo-pack is the de-duplicated concatenation of
> +objects in packs stored by the MIDX, laid out in pack order, and the
> +packs arranged in MIDX order (with the preferred pack coming first).
> +____
> +
> +In the incremental MIDX design, we extend this definition to include
> +objects from multiple layers of the MIDX chain. The pseudo-pack order
> +for incremental MIDXs is determined by concatenating the pseudo-pack
> +ordering for each layer of the MIDX chain in order. Formally two objects
> +`o1` and `o2` are compared as follows:
> +
> +1. If `o1` appears in an earlier layer of the MIDX chain than `o2`, then
> +  `o1` is considered less than `o2`.

Just as a refresher for myself: what is the consequence of an object
`o1` sorting earlier than `o2`? In the case where those refer to
different objects it is only used to establish the pseudo-pack order so
that we know how to interpret the bitmaps. But in the case where those
two objects refer to the same underlying object, e.g. because the object
is contained in two packs, it also impacts which of both objects would
be preferred e.g. during a clone, right?

> +2. Otherwise, if `o1` and `o2` appear in the same MIDX layer, and that
> +  MIDX layer has no base, then If one of `pack(o1)` and `pack(o2)` is

s/If/if

> +  preferred and the other is not, then the preferred one sorts first. If
> +  there is a base layer (i.e. the MIDX layer is not the first layer in
> +  the chain), then if `pack(o1)` appears earlier in that MIDX layer's
> +  pack order, than `o1` is less than `o2`. Likewise if `pack(o2)`
> +  appears earlier, than the opposite is true.

Another question for my own understanding: why is it relevant whether we
have a base or not? I would have expected that the case where the
objects appear in two different layers is already covered by (1), so
from thereon we only need to care about two objects existing in the same
layer.

> +3. Otherwise, `o1` and `o2` appear in the same pack, and thus in the
> +  same MIDX layer. Sort `o1` and `o2` by their offset within their
> +  containing packfile.
> +
> +=== Reachability bitmaps and incremental MIDXs
> +
> +Each layer of an incremental MIDX chain may have its objects (and the
> +objects from any previous layer in the same MIDX chain) represented in
> +its own `*.bitmap` file.
> +
> +The structure of a `*.bitmap` file belonging to an incremental MIDX
> +chain is identical to that of a non-incremental MIDX bitmap, or a
> +classic single-pack bitmap. Since objects are added to the end of the
> +incremental MIDX's pseudo-pack order (see: above), it is possible to
> +extend a bitmap when appending to the end of a MIDX chain.
> +
> +(Note: it is possible likewise to compress a contiguous sequence of MIDX
> +incremental layers, and their `*.bitmap`(s) into a single layer and
> +`*.bitmap`, but this is not yet implemented.)

Fair. What do we currently do in this context? Do we just keep on
appending layer after layer?

Patrick