technical/multi-pack-index.html - pub/scm/git/git-htmldocs - Git at Google

 <?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">
 /*<![CDATA[*/
 var asciidoc = {  // Namespace.

 /////////////////////////////////////////////////////////////////////
 // Table Of Contents generator
 /////////////////////////////////////////////////////////////////////

 /* Author: Mihai Bazon, September 2002
  * http://students.infoiasi.ro/~mishoo
  *
  * Table Of Content generator
  * Version: 0.4
  *
  * Feel free to use this script under the terms of the GNU General Public
  * License, as long as you do not remove or alter this notice.
  */

  /* modified by Troy D. Hanson, September 2006. License: GPL */
  /* modified by Stuart Rackham, 2006, 2009. License: GPL */

 // toclevels = 1..4.
 toc: function (toclevels) {

   function getText(el) {
     var text = "";
     for (var i = el.firstChild; i != null; i = i.nextSibling) {
       if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
         text += i.data;
       else if (i.firstChild != null)
         text += getText(i);
     }
     return text;
   }

   function TocEntry(el, text, toclevel) {
     this.element = el;
     this.text = text;
     this.toclevel = toclevel;
   }

   function tocEntries(el, toclevels) {
     var result = new Array;
     var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
     // 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>
 </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>
 </li>
 <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>
 <li>
 <p>
 If large offsets are required, we use another list of large
   offsets similar to version 2 pack-indexes.
 </p>
 </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 pack.multiIndex config setting must be on to consume MIDX files.
 </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 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>
 Add a <em>verify</em> subcommand to the <em>git midx</em> builtin to verify the
   contents of the multi-pack-index file match the offsets listed in
   the corresponding pack-indexes.
 </p>
 </li>
 <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>
 The reachability bitmap is currently paired directly with a single
   packfile, using the pack-order as the object order to hopefully
   compress the bitmaps well using run-length encoding. This could be
   extended to pair a reachability bitmap with a multi-pack-index. 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 a reachability bitmap
   could point to a multi-pack-index and be updated independently.
 </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>
 <li>
 <p>
 The partial clone feature records special "promisor" packs that
   may point to objects that are not stored locally, but available
   on request to a server. The multi-pack-index does not currently
   track these promisor packs.
 </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://public-inbox.org/git/20180107181459.222909-1-dstolee@microsoft.com/">https://public-inbox.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://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/">https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/</a>
     Git Merge 2018 Contributor&#8217;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
  2018-09-17 15:45:24 PDT
 </div>
 </div>
 </body>
 </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 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">
	/<![CDATA[/
	var asciidoc = { // Namespace.

	/////////////////////////////////////////////////////////////////////
	// Table Of Contents generator
	/////////////////////////////////////////////////////////////////////

	/* Author: Mihai Bazon, September 2002
	* http://students.infoiasi.ro/~mishoo
	*
	* Table Of Content generator
	* Version: 0.4
	*
	* Feel free to use this script under the terms of the GNU General Public
	* License, as long as you do not remove or alter this notice.
	*/

	/* modified by Troy D. Hanson, September 2006. License: GPL */
	/* modified by Stuart Rackham, 2006, 2009. License: GPL */

	// toclevels = 1..4.
	toc: function (toclevels) {

	function getText(el) {
	var text = "";
	for (var i = el.firstChild; i != null; i = i.nextSibling) {
	if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
	text += i.data;
	else if (i.firstChild != null)
	text += getText(i);
	}
	return text;
	}

	function TocEntry(el, text, toclevel) {
	this.element = el;
	this.text = text;
	this.toclevel = toclevel;
	}

	function tocEntries(el, toclevels) {
	var result = new Array;
	var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
	// 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>
	</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>
	</li>
	<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>
	<li>
	<p>
	If large offsets are required, we use another list of large
	offsets similar to version 2 pack-indexes.
	</p>
	</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 pack.multiIndex config setting must be on to consume MIDX files.
	</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 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>
	Add a <em>verify</em> subcommand to the <em>git midx</em> builtin to verify the
	contents of the multi-pack-index file match the offsets listed in
	the corresponding pack-indexes.
	</p>
	</li>
	<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>
	The reachability bitmap is currently paired directly with a single
	packfile, using the pack-order as the object order to hopefully
	compress the bitmaps well using run-length encoding. This could be
	extended to pair a reachability bitmap with a multi-pack-index. 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 a reachability bitmap
	could point to a multi-pack-index and be updated independently.
	</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>
	<li>
	<p>
	The partial clone feature records special "promisor" packs that
	may point to objects that are not stored locally, but available
	on request to a server. The multi-pack-index does not currently
	track these promisor packs.
	</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://public-inbox.org/git/20180107181459.222909-1-dstolee@microsoft.com/">https://public-inbox.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://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/">https://public-inbox.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
	2018-09-17 15:45:24 PDT
	</div>
	</div>
	</body>
	</html>