freshlybakedca.ke
Git fork
1Multi-Pack-Index (MIDX) Design Notes
2====================================
3
4The Git object directory contains a 'pack' directory containing
5packfiles (with suffix ".pack") and pack-indexes (with suffix
6".idx"). The pack-indexes provide a way to lookup objects and
7navigate to their offset within the pack, but these must come
8in pairs with the packfiles. This pairing depends on the file
9names, as the pack-index differs only in suffix with its pack-
10file. While the pack-indexes provide fast lookup per packfile,
11this performance degrades as the number of packfiles increases,
12because abbreviations need to inspect every packfile and we are
13more likely to have a miss on our most-recently-used packfile.
14For some large repositories, repacking into a single packfile
15is not feasible due to storage space or excessive repack times.
16
17The multi-pack-index (MIDX for short) stores a list of objects
18and their offsets into multiple packfiles. It contains:
19
20* A list of packfile names.
21* A sorted list of object IDs.
22* A list of metadata for the ith object ID including:
23** A value j referring to the jth packfile.
24** An offset within the jth packfile for the object.
25* If large offsets are required, we use another list of large
26 offsets similar to version 2 pack-indexes.
27- An optional list of objects in pseudo-pack order (used with MIDX bitmaps).
28
29Thus, we can provide O(log N) lookup time for any number
30of packfiles.
31
32Design Details
33--------------
34
35- The MIDX is stored in a file named 'multi-pack-index' in the
36 .git/objects/pack directory. This could be stored in the pack
37 directory of an alternate. It refers only to packfiles in that
38 same directory.
39
40- The core.multiPackIndex config setting must be on (which is the
41 default) to consume MIDX files. Setting it to `false` prevents
42 Git from reading a MIDX file, even if one exists.
43
44- The file format includes parameters for the object ID hash
45 function, so a future change of hash algorithm does not require
46 a change in format.
47
48- The MIDX keeps only one record per object ID. If an object appears
49 in multiple packfiles, then the MIDX selects the copy in the
50 preferred packfile, otherwise selecting from the most-recently
51 modified packfile.
52
53- If there exist packfiles in the pack directory not registered in
54 the MIDX, then those packfiles are loaded into the `packed_git`
55 list and `packed_git_mru` cache.
56
57- The pack-indexes (.idx files) remain in the pack directory so we
58 can delete the MIDX file, set core.midx to false, or downgrade
59 without any loss of information.
60
61- The MIDX file format uses a chunk-based approach (similar to the
62 commit-graph file) that allows optional data to be added.
63
64Incremental multi-pack indexes
65------------------------------
66
67As repositories grow in size, it becomes more expensive to write a
68multi-pack index (MIDX) that includes all packfiles. To accommodate
69this, the "incremental multi-pack indexes" feature allows for combining
70a "chain" of multi-pack indexes.
71
72Each individual component of the chain need only contain a small number
73of packfiles. Appending to the chain does not invalidate earlier parts
74of the chain, so repositories can control how much time is spent
75updating the MIDX chain by determining the number of packs in each layer
76of the MIDX chain.
77
78=== Design state
79
80At present, the incremental multi-pack indexes feature is missing two
81important components:
82
83 - The ability to rewrite earlier portions of the MIDX chain (i.e., to
84 "compact" some collection of adjacent MIDX layers into a single
85 MIDX). At present the only supported way of shrinking a MIDX chain
86 is to rewrite the entire chain from scratch without the `--split`
87 flag.
88+
89There are no fundamental limitations that stand in the way of being able
90to implement this feature. It is omitted from the initial implementation
91in order to reduce the complexity, but will be added later.
92
93 - Support for reachability bitmaps. The classic single MIDX
94 implementation does support reachability bitmaps (see the section
95 titled "multi-pack-index reverse indexes" in
96 linkgit:gitformat-pack[5] for more details).
97+
98As above, there are no fundamental limitations that stand in the way of
99extending the incremental MIDX format to support reachability bitmaps.
100The design below specifically takes this into account, and support for
101reachability bitmaps will be added in a future patch series. It is
102omitted from the current implementation for the same reason as above.
103+
104In brief, to support reachability bitmaps with the incremental MIDX
105feature, the concept of the pseudo-pack order is extended across each
106layer of the incremental MIDX chain to form a concatenated pseudo-pack
107order. This concatenation takes place in the same order as the chain
108itself (in other words, the concatenated pseudo-pack order for a chain
109`{$H1, $H2, $H3}` would be the pseudo-pack order for `$H1`, followed by
110the pseudo-pack order for `$H2`, followed by the pseudo-pack order for
111`$H3`).
112+
113The layout will then be extended so that each layer of the incremental
114MIDX chain can write a `*.bitmap`. The objects in each layer's bitmap
115are offset by the number of objects in the previous layers of the chain.
116
117=== File layout
118
119Instead of storing a single `multi-pack-index` file (with an optional
120`.rev` and `.bitmap` extension) in `$GIT_DIR/objects/pack`, incremental
121MIDXs are stored in the following layout:
122
123----
124$GIT_DIR/objects/pack/multi-pack-index.d/
125$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-chain
126$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H1.midx
127$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H2.midx
128$GIT_DIR/objects/pack/multi-pack-index.d/multi-pack-index-$H3.midx
129----
130
131The `multi-pack-index-chain` file contains a list of the incremental
132MIDX files in the chain, in order. The above example shows a chain whose
133`multi-pack-index-chain` file would contain the following lines:
134
135----
136$H1
137$H2
138$H3
139----
140
141The `multi-pack-index-$H1.midx` file contains the first layer of the
142multi-pack-index chain. The `multi-pack-index-$H2.midx` file contains
143the second layer of the chain, and so on.
144
145When both an incremental- and non-incremental MIDX are present, the
146non-incremental MIDX is always read first.
147
148=== Object positions for incremental MIDXs
149
150In the original multi-pack-index design, we refer to objects via their
151lexicographic position (by object IDs) within the repository's singular
152multi-pack-index. In the incremental multi-pack-index design, we refer
153to objects via their index into a concatenated lexicographic ordering
154among each component in the MIDX chain.
155
156If `objects_nr()` is a function that returns the number of objects in a
157given MIDX layer, then the index of an object at lexicographic position
158`i` within, say, $H3 is defined as:
159
160----
161objects_nr($H2) + objects_nr($H1) + i
162----
163
164(in the C implementation, this is often computed as `i +
165m->num_objects_in_base`).
166
167=== Pseudo-pack order for incremental MIDXs
168
169The original implementation of multi-pack reachability bitmaps defined
170the pseudo-pack order in linkgit:gitformat-pack[5] (see the section
171titled "multi-pack-index reverse indexes") roughly as follows:
172
173____
174In short, a MIDX's pseudo-pack is the de-duplicated concatenation of
175objects in packs stored by the MIDX, laid out in pack order, and the
176packs arranged in MIDX order (with the preferred pack coming first).
177____
178
179In the incremental MIDX design, we extend this definition to include
180objects from multiple layers of the MIDX chain. The pseudo-pack order
181for incremental MIDXs is determined by concatenating the pseudo-pack
182ordering for each layer of the MIDX chain in order. Formally two objects
183`o1` and `o2` are compared as follows:
184
1851. If `o1` appears in an earlier layer of the MIDX chain than `o2`, then
186 `o1` sorts ahead of `o2`.
187
1882. Otherwise, if `o1` and `o2` appear in the same MIDX layer, and that
189 MIDX layer has no base, then if one of `pack(o1)` and `pack(o2)` is
190 preferred and the other is not, then the preferred one sorts ahead of
191 the non-preferred one. If there is a base layer (i.e. the MIDX layer
192 is not the first layer in the chain), then if `pack(o1)` appears
193 earlier in that MIDX layer's pack order, then `o1` sorts ahead of
194 `o2`. Likewise if `pack(o2)` appears earlier, then the opposite is
195 true.
196
1973. Otherwise, `o1` and `o2` appear in the same pack, and thus in the
198 same MIDX layer. Sort `o1` and `o2` by their offset within their
199 containing packfile.
200
201Note that the preferred pack is a property of the MIDX chain, not the
202individual layers themselves. Fundamentally we could introduce a
203per-layer preferred pack, but this is less relevant now that we can
204perform multi-pack reuse across the set of packs in a MIDX.
205
206=== Reachability bitmaps and incremental MIDXs
207
208Each layer of an incremental MIDX chain may have its objects (and the
209objects from any previous layer in the same MIDX chain) represented in
210its own `*.bitmap` file.
211
212The structure of a `*.bitmap` file belonging to an incremental MIDX
213chain is identical to that of a non-incremental MIDX bitmap, or a
214classic single-pack bitmap. Since objects are added to the end of the
215incremental MIDX's pseudo-pack order (see above), it is possible to
216extend a bitmap when appending to the end of a MIDX chain.
217
218(Note: it is possible likewise to compress a contiguous sequence of MIDX
219incremental layers, and their `*.bitmap` files into a single layer and
220`*.bitmap`, but this is not yet implemented.)
221
222The object positions used are global within the pseudo-pack order, so
223subsequent layers will have, for example, `m->num_objects_in_base`
224number of `0` bits in each of their four type bitmaps. This follows from
225the fact that we only write type bitmap entries for objects present in
226the layer immediately corresponding to the bitmap).
227
228Note also that only the bitmap pertaining to the most recent layer in an
229incremental MIDX chain is used to store reachability information about
230the interesting and uninteresting objects in a reachability query.
231Earlier bitmap layers are only used to look up commit and pseudo-merge
232bitmaps from that layer, as well as the type-level bitmaps for objects
233in that layer.
234
235To simplify the implementation, type-level bitmaps are iterated
236simultaneously, and their results are OR'd together to avoid recursively
237calling internal bitmap functions.
238
239Future Work
240-----------
241
242- If the multi-pack-index is extended to store a "stable object order"
243 (a function Order(hash) = integer that is constant for a given hash,
244 even as the multi-pack-index is updated) then MIDX bitmaps could be
245 updated independently of the MIDX.
246
247- Packfiles can be marked as "special" using empty files that share
248 the initial name but replace ".pack" with ".keep" or ".promisor".
249 We can add an optional chunk of data to the multi-pack-index that
250 records flags of information about the packfiles. This allows new
251 states, such as 'repacked' or 'redeltified', that can help with
252 pack maintenance in a multi-pack environment. It may also be
253 helpful to organize packfiles by object type (commit, tree, blob,
254 etc.) and use this metadata to help that maintenance.
255
256Related Links
257-------------
258[0] https://bugs.chromium.org/p/git/issues/detail?id=6
259 Chromium work item for: Multi-Pack Index (MIDX)
260
261[1] https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/
262 An earlier RFC for the multi-pack-index feature
263
264[2] https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/
265 Git Merge 2018 Contributor's summit notes (includes discussion of MIDX)