/
usr
/
share
/
doc
/
git
/
technical
/
/usr/share/doc/git/technical
mkdir
upload
Name
Size
Mode
Actions
api-error-handling.html
22259
0644
edit
dl
rm
api-error-handling.txt
3818
0644
edit
dl
rm
api-index-skel.txt
432
0644
edit
dl
rm
api-index.html
17183
0644
edit
dl
rm
api-index.sh
611
0644
edit
dl
rm
api-index.txt
648
0644
edit
dl
rm
api-merge.html
18305
0644
edit
dl
rm
api-merge.txt
1090
0644
edit
dl
rm
api-parse-options.html
36657
0644
edit
dl
rm
api-parse-options.txt
13157
0644
edit
dl
rm
api-simple-ipc.html
22388
0644
edit
dl
rm
api-simple-ipc.txt
4852
0644
edit
dl
rm
api-trace2.html
77619
0644
edit
dl
rm
api-trace2.txt
44255
0644
edit
dl
rm
bitmap-format.html
30403
0644
edit
dl
rm
bitmap-format.txt
8871
0644
edit
dl
rm
bundle-uri.html
51387
0644
edit
dl
rm
bundle-uri.txt
26787
0644
edit
dl
rm
commit-graph.txt
17957
0644
edit
dl
rm
directory-rename-detection.txt
5199
0644
edit
dl
rm
hash-function-transition.html
64539
0644
edit
dl
rm
hash-function-transition.txt
35894
0644
edit
dl
rm
long-running-process-protocol.html
18995
0644
edit
dl
rm
long-running-process-protocol.txt
1929
0644
edit
dl
rm
multi-pack-index.html
22462
0644
edit
dl
rm
multi-pack-index.txt
4459
0644
edit
dl
rm
pack-heuristics.html
43594
0644
edit
dl
rm
pack-heuristics.txt
18040
0644
edit
dl
rm
packfile-uri.txt
3748
0644
edit
dl
rm
parallel-checkout.html
31715
0644
edit
dl
rm
parallel-checkout.txt
12301
0644
edit
dl
rm
partial-clone.html
36496
0644
edit
dl
rm
partial-clone.txt
14968
0644
edit
dl
rm
racy-git.html
27995
0644
edit
dl
rm
racy-git.txt
9121
0644
edit
dl
rm
reftable.html
73792
0644
edit
dl
rm
reftable.txt
37525
0644
edit
dl
rm
remembering-renames.txt
30360
0644
edit
dl
rm
repository-version.txt
4311
0644
edit
dl
rm
rerere.txt
6510
0644
edit
dl
rm
scalar.html
20458
0644
edit
dl
rm
scalar.txt
2935
0644
edit
dl
rm
send-pack-pipeline.html
19315
0644
edit
dl
rm
send-pack-pipeline.txt
1969
0644
edit
dl
rm
shallow.html
19685
0644
edit
dl
rm
shallow.txt
2548
0644
edit
dl
rm
sparse-checkout.txt
47499
0644
edit
dl
rm
sparse-index.txt
9501
0644
edit
dl
rm
trivial-merge.html
22273
0644
edit
dl
rm
trivial-merge.txt
4264
0644
edit
dl
rm
Edit:
/usr/share/doc/git/technical/multi-pack-index.html
(22462B)
<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" /> <meta name="generator" content="AsciiDoc 8.6.10" /> <title>Multi-Pack-Index (MIDX) Design Notes</title> <style type="text/css"> /* Shared CSS for AsciiDoc xhtml11 and html5 backends */ /* Default font. */ body { font-family: Georgia,serif; } /* Title font. */ h1, h2, h3, h4, h5, h6, div.title, caption.title, thead, p.table.header, #toctitle, #author, #revnumber, #revdate, #revremark, #footer { font-family: Arial,Helvetica,sans-serif; } body { margin: 1em 5% 1em 5%; } a { color: blue; text-decoration: underline; } a:visited { color: fuchsia; } em { font-style: italic; color: navy; } strong { font-weight: bold; color: #083194; } h1, h2, h3, h4, h5, h6 { color: #527bbd; margin-top: 1.2em; margin-bottom: 0.5em; line-height: 1.3; } h1, h2, h3 { border-bottom: 2px solid silver; } h2 { padding-top: 0.5em; } h3 { float: left; } h3 + * { clear: left; } h5 { font-size: 1.0em; } div.sectionbody { margin-left: 0; } hr { border: 1px solid silver; } p { margin-top: 0.5em; margin-bottom: 0.5em; } ul, ol, li > p { margin-top: 0; } ul > li { color: #aaa; } ul > li > * { color: black; } .monospaced, code, pre { font-family: "Courier New", Courier, monospace; font-size: inherit; color: navy; padding: 0; margin: 0; } pre { white-space: pre-wrap; } #author { color: #527bbd; font-weight: bold; font-size: 1.1em; } #email { } #revnumber, #revdate, #revremark { } #footer { font-size: small; border-top: 2px solid silver; padding-top: 0.5em; margin-top: 4.0em; } #footer-text { float: left; padding-bottom: 0.5em; } #footer-badges { float: right; padding-bottom: 0.5em; } #preamble { margin-top: 1.5em; margin-bottom: 1.5em; } div.imageblock, div.exampleblock, div.verseblock, div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock, div.admonitionblock { margin-top: 1.0em; margin-bottom: 1.5em; } div.admonitionblock { margin-top: 2.0em; margin-bottom: 2.0em; margin-right: 10%; color: #606060; } div.content { /* Block element content. */ padding: 0; } /* Block element titles. */ div.title, caption.title { color: #527bbd; font-weight: bold; text-align: left; margin-top: 1.0em; margin-bottom: 0.5em; } div.title + * { margin-top: 0; } td div.title:first-child { margin-top: 0.0em; } div.content div.title:first-child { margin-top: 0.0em; } div.content + div.title { margin-top: 0.0em; } div.sidebarblock > div.content { background: #ffffee; border: 1px solid #dddddd; border-left: 4px solid #f0f0f0; padding: 0.5em; } div.listingblock > div.content { border: 1px solid #dddddd; border-left: 5px solid #f0f0f0; background: #f8f8f8; padding: 0.5em; } div.quoteblock, div.verseblock { padding-left: 1.0em; margin-left: 1.0em; margin-right: 10%; border-left: 5px solid #f0f0f0; color: #888; } div.quoteblock > div.attribution { padding-top: 0.5em; text-align: right; } div.verseblock > pre.content { font-family: inherit; font-size: inherit; } div.verseblock > div.attribution { padding-top: 0.75em; text-align: left; } /* DEPRECATED: Pre version 8.2.7 verse style literal block. */ div.verseblock + div.attribution { text-align: left; } div.admonitionblock .icon { vertical-align: top; font-size: 1.1em; font-weight: bold; text-decoration: underline; color: #527bbd; padding-right: 0.5em; } div.admonitionblock td.content { padding-left: 0.5em; border-left: 3px solid #dddddd; } div.exampleblock > div.content { border-left: 3px solid #dddddd; padding-left: 0.5em; } div.imageblock div.content { padding-left: 0; } span.image img { border-style: none; vertical-align: text-bottom; } a.image:visited { color: white; } dl { margin-top: 0.8em; margin-bottom: 0.8em; } dt { margin-top: 0.5em; margin-bottom: 0; font-style: normal; color: navy; } dd > *:first-child { margin-top: 0.1em; } ul, ol { list-style-position: outside; } ol.arabic { list-style-type: decimal; } ol.loweralpha { list-style-type: lower-alpha; } ol.upperalpha { list-style-type: upper-alpha; } ol.lowerroman { list-style-type: lower-roman; } ol.upperroman { list-style-type: upper-roman; } div.compact ul, div.compact ol, div.compact p, div.compact p, div.compact div, div.compact div { margin-top: 0.1em; margin-bottom: 0.1em; } tfoot { font-weight: bold; } td > div.verse { white-space: pre; } div.hdlist { margin-top: 0.8em; margin-bottom: 0.8em; } div.hdlist tr { padding-bottom: 15px; } dt.hdlist1.strong, td.hdlist1.strong { font-weight: bold; } td.hdlist1 { vertical-align: top; font-style: normal; padding-right: 0.8em; color: navy; } td.hdlist2 { vertical-align: top; } div.hdlist.compact tr { margin: 0; padding-bottom: 0; } .comment { background: yellow; } .footnote, .footnoteref { font-size: 0.8em; } span.footnote, span.footnoteref { vertical-align: super; } #footnotes { margin: 20px 0 20px 0; padding: 7px 0 0 0; } #footnotes div.footnote { margin: 0 0 5px 0; } #footnotes hr { border: none; border-top: 1px solid silver; height: 1px; text-align: left; margin-left: 0; width: 20%; min-width: 100px; } div.colist td { padding-right: 0.5em; padding-bottom: 0.3em; vertical-align: top; } div.colist td img { margin-top: 0.3em; } @media print { #footer-badges { display: none; } } #toc { margin-bottom: 2.5em; } #toctitle { color: #527bbd; font-size: 1.1em; font-weight: bold; margin-top: 1.0em; margin-bottom: 0.1em; } div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 { margin-top: 0; margin-bottom: 0; } div.toclevel2 { margin-left: 2em; font-size: 0.9em; } div.toclevel3 { margin-left: 4em; font-size: 0.9em; } div.toclevel4 { margin-left: 6em; font-size: 0.9em; } span.aqua { color: aqua; } span.black { color: black; } span.blue { color: blue; } span.fuchsia { color: fuchsia; } span.gray { color: gray; } span.green { color: green; } span.lime { color: lime; } span.maroon { color: maroon; } span.navy { color: navy; } span.olive { color: olive; } span.purple { color: purple; } span.red { color: red; } span.silver { color: silver; } span.teal { color: teal; } span.white { color: white; } span.yellow { color: yellow; } span.aqua-background { background: aqua; } span.black-background { background: black; } span.blue-background { background: blue; } span.fuchsia-background { background: fuchsia; } span.gray-background { background: gray; } span.green-background { background: green; } span.lime-background { background: lime; } span.maroon-background { background: maroon; } span.navy-background { background: navy; } span.olive-background { background: olive; } span.purple-background { background: purple; } span.red-background { background: red; } span.silver-background { background: silver; } span.teal-background { background: teal; } span.white-background { background: white; } span.yellow-background { background: yellow; } span.big { font-size: 2em; } span.small { font-size: 0.6em; } span.underline { text-decoration: underline; } span.overline { text-decoration: overline; } span.line-through { text-decoration: line-through; } div.unbreakable { page-break-inside: avoid; } /* * xhtml11 specific * * */ div.tableblock { margin-top: 1.0em; margin-bottom: 1.5em; } div.tableblock > table { border: 3px solid #527bbd; } thead, p.table.header { font-weight: bold; color: #527bbd; } p.table { margin-top: 0; } /* Because the table frame attribute is overriden by CSS in most browsers. */ div.tableblock > table[frame="void"] { border-style: none; } div.tableblock > table[frame="hsides"] { border-left-style: none; border-right-style: none; } div.tableblock > table[frame="vsides"] { border-top-style: none; border-bottom-style: none; } /* * html5 specific * * */ table.tableblock { margin-top: 1.0em; margin-bottom: 1.5em; } thead, p.tableblock.header { font-weight: bold; color: #527bbd; } p.tableblock { margin-top: 0; } table.tableblock { border-width: 3px; border-spacing: 0px; border-style: solid; border-color: #527bbd; border-collapse: collapse; } th.tableblock, td.tableblock { border-width: 1px; padding: 4px; border-style: solid; border-color: #527bbd; } table.tableblock.frame-topbot { border-left-style: hidden; border-right-style: hidden; } table.tableblock.frame-sides { border-top-style: hidden; border-bottom-style: hidden; } table.tableblock.frame-none { border-style: hidden; } th.tableblock.halign-left, td.tableblock.halign-left { text-align: left; } th.tableblock.halign-center, td.tableblock.halign-center { text-align: center; } th.tableblock.halign-right, td.tableblock.halign-right { text-align: right; } th.tableblock.valign-top, td.tableblock.valign-top { vertical-align: top; } th.tableblock.valign-middle, td.tableblock.valign-middle { vertical-align: middle; } th.tableblock.valign-bottom, td.tableblock.valign-bottom { vertical-align: bottom; } /* * manpage specific * * */ body.manpage h1 { padding-top: 0.5em; padding-bottom: 0.5em; border-top: 2px solid silver; border-bottom: 2px solid silver; } body.manpage h2 { border-style: none; } body.manpage div.sectionbody { margin-left: 3em; } @media print { body.manpage div#toc { display: none; } } </style> <script type="text/javascript"> /*<+'])'); // Function that scans the DOM tree for header elements (the DOM2 // nodeIterator API would be a better technique but not supported by all // browsers). var iterate = function (el) { for (var i = el.firstChild; i != null; i = i.nextSibling) { if (i.nodeType == 1 /* Node.ELEMENT_NODE */) { var mo = re.exec(i.tagName); if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") { result[result.length] = new TocEntry(i, getText(i), mo[1]-1); } iterate(i); } } } iterate(el); return result; } var toc = document.getElementById("toc"); if (!toc) { return; } // Delete existing TOC entries in case we're reloading the TOC. var tocEntriesToRemove = []; var i; for (i = 0; i < toc.childNodes.length; i++) { var entry = toc.childNodes[i]; if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") && entry.getAttribute("class").match(/^toclevel/)) tocEntriesToRemove.push(entry); } for (i = 0; i < tocEntriesToRemove.length; i++) { toc.removeChild(tocEntriesToRemove[i]); } // Rebuild TOC entries. var entries = tocEntries(document.getElementById("content"), toclevels); for (var i = 0; i < entries.length; ++i) { var entry = entries[i]; if (entry.element.id == "") entry.element.id = "_toc_" + i; var a = document.createElement("a"); a.href = "#" + entry.element.id; a.appendChild(document.createTextNode(entry.text)); var div = document.createElement("div"); div.appendChild(a); div.className = "toclevel" + entry.toclevel; toc.appendChild(div); } if (entries.length == 0) toc.parentNode.removeChild(toc); }, ///////////////////////////////////////////////////////////////////// // Footnotes generator ///////////////////////////////////////////////////////////////////// /* Based on footnote generation code from: * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html */ footnotes: function () { // Delete existing footnote entries in case we're reloading the footnodes. var i; var noteholder = document.getElementById("footnotes"); if (!noteholder) { return; } var entriesToRemove = []; for (i = 0; i < noteholder.childNodes.length; i++) { var entry = noteholder.childNodes[i]; if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote") entriesToRemove.push(entry); } for (i = 0; i < entriesToRemove.length; i++) { noteholder.removeChild(entriesToRemove[i]); } // Rebuild footnote entries. var cont = document.getElementById("content"); var spans = cont.getElementsByTagName("span"); var refs = {}; var n = 0; for (i=0; i<spans.length; i++) { if (spans[i].className == "footnote") { n++; var note = spans[i].getAttribute("data-note"); if (!note) { // Use [\s\S] in place of . so multi-line matches work. // Because JavaScript has no s (dotall) regex flag. note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1]; spans[i].innerHTML = "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n + "' title='View footnote' class='footnote'>" + n + "</a>]"; spans[i].setAttribute("data-note", note); } noteholder.innerHTML += "<div class='footnote' id='_footnote_" + n + "'>" + "<a href='#_footnoteref_" + n + "' title='Return to text'>" + n + "</a>. " + note + "</div>"; var id =spans[i].getAttribute("id"); if (id != null) refs["#"+id] = n; } } if (n == 0) noteholder.parentNode.removeChild(noteholder); else { // Process footnoterefs. for (i=0; i<spans.length; i++) { if (spans[i].className == "footnoteref") { var href = spans[i].getElementsByTagName("a")[0].getAttribute("href"); href = href.match(/#.*/)[0]; // Because IE return full URL. n = refs[href]; spans[i].innerHTML = "[<a href='#_footnote_" + n + "' title='View footnote' class='footnote'>" + n + "</a>]"; } } } }, install: function(toclevels) { var timerId; function reinstall() { asciidoc.footnotes(); if (toclevels) { asciidoc.toc(toclevels); } } function reinstallAndRemoveTimer() { clearInterval(timerId); reinstall(); } timerId = setInterval(reinstall, 500); if (document.addEventListener) document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false); else window.onload = reinstallAndRemoveTimer; } } asciidoc.install(); /*]]>*/ </script> </head> <body class="article"> <div id="header"> <h1>Multi-Pack-Index (MIDX) Design Notes</h1> <span id="revdate"></span> </div> <div id="content"> <div id="preamble"> <div class="sectionbody"> <div class="paragraph"><p>The Git object directory contains a <em>pack</em> 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.</p></div> <div class="paragraph"><p>The multi-pack-index (MIDX for short) stores a list of objects and their offsets into multiple packfiles. It contains:</p></div> <div class="ulist"><ul> <li> <p> A list of packfile names. </p> </li> <li> <p> A sorted list of object IDs. </p> </li> <li> <p> A list of metadata for the ith object ID including: </p> <div class="ulist"><ul> <li> <p> A value j referring to the jth packfile. </p> </li> <li> <p> An offset within the jth packfile for the object. </p> </li> </ul></div> </li> <li> <p> If large offsets are required, we use another list of large offsets similar to version 2 pack-indexes. </p> <div class="ulist"><ul> <li> <p> An optional list of objects in pseudo-pack order (used with MIDX bitmaps). </p> </li> </ul></div> </li> </ul></div> <div class="paragraph"><p>Thus, we can provide O(log N) lookup time for any number of packfiles.</p></div> </div> </div> <div class="sect1"> <h2 id="_design_details">Design Details</h2> <div class="sectionbody"> <div class="ulist"><ul> <li> <p> The MIDX is stored in a file named <em>multi-pack-index</em> 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. </p> </li> <li> <p> The core.multiPackIndex config setting must be on (which is the default) to consume MIDX files. Setting it to <code>false</code> prevents Git from reading a MIDX file, even if one exists. </p> </li> <li> <p> 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. </p> </li> <li> <p> 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. </p> </li> <li> <p> If there exist packfiles in the pack directory not registered in the MIDX, then those packfiles are loaded into the <code>packed_git</code> list and <code>packed_git_mru</code> cache. </p> </li> <li> <p> 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. </p> </li> <li> <p> The MIDX file format uses a chunk-based approach (similar to the commit-graph file) that allows optional data to be added. </p> </li> </ul></div> </div> </div> <div class="sect1"> <h2 id="_future_work">Future Work</h2> <div class="sectionbody"> <div class="ulist"><ul> <li> <p> 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. </p> </li> <li> <p> 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. </p> </li> <li> <p> 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 <em>repacked</em> or <em>redeltified</em>, 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. </p> </li> </ul></div> </div> </div> <div class="sect1"> <h2 id="_related_links">Related Links</h2> <div class="sectionbody"> <div class="paragraph"><p>[0] <a href="https://bugs.chromium.org/p/git/issues/detail?id=6">https://bugs.chromium.org/p/git/issues/detail?id=6</a> Chromium work item for: Multi-Pack Index (MIDX)</p></div> <div class="paragraph"><p>[1] <a href="https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/">https://lore.kernel.org/git/20180107181459.222909-1-dstolee@microsoft.com/</a> An earlier RFC for the multi-pack-index feature</p></div> <div class="paragraph"><p>[2] <a href="https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/">https://lore.kernel.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/</a> Git Merge 2018 Contributor’s summit notes (includes discussion of MIDX)</p></div> </div> </div> </div> <div id="footnotes"><hr /></div> <div id="footer"> <div id="footer-text"> Last updated 2025-06-13 22:14:31 UTC </div> </div> </body> </html>
Save
cmd:
run