| <!DOCTYPE html> |
| <html xmlns="http://www.w3.org/1999/xhtml" lang="en"> |
| <head> |
| <meta charset="UTF-8"/> |
| <meta http-equiv="X-UA-Compatible" content="IE=edge"/> |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"/> |
| <meta name="generator" content="Asciidoctor 2.0.23"/> |
| <title>reftable</title> |
| <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700"/> |
| <style> |
| /*! Asciidoctor default stylesheet | MIT License | https://asciidoctor.org */ |
| /* Uncomment the following line when using as a custom stylesheet */ |
| /* @import "https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700"; */ |
| html{font-family:sans-serif;-webkit-text-size-adjust:100%} |
| a{background:none} |
| a:focus{outline:thin dotted} |
| a:active,a:hover{outline:0} |
| h1{font-size:2em;margin:.67em 0} |
| b,strong{font-weight:bold} |
| abbr{font-size:.9em} |
| abbr[title]{cursor:help;border-bottom:1px dotted #dddddf;text-decoration:none} |
| dfn{font-style:italic} |
| hr{height:0} |
| mark{background:#ff0;color:#000} |
| code,kbd,pre,samp{font-family:monospace;font-size:1em} |
| pre{white-space:pre-wrap} |
| q{quotes:"\201C" "\201D" "\2018" "\2019"} |
| small{font-size:80%} |
| sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline} |
| sup{top:-.5em} |
| sub{bottom:-.25em} |
| img{border:0} |
| svg:not(:root){overflow:hidden} |
| figure{margin:0} |
| audio,video{display:inline-block} |
| audio:not([controls]){display:none;height:0} |
| fieldset{border:1px solid silver;margin:0 2px;padding:.35em .625em .75em} |
| legend{border:0;padding:0} |
| button,input,select,textarea{font-family:inherit;font-size:100%;margin:0} |
| button,input{line-height:normal} |
| button,select{text-transform:none} |
| button,html input[type=button],input[type=reset],input[type=submit]{-webkit-appearance:button;cursor:pointer} |
| button[disabled],html input[disabled]{cursor:default} |
| input[type=checkbox],input[type=radio]{padding:0} |
| button::-moz-focus-inner,input::-moz-focus-inner{border:0;padding:0} |
| textarea{overflow:auto;vertical-align:top} |
| table{border-collapse:collapse;border-spacing:0} |
| *,::before,::after{box-sizing:border-box} |
| html,body{font-size:100%} |
| body{background:#fff;color:rgba(0,0,0,.8);padding:0;margin:0;font-family:"Noto Serif","DejaVu Serif",serif;line-height:1;position:relative;cursor:auto;-moz-tab-size:4;-o-tab-size:4;tab-size:4;word-wrap:anywhere;-moz-osx-font-smoothing:grayscale;-webkit-font-smoothing:antialiased} |
| a:hover{cursor:pointer} |
| img,object,embed{max-width:100%;height:auto} |
| object,embed{height:100%} |
| img{-ms-interpolation-mode:bicubic} |
| .left{float:left!important} |
| .right{float:right!important} |
| .text-left{text-align:left!important} |
| .text-right{text-align:right!important} |
| .text-center{text-align:center!important} |
| .text-justify{text-align:justify!important} |
| .hide{display:none} |
| img,object,svg{display:inline-block;vertical-align:middle} |
| textarea{height:auto;min-height:50px} |
| select{width:100%} |
| .subheader,.admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{line-height:1.45;color:#7a2518;font-weight:400;margin-top:0;margin-bottom:.25em} |
| div,dl,dt,dd,ul,ol,li,h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6,pre,form,p,blockquote,th,td{margin:0;padding:0} |
| a{color:#2156a5;text-decoration:underline;line-height:inherit} |
| a:hover,a:focus{color:#1d4b8f} |
| a img{border:0} |
| p{line-height:1.6;margin-bottom:1.25em;text-rendering:optimizeLegibility} |
| p aside{font-size:.875em;line-height:1.35;font-style:italic} |
| h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{font-family:"Open Sans","DejaVu Sans",sans-serif;font-weight:300;font-style:normal;color:#ba3925;text-rendering:optimizeLegibility;margin-top:1em;margin-bottom:.5em;line-height:1.0125em} |
| h1 small,h2 small,h3 small,#toctitle small,.sidebarblock>.content>.title small,h4 small,h5 small,h6 small{font-size:60%;color:#e99b8f;line-height:0} |
| h1{font-size:2.125em} |
| h2{font-size:1.6875em} |
| h3,#toctitle,.sidebarblock>.content>.title{font-size:1.375em} |
| h4,h5{font-size:1.125em} |
| h6{font-size:1em} |
| hr{border:solid #dddddf;border-width:1px 0 0;clear:both;margin:1.25em 0 1.1875em} |
| em,i{font-style:italic;line-height:inherit} |
| strong,b{font-weight:bold;line-height:inherit} |
| small{font-size:60%;line-height:inherit} |
| code{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;color:rgba(0,0,0,.9)} |
| ul,ol,dl{line-height:1.6;margin-bottom:1.25em;list-style-position:outside;font-family:inherit} |
| ul,ol{margin-left:1.5em} |
| ul li ul,ul li ol{margin-left:1.25em;margin-bottom:0} |
| ul.circle{list-style-type:circle} |
| ul.disc{list-style-type:disc} |
| ul.square{list-style-type:square} |
| ul.circle ul:not([class]),ul.disc ul:not([class]),ul.square ul:not([class]){list-style:inherit} |
| ol li ul,ol li ol{margin-left:1.25em;margin-bottom:0} |
| dl dt{margin-bottom:.3125em;font-weight:bold} |
| dl dd{margin-bottom:1.25em} |
| blockquote{margin:0 0 1.25em;padding:.5625em 1.25em 0 1.1875em;border-left:1px solid #ddd} |
| blockquote,blockquote p{line-height:1.6;color:rgba(0,0,0,.85)} |
| @media screen and (min-width:768px){h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2} |
| h1{font-size:2.75em} |
| h2{font-size:2.3125em} |
| h3,#toctitle,.sidebarblock>.content>.title{font-size:1.6875em} |
| h4{font-size:1.4375em}} |
| table{background:#fff;margin-bottom:1.25em;border:1px solid #dedede;word-wrap:normal} |
| table thead,table tfoot{background:#f7f8f7} |
| table thead tr th,table thead tr td,table tfoot tr th,table tfoot tr td{padding:.5em .625em .625em;font-size:inherit;color:rgba(0,0,0,.8);text-align:left} |
| table tr th,table tr td{padding:.5625em .625em;font-size:inherit;color:rgba(0,0,0,.8)} |
| table tr.even,table tr.alt{background:#f8f8f7} |
| table thead tr th,table tfoot tr th,table tbody tr td,table tr td,table tfoot tr td{line-height:1.6} |
| h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2;word-spacing:-.05em} |
| h1 strong,h2 strong,h3 strong,#toctitle strong,.sidebarblock>.content>.title strong,h4 strong,h5 strong,h6 strong{font-weight:400} |
| .center{margin-left:auto;margin-right:auto} |
| .stretch{width:100%} |
| .clearfix::before,.clearfix::after,.float-group::before,.float-group::after{content:" ";display:table} |
| .clearfix::after,.float-group::after{clear:both} |
| :not(pre).nobreak{word-wrap:normal} |
| :not(pre).nowrap{white-space:nowrap} |
| :not(pre).pre-wrap{white-space:pre-wrap} |
| :not(pre):not([class^=L])>code{font-size:.9375em;font-style:normal!important;letter-spacing:0;padding:.1em .5ex;word-spacing:-.15em;background:#f7f7f8;border-radius:4px;line-height:1.45;text-rendering:optimizeSpeed} |
| pre{color:rgba(0,0,0,.9);font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;line-height:1.45;text-rendering:optimizeSpeed} |
| pre code,pre pre{color:inherit;font-size:inherit;line-height:inherit} |
| pre>code{display:block} |
| pre.nowrap,pre.nowrap pre{white-space:pre;word-wrap:normal} |
| em em{font-style:normal} |
| strong strong{font-weight:400} |
| .keyseq{color:rgba(51,51,51,.8)} |
| kbd{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;display:inline-block;color:rgba(0,0,0,.8);font-size:.65em;line-height:1.45;background:#f7f7f7;border:1px solid #ccc;border-radius:3px;box-shadow:0 1px 0 rgba(0,0,0,.2),inset 0 0 0 .1em #fff;margin:0 .15em;padding:.2em .5em;vertical-align:middle;position:relative;top:-.1em;white-space:nowrap} |
| .keyseq kbd:first-child{margin-left:0} |
| .keyseq kbd:last-child{margin-right:0} |
| .menuseq,.menuref{color:#000} |
| .menuseq b:not(.caret),.menuref{font-weight:inherit} |
| .menuseq{word-spacing:-.02em} |
| .menuseq b.caret{font-size:1.25em;line-height:.8} |
| .menuseq i.caret{font-weight:bold;text-align:center;width:.45em} |
| b.button::before,b.button::after{position:relative;top:-1px;font-weight:400} |
| b.button::before{content:"[";padding:0 3px 0 2px} |
| b.button::after{content:"]";padding:0 2px 0 3px} |
| p a>code:hover{color:rgba(0,0,0,.9)} |
| #header,#content,#footnotes,#footer{width:100%;margin:0 auto;max-width:62.5em;*zoom:1;position:relative;padding-left:.9375em;padding-right:.9375em} |
| #header::before,#header::after,#content::before,#content::after,#footnotes::before,#footnotes::after,#footer::before,#footer::after{content:" ";display:table} |
| #header::after,#content::after,#footnotes::after,#footer::after{clear:both} |
| #content{margin-top:1.25em} |
| #content::before{content:none} |
| #header>h1:first-child{color:rgba(0,0,0,.85);margin-top:2.25rem;margin-bottom:0} |
| #header>h1:first-child+#toc{margin-top:8px;border-top:1px solid #dddddf} |
| #header>h1:only-child{border-bottom:1px solid #dddddf;padding-bottom:8px} |
| #header .details{border-bottom:1px solid #dddddf;line-height:1.45;padding-top:.25em;padding-bottom:.25em;padding-left:.25em;color:rgba(0,0,0,.6);display:flex;flex-flow:row wrap} |
| #header .details span:first-child{margin-left:-.125em} |
| #header .details span.email a{color:rgba(0,0,0,.85)} |
| #header .details br{display:none} |
| #header .details br+span::before{content:"\00a0\2013\00a0"} |
| #header .details br+span.author::before{content:"\00a0\22c5\00a0";color:rgba(0,0,0,.85)} |
| #header .details br+span#revremark::before{content:"\00a0|\00a0"} |
| #header #revnumber{text-transform:capitalize} |
| #header #revnumber::after{content:"\00a0"} |
| #content>h1:first-child:not([class]){color:rgba(0,0,0,.85);border-bottom:1px solid #dddddf;padding-bottom:8px;margin-top:0;padding-top:1rem;margin-bottom:1.25rem} |
| #toc{border-bottom:1px solid #e7e7e9;padding-bottom:.5em} |
| #toc>ul{margin-left:.125em} |
| #toc ul.sectlevel0>li>a{font-style:italic} |
| #toc ul.sectlevel0 ul.sectlevel1{margin:.5em 0} |
| #toc ul{font-family:"Open Sans","DejaVu Sans",sans-serif;list-style-type:none} |
| #toc li{line-height:1.3334;margin-top:.3334em} |
| #toc a{text-decoration:none} |
| #toc a:active{text-decoration:underline} |
| #toctitle{color:#7a2518;font-size:1.2em} |
| @media screen and (min-width:768px){#toctitle{font-size:1.375em} |
| body.toc2{padding-left:15em;padding-right:0} |
| body.toc2 #header>h1:nth-last-child(2){border-bottom:1px solid #dddddf;padding-bottom:8px} |
| #toc.toc2{margin-top:0!important;background:#f8f8f7;position:fixed;width:15em;left:0;top:0;border-right:1px solid #e7e7e9;border-top-width:0!important;border-bottom-width:0!important;z-index:1000;padding:1.25em 1em;height:100%;overflow:auto} |
| #toc.toc2 #toctitle{margin-top:0;margin-bottom:.8rem;font-size:1.2em} |
| #toc.toc2>ul{font-size:.9em;margin-bottom:0} |
| #toc.toc2 ul ul{margin-left:0;padding-left:1em} |
| #toc.toc2 ul.sectlevel0 ul.sectlevel1{padding-left:0;margin-top:.5em;margin-bottom:.5em} |
| body.toc2.toc-right{padding-left:0;padding-right:15em} |
| body.toc2.toc-right #toc.toc2{border-right-width:0;border-left:1px solid #e7e7e9;left:auto;right:0}} |
| @media screen and (min-width:1280px){body.toc2{padding-left:20em;padding-right:0} |
| #toc.toc2{width:20em} |
| #toc.toc2 #toctitle{font-size:1.375em} |
| #toc.toc2>ul{font-size:.95em} |
| #toc.toc2 ul ul{padding-left:1.25em} |
| body.toc2.toc-right{padding-left:0;padding-right:20em}} |
| #content #toc{border:1px solid #e0e0dc;margin-bottom:1.25em;padding:1.25em;background:#f8f8f7;border-radius:4px} |
| #content #toc>:first-child{margin-top:0} |
| #content #toc>:last-child{margin-bottom:0} |
| #footer{max-width:none;background:rgba(0,0,0,.8);padding:1.25em} |
| #footer-text{color:hsla(0,0%,100%,.8);line-height:1.44} |
| #content{margin-bottom:.625em} |
| .sect1{padding-bottom:.625em} |
| @media screen and (min-width:768px){#content{margin-bottom:1.25em} |
| .sect1{padding-bottom:1.25em}} |
| .sect1:last-child{padding-bottom:0} |
| .sect1+.sect1{border-top:1px solid #e7e7e9} |
| #content h1>a.anchor,h2>a.anchor,h3>a.anchor,#toctitle>a.anchor,.sidebarblock>.content>.title>a.anchor,h4>a.anchor,h5>a.anchor,h6>a.anchor{position:absolute;z-index:1001;width:1.5ex;margin-left:-1.5ex;display:block;text-decoration:none!important;visibility:hidden;text-align:center;font-weight:400} |
| #content h1>a.anchor::before,h2>a.anchor::before,h3>a.anchor::before,#toctitle>a.anchor::before,.sidebarblock>.content>.title>a.anchor::before,h4>a.anchor::before,h5>a.anchor::before,h6>a.anchor::before{content:"\00A7";font-size:.85em;display:block;padding-top:.1em} |
| #content h1:hover>a.anchor,#content h1>a.anchor:hover,h2:hover>a.anchor,h2>a.anchor:hover,h3:hover>a.anchor,#toctitle:hover>a.anchor,.sidebarblock>.content>.title:hover>a.anchor,h3>a.anchor:hover,#toctitle>a.anchor:hover,.sidebarblock>.content>.title>a.anchor:hover,h4:hover>a.anchor,h4>a.anchor:hover,h5:hover>a.anchor,h5>a.anchor:hover,h6:hover>a.anchor,h6>a.anchor:hover{visibility:visible} |
| #content h1>a.link,h2>a.link,h3>a.link,#toctitle>a.link,.sidebarblock>.content>.title>a.link,h4>a.link,h5>a.link,h6>a.link{color:#ba3925;text-decoration:none} |
| #content h1>a.link:hover,h2>a.link:hover,h3>a.link:hover,#toctitle>a.link:hover,.sidebarblock>.content>.title>a.link:hover,h4>a.link:hover,h5>a.link:hover,h6>a.link:hover{color:#a53221} |
| details,.audioblock,.imageblock,.literalblock,.listingblock,.stemblock,.videoblock{margin-bottom:1.25em} |
| details{margin-left:1.25rem} |
| details>summary{cursor:pointer;display:block;position:relative;line-height:1.6;margin-bottom:.625rem;outline:none;-webkit-tap-highlight-color:transparent} |
| details>summary::-webkit-details-marker{display:none} |
| details>summary::before{content:"";border:solid transparent;border-left:solid;border-width:.3em 0 .3em .5em;position:absolute;top:.5em;left:-1.25rem;transform:translateX(15%)} |
| details[open]>summary::before{border:solid transparent;border-top:solid;border-width:.5em .3em 0;transform:translateY(15%)} |
| details>summary::after{content:"";width:1.25rem;height:1em;position:absolute;top:.3em;left:-1.25rem} |
| .admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{text-rendering:optimizeLegibility;text-align:left;font-family:"Noto Serif","DejaVu Serif",serif;font-size:1rem;font-style:italic} |
| table.tableblock.fit-content>caption.title{white-space:nowrap;width:0} |
| .paragraph.lead>p,#preamble>.sectionbody>[class=paragraph]:first-of-type p{font-size:1.21875em;line-height:1.6;color:rgba(0,0,0,.85)} |
| .admonitionblock>table{border-collapse:separate;border:0;background:none;width:100%} |
| .admonitionblock>table td.icon{text-align:center;width:80px} |
| .admonitionblock>table td.icon img{max-width:none} |
| .admonitionblock>table td.icon .title{font-weight:bold;font-family:"Open Sans","DejaVu Sans",sans-serif;text-transform:uppercase} |
| .admonitionblock>table td.content{padding-left:1.125em;padding-right:1.25em;border-left:1px solid #dddddf;color:rgba(0,0,0,.6);word-wrap:anywhere} |
| .admonitionblock>table td.content>:last-child>:last-child{margin-bottom:0} |
| .exampleblock>.content{border:1px solid #e6e6e6;margin-bottom:1.25em;padding:1.25em;background:#fff;border-radius:4px} |
| .sidebarblock{border:1px solid #dbdbd6;margin-bottom:1.25em;padding:1.25em;background:#f3f3f2;border-radius:4px} |
| .sidebarblock>.content>.title{color:#7a2518;margin-top:0;text-align:center} |
| .exampleblock>.content>:first-child,.sidebarblock>.content>:first-child{margin-top:0} |
| .exampleblock>.content>:last-child,.exampleblock>.content>:last-child>:last-child,.exampleblock>.content .olist>ol>li:last-child>:last-child,.exampleblock>.content .ulist>ul>li:last-child>:last-child,.exampleblock>.content .qlist>ol>li:last-child>:last-child,.sidebarblock>.content>:last-child,.sidebarblock>.content>:last-child>:last-child,.sidebarblock>.content .olist>ol>li:last-child>:last-child,.sidebarblock>.content .ulist>ul>li:last-child>:last-child,.sidebarblock>.content .qlist>ol>li:last-child>:last-child{margin-bottom:0} |
| .literalblock pre,.listingblock>.content>pre{border-radius:4px;overflow-x:auto;padding:1em;font-size:.8125em} |
| @media screen and (min-width:768px){.literalblock pre,.listingblock>.content>pre{font-size:.90625em}} |
| @media screen and (min-width:1280px){.literalblock pre,.listingblock>.content>pre{font-size:1em}} |
| .literalblock pre,.listingblock>.content>pre:not(.highlight),.listingblock>.content>pre[class=highlight],.listingblock>.content>pre[class^="highlight "]{background:#f7f7f8} |
| .literalblock.output pre{color:#f7f7f8;background:rgba(0,0,0,.9)} |
| .listingblock>.content{position:relative} |
| .listingblock code[data-lang]::before{display:none;content:attr(data-lang);position:absolute;font-size:.75em;top:.425rem;right:.5rem;line-height:1;text-transform:uppercase;color:inherit;opacity:.5} |
| .listingblock:hover code[data-lang]::before{display:block} |
| .listingblock.terminal pre .command::before{content:attr(data-prompt);padding-right:.5em;color:inherit;opacity:.5} |
| .listingblock.terminal pre .command:not([data-prompt])::before{content:"$"} |
| .listingblock pre.highlightjs{padding:0} |
| .listingblock pre.highlightjs>code{padding:1em;border-radius:4px} |
| .listingblock pre.prettyprint{border-width:0} |
| .prettyprint{background:#f7f7f8} |
| pre.prettyprint .linenums{line-height:1.45;margin-left:2em} |
| pre.prettyprint li{background:none;list-style-type:inherit;padding-left:0} |
| pre.prettyprint li code[data-lang]::before{opacity:1} |
| pre.prettyprint li:not(:first-child) code[data-lang]::before{display:none} |
| table.linenotable{border-collapse:separate;border:0;margin-bottom:0;background:none} |
| table.linenotable td[class]{color:inherit;vertical-align:top;padding:0;line-height:inherit;white-space:normal} |
| table.linenotable td.code{padding-left:.75em} |
| table.linenotable td.linenos,pre.pygments .linenos{border-right:1px solid;opacity:.35;padding-right:.5em;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none} |
| pre.pygments span.linenos{display:inline-block;margin-right:.75em} |
| .quoteblock{margin:0 1em 1.25em 1.5em;display:table} |
| .quoteblock:not(.excerpt)>.title{margin-left:-1.5em;margin-bottom:.75em} |
| .quoteblock blockquote,.quoteblock p{color:rgba(0,0,0,.85);font-size:1.15rem;line-height:1.75;word-spacing:.1em;letter-spacing:0;font-style:italic;text-align:justify} |
| .quoteblock blockquote{margin:0;padding:0;border:0} |
| .quoteblock blockquote::before{content:"\201c";float:left;font-size:2.75em;font-weight:bold;line-height:.6em;margin-left:-.6em;color:#7a2518;text-shadow:0 1px 2px rgba(0,0,0,.1)} |
| .quoteblock blockquote>.paragraph:last-child p{margin-bottom:0} |
| .quoteblock .attribution{margin-top:.75em;margin-right:.5ex;text-align:right} |
| .verseblock{margin:0 1em 1.25em} |
| .verseblock pre{font-family:"Open Sans","DejaVu Sans",sans-serif;font-size:1.15rem;color:rgba(0,0,0,.85);font-weight:300;text-rendering:optimizeLegibility} |
| .verseblock pre strong{font-weight:400} |
| .verseblock .attribution{margin-top:1.25rem;margin-left:.5ex} |
| .quoteblock .attribution,.verseblock .attribution{font-size:.9375em;line-height:1.45;font-style:italic} |
| .quoteblock .attribution br,.verseblock .attribution br{display:none} |
| .quoteblock .attribution cite,.verseblock .attribution cite{display:block;letter-spacing:-.025em;color:rgba(0,0,0,.6)} |
| .quoteblock.abstract blockquote::before,.quoteblock.excerpt blockquote::before,.quoteblock .quoteblock blockquote::before{display:none} |
| .quoteblock.abstract blockquote,.quoteblock.abstract p,.quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{line-height:1.6;word-spacing:0} |
| .quoteblock.abstract{margin:0 1em 1.25em;display:block} |
| .quoteblock.abstract>.title{margin:0 0 .375em;font-size:1.15em;text-align:center} |
| .quoteblock.excerpt>blockquote,.quoteblock .quoteblock{padding:0 0 .25em 1em;border-left:.25em solid #dddddf} |
| .quoteblock.excerpt,.quoteblock .quoteblock{margin-left:0} |
| .quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{color:inherit;font-size:1.0625rem} |
| .quoteblock.excerpt .attribution,.quoteblock .quoteblock .attribution{color:inherit;font-size:.85rem;text-align:left;margin-right:0} |
| p.tableblock:last-child{margin-bottom:0} |
| td.tableblock>.content{margin-bottom:1.25em;word-wrap:anywhere} |
| td.tableblock>.content>:last-child{margin-bottom:-1.25em} |
| table.tableblock,th.tableblock,td.tableblock{border:0 solid #dedede} |
| table.grid-all>*>tr>*{border-width:1px} |
| table.grid-cols>*>tr>*{border-width:0 1px} |
| table.grid-rows>*>tr>*{border-width:1px 0} |
| table.frame-all{border-width:1px} |
| table.frame-ends{border-width:1px 0} |
| table.frame-sides{border-width:0 1px} |
| table.frame-none>colgroup+*>:first-child>*,table.frame-sides>colgroup+*>:first-child>*{border-top-width:0} |
| table.frame-none>:last-child>:last-child>*,table.frame-sides>:last-child>:last-child>*{border-bottom-width:0} |
| table.frame-none>*>tr>:first-child,table.frame-ends>*>tr>:first-child{border-left-width:0} |
| table.frame-none>*>tr>:last-child,table.frame-ends>*>tr>:last-child{border-right-width:0} |
| table.stripes-all>*>tr,table.stripes-odd>*>tr:nth-of-type(odd),table.stripes-even>*>tr:nth-of-type(even),table.stripes-hover>*>tr:hover{background:#f8f8f7} |
| th.halign-left,td.halign-left{text-align:left} |
| th.halign-right,td.halign-right{text-align:right} |
| th.halign-center,td.halign-center{text-align:center} |
| th.valign-top,td.valign-top{vertical-align:top} |
| th.valign-bottom,td.valign-bottom{vertical-align:bottom} |
| th.valign-middle,td.valign-middle{vertical-align:middle} |
| table thead th,table tfoot th{font-weight:bold} |
| tbody tr th{background:#f7f8f7} |
| tbody tr th,tbody tr th p,tfoot tr th,tfoot tr th p{color:rgba(0,0,0,.8);font-weight:bold} |
| p.tableblock>code:only-child{background:none;padding:0} |
| p.tableblock{font-size:1em} |
| ol{margin-left:1.75em} |
| ul li ol{margin-left:1.5em} |
| dl dd{margin-left:1.125em} |
| dl dd:last-child,dl dd:last-child>:last-child{margin-bottom:0} |
| li p,ul dd,ol dd,.olist .olist,.ulist .ulist,.ulist .olist,.olist .ulist{margin-bottom:.625em} |
| ul.checklist,ul.none,ol.none,ul.no-bullet,ol.no-bullet,ol.unnumbered,ul.unstyled,ol.unstyled{list-style-type:none} |
| ul.no-bullet,ol.no-bullet,ol.unnumbered{margin-left:.625em} |
| ul.unstyled,ol.unstyled{margin-left:0} |
| li>p:empty:only-child::before{content:"";display:inline-block} |
| ul.checklist>li>p:first-child{margin-left:-1em} |
| ul.checklist>li>p:first-child>.fa-square-o:first-child,ul.checklist>li>p:first-child>.fa-check-square-o:first-child{width:1.25em;font-size:.8em;position:relative;bottom:.125em} |
| ul.checklist>li>p:first-child>input[type=checkbox]:first-child{margin-right:.25em} |
| ul.inline{display:flex;flex-flow:row wrap;list-style:none;margin:0 0 .625em -1.25em} |
| ul.inline>li{margin-left:1.25em} |
| .unstyled dl dt{font-weight:400;font-style:normal} |
| ol.arabic{list-style-type:decimal} |
| ol.decimal{list-style-type:decimal-leading-zero} |
| 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} |
| ol.lowergreek{list-style-type:lower-greek} |
| .hdlist>table,.colist>table{border:0;background:none} |
| .hdlist>table>tbody>tr,.colist>table>tbody>tr{background:none} |
| td.hdlist1,td.hdlist2{vertical-align:top;padding:0 .625em} |
| td.hdlist1{font-weight:bold;padding-bottom:1.25em} |
| td.hdlist2{word-wrap:anywhere} |
| .literalblock+.colist,.listingblock+.colist{margin-top:-.5em} |
| .colist td:not([class]):first-child{padding:.4em .75em 0;line-height:1;vertical-align:top} |
| .colist td:not([class]):first-child img{max-width:none} |
| .colist td:not([class]):last-child{padding:.25em 0} |
| .thumb,.th{line-height:0;display:inline-block;border:4px solid #fff;box-shadow:0 0 0 1px #ddd} |
| .imageblock.left{margin:.25em .625em 1.25em 0} |
| .imageblock.right{margin:.25em 0 1.25em .625em} |
| .imageblock>.title{margin-bottom:0} |
| .imageblock.thumb,.imageblock.th{border-width:6px} |
| .imageblock.thumb>.title,.imageblock.th>.title{padding:0 .125em} |
| .image.left,.image.right{margin-top:.25em;margin-bottom:.25em;display:inline-block;line-height:0} |
| .image.left{margin-right:.625em} |
| .image.right{margin-left:.625em} |
| a.image{text-decoration:none;display:inline-block} |
| a.image object{pointer-events:none} |
| sup.footnote,sup.footnoteref{font-size:.875em;position:static;vertical-align:super} |
| sup.footnote a,sup.footnoteref a{text-decoration:none} |
| sup.footnote a:active,sup.footnoteref a:active,#footnotes .footnote a:first-of-type:active{text-decoration:underline} |
| #footnotes{padding-top:.75em;padding-bottom:.75em;margin-bottom:.625em} |
| #footnotes hr{width:20%;min-width:6.25em;margin:-.25em 0 .75em;border-width:1px 0 0} |
| #footnotes .footnote{padding:0 .375em 0 .225em;line-height:1.3334;font-size:.875em;margin-left:1.2em;margin-bottom:.2em} |
| #footnotes .footnote a:first-of-type{font-weight:bold;text-decoration:none;margin-left:-1.05em} |
| #footnotes .footnote:last-of-type{margin-bottom:0} |
| #content #footnotes{margin-top:-.625em;margin-bottom:0;padding:.75em 0} |
| div.unbreakable{page-break-inside:avoid} |
| .big{font-size:larger} |
| .small{font-size:smaller} |
| .underline{text-decoration:underline} |
| .overline{text-decoration:overline} |
| .line-through{text-decoration:line-through} |
| .aqua{color:#00bfbf} |
| .aqua-background{background:#00fafa} |
| .black{color:#000} |
| .black-background{background:#000} |
| .blue{color:#0000bf} |
| .blue-background{background:#0000fa} |
| .fuchsia{color:#bf00bf} |
| .fuchsia-background{background:#fa00fa} |
| .gray{color:#606060} |
| .gray-background{background:#7d7d7d} |
| .green{color:#006000} |
| .green-background{background:#007d00} |
| .lime{color:#00bf00} |
| .lime-background{background:#00fa00} |
| .maroon{color:#600000} |
| .maroon-background{background:#7d0000} |
| .navy{color:#000060} |
| .navy-background{background:#00007d} |
| .olive{color:#606000} |
| .olive-background{background:#7d7d00} |
| .purple{color:#600060} |
| .purple-background{background:#7d007d} |
| .red{color:#bf0000} |
| .red-background{background:#fa0000} |
| .silver{color:#909090} |
| .silver-background{background:#bcbcbc} |
| .teal{color:#006060} |
| .teal-background{background:#007d7d} |
| .white{color:#bfbfbf} |
| .white-background{background:#fafafa} |
| .yellow{color:#bfbf00} |
| .yellow-background{background:#fafa00} |
| span.icon>.fa{cursor:default} |
| a span.icon>.fa{cursor:inherit} |
| .admonitionblock td.icon [class^="fa icon-"]{font-size:2.5em;text-shadow:1px 1px 2px rgba(0,0,0,.5);cursor:default} |
| .admonitionblock td.icon .icon-note::before{content:"\f05a";color:#19407c} |
| .admonitionblock td.icon .icon-tip::before{content:"\f0eb";text-shadow:1px 1px 2px rgba(155,155,0,.8);color:#111} |
| .admonitionblock td.icon .icon-warning::before{content:"\f071";color:#bf6900} |
| .admonitionblock td.icon .icon-caution::before{content:"\f06d";color:#bf3400} |
| .admonitionblock td.icon .icon-important::before{content:"\f06a";color:#bf0000} |
| .conum[data-value]{display:inline-block;color:#fff!important;background:rgba(0,0,0,.8);border-radius:50%;text-align:center;font-size:.75em;width:1.67em;height:1.67em;line-height:1.67em;font-family:"Open Sans","DejaVu Sans",sans-serif;font-style:normal;font-weight:bold} |
| .conum[data-value] *{color:#fff!important} |
| .conum[data-value]+b{display:none} |
| .conum[data-value]::after{content:attr(data-value)} |
| pre .conum[data-value]{position:relative;top:-.125em} |
| b.conum *{color:inherit!important} |
| .conum:not([data-value]):empty{display:none} |
| dt,th.tableblock,td.content,div.footnote{text-rendering:optimizeLegibility} |
| h1,h2,p,td.content,span.alt,summary{letter-spacing:-.01em} |
| p strong,td.content strong,div.footnote strong{letter-spacing:-.005em} |
| p,blockquote,dt,td.content,td.hdlist1,span.alt,summary{font-size:1.0625rem} |
| p{margin-bottom:1.25rem} |
| .sidebarblock p,.sidebarblock dt,.sidebarblock td.content,p.tableblock{font-size:1em} |
| .exampleblock>.content{background:#fffef7;border-color:#e0e0dc;box-shadow:0 1px 4px #e0e0dc} |
| .print-only{display:none!important} |
| @page{margin:1.25cm .75cm} |
| @media print{*{box-shadow:none!important;text-shadow:none!important} |
| html{font-size:80%} |
| a{color:inherit!important;text-decoration:underline!important} |
| a.bare,a[href^="#"],a[href^="mailto:"]{text-decoration:none!important} |
| a[href^="http:"]:not(.bare)::after,a[href^="https:"]:not(.bare)::after{content:"(" attr(href) ")";display:inline-block;font-size:.875em;padding-left:.25em} |
| abbr[title]{border-bottom:1px dotted} |
| abbr[title]::after{content:" (" attr(title) ")"} |
| pre,blockquote,tr,img,object,svg{page-break-inside:avoid} |
| thead{display:table-header-group} |
| svg{max-width:100%} |
| p,blockquote,dt,td.content{font-size:1em;orphans:3;widows:3} |
| h2,h3,#toctitle,.sidebarblock>.content>.title{page-break-after:avoid} |
| #header,#content,#footnotes,#footer{max-width:none} |
| #toc,.sidebarblock,.exampleblock>.content{background:none!important} |
| #toc{border-bottom:1px solid #dddddf!important;padding-bottom:0!important} |
| body.book #header{text-align:center} |
| body.book #header>h1:first-child{border:0!important;margin:2.5em 0 1em} |
| body.book #header .details{border:0!important;display:block;padding:0!important} |
| body.book #header .details span:first-child{margin-left:0!important} |
| body.book #header .details br{display:block} |
| body.book #header .details br+span::before{content:none!important} |
| body.book #toc{border:0!important;text-align:left!important;padding:0!important;margin:0!important} |
| body.book #toc,body.book #preamble,body.book h1.sect0,body.book .sect1>h2{page-break-before:always} |
| .listingblock code[data-lang]::before{display:block} |
| #footer{padding:0 .9375em} |
| .hide-on-print{display:none!important} |
| .print-only{display:block!important} |
| .hide-for-print{display:none!important} |
| .show-for-print{display:inherit!important}} |
| @media amzn-kf8,print{#header>h1:first-child{margin-top:1.25rem} |
| .sect1{padding:0!important} |
| .sect1+.sect1{border:0} |
| #footer{background:none} |
| #footer-text{color:rgba(0,0,0,.6);font-size:.9em}} |
| @media amzn-kf8{#header,#content,#footnotes,#footer{padding:0}} |
| </style> |
| </head> |
| <body class="article"> |
| <div id="header"> |
| </div> |
| <div id="content"> |
| <div class="sect1"> |
| <h2 id="_reftable">reftable</h2> |
| <div class="sectionbody"> |
| <div class="sect2"> |
| <h3 id="_overview">Overview</h3> |
| <div class="sect3"> |
| <h4 id="_problem_statement">Problem statement</h4> |
| <div class="paragraph"> |
| <p>Some repositories contain a lot of references (e.g. android at 866k, |
| rails at 31k). The existing packed-refs format takes up a lot of space |
| (e.g. 62M), and does not scale with additional references. Lookup of a |
| single reference requires linearly scanning the file.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Atomic pushes modifying multiple references require copying the entire |
| packed-refs file, which can be a considerable amount of data moved |
| (e.g. 62M in, 62M out) for even small transactions (2 refs modified).</p> |
| </div> |
| <div class="paragraph"> |
| <p>Repositories with many loose references occupy a large number of disk |
| blocks from the local file system, as each reference is its own file |
| storing 41 bytes (and another file for the corresponding reflog). This |
| negatively affects the number of inodes available when a large number of |
| repositories are stored on the same filesystem. Readers can be penalized |
| due to the larger number of syscalls required to traverse and read the |
| <code>$GIT_DIR/refs</code> directory.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_objectives">Objectives</h4> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p>Near constant time lookup for any single reference, even when the |
| repository is cold and not in process or kernel cache.</p> |
| </li> |
| <li> |
| <p>Near constant time verification if an object name is referred to by at least |
| one reference (for allow-tip-sha1-in-want).</p> |
| </li> |
| <li> |
| <p>Efficient enumeration of an entire namespace, such as <code>refs/tags/</code>.</p> |
| </li> |
| <li> |
| <p>Support atomic push with <code>O</code>(<code>size_of_update</code>) operations.</p> |
| </li> |
| <li> |
| <p>Combine reflog storage with ref storage for small transactions.</p> |
| </li> |
| <li> |
| <p>Separate reflog storage for base refs and historical logs.</p> |
| </li> |
| </ul> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_description">Description</h4> |
| <div class="paragraph"> |
| <p>A reftable file is a portable binary file format customized for |
| reference storage. References are sorted, enabling linear scans, binary |
| search lookup, and range scans.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Storage in the file is organized into variable sized blocks. Prefix |
| compression is used within a single block to reduce disk space. Block |
| size and alignment are tunable by the writer.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_performance">Performance</h4> |
| <div class="paragraph"> |
| <p>Space used, packed-refs vs. reftable:</p> |
| </div> |
| <table class="tableblock frame-all grid-all stretch"> |
| <colgroup> |
| <col style="width: 16.6666%;"/> |
| <col style="width: 16.6666%;"/> |
| <col style="width: 16.6666%;"/> |
| <col style="width: 16.6666%;"/> |
| <col style="width: 16.6666%;"/> |
| <col style="width: 16.667%;"/> |
| </colgroup> |
| <thead> |
| <tr> |
| <th class="tableblock halign-left valign-top">repository</th> |
| <th class="tableblock halign-right valign-top">packed-refs</th> |
| <th class="tableblock halign-right valign-top">reftable</th> |
| <th class="tableblock halign-right valign-top">% original</th> |
| <th class="tableblock halign-right valign-top">avg ref</th> |
| <th class="tableblock halign-right valign-top">avg obj</th> |
| </tr> |
| </thead> |
| <tbody> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">android</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">62.2 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">36.1 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">58.0%</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">33 bytes</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">5 bytes</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">rails</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">1.8 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">1.1 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">57.7%</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">29 bytes</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">4 bytes</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">git</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">78.7 K</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">48.1 K</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">61.0%</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">50 bytes</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">4 bytes</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">git (heads)</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">332 b</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">269 b</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">81.0%</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">33 bytes</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">0 bytes</p></td> |
| </tr> |
| </tbody> |
| </table> |
| <div class="paragraph"> |
| <p>Scan (read 866k refs), by reference name lookup (single ref from 866k |
| refs), and by SHA-1 lookup (refs with that SHA-1, from 866k refs):</p> |
| </div> |
| <table class="tableblock frame-all grid-all stretch"> |
| <colgroup> |
| <col style="width: 20%;"/> |
| <col style="width: 20%;"/> |
| <col style="width: 20%;"/> |
| <col style="width: 20%;"/> |
| <col style="width: 20%;"/> |
| </colgroup> |
| <thead> |
| <tr> |
| <th class="tableblock halign-left valign-top">format</th> |
| <th class="tableblock halign-right valign-top">cache</th> |
| <th class="tableblock halign-right valign-top">scan</th> |
| <th class="tableblock halign-right valign-top">by name</th> |
| <th class="tableblock halign-right valign-top">by SHA-1</th> |
| </tr> |
| </thead> |
| <tbody> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">packed-refs</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">cold</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">402 ms</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">409,660.1 usec</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">412,535.8 usec</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">packed-refs</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">hot</p></td> |
| <td class="tableblock halign-right valign-top"></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">6,844.6 usec</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">20,110.1 usec</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">reftable</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">cold</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">112 ms</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">33.9 usec</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">323.2 usec</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">reftable</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">hot</p></td> |
| <td class="tableblock halign-right valign-top"></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">20.2 usec</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">320.8 usec</p></td> |
| </tr> |
| </tbody> |
| </table> |
| <div class="paragraph"> |
| <p>Space used for 149,932 log entries for 43,061 refs, reflog vs. reftable:</p> |
| </div> |
| <table class="tableblock frame-all grid-all stretch"> |
| <colgroup> |
| <col style="width: 33.3333%;"/> |
| <col style="width: 33.3333%;"/> |
| <col style="width: 33.3334%;"/> |
| </colgroup> |
| <thead> |
| <tr> |
| <th class="tableblock halign-left valign-top">format</th> |
| <th class="tableblock halign-right valign-top">size</th> |
| <th class="tableblock halign-right valign-top">avg entry</th> |
| </tr> |
| </thead> |
| <tbody> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">$GIT_DIR/logs</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">173 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">1209 bytes</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-left valign-top"><p class="tableblock">reftable</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">5 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">37 bytes</p></td> |
| </tr> |
| </tbody> |
| </table> |
| </div> |
| </div> |
| <div class="sect2"> |
| <h3 id="_details">Details</h3> |
| <div class="sect3"> |
| <h4 id="_peeling">Peeling</h4> |
| <div class="paragraph"> |
| <p>References stored in a reftable are peeled, a record for an annotated |
| (or signed) tag records both the tag object, and the object it refers |
| to. This is analogous to storage in the packed-refs format.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_reference_name_encoding">Reference name encoding</h4> |
| <div class="paragraph"> |
| <p>Reference names are an uninterpreted sequence of bytes that must pass |
| <a href="../git-check-ref-format.html">git-check-ref-format(1)</a> as a valid reference name.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_key_unicity">Key unicity</h4> |
| <div class="paragraph"> |
| <p>Each entry must have a unique key; repeated keys are disallowed.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_network_byte_order">Network byte order</h4> |
| <div class="paragraph"> |
| <p>All multi-byte, fixed width fields are in network byte order.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_varint_encoding">Varint encoding</h4> |
| <div class="paragraph"> |
| <p>Varint encoding is identical to the ofs-delta encoding method used |
| within pack files.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Decoder works as follows:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>val = buf[ptr] & 0x7f |
| while (buf[ptr] & 0x80) { |
| ptr++ |
| val = ((val + 1) << 7) | (buf[ptr] & 0x7f) |
| }</pre> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_ordering">Ordering</h4> |
| <div class="paragraph"> |
| <p>Blocks are lexicographically ordered by their first reference.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_directoryfile_conflicts">Directory/file conflicts</h4> |
| <div class="paragraph"> |
| <p>The reftable format accepts both <code>refs/heads/foo</code> and |
| <code>refs/heads/foo/bar</code> as distinct references.</p> |
| </div> |
| <div class="paragraph"> |
| <p>This property is useful for retaining log records in reftable, but may |
| confuse versions of Git using <code>$GIT_DIR/refs</code> directory tree to maintain |
| references. Users of reftable may choose to continue to reject <code>foo</code> and |
| <code>foo/bar</code> type conflicts to prevent problems for peers.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect2"> |
| <h3 id="_file_format">File format</h3> |
| <div class="sect3"> |
| <h4 id="_structure">Structure</h4> |
| <div class="paragraph"> |
| <p>A reftable file has the following high-level structure:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>first_block { |
| header |
| first_ref_block |
| } |
| ref_block* |
| ref_index* |
| obj_block* |
| obj_index* |
| log_block* |
| log_index* |
| footer</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>A log-only file omits the <code>ref_block</code>, <code>ref_index</code>, <code>obj_block</code> and |
| <code>obj_index</code> sections, containing only the file header and log block:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>first_block { |
| header |
| } |
| log_block* |
| log_index* |
| footer</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>In a log-only file, the first log block immediately follows the file |
| header, without padding to block alignment.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_block_size">Block size</h4> |
| <div class="paragraph"> |
| <p>The file’s block size is arbitrarily determined by the writer, and does |
| not have to be a power of 2. The block size must be larger than the |
| longest reference name or log entry used in the repository, as |
| references cannot span blocks.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Powers of two that are friendly to the virtual memory system or |
| filesystem (such as 4k or 8k) are recommended. Larger sizes (64k) can |
| yield better compression, with a possible increased cost incurred by |
| readers during access.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The largest block size is <code>16777215</code> bytes (15.99 MiB).</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_block_alignment">Block alignment</h4> |
| <div class="paragraph"> |
| <p>Writers may choose to align blocks at multiples of the block size by |
| including <code>padding</code> filled with NUL bytes at the end of a block to round |
| out to the chosen alignment. When alignment is used, writers must |
| specify the alignment with the file header’s <code>block_size</code> field.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Block alignment is not required by the file format. Unaligned files must |
| set <code>block_size</code> <code>=</code> <code>0</code> in the file header, and omit <code>padding</code>. Unaligned |
| files with more than one ref block must include the <a href="#Ref-index">ref |
| index</a> to support fast lookup. Readers must be able to read both aligned |
| and non-aligned files.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Very small files (e.g. a single ref block) may omit <code>padding</code> and the ref |
| index to reduce total file size.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_header_version_1">Header (version 1)</h4> |
| <div class="paragraph"> |
| <p>A 24-byte header appears at the beginning of the file:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>'REFT' |
| uint8( version_number = 1 ) |
| uint24( block_size ) |
| uint64( min_update_index ) |
| uint64( max_update_index )</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Aligned files must specify <code>block_size</code> to configure readers with the |
| expected block alignment. Unaligned files must set <code>block_size</code> <code>=</code> <code>0</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>min_update_index</code> and <code>max_update_index</code> describe bounds for the |
| <code>update_index</code> field of all log records in this file. When reftables are |
| used in a stack for <a href="#Update-transactions">transactions</a>, these |
| fields can order the files such that the prior file’s |
| <code>max_update_index</code> <code>+</code> <code>1</code> is the next file’s <code>min_update_index</code>.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_header_version_2">Header (version 2)</h4> |
| <div class="paragraph"> |
| <p>A 28-byte header appears at the beginning of the file:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>'REFT' |
| uint8( version_number = 2 ) |
| uint24( block_size ) |
| uint64( min_update_index ) |
| uint64( max_update_index ) |
| uint32( hash_id )</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>The header is identical to <code>version_number=1</code>, with the 4-byte hash ID |
| ("sha1" for SHA1 and "s256" for SHA-256) appended to the header.</p> |
| </div> |
| <div class="paragraph"> |
| <p>For maximum backward compatibility, it is recommended to use version 1 when |
| writing SHA1 reftables.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_first_ref_block">First ref block</h4> |
| <div class="paragraph"> |
| <p>The first ref block shares the same block as the file header, and is 24 |
| bytes smaller than all other blocks in the file. The first block |
| immediately begins after the file header, at position 24.</p> |
| </div> |
| <div class="paragraph"> |
| <p>If the first block is a log block (a log-only file), its block header |
| begins immediately at position 24.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_ref_block_format">Ref block format</h4> |
| <div class="paragraph"> |
| <p>A ref block is written as:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>'r' |
| uint24( block_len ) |
| ref_record+ |
| uint24( restart_offset )+ |
| uint16( restart_count ) |
| |
| padding?</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Blocks begin with <code>block_type</code> <code>=</code> 'r' and a 3-byte <code>block_len</code> which |
| encodes the number of bytes in the block up to, but not including the |
| optional <code>padding</code>. This is always less than or equal to the file’s |
| block size. In the first ref block, <code>block_len</code> includes 24 bytes for |
| the file header.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The 2-byte <code>restart_count</code> stores the number of entries in the |
| <code>restart_offset</code> list, which must not be empty. Readers can use |
| <code>restart_count</code> to binary search between restarts before starting a |
| linear scan.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Exactly <code>restart_count</code> 3-byte <code>restart_offset</code> values precede the |
| <code>restart_count</code>. Offsets are relative to the start of the block and |
| refer to the first byte of any <code>ref_record</code> whose name has not been |
| prefix compressed. Entries in the <code>restart_offset</code> list must be sorted, |
| ascending. Readers can start linear scans from any of these records.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A variable number of <code>ref_record</code> fill the middle of the block, |
| describing reference names and values. The format is described below.</p> |
| </div> |
| <div class="paragraph"> |
| <p>As the first ref block shares the first file block with the file header, |
| all <code>restart_offset</code> in the first block are relative to the start of the |
| file (position 0), and include the file header. This forces the first |
| <code>restart_offset</code> to be <code>28</code>.</p> |
| </div> |
| <div class="sect4"> |
| <h5 id="_ref_record">ref record</h5> |
| <div class="paragraph"> |
| <p>A <code>ref_record</code> describes a single reference, storing both the name and |
| its value(s). Records are formatted as:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>varint( prefix_length ) |
| varint( (suffix_length << 3) | value_type ) |
| suffix |
| varint( update_index_delta ) |
| value?</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>prefix_length</code> field specifies how many leading bytes of the prior |
| reference record’s name should be copied to obtain this reference’s |
| name. This must be 0 for the first reference in any block, and also must |
| be 0 for any <code>ref_record</code> whose offset is listed in the <code>restart_offset</code> |
| table at the end of the block.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Recovering a reference name from any <code>ref_record</code> is a simple concat:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>this_name = prior_name[0..prefix_length] + suffix</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>suffix_length</code> value provides the number of bytes available in |
| <code>suffix</code> to copy from <code>suffix</code> to complete the reference name.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>update_index</code> that last modified the reference can be obtained by |
| adding <code>update_index_delta</code> to the <code>min_update_index</code> from the file |
| header: <code>min_update_index</code> <code>+</code> <code>update_index_delta</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>value</code> follows. Its format is determined by <code>value_type</code>, one of |
| the following:</p> |
| </div> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p><code>0x0</code>: deletion; no value data (see transactions, below)</p> |
| </li> |
| <li> |
| <p><code>0x1</code>: one object name; value of the ref</p> |
| </li> |
| <li> |
| <p><code>0x2</code>: two object names; value of the ref, peeled target</p> |
| </li> |
| <li> |
| <p><code>0x3</code>: symbolic reference: <code>varint</code>( <code>target_len</code> ) <code>target</code></p> |
| </li> |
| </ul> |
| </div> |
| <div class="paragraph"> |
| <p>Symbolic references use <code>0x3</code>, followed by the complete name of the |
| reference target. No compression is applied to the target name.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Types <code>0x4</code><code>..</code><code>0x7</code> are reserved for future use.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_ref_index">Ref index</h4> |
| <div class="paragraph"> |
| <p>The ref index stores the name of the last reference from every ref block |
| in the file, enabling reduced disk seeks for lookups. Any reference can |
| be found by searching the index, identifying the containing block, and |
| searching within that block.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The index may be organized into a multi-level index, where the 1st level |
| index block points to additional ref index blocks (2nd level), which may |
| in turn point to either additional index blocks (e.g. 3rd level) or ref |
| blocks (leaf level). Disk reads required to access a ref go up with |
| higher index levels. Multi-level indexes may be required to ensure no |
| single index block exceeds the file format’s max block size of |
| <code>16777215</code> bytes (15.99 MiB). To achieve constant O(1) disk seeks for |
| lookups the index must be a single level, which is permitted to exceed |
| the file’s configured block size, but not the format’s max block size of |
| 15.99 MiB.</p> |
| </div> |
| <div class="paragraph"> |
| <p>If present, the ref index block(s) appears after the last ref block.</p> |
| </div> |
| <div class="paragraph"> |
| <p>If there are at least 4 ref blocks, a ref index block should be written |
| to improve lookup times. Cold reads using the index require 2 disk reads |
| (read index, read block), and binary searching < 4 blocks also requires |
| ⇐ 2 reads. Omitting the index block from smaller files saves space.</p> |
| </div> |
| <div class="paragraph"> |
| <p>If the file is unaligned and contains more than one ref block, the ref |
| index must be written.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Index block format:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>'i' |
| uint24( block_len ) |
| index_record+ |
| uint24( restart_offset )+ |
| uint16( restart_count ) |
| |
| padding?</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>The index blocks begin with <code>block_type</code> <code>=</code> 'i' and a 3-byte <code>block_len</code> |
| which encodes the number of bytes in the block, up to but not including |
| the optional <code>padding</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>restart_offset</code> and <code>restart_count</code> fields are identical in format, |
| meaning and usage as in ref blocks.</p> |
| </div> |
| <div class="paragraph"> |
| <p>To reduce the number of reads required for random access in very large |
| files the index block may be larger than other blocks. However, readers |
| must hold the entire index in memory to benefit from this, so it’s a |
| time-space tradeoff in both file size and reader memory.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Increasing the file’s block size decreases the index size. Alternatively |
| a multi-level index may be used, keeping index blocks within the file’s |
| block size, but increasing the number of blocks that need to be |
| accessed.</p> |
| </div> |
| <div class="sect4"> |
| <h5 id="_index_record">index record</h5> |
| <div class="paragraph"> |
| <p>An index record describes the last entry in another block. Index records |
| are written as:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>varint( prefix_length ) |
| varint( (suffix_length << 3) | 0 ) |
| suffix |
| varint( block_position )</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Index records use prefix compression exactly like <code>ref_record</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Index records store <code>block_position</code> after the suffix, specifying the |
| absolute position in bytes (from the start of the file) of the block |
| that ends with this reference. Readers can seek to <code>block_position</code> to |
| begin reading the block header.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Readers must examine the block header at <code>block_position</code> to determine |
| if the next block is another level index block, or the leaf-level ref |
| block.</p> |
| </div> |
| </div> |
| <div class="sect4"> |
| <h5 id="_reading_the_index">Reading the index</h5> |
| <div class="paragraph"> |
| <p>Readers loading the ref index must first read the footer (below) to |
| obtain <code>ref_index_position</code>. If not present, the position will be 0. The |
| <code>ref_index_position</code> is for the 1st level root of the ref index.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_obj_block_format">Obj block format</h4> |
| <div class="paragraph"> |
| <p>Object blocks are optional. Writers may choose to omit object blocks, |
| especially if readers will not use the object name to ref mapping.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Object blocks use unique, abbreviated 2-31 byte object name keys, mapping to |
| ref blocks containing references pointing to that object directly, or as |
| the peeled value of an annotated tag. Like ref blocks, object blocks use |
| the file’s standard block size. The abbreviation length is available in |
| the footer as <code>obj_id_len</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>To save space in small files, object blocks may be omitted if the ref |
| index is not present, as brute force search will only need to read a few |
| ref blocks. When missing, readers should brute force a linear search of |
| all references to lookup by object name.</p> |
| </div> |
| <div class="paragraph"> |
| <p>An object block is written as:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>'o' |
| uint24( block_len ) |
| obj_record+ |
| uint24( restart_offset )+ |
| uint16( restart_count ) |
| |
| padding?</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Fields are identical to ref block. Binary search using the restart table |
| works the same as in reference blocks.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Because object names are abbreviated by writers to the shortest unique |
| abbreviation within the reftable, obj key lengths have a variable length. Their |
| length must be at least 2 bytes. Readers must compare only for common prefix |
| match within an obj block or obj index.</p> |
| </div> |
| <div class="sect4"> |
| <h5 id="_obj_record">obj record</h5> |
| <div class="paragraph"> |
| <p>An <code>obj_record</code> describes a single object abbreviation, and the blocks |
| containing references using that unique abbreviation:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>varint( prefix_length ) |
| varint( (suffix_length << 3) | cnt_3 ) |
| suffix |
| varint( cnt_large )? |
| varint( position_delta )*</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Like in reference blocks, abbreviations are prefix compressed within an |
| obj block. On large reftables with many unique objects, higher block |
| sizes (64k), and higher restart interval (128), a <code>prefix_length</code> of 2 |
| or 3 and <code>suffix_length</code> of 3 may be common in obj records (unique |
| abbreviation of 5-6 raw bytes, 10-12 hex digits).</p> |
| </div> |
| <div class="paragraph"> |
| <p>Each record contains <code>position_count</code> number of positions for matching |
| ref blocks. For 1-7 positions the count is stored in <code>cnt_3</code>. When |
| <code>cnt_3</code> <code>=</code> <code>0</code> the actual count follows in a varint, <code>cnt_large</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The use of <code>cnt_3</code> bets most objects are pointed to by only a single |
| reference, some may be pointed to by a couple of references, and very |
| few (if any) are pointed to by more than 7 references.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A special case exists when <code>cnt_3</code> <code>=</code> <code>0</code> and <code>cnt_large</code> <code>=</code> <code>0</code>: there are no |
| <code>position_delta</code>, but at least one reference starts with this |
| abbreviation. A reader that needs exact reference names must scan all |
| references to find which specific references have the desired object. |
| Writers should use this format when the <code>position_delta</code> list would have |
| overflowed the file’s block size due to a high number of references |
| pointing to the same object.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The first <code>position_delta</code> is the position from the start of the file. |
| Additional <code>position_delta</code> entries are sorted ascending and relative to |
| the prior entry, e.g. a reader would perform:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>pos = position_delta[0] |
| prior = pos |
| for (j = 1; j < position_count; j++) { |
| pos = prior + position_delta[j] |
| prior = pos |
| }</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>With a position in hand, a reader must linearly scan the ref block, |
| starting from the first <code>ref_record</code>, testing each reference’s object names |
| (for <code>value_type</code> <code>=</code> <code>0x1</code> or <code>0x2</code>) for full equality. Faster searching by |
| object name within a single ref block is not supported by the reftable format. |
| Smaller block sizes reduce the number of candidates this step must |
| consider.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_obj_index">Obj index</h4> |
| <div class="paragraph"> |
| <p>The obj index stores the abbreviation from the last entry for every obj |
| block in the file, enabling reduced disk seeks for all lookups. It is |
| formatted exactly the same as the ref index, but refers to obj blocks.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The obj index should be present if obj blocks are present, as obj blocks |
| should only be written in larger files.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Readers loading the obj index must first read the footer (below) to |
| obtain <code>obj_index_position</code>. If not present, the position will be 0.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_log_block_format">Log block format</h4> |
| <div class="paragraph"> |
| <p>Unlike ref and obj blocks, log blocks are always unaligned.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Log blocks are variable in size, and do not match the <code>block_size</code> |
| specified in the file header or footer. Writers should choose an |
| appropriate buffer size to prepare a log block for deflation, such as |
| <code>2</code> <code>*</code> <code>block_size</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A log block is written as:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>'g' |
| uint24( block_len ) |
| zlib_deflate { |
| log_record+ |
| uint24( restart_offset )+ |
| uint16( restart_count ) |
| }</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Log blocks look similar to ref blocks, except <code>block_type</code> <code>=</code> 'g'.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The 4-byte block header is followed by the deflated block contents using |
| zlib deflate. The <code>block_len</code> in the header is the inflated size |
| (including 4-byte block header), and should be used by readers to |
| preallocate the inflation output buffer. A log block’s <code>block_len</code> may |
| exceed the file’s block size.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Offsets within the log block (e.g. <code>restart_offset</code>) still include the |
| 4-byte header. Readers may prefer prefixing the inflation output buffer |
| with the 4-byte header.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Within the deflate container, a variable number of <code>log_record</code> describe |
| reference changes. The log record format is described below. See ref |
| block format (above) for a description of <code>restart_offset</code> and |
| <code>restart_count</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Because log blocks have no alignment or padding between blocks, readers |
| must keep track of the bytes consumed by the inflater to know where the |
| next log block begins.</p> |
| </div> |
| <div class="sect4"> |
| <h5 id="_log_record">log record</h5> |
| <div class="paragraph"> |
| <p>Log record keys are structured as:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>ref_name '\0' reverse_int64( update_index )</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>where <code>update_index</code> is the unique transaction identifier. The |
| <code>update_index</code> field must be unique within the scope of a <code>ref_name</code>. |
| See the update transactions section below for further details.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>reverse_int64</code> function inverses the value so lexicographical |
| ordering the network byte order encoding sorts the more recent records |
| with higher <code>update_index</code> values first:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>reverse_int64(int64 t) { |
| return 0xffffffffffffffff - t; |
| }</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Log records have a similar starting structure to ref and index records, |
| utilizing the same prefix compression scheme applied to the log record |
| key described above.</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre> varint( prefix_length ) |
| varint( (suffix_length << 3) | log_type ) |
| suffix |
| log_data { |
| old_id |
| new_id |
| varint( name_length ) name |
| varint( email_length ) email |
| varint( time_seconds ) |
| sint16( tz_offset ) |
| varint( message_length ) message |
| }?</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Log record entries use <code>log_type</code> to indicate what follows:</p> |
| </div> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p><code>0x0</code>: deletion; no log data.</p> |
| </li> |
| <li> |
| <p><code>0x1</code>: standard git reflog data using <code>log_data</code> above.</p> |
| </li> |
| </ul> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>log_type</code> <code>=</code> <code>0x0</code> is mostly useful for <code>git</code> <code>stash</code> <code>drop</code>, removing an |
| entry from the reflog of <code>refs/stash</code> in a transaction file (below), |
| without needing to rewrite larger files. Readers reading a stack of |
| reflogs must treat this as a deletion.</p> |
| </div> |
| <div class="paragraph"> |
| <p>For <code>log_type</code> <code>=</code> <code>0x1</code>, the <code>log_data</code> section follows |
| <a href="../git-update-ref.html">git-update-ref(1)</a> logging and includes:</p> |
| </div> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p>two object names (old id, new id)</p> |
| </li> |
| <li> |
| <p>varint string of committer’s name</p> |
| </li> |
| <li> |
| <p>varint string of committer’s email</p> |
| </li> |
| <li> |
| <p>varint time in seconds since epoch (Jan 1, 1970)</p> |
| </li> |
| <li> |
| <p>2-byte timezone offset in minutes (signed)</p> |
| </li> |
| <li> |
| <p>varint string of message</p> |
| </li> |
| </ul> |
| </div> |
| <div class="paragraph"> |
| <p><code>tz_offset</code> is the absolute number of minutes from GMT the committer was |
| at the time of the update. For example <code>GMT-0800</code> is encoded in reftable |
| as <code>sint16</code>(<code>-480</code>) and <code>GMT+0230</code> is <code>sint16</code>(<code>150</code>).</p> |
| </div> |
| <div class="paragraph"> |
| <p>The committer email does not contain < or >, it’s the value normally |
| found between the <> in a git commit object header.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The <code>message_length</code> may be 0, in which case there was no message |
| supplied for the update.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Contrary to traditional reflog (which is a file), renames are encoded as |
| a combination of ref deletion and ref creation. A deletion is a log |
| record with a zero new_id, and a creation is a log record with a zero old_id.</p> |
| </div> |
| </div> |
| <div class="sect4"> |
| <h5 id="_reading_the_log">Reading the log</h5> |
| <div class="paragraph"> |
| <p>Readers accessing the log must first read the footer (below) to |
| determine the <code>log_position</code>. The first block of the log begins at |
| <code>log_position</code> bytes since the start of the file. The <code>log_position</code> is |
| not block aligned.</p> |
| </div> |
| </div> |
| <div class="sect4"> |
| <h5 id="_importing_logs">Importing logs</h5> |
| <div class="paragraph"> |
| <p>When importing from <code>$GIT_DIR/logs</code> writers should globally order all |
| log records roughly by timestamp while preserving file order, and assign |
| unique, increasing <code>update_index</code> values for each log line. Newer log |
| records get higher <code>update_index</code> values.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Although an import may write only a single reftable file, the reftable |
| file must span many unique <code>update_index</code>, as each log line requires its |
| own <code>update_index</code> to preserve semantics.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_log_index">Log index</h4> |
| <div class="paragraph"> |
| <p>The log index stores the log key |
| (<code>refname</code> <code>\0</code> <code>reverse_int64</code>(<code>update_index</code>)) for the last log record of |
| every log block in the file, supporting bounded-time lookup.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A log index block must be written if 2 or more log blocks are written to |
| the file. If present, the log index appears after the last log block. |
| There is no padding used to align the log index to block alignment.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Log index format is identical to ref index, except the keys are 9 bytes |
| longer to include '\0' and the 8-byte <code>reverse_int64</code>(<code>update_index</code>). |
| Records use <code>block_position</code> to refer to the start of a log block.</p> |
| </div> |
| <div class="sect4"> |
| <h5 id="_reading_the_index_2">Reading the index</h5> |
| <div class="paragraph"> |
| <p>Readers loading the log index must first read the footer (below) to |
| obtain <code>log_index_position</code>. If not present, the position will be 0.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_footer">Footer</h4> |
| <div class="paragraph"> |
| <p>After the last block of the file, a file footer is written. It begins |
| like the file header, but is extended with additional data.</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre> HEADER |
| |
| uint64( ref_index_position ) |
| uint64( (obj_position << 5) | obj_id_len ) |
| uint64( obj_index_position ) |
| |
| uint64( log_position ) |
| uint64( log_index_position ) |
| |
| uint32( CRC-32 of above )</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>If a section is missing (e.g. ref index) the corresponding position |
| field (e.g. <code>ref_index_position</code>) will be 0.</p> |
| </div> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p><code>obj_position</code>: byte position for the first obj block.</p> |
| </li> |
| <li> |
| <p><code>obj_id_len</code>: number of bytes used to abbreviate object names in |
| obj blocks.</p> |
| </li> |
| <li> |
| <p><code>log_position</code>: byte position for the first log block.</p> |
| </li> |
| <li> |
| <p><code>ref_index_position</code>: byte position for the start of the ref index.</p> |
| </li> |
| <li> |
| <p><code>obj_index_position</code>: byte position for the start of the obj index.</p> |
| </li> |
| <li> |
| <p><code>log_index_position</code>: byte position for the start of the log index.</p> |
| </li> |
| </ul> |
| </div> |
| <div class="paragraph"> |
| <p>The size of the footer is 68 bytes for version 1, and 72 bytes for |
| version 2.</p> |
| </div> |
| <div class="sect4"> |
| <h5 id="_reading_the_footer">Reading the footer</h5> |
| <div class="paragraph"> |
| <p>Readers must first read the file start to determine the version |
| number. Then they seek to <code>file_length</code> <code>-</code> <code>FOOTER_LENGTH</code> to access the |
| footer. A trusted external source (such as <code>stat</code>(<code>2</code>)) is necessary to |
| obtain <code>file_length</code>. When reading the footer, readers must verify:</p> |
| </div> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p>4-byte magic is correct</p> |
| </li> |
| <li> |
| <p>1-byte version number is recognized</p> |
| </li> |
| <li> |
| <p>4-byte CRC-32 matches the other 64 bytes (including magic, and |
| version)</p> |
| </li> |
| </ul> |
| </div> |
| <div class="paragraph"> |
| <p>Once verified, the other fields of the footer can be accessed.</p> |
| </div> |
| </div> |
| <div class="sect4"> |
| <h5 id="_empty_tables">Empty tables</h5> |
| <div class="paragraph"> |
| <p>A reftable may be empty. In this case, the file starts with a header |
| and is immediately followed by a footer.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_binary_search">Binary search</h4> |
| <div class="paragraph"> |
| <p>Binary search within a block is supported by the <code>restart_offset</code> fields |
| at the end of the block. Readers can binary search through the restart |
| table to locate between which two restart points the sought reference or |
| key should appear.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Each record identified by a <code>restart_offset</code> stores the complete key in |
| the <code>suffix</code> field of the record, making the compare operation during |
| binary search straightforward.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Once a restart point lexicographically before the sought reference has |
| been identified, readers can linearly scan through the following record |
| entries to locate the sought record, terminating if the current record |
| sorts after (and therefore the sought key is not present).</p> |
| </div> |
| <div class="sect4"> |
| <h5 id="_restart_point_selection">Restart point selection</h5> |
| <div class="paragraph"> |
| <p>Writers determine the restart points at file creation. The process is |
| arbitrary, but every 16 or 64 records is recommended. Every 16 may be |
| more suitable for smaller block sizes (4k or 8k), every 64 for larger |
| block sizes (64k).</p> |
| </div> |
| <div class="paragraph"> |
| <p>More frequent restart points reduces prefix compression and increases |
| space consumed by the restart table, both of which increase file size.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Less frequent restart points makes prefix compression more effective, |
| decreasing overall file size, with increased penalties for readers |
| walking through more records after the binary search step.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A maximum of <code>65535</code> restart points per block is supported.</p> |
| </div> |
| </div> |
| </div> |
| </div> |
| <div class="sect2"> |
| <h3 id="_considerations">Considerations</h3> |
| <div class="sect3"> |
| <h4 id="_lightweight_refs_dominate">Lightweight refs dominate</h4> |
| <div class="paragraph"> |
| <p>The reftable format assumes the vast majority of references are single |
| object names valued with common prefixes, such as Gerrit Code Review’s |
| <code>refs/changes/</code> namespace, GitHub’s <code>refs/pulls/</code> namespace, or many |
| lightweight tags in the <code>refs/tags/</code> namespace.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Annotated tags storing the peeled object cost an additional object name per |
| reference.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_low_overhead">Low overhead</h4> |
| <div class="paragraph"> |
| <p>A reftable with very few references (e.g. git.git with 5 heads) is 269 |
| bytes for reftable, vs. 332 bytes for packed-refs. This supports |
| reftable scaling down for transaction logs (below).</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_block_size_2">Block size</h4> |
| <div class="paragraph"> |
| <p>For a Gerrit Code Review type repository with many change refs, larger |
| block sizes (64 KiB) and less frequent restart points (every 64) yield |
| better compression due to more references within the block compressing |
| against the prior reference.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Larger block sizes reduce the index size, as the reftable will require |
| fewer blocks to store the same number of references.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_minimal_disk_seeks">Minimal disk seeks</h4> |
| <div class="paragraph"> |
| <p>Assuming the index block has been loaded into memory, binary searching |
| for any single reference requires exactly 1 disk seek to load the |
| containing block.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_scans_and_lookups_dominate">Scans and lookups dominate</h4> |
| <div class="paragraph"> |
| <p>Scanning all references and lookup by name (or namespace such as |
| <code>refs/heads/</code>) are the most common activities performed on repositories. |
| Object names are stored directly with references to optimize this use case.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_logs_are_infrequently_read">Logs are infrequently read</h4> |
| <div class="paragraph"> |
| <p>Logs are infrequently accessed, but can be large. Deflating log blocks |
| saves disk space, with some increased penalty at read time.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Logs are stored in an isolated section from refs, reducing the burden on |
| reference readers that want to ignore logs. Further, historical logs can |
| be isolated into log-only files.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_logs_are_read_backwards">Logs are read backwards</h4> |
| <div class="paragraph"> |
| <p>Logs are frequently accessed backwards (most recent N records for master |
| to answer <code>master@</code>{4}), so log records are grouped by reference, and |
| sorted descending by update index.</p> |
| </div> |
| </div> |
| </div> |
| <div class="sect2"> |
| <h3 id="_repository_format">Repository format</h3> |
| <div class="sect3"> |
| <h4 id="_version_1">Version 1</h4> |
| <div class="paragraph"> |
| <p>A repository must set its <code>$GIT_DIR/config</code> to configure reftable:</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>[core] |
| repositoryformatversion = 1 |
| [extensions] |
| refStorage = reftable</pre> |
| </div> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_layout">Layout</h4> |
| <div class="paragraph"> |
| <p>A collection of reftable files are stored in the <code>$GIT_DIR/reftable/</code> directory. |
| Their names should have a random element, such that each filename is globally |
| unique; this helps avoid spurious failures on Windows, where open files cannot |
| be removed or overwritten. It suggested to use |
| <code>$</code>{min_update_index}-${max_update_index}-${random}.<code>ref</code> as a naming convention.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Log-only files use the .<code>log</code> extension, while ref-only and mixed ref |
| and log files use .<code>ref</code>. extension.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The stack ordering file is <code>$GIT_DIR/reftable/tables.list</code> and lists the |
| current files, one per line, in order, from oldest (base) to newest |
| (most recent):</p> |
| </div> |
| <div class="literalblock"> |
| <div class="content"> |
| <pre>$ cat .git/reftable/tables.list |
| 00000001-00000001-RANDOM1.log |
| 00000002-00000002-RANDOM2.ref |
| 00000003-00000003-RANDOM3.ref</pre> |
| </div> |
| </div> |
| <div class="paragraph"> |
| <p>Readers must read <code>$GIT_DIR/reftable/tables.list</code> to determine which |
| files are relevant right now, and search through the stack in reverse |
| order (last reftable is examined first).</p> |
| </div> |
| <div class="paragraph"> |
| <p>Reftable files not listed in <code>tables.list</code> may be new (and about to be |
| added to the stack by the active writer), or ancient and ready to be |
| pruned.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_backward_compatibility">Backward compatibility</h4> |
| <div class="paragraph"> |
| <p>Older clients should continue to recognize the directory as a git |
| repository so they don’t look for an enclosing repository in parent |
| directories. To this end, a reftable-enabled repository must contain the |
| following dummy files</p> |
| </div> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p>.<code>git/HEAD</code>, a regular file containing <code>ref:</code> <code>refs/heads/.invalid</code>.</p> |
| </li> |
| <li> |
| <p>.<code>git/refs/</code>, a directory</p> |
| </li> |
| <li> |
| <p>.<code>git/refs/heads</code>, a regular file</p> |
| </li> |
| </ul> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_readers">Readers</h4> |
| <div class="paragraph"> |
| <p>Readers can obtain a consistent snapshot of the reference space by |
| following:</p> |
| </div> |
| <div class="olist arabic"> |
| <ol class="arabic"> |
| <li> |
| <p>Open and read the <code>tables.list</code> file.</p> |
| </li> |
| <li> |
| <p>Open each of the reftable files that it mentions.</p> |
| </li> |
| <li> |
| <p>If any of the files is missing, goto 1.</p> |
| </li> |
| <li> |
| <p>Read from the now-open files as long as necessary.</p> |
| </li> |
| </ol> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_update_transactions">Update transactions</h4> |
| <div class="paragraph"> |
| <p>Although reftables are immutable, mutations are supported by writing a |
| new reftable and atomically appending it to the stack:</p> |
| </div> |
| <div class="olist arabic"> |
| <ol class="arabic"> |
| <li> |
| <p>Acquire <code>tables.list.lock</code>.</p> |
| </li> |
| <li> |
| <p>Read <code>tables.list</code> to determine current reftables.</p> |
| </li> |
| <li> |
| <p>Select <code>update_index</code> to be most recent file’s |
| <code>max_update_index</code> <code>+</code> <code>1</code>.</p> |
| </li> |
| <li> |
| <p>Prepare temp reftable <code>tmp_XXXXXX</code>, including log entries.</p> |
| </li> |
| <li> |
| <p>Rename <code>tmp_XXXXXX</code> to <code>$</code>{update_index}-${update_index}-${random}.<code>ref</code>.</p> |
| </li> |
| <li> |
| <p>Copy <code>tables.list</code> to <code>tables.list.lock</code>, appending file from (5).</p> |
| </li> |
| <li> |
| <p>Rename <code>tables.list.lock</code> to <code>tables.list</code>.</p> |
| </li> |
| </ol> |
| </div> |
| <div class="paragraph"> |
| <p>During step 4 the new file’s <code>min_update_index</code> and <code>max_update_index</code> |
| are both set to the <code>update_index</code> selected by step 3. All log records |
| for the transaction use the same <code>update_index</code> in their keys. This |
| enables later correlation of which references were updated by the same |
| transaction.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Because a single <code>tables.list.lock</code> file is used to manage locking, the |
| repository is single-threaded for writers. Writers may have to busy-spin |
| (with backoff) around creating <code>tables.list.lock</code>, for up to an |
| acceptable wait period, aborting if the repository is too busy to |
| mutate. Application servers wrapped around repositories (e.g. Gerrit |
| Code Review) can layer their own lock/wait queue to improve fairness to |
| writers.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_reference_deletions">Reference deletions</h4> |
| <div class="paragraph"> |
| <p>Deletion of any reference can be explicitly stored by setting the <code>type</code> |
| to <code>0x0</code> and omitting the <code>value</code> field of the <code>ref_record</code>. This serves |
| as a tombstone, overriding any assertions about the existence of the |
| reference from earlier files in the stack.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_compaction">Compaction</h4> |
| <div class="paragraph"> |
| <p>A partial stack of reftables can be compacted by merging references |
| using a straightforward merge join across reftables, selecting the most |
| recent value for output, and omitting deleted references that do not |
| appear in remaining, lower reftables.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A compacted reftable should set its <code>min_update_index</code> to the smallest |
| of the input files' <code>min_update_index</code>, and its <code>max_update_index</code> |
| likewise to the largest input <code>max_update_index</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>For sake of illustration, assume the stack currently consists of |
| reftable files (from oldest to newest): A, B, C, and D. The compactor is |
| going to compact B and C, leaving A and D alone.</p> |
| </div> |
| <div class="olist arabic"> |
| <ol class="arabic"> |
| <li> |
| <p>Obtain lock <code>tables.list.lock</code> and read the <code>tables.list</code> file.</p> |
| </li> |
| <li> |
| <p>Obtain locks <code>B.lock</code> and <code>C.lock</code>. Ownership of these locks |
| prevents other processes from trying to compact these files.</p> |
| </li> |
| <li> |
| <p>Release <code>tables.list.lock</code>.</p> |
| </li> |
| <li> |
| <p>Compact <code>B</code> and <code>C</code> into a temp file |
| <code>$</code>{min_update_index}-${max_update_index}_XXXXXX.</p> |
| </li> |
| <li> |
| <p>Reacquire lock <code>tables.list.lock</code>.</p> |
| </li> |
| <li> |
| <p>Verify that <code>B</code> and <code>C</code> are still in the stack, in that order. This |
| should always be the case, assuming that other processes are adhering to |
| the locking protocol.</p> |
| </li> |
| <li> |
| <p>Rename <code>$</code>{min_update_index}-${max_update_index}_XXXXXX to |
| <code>$</code>{min_update_index}-${max_update_index}-${random}.<code>ref</code>.</p> |
| </li> |
| <li> |
| <p>Write the new stack to <code>tables.list.lock</code>, replacing <code>B</code> and <code>C</code> |
| with the file from (4).</p> |
| </li> |
| <li> |
| <p>Rename <code>tables.list.lock</code> to <code>tables.list</code>.</p> |
| </li> |
| <li> |
| <p>Delete <code>B</code> and <code>C</code>, perhaps after a short sleep to avoid forcing |
| readers to backtrack.</p> |
| </li> |
| </ol> |
| </div> |
| <div class="paragraph"> |
| <p>This strategy permits compactions to proceed independently of updates.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Each reftable (compacted or not) is uniquely identified by its name, so |
| open reftables can be cached by their name.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_windows">Windows</h4> |
| <div class="paragraph"> |
| <p>On windows, and other systems that do not allow deleting or renaming to open |
| files, compaction may succeed, but other readers may prevent obsolete tables |
| from being deleted.</p> |
| </div> |
| <div class="paragraph"> |
| <p>On these platforms, the following strategy can be followed: on closing a |
| reftable stack, reload <code>tables.list</code>, and delete any tables no longer mentioned |
| in <code>tables.list</code>.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Irregular program exit may still leave about unused files. In this case, a |
| cleanup operation should proceed as follows:</p> |
| </div> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p>take a lock <code>tables.list.lock</code> to prevent concurrent modifications</p> |
| </li> |
| <li> |
| <p>refresh the reftable stack, by reading <code>tables.list</code></p> |
| </li> |
| <li> |
| <p>for each <code>*.ref</code> file, remove it if</p> |
| <div class="ulist"> |
| <ul> |
| <li> |
| <p>it is not mentioned in <code>tables.list</code>, and</p> |
| </li> |
| <li> |
| <p>its max update_index is not beyond the max update_index of the stack</p> |
| </li> |
| </ul> |
| </div> |
| </li> |
| </ul> |
| </div> |
| </div> |
| </div> |
| <div class="sect2"> |
| <h3 id="_alternatives_considered">Alternatives considered</h3> |
| <div class="sect3"> |
| <h4 id="_bzip_packed_refs">bzip packed-refs</h4> |
| <div class="paragraph"> |
| <p><code>bzip2</code> can significantly shrink a large packed-refs file (e.g. 62 MiB |
| compresses to 23 MiB, 37%). However the bzip format does not support |
| random access to a single reference. Readers must inflate and discard |
| while performing a linear scan.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Breaking packed-refs into chunks (individually compressing each chunk) |
| would reduce the amount of data a reader must inflate, but still leaves |
| the problem of indexing chunks to support readers efficiently locating |
| the correct chunk.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Given the compression achieved by reftable’s encoding, it does not seem |
| necessary to add the complexity of bzip/gzip/zlib.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_michael_haggertys_alternate_format">Michael Haggerty’s alternate format</h4> |
| <div class="paragraph"> |
| <p>Michael Haggerty proposed |
| <a href="https://lore.kernel.org/git/CAMy9T_HCnyc1g8XWOOWhe7nN0aEFyyBskV2aOMb_fe%2BwGvEJ7A%40mail.gmail.com/">an |
| alternate</a> format to reftable on the Git mailing list. This format uses |
| smaller chunks, without the restart table, and avoids block alignment |
| with padding. Reflog entries immediately follow each ref, and are thus |
| interleaved between refs.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Performance testing indicates reftable is faster for lookups (51% |
| faster, 11.2 usec vs. 5.4 usec), although reftable produces a slightly |
| larger file (+ ~3.2%, 28.3M vs 29.2M):</p> |
| </div> |
| <table class="tableblock frame-all grid-all stretch"> |
| <colgroup> |
| <col style="width: 25%;"/> |
| <col style="width: 25%;"/> |
| <col style="width: 25%;"/> |
| <col style="width: 25%;"/> |
| </colgroup> |
| <thead> |
| <tr> |
| <th class="tableblock halign-right valign-top">format</th> |
| <th class="tableblock halign-right valign-top">size</th> |
| <th class="tableblock halign-right valign-top">seek cold</th> |
| <th class="tableblock halign-right valign-top">seek hot</th> |
| </tr> |
| </thead> |
| <tbody> |
| <tr> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">mh-alt</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">28.3 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">23.4 usec</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">11.2 usec</p></td> |
| </tr> |
| <tr> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">reftable</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">29.2 M</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">19.9 usec</p></td> |
| <td class="tableblock halign-right valign-top"><p class="tableblock">5.4 usec</p></td> |
| </tr> |
| </tbody> |
| </table> |
| </div> |
| <div class="sect3"> |
| <h4 id="_jgit_ketch_reftree">JGit Ketch RefTree</h4> |
| <div class="paragraph"> |
| <p><a href="https://dev.eclipse.org/mhonarc/lists/jgit-dev/msg03073.html">JGit Ketch</a> |
| proposed |
| <a href="https://lore.kernel.org/git/CAJo%3DhJvnAPNAdDcAAwAvU9C4RVeQdoS3Ev9WTguHx4fD0V_nOg%40mail.gmail.com/">RefTree</a>, |
| an encoding of references inside Git tree objects stored as part of the |
| repository’s object database.</p> |
| </div> |
| <div class="paragraph"> |
| <p>The RefTree format adds additional load on the object database storage |
| layer (more loose objects, more objects in packs), and relies heavily on |
| the packer’s delta compression to save space. Namespaces which are flat |
| (e.g. thousands of tags in refs/tags) initially create very large loose |
| objects, and so RefTree does not address the problem of copying many |
| references to modify a handful.</p> |
| </div> |
| <div class="paragraph"> |
| <p>Flat namespaces are not efficiently searchable in RefTree, as tree |
| objects in canonical formatting cannot be binary searched. This fails |
| the need to handle a large number of references in a single namespace, |
| such as GitHub’s <code>refs/pulls</code>, or a project with many tags.</p> |
| </div> |
| </div> |
| <div class="sect3"> |
| <h4 id="_lmdb">LMDB</h4> |
| <div class="paragraph"> |
| <p>David Turner proposed |
| <a href="https://lore.kernel.org/git/1455772670-21142-26-git-send-email-dturner@twopensource.com/">using |
| LMDB</a>, as LMDB is lightweight (64k of runtime code) and GPL-compatible |
| license.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A downside of LMDB is its reliance on a single C implementation. This |
| makes embedding inside JGit (a popular reimplementation of Git) |
| difficult, and hoisting onto virtual storage (for JGit DFS) virtually |
| impossible.</p> |
| </div> |
| <div class="paragraph"> |
| <p>A common format that can be supported by all major Git implementations |
| (git-core, JGit, libgit2) is strongly preferred.</p> |
| </div> |
| </div> |
| </div> |
| </div> |
| </div> |
| </div> |
| <div id="footer"> |
| <div id="footer-text"> |
| Last updated 2025-06-20 18:10:42 -0700 |
| </div> |
| </div> |
| </body> |
| </html> |
