[RFC PATCH 01/18] docs: Multi-Pack Index (MIDX) Design Notes
- Date: Sun, 7 Jan 2018 13:14:42 -0500
- From: Derrick Stolee <stolee@xxxxxxxxx>
- Subject: [RFC PATCH 01/18] docs: Multi-Pack Index (MIDX) Design Notes
Commentary: This file format uses the large offsets from the pack-index
version 2 format, but drops the CRC32 hashes from that format.
Also: I included the HASH footer at the end only because it is already in
the pack and pack-index formats, but not because it is particularly useful
here. If possible, I'd like to remove it and speed up MIDX writes.
-- >8 --
Add a technical documentation file describing the design
for the multi-pack index (MIDX). Includes current limitations
and future work.
Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
Documentation/technical/multi-pack-index.txt | 149 +++++++++++++++++++++++++++
1 file changed, 149 insertions(+)
create mode 100644 Documentation/technical/multi-pack-index.txt
diff --git a/Documentation/technical/multi-pack-index.txt b/Documentation/technical/multi-pack-index.txt
new file mode 100644
@@ -0,0 +1,149 @@
+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, with suffix ".midx")
+stores a list of objects and their offsets into multiple pack-
+files. 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.
+Thus, we can provide O(log N) lookup time for any number
+A new config setting 'core.midx' must be enabled before writing
+or reading MIDX files.
+The MIDX files are updated by the 'midx' builtin with the
+following common parameter combinations:
+- 'git midx' gives the hash of the current MIDX head.
+- 'git midx --write --update-head --delete-expired' writes a new
+ MIDX file, points the MIDX head to that file, and deletes the
+ existing MIDX file if out-of-date.
+- 'git midx --read' lists some basic information about the current
+ MIDX head. Used for basic tests.
+- 'git midx --clear' deletes the current MIDX head.
+- The MIDX file refers only to packfiles in the same directory
+ as the MIDX file.
+- A special file, 'midx-head', stores the hash of the latest
+ MIDX file so we can load the file without performing a dirstat.
+ This file is especially important with incremental MIDX files,
+ pointing to the newest file.
+- If a packfile exists in the pack directory but is not referenced
+ by the MIDX file, then the packfile is loaded into the packed_git
+ list and Git can access the objects as usual. This behavior is
+ necessary since other tools could add packfiles to the pack
+ directory without notifying Git.
+- The MIDX file should be only a supplemental structure. If a
+ user downgrades or disables the `core.midx` config setting,
+ then the existing .idx and .pack files should be sufficient
+ to operate correctly.
+- The file format includes parameters for the object id length
+ and hash algorithm, so a future change of hash algorithm does
+ not require a change in format.
+- If an object appears in multiple packfiles, then only one copy
+ is stored in the MIDX. This has a possible performance issue:
+ If an object appears as the delta-base of multiple objects from
+ multiple packs, then cross-pack delta calculations may slow down.
+ This is currently only theoretical and has not been demonstrated
+ to be a measurable issue.
+- MIDX files are managed only by the midx builtin and is not
+ automatically updated on clone or fetch.
+- There is no '--verify' option for the midx builtin to verify
+ the contents of the MIDX file against the pack contents.
+- Constructing a MIDX file currently requires the single-pack
+ index for every pack being added to the MIDX.
+- The fsck builtin does not check MIDX files, but should.
+- The repack builtin is not aware of the MIDX files, and may
+ invalidate the MIDX files by deleting existing packfiles. The
+ MIDX may also be extended in the future to store metadata about
+ a packfile that can be used for faster repack commands.
+- The naive Git HTTP server advertises lists of packfiles using
+ the file system directly.
+- The current file-format requires between 28 and 36 bytes per
+ object. As the repository grows, the MIDX file can become
+ very large and become a bottleneck when updating the file. To
+ fix this "big write" problem, we can make the MIDX file
+ incremental. Instead of just one MIDX file, we will have a
+ sequence of MIDX files that can be unioned together. Then
+ on write we take the new objects to add and consider how many
+ existing files should be merged into a new file containing
+ the latest objects.
+ This list of "base indexes" will be presented as an optional
+ chunk in the MIDX format and contains the OIDs for the base
+ files. Thus, the `midx_head` file only stores the OID for the
+ "tip" MIDX file and then the rest are loaded based on those
+ pointers, such as the following figure:
+ [ BIG ] <- [ MEDIUM ] <- [tiny] <- midx_head
+ The plan being that every write replaces the "tiny" index,
+ and when that index becomes large enough it merges with the
+ "medium" index and a new tiny index is created in the next
+ write. Very rarely, the "big" index would be updated, causing
+ a slow write.
+- After the MIDX feature is sufficiently hardened and widely used,
+ consider making Git more fully depend on the MIDX file. If MIDX
+ is the default, then we can delete the single-pack-indexes from
+ the pack directory. We could also allow thin packs in the pack
+- The MIDX could be extended to store a "stable object order" such
+ that adding objects to the order does not change the existing
+ objects. This would enable re-using the reachability bitmaps after
+ repacking and updating the MIDX file.
+ Chromium work item for: Multi-Pack Index (MIDX)
+ Subject: Git performance results on a large repository
+ Date: 3 Feb 2012