1087 lines
31 KiB
HTML
1087 lines
31 KiB
HTML
<?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 10.2.0" />
|
|
<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 overridden 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="_incremental_multi_pack_indexes">Incremental multi-pack indexes</h2>
|
|
<div class="sectionbody">
|
|
<div class="paragraph"><p>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.</p></div>
|
|
<div class="paragraph"><p>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.</p></div>
|
|
<div class="sect2">
|
|
<h3 id="_design_state">Design state</h3>
|
|
<div class="paragraph"><p>At present, the incremental multi-pack indexes feature is missing two
|
|
important components:</p></div>
|
|
<div class="ulist"><ul>
|
|
<li>
|
|
<p>
|
|
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 <code>--split</code>
|
|
flag.
|
|
</p>
|
|
<div class="paragraph"><p>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.</p></div>
|
|
</li>
|
|
<li>
|
|
<p>
|
|
Support for reachability bitmaps. The classic single MIDX
|
|
implementation does support reachability bitmaps (see the section
|
|
titled "multi-pack-index reverse indexes" in
|
|
<a href="../gitformat-pack.html">gitformat-pack(5)</a> for more details).
|
|
</p>
|
|
<div class="paragraph"><p>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.</p></div>
|
|
<div class="paragraph"><p>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, <code>$H2,</code> <code>$H3</code>} would be the pseudo-pack order for <code>$H1</code>, followed by
|
|
the pseudo-pack order for <code>$H2</code>, followed by the pseudo-pack order for
|
|
<code>$H3</code>).</p></div>
|
|
<div class="paragraph"><p>The layout will then be extended so that each layer of the incremental
|
|
MIDX chain can write a <code>*.bitmap</code>. The objects in each layer’s bitmap
|
|
are offset by the number of objects in the previous layers of the chain.</p></div>
|
|
</li>
|
|
</ul></div>
|
|
</div>
|
|
<div class="sect2">
|
|
<h3 id="_file_layout">File layout</h3>
|
|
<div class="paragraph"><p>Instead of storing a single <code>multi-pack-index</code> file (with an optional
|
|
<code>.rev</code> and <code>.bitmap</code> extension) in <code>$GIT_DIR/objects/pack</code>, incremental
|
|
MIDXs are stored in the following layout:</p></div>
|
|
<div class="listingblock">
|
|
<div class="content">
|
|
<pre><code>$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</code></pre>
|
|
</div></div>
|
|
<div class="paragraph"><p>The <code>multi-pack-index-chain</code> file contains a list of the incremental
|
|
MIDX files in the chain, in order. The above example shows a chain whose
|
|
<code>multi-pack-index-chain</code> file would contain the following lines:</p></div>
|
|
<div class="listingblock">
|
|
<div class="content">
|
|
<pre><code>$H1
|
|
$H2
|
|
$H3</code></pre>
|
|
</div></div>
|
|
<div class="paragraph"><p>The <code>multi-pack-index-$H1.midx</code> file contains the first layer of the
|
|
multi-pack-index chain. The <code>multi-pack-index-$H2.midx</code> file contains
|
|
the second layer of the chain, and so on.</p></div>
|
|
<div class="paragraph"><p>When both an incremental- and non-incremental MIDX are present, the
|
|
non-incremental MIDX is always read first.</p></div>
|
|
</div>
|
|
<div class="sect2">
|
|
<h3 id="_object_positions_for_incremental_midxs">Object positions for incremental MIDXs</h3>
|
|
<div class="paragraph"><p>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.</p></div>
|
|
<div class="paragraph"><p>If <code>objects_nr</code>() is a function that returns the number of objects in a
|
|
given MIDX layer, then the index of an object at lexicographic position
|
|
<code>i</code> within, say, $H3 is defined as:</p></div>
|
|
<div class="listingblock">
|
|
<div class="content">
|
|
<pre><code>objects_nr($H2) + objects_nr($H1) + i</code></pre>
|
|
</div></div>
|
|
<div class="paragraph"><p>(in the C implementation, this is often computed as <code>i</code> <code>+</code>
|
|
<code>m-</code>><code>num_objects_in_base</code>).</p></div>
|
|
</div>
|
|
<div class="sect2">
|
|
<h3 id="_pseudo_pack_order_for_incremental_midxs">Pseudo-pack order for incremental MIDXs</h3>
|
|
<div class="paragraph"><p>The original implementation of multi-pack reachability bitmaps defined
|
|
the pseudo-pack order in <a href="../gitformat-pack.html">gitformat-pack(5)</a> (see the section
|
|
titled "multi-pack-index reverse indexes") roughly as follows:</p></div>
|
|
<div class="quoteblock">
|
|
<div class="content">
|
|
<div class="paragraph"><p>In short, a MIDX’s pseudo-pack is the de-duplicated concatenation of
|
|
objects in packs stored by the MIDX, laid out in pack order, and the
|
|
packs arranged in MIDX order (with the preferred pack coming first).</p></div>
|
|
</div>
|
|
<div class="attribution">
|
|
</div></div>
|
|
<div class="paragraph"><p>In the incremental MIDX design, we extend this definition to include
|
|
objects from multiple layers of the MIDX chain. The pseudo-pack order
|
|
for incremental MIDXs is determined by concatenating the pseudo-pack
|
|
ordering for each layer of the MIDX chain in order. Formally two objects
|
|
<code>o1</code> and <code>o2</code> are compared as follows:</p></div>
|
|
<div class="olist arabic"><ol class="arabic">
|
|
<li>
|
|
<p>
|
|
If <code>o1</code> appears in an earlier layer of the MIDX chain than <code>o2</code>, then
|
|
<code>o1</code> sorts ahead of <code>o2</code>.
|
|
</p>
|
|
</li>
|
|
<li>
|
|
<p>
|
|
Otherwise, if <code>o1</code> and <code>o2</code> appear in the same MIDX layer, and that
|
|
MIDX layer has no base, then if one of <code>pack</code>(<code>o1</code>) and <code>pack</code>(<code>o2</code>) is
|
|
preferred and the other is not, then the preferred one sorts ahead of
|
|
the non-preferred one. If there is a base layer (i.e. the MIDX layer
|
|
is not the first layer in the chain), then if <code>pack</code>(<code>o1</code>) appears
|
|
earlier in that MIDX layer’s pack order, then <code>o1</code> sorts ahead of
|
|
<code>o2</code>. Likewise if <code>pack</code>(<code>o2</code>) appears earlier, then the opposite is
|
|
true.
|
|
</p>
|
|
</li>
|
|
<li>
|
|
<p>
|
|
Otherwise, <code>o1</code> and <code>o2</code> appear in the same pack, and thus in the
|
|
same MIDX layer. Sort <code>o1</code> and <code>o2</code> by their offset within their
|
|
containing packfile.
|
|
</p>
|
|
</li>
|
|
</ol></div>
|
|
<div class="paragraph"><p>Note that the preferred pack is a property of the MIDX chain, not the
|
|
individual layers themselves. Fundamentally we could introduce a
|
|
per-layer preferred pack, but this is less relevant now that we can
|
|
perform multi-pack reuse across the set of packs in a MIDX.</p></div>
|
|
</div>
|
|
<div class="sect2">
|
|
<h3 id="_reachability_bitmaps_and_incremental_midxs">Reachability bitmaps and incremental MIDXs</h3>
|
|
<div class="paragraph"><p>Each layer of an incremental MIDX chain may have its objects (and the
|
|
objects from any previous layer in the same MIDX chain) represented in
|
|
its own <code>*.bitmap</code> file.</p></div>
|
|
<div class="paragraph"><p>The structure of a <code>*.bitmap</code> file belonging to an incremental MIDX
|
|
chain is identical to that of a non-incremental MIDX bitmap, or a
|
|
classic single-pack bitmap. Since objects are added to the end of the
|
|
incremental MIDX’s pseudo-pack order (see above), it is possible to
|
|
extend a bitmap when appending to the end of a MIDX chain.</p></div>
|
|
<div class="paragraph"><p>(Note: it is possible likewise to compress a contiguous sequence of MIDX
|
|
incremental layers, and their <code>*.bitmap</code> files into a single layer and
|
|
<code>*.bitmap</code>, but this is not yet implemented.)</p></div>
|
|
<div class="paragraph"><p>The object positions used are global within the pseudo-pack order, so
|
|
subsequent layers will have, for example, <code>m-</code>><code>num_objects_in_base</code>
|
|
number of <code>0</code> bits in each of their four type bitmaps. This follows from
|
|
the fact that we only write type bitmap entries for objects present in
|
|
the layer immediately corresponding to the bitmap).</p></div>
|
|
<div class="paragraph"><p>Note also that only the bitmap pertaining to the most recent layer in an
|
|
incremental MIDX chain is used to store reachability information about
|
|
the interesting and uninteresting objects in a reachability query.
|
|
Earlier bitmap layers are only used to look up commit and pseudo-merge
|
|
bitmaps from that layer, as well as the type-level bitmaps for objects
|
|
in that layer.</p></div>
|
|
<div class="paragraph"><p>To simplify the implementation, type-level bitmaps are iterated
|
|
simultaneously, and their results are OR’d together to avoid recursively
|
|
calling internal bitmap functions.</p></div>
|
|
</div>
|
|
</div>
|
|
</div>
|
|
<div class="sect1">
|
|
<h2 id="_future_work">Future Work</h2>
|
|
<div class="sectionbody">
|
|
<div class="ulist"><ul>
|
|
<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-08-18 02:18:23 CEST
|
|
</div>
|
|
</div>
|
|
</body>
|
|
</html>
|