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 28Thus, we can provide O(log N) lookup time for any number 29of packfiles. 30 31Design Details 32-------------- 33 34- The MIDX is stored in a file named 'multi-pack-index' in the 35 .git/objects/pack directory. This could be stored in the pack 36 directory of an alternate. It refers only to packfiles in that 37 same directory. 38 39- The pack.multiIndex config setting must be on to consume MIDX files. 40 41- The file format includes parameters for the object ID hash 42 function, so a future change of hash algorithm does not require 43 a change in format. 44 45- The MIDX keeps only one record per object ID. If an object appears 46 in multiple packfiles, then the MIDX selects the copy in the most- 47 recently modified packfile. 48 49- If there exist packfiles in the pack directory not registered in 50 the MIDX, then those packfiles are loaded into the `packed_git` 51 list and `packed_git_mru` cache. 52 53- The pack-indexes (.idx files) remain in the pack directory so we 54 can delete the MIDX file, set core.midx to false, or downgrade 55 without any loss of information. 56 57- The MIDX file format uses a chunk-based approach (similar to the 58 commit-graph file) that allows optional data to be added. 59 60Future Work 61----------- 62 63- Add a 'verify' subcommand to the 'git midx' builtin to verify the 64 contents of the multi-pack-index file match the offsets listed in 65 the corresponding pack-indexes. 66 67- The multi-pack-index allows many packfiles, especially in a context 68 where repacking is expensive (such as a very large repo), or 69 unexpected maintenance time is unacceptable (such as a high-demand 70 build machine). However, the multi-pack-index needs to be rewritten 71 in full every time. We can extend the format to be incremental, so 72 writes are fast. By storing a small "tip" multi-pack-index that 73 points to large "base" MIDX files, we can keep writes fast while 74 still reducing the number of binary searches required for object 75 lookups. 76 77- The reachability bitmap is currently paired directly with a single 78 packfile, using the pack-order as the object order to hopefully 79 compress the bitmaps well using run-length encoding. This could be 80 extended to pair a reachability bitmap with a multi-pack-index. If 81 the multi-pack-index is extended to store a "stable object order" 82 (a function Order(hash) = integer that is constant for a given hash, 83 even as the multi-pack-index is updated) then a reachability bitmap 84 could point to a multi-pack-index and be updated independently. 85 86- Packfiles can be marked as "special" using empty files that share 87 the initial name but replace ".pack" with ".keep" or ".promisor". 88 We can add an optional chunk of data to the multi-pack-index that 89 records flags of information about the packfiles. This allows new 90 states, such as 'repacked' or 'redeltified', that can help with 91 pack maintenance in a multi-pack environment. It may also be 92 helpful to organize packfiles by object type (commit, tree, blob, 93 etc.) and use this metadata to help that maintenance. 94 95- The partial clone feature records special "promisor" packs that 96 may point to objects that are not stored locally, but available 97 on request to a server. The multi-pack-index does not currently 98 track these promisor packs. 99 100Related Links 101------------- 102[0] https://bugs.chromium.org/p/git/issues/detail?id=6 103 Chromium work item for: Multi-Pack Index (MIDX) 104 105[1] https://public-inbox.org/git/20180107181459.222909-1-dstolee@microsoft.com/ 106 An earlier RFC for the multi-pack-index feature 107 108[2] https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/ 109 Git Merge 2018 Contributor's summit notes (includes discussion of MIDX)