On Fri, Mar 14, 2025 at 04:18:20PM -0400, Taylor Blau wrote:
> +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`.
> +
> +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
> + 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.
> +
> +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.
OK, I think this ordering makes sense. I had to read this description
over several times to make sure I wasn't missing something. The earlier
part that says "it's just concatenating the pack order of the layers" is
a much more intuitive way of looking at it (modulo that you might need
to remove duplicates found in earlier layers).
But I think an even more basic way of thinking about it is that it's the
same as the pseudo-pack order you would get if you had a single midx of
all of the packs in all of the layers (in their layer order). We already
have to deal with (and have documented) duplicates in that case.
Not really suggesting any wording change here, just making sure I
grokked it all.
> +Note that the preferred pack is a property of the MIDX chain, not the
> +individual layers themselves. Fundamentally we could introduce a
> +per-layer preferred pack, but this is less relevant now that we can
> +perform multi-pack reuse across the set of packs in a MIDX.
Calling this out explicitly is good, since it's an obvious question
for somebody to have.
> +=== 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.)
> +
> +The object positions used are global within the pseudo-pack order, so
> +subsequent layers will have, for example, `m->num_objects_in_base`
> +number of `0` bits in each of their four type bitmaps. This follows from
> +the fact that we only write type bitmap entries for objects present in
> +the layer immediately corresponding to the bitmap).
OK, so each layer's bitmap does depend on the layers above/before it.
That obviously needs to happen because each incremental midx is not
likely to be a complete reachability set anyway.
But I also wondered what would happen with a situation like this:
A -- B
\
-- C
stored like this:
base midx:
- pack 1:
- object A
- object B, which can reach A
incremental midx:
- pack 2:
- object A
- object C, which can reach A
That is, two objects B and C both depend on A, which is duplicated in
two midx layers. Even if the incremental midx is complete in the sense
that C only depends on A, its bitmap cannot just be "11". Because the
bit position for object A in the incremental midx does not exist in the
pseudo-pack order at all! It must refer to the copy of "A" in the base
midx, so it's correct bitmap is "101" (A and C, but not B).
Again, just talking through it here.
> +Note also that only the bitmap pertaining to the most recent layer in an
> +incremental MIDX chain is used to store reachability information about
> +the interesting and uninteresting objects in a reachability query.
> +Earlier bitmap layers are only used to look up commit and pseudo-merge
> +bitmaps from that layer, as well as the type-level bitmaps for objects
> +in that layer.
I'm not quite sure what this means, but I guess you're saying that
internally as we produce a bitmap, we'll always use the complete bitmap
over all of the layers?
> +To simplify the implementation, type-level bitmaps are iterated
> +simultaneously, and their results are OR'd together to avoid recursively
> +calling internal bitmap functions.
OK, I guess we'll see what this means in the patches. ;)
The general rules for the data structure make sense to me, though.
-Peff
