95e8383bac
The previous patch demonstrates a bug where a MIDX's auxiliary object
order can become out of sync with a MIDX bitmap.
This is because of two confounding factors:
- First, the object order is stored in a file which is named according
to the multi-pack index's checksum, and the MIDX does not store the
object order. This means that the object order can change without
altering the checksum.
- But the .rev file is moved into place with finalize_object_file(),
which link(2)'s the file into place instead of renaming it. For us,
that means that a modified .rev file will not be moved into place if
MIDX's checksum was unchanged.
This fix is to force the MIDX's checksum to change when the preferred
pack changes but the set of packs contained in the MIDX does not. In
other words, when the object order changes, the MIDX's checksum needs to
change with it (regardless of whether the MIDX is tracking the same or
different packs).
This prevents a race whereby changing the object order (but not the
packs themselves) enables a reader to see the new .rev file with the old
MIDX, or similarly seeing the new bitmap with the old object order.
But why can't we just stop hardlinking the .rev into place instead
adding additional data to the MIDX? Suppose that's what we did. Then
when we go to generate the new bitmap, we'll load the old MIDX bitmap,
along with the MIDX that it references. That's fine, since the new MIDX
isn't moved into place until after the new bitmap is generated. But the
new object order *has* been moved into place. So we'll read the old
bitmaps in the new order when generating the new bitmap file, meaning
that without this secondary change, bitmap generation itself would
become a victim of the race described here.
This can all be prevented by forcing the MIDX's checksum to change when
the object order does. By embedding the entire object order into the
MIDX, we do just that. That is, the MIDX's checksum will change in
response to any perturbation of the underlying object order. In t5326,
this will cause the MIDX's checksum to update (even without changing the
set of packs in the MIDX), preventing the stale read problem.
Note that this makes it safe to continue to link(2) the MIDX .rev file
into place, since it is now impossible to have a .rev file that is
out-of-sync with the MIDX whose checksum it references. (But we will do
away with MIDX .rev files later in this series anyway, so this is
somewhat of a moot point).
In theory, it is possible to store a "fingerprint" of the full object
order here, so long as that fingerprint changes at least as often as the
full object order does. Some possibilities here include storing the
identity of the preferred pack, along with the mtimes of the
non-preferred packs in a consistent order. But storing a limited part of
the information makes it difficult to reason about whether or not there
are gaps between the two that would cause us to get bitten by this bug
again.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Reviewed-by: Derrick Stolee <dstolee@microsoft.com>
Reviewed-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
101 lines
4.4 KiB
Plaintext
101 lines
4.4 KiB
Plaintext
Multi-Pack-Index (MIDX) Design Notes
|
|
====================================
|
|
|
|
The Git object directory contains a 'pack' directory containing
|
|
packfiles (with suffix ".pack") and pack-indexes (with suffix
|
|
".idx"). The pack-indexes provide a way to lookup objects and
|
|
navigate to their offset within the pack, but these must come
|
|
in pairs with the packfiles. This pairing depends on the file
|
|
names, as the pack-index differs only in suffix with its pack-
|
|
file. While the pack-indexes provide fast lookup per packfile,
|
|
this performance degrades as the number of packfiles increases,
|
|
because abbreviations need to inspect every packfile and we are
|
|
more likely to have a miss on our most-recently-used packfile.
|
|
For some large repositories, repacking into a single packfile
|
|
is not feasible due to storage space or excessive repack times.
|
|
|
|
The multi-pack-index (MIDX for short) stores a list of objects
|
|
and their offsets into multiple packfiles. It contains:
|
|
|
|
* A list of packfile names.
|
|
* A sorted list of object IDs.
|
|
* A list of metadata for the ith object ID including:
|
|
** A value j referring to the jth packfile.
|
|
** An offset within the jth packfile for the object.
|
|
* If large offsets are required, we use another list of large
|
|
offsets similar to version 2 pack-indexes.
|
|
- An optional list of objects in pseudo-pack order (used with MIDX bitmaps).
|
|
|
|
Thus, we can provide O(log N) lookup time for any number
|
|
of packfiles.
|
|
|
|
Design Details
|
|
--------------
|
|
|
|
- The MIDX is stored in a file named 'multi-pack-index' in the
|
|
.git/objects/pack directory. This could be stored in the pack
|
|
directory of an alternate. It refers only to packfiles in that
|
|
same directory.
|
|
|
|
- The core.multiPackIndex config setting must be on (which is the
|
|
default) to consume MIDX files. Setting it to `false` prevents
|
|
Git from reading a MIDX file, even if one exists.
|
|
|
|
- The file format includes parameters for the object ID hash
|
|
function, so a future change of hash algorithm does not require
|
|
a change in format.
|
|
|
|
- The MIDX keeps only one record per object ID. If an object appears
|
|
in multiple packfiles, then the MIDX selects the copy in the
|
|
preferred packfile, otherwise selecting from the most-recently
|
|
modified packfile.
|
|
|
|
- If there exist packfiles in the pack directory not registered in
|
|
the MIDX, then those packfiles are loaded into the `packed_git`
|
|
list and `packed_git_mru` cache.
|
|
|
|
- The pack-indexes (.idx files) remain in the pack directory so we
|
|
can delete the MIDX file, set core.midx to false, or downgrade
|
|
without any loss of information.
|
|
|
|
- The MIDX file format uses a chunk-based approach (similar to the
|
|
commit-graph file) that allows optional data to be added.
|
|
|
|
Future Work
|
|
-----------
|
|
|
|
- The multi-pack-index allows many packfiles, especially in a context
|
|
where repacking is expensive (such as a very large repo), or
|
|
unexpected maintenance time is unacceptable (such as a high-demand
|
|
build machine). However, the multi-pack-index needs to be rewritten
|
|
in full every time. We can extend the format to be incremental, so
|
|
writes are fast. By storing a small "tip" multi-pack-index that
|
|
points to large "base" MIDX files, we can keep writes fast while
|
|
still reducing the number of binary searches required for object
|
|
lookups.
|
|
|
|
- If the multi-pack-index is extended to store a "stable object order"
|
|
(a function Order(hash) = integer that is constant for a given hash,
|
|
even as the multi-pack-index is updated) then MIDX bitmaps could be
|
|
updated independently of the MIDX.
|
|
|
|
- Packfiles can be marked as "special" using empty files that share
|
|
the initial name but replace ".pack" with ".keep" or ".promisor".
|
|
We can add an optional chunk of data to the multi-pack-index that
|
|
records flags of information about the packfiles. This allows new
|
|
states, such as 'repacked' or 'redeltified', that can help with
|
|
pack maintenance in a multi-pack environment. It may also be
|
|
helpful to organize packfiles by object type (commit, tree, blob,
|
|
etc.) and use this metadata to help that maintenance.
|
|
|
|
Related Links
|
|
-------------
|
|
[0] https://bugs.chromium.org/p/git/issues/detail?id=6
|
|
Chromium work item for: Multi-Pack Index (MIDX)
|
|
|
|
[1] https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/
|
|
An earlier RFC for the multi-pack-index feature
|
|
|
|
[2] https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/
|
|
Git Merge 2018 Contributor's summit notes (includes discussion of MIDX)
|