204 lines
8.5 KiB
Plaintext
204 lines
8.5 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.
|
|
|
|
Incremental multi-pack indexes
|
|
------------------------------
|
|
|
|
As repositories grow in size, it becomes more expensive to write a
|
|
multi-pack index (MIDX) that includes all packfiles. To accommodate
|
|
this, the "incremental multi-pack indexes" feature allows for combining
|
|
a "chain" of multi-pack indexes.
|
|
|
|
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 the current implementation for the same reason as above.
|
|
+
|
|
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`).
|
|
+
|
|
The layout will then be extended so that each layer of the incremental
|
|
MIDX chain can write a `*.bitmap`. The objects in each layer's bitmap
|
|
are offset by the number of objects in the previous layers of the chain.
|
|
|
|
=== 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.
|
|
|
|
When both an incremental- and non-incremental MIDX are present, the
|
|
non-incremental MIDX is always read first.
|
|
|
|
=== 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.
|
|
|
|
If `objects_nr()` is a function that returns the number of objects in a
|
|
given MIDX layer, then the index of an object at lexicographic position
|
|
`i` within, say, $H3 is defined as:
|
|
|
|
----
|
|
objects_nr($H2) + objects_nr($H1) + i
|
|
----
|
|
|
|
(in the C implementation, this is often computed as `i +
|
|
m->num_objects_in_base`).
|
|
|
|
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)
|