man7/gitpacking.7

   1 '\" t
   2 .\"     Title: gitpacking
   3 .\"    Author: [FIXME: author] [see http://www.docbook.org/tdg5/en/html/author]
   4 .\" Generator: DocBook XSL Stylesheets v1.79.2 <http://docbook.sf.net/>
   5 .\"      Date: 2024-09-10
   6 .\"    Manual: Git Manual
   7 .\"    Source: Git 2.46.0.551.gc5ee8f2d1c
   8 .\"  Language: English
   9 .\"
  10 .TH "GITPACKING" "7" "2024-09-10" "Git 2\&.46\&.0\&.551\&.gc5ee8f" "Git Manual"
  11 .\" -----------------------------------------------------------------
  12 .\" * Define some portability stuff
  13 .\" -----------------------------------------------------------------
  14 .\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  15 .\" http://bugs.debian.org/507673
  16 .\" http://lists.gnu.org/archive/html/groff/2009-02/msg00013.html
  17 .\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  18 .ie \n(.g .ds Aq \(aq
  19 .el       .ds Aq '
  20 .\" -----------------------------------------------------------------
  21 .\" * set default formatting
  22 .\" -----------------------------------------------------------------
  23 .\" disable hyphenation
  24 .nh
  25 .\" disable justification (adjust text to left margin only)
  26 .ad l
  27 .\" -----------------------------------------------------------------
  28 .\" * MAIN CONTENT STARTS HERE *
  29 .\" -----------------------------------------------------------------
  30 .SH "NAME"
  31 gitpacking \- Advanced concepts related to packing in Git
  32 .SH "SYNOPSIS"
  33 .sp
  34 gitpacking
  35 .SH "DESCRIPTION"
  36 .sp
  37 This document aims to describe some advanced concepts related to packing in Git\&.
  38 .sp
  39 Many concepts are currently described scattered between manual pages of various Git commands, including \fBgit-pack-objects\fR(1), \fBgit-repack\fR(1), and others, as well as \fBgitformat-pack\fR(5), and parts of the \fBDocumentation/technical\fR tree\&.
  40 .sp
  41 There are many aspects of packing in Git that are not covered in this document that instead live in the aforementioned areas\&. Over time, those scattered bits may coalesce into this document\&.
  42 .SH "PSEUDO\-MERGE BITMAPS"
  43 .if n \{\
  44 .sp
  45 .\}
  46 .RS 4
  47 .it 1 an-trap
  48 .nr an-no-space-flag 1
  49 .nr an-break-flag 1
  50 .br
  51 .ps +1
  52 \fBNote\fR
  53 .ps -1
  54 .br
  55 .sp
  56 Pseudo\-merge bitmaps are considered an experimental feature, so the configuration and many of the ideas are subject to change\&.
  57 .sp .5v
  58 .RE
  59 .SS "Background"
  60 .sp
  61 Reachability bitmaps are most efficient when we have on\-disk stored bitmaps for one or more of the starting points of a traversal\&. For this reason, Git prefers storing bitmaps for commits at the tips of refs, because traversals tend to start with those points\&.
  62 .sp
  63 But if you have a large number of refs, it\(cqs not feasible to store a bitmap for \fIevery\fR ref tip\&. It takes up space, and just OR\-ing all of those bitmaps together is expensive\&.
  64 .sp
  65 One way we can deal with that is to create bitmaps that represent \fIgroups\fR of refs\&. When a traversal asks about the entire group, then we can use this single bitmap instead of considering each ref individually\&. Because these bitmaps represent the set of objects which would be reachable in a hypothetical merge of all of the commits, we call them pseudo\-merge bitmaps\&.
  66 .SS "Overview"
  67 .sp
  68 A "pseudo\-merge bitmap" is used to refer to a pair of bitmaps, as follows:
  69 .PP
  70 Commit bitmap
  71 .RS 4
  72 A bitmap whose set bits describe the set of commits included in the pseudo\-merge\(cqs "merge" bitmap (as below)\&.
  73 .RE
  74 .PP
  75 Merge bitmap
  76 .RS 4
  77 A bitmap whose set bits describe the reachability closure over the set of commits in the pseudo\-merge\(cqs "commits" bitmap (as above)\&. An identical bitmap would be generated for an octopus merge with the same set of parents as described in the commits bitmap\&.
  78 .RE
  79 .sp
  80 Pseudo\-merge bitmaps can accelerate bitmap traversals when all commits for a given pseudo\-merge are listed on either side of the traversal, either directly (by explicitly asking for them as part of the \fBHAVES\fR or \fBWANTS\fR) or indirectly (by encountering them during a fill\-in traversal)\&.
  81 .SS "Use\-cases"
  82 .sp
  83 For example, suppose there exists a pseudo\-merge bitmap with a large number of commits, all of which are listed in the \fBWANTS\fR section of some bitmap traversal query\&. When pseudo\-merge bitmaps are enabled, the bitmap machinery can quickly determine there is a pseudo\-merge which satisfies some subset of the wanted objects on either side of the query\&. Then, we can inflate the EWAH\-compressed bitmap, and \fBOR\fR it in to the resulting bitmap\&. By contrast, without pseudo\-merge bitmaps, we would have to repeat the decompression and \fBOR\fR\-ing step over a potentially large number of individual bitmaps, which can take proportionally more time\&.
  84 .sp
  85 Another benefit of pseudo\-merges arises when there is some combination of (a) a large number of references, with (b) poor bitmap coverage, and (c) deep, nested trees, making fill\-in traversal relatively expensive\&. For example, suppose that there are a large enough number of tags where bitmapping each of the tags individually is infeasible\&. Without pseudo\-merge bitmaps, computing the result of, say, \fBgit rev\-list \-\-use\-bitmap\-index \-\-count \-\-objects \-\-tags\fR would likely require a large amount of fill\-in traversal\&. But when a large quantity of those tags are stored together in a pseudo\-merge bitmap, the bitmap machinery can take advantage of the fact that we only care about the union of objects reachable from all of those tags, and answer the query much faster\&.
  86 .SS "Configuration"
  87 .sp
  88 Reference tips are grouped into different pseudo\-merge groups according to two criteria\&. A reference name matches one or more of the defined pseudo\-merge patterns, and optionally one or more capture groups within that pattern which further partition the group\&.
  89 .sp
  90 Within a group, commits may be considered "stable", or "unstable" depending on their age\&. These are adjusted by setting the \fBbitmapPseudoMerge\&.<name>\&.stableThreshold\fR and \fBbitmapPseudoMerge\&.<name>\&.threshold\fR configuration values, respectively\&.
  91 .sp
  92 All stable commits are grouped into pseudo\-merges of equal size (\fBbitmapPseudoMerge\&.<name>\&.stableSize\fR)\&. If the \fBstableSize\fR configuration is set to, say, 100, then the first 100 commits (ordered by committer date) which are older than the \fBstableThreshold\fR value will form one group, the next 100 commits will form another group, and so on\&.
  93 .sp
  94 Among unstable commits, the pseudo\-merge machinery will attempt to combine older commits into large groups as opposed to newer commits which will appear in smaller groups\&. This is based on the heuristic that references whose tip commit is older are less likely to be modified to point at a different commit than a reference whose tip commit is newer\&.
  95 .sp
  96 The size of groups is determined by a power\-law decay function, and the decay parameter roughly corresponds to "k" in \fBf(n) = C*n^(\-k/100)\fR, where \fBf(n)\fR describes the size of the \fBn\fR\-th pseudo\-merge group\&. The sample rate controls what percentage of eligible commits are considered as candidates\&. The threshold parameter indicates the minimum age (so as to avoid including too\-recent commits in a pseudo\-merge group, making it less likely to be valid)\&. The "maxMerges" parameter sets an upper\-bound on the number of pseudo\-merge commits an individual group
  97 .sp
  98 The "stable"\-related parameters control "stable" pseudo\-merge groups, comprised of a fixed number of commits which are older than the configured "stable threshold" value and may be grouped together in chunks of "stableSize" in order of age\&.
  99 .sp
 100 The exact configuration for pseudo\-merges is as follows:
 101 .if n \{\
 102 .sp
 103 .\}
 104 .RS 4
 105 .it 1 an-trap
 106 .nr an-no-space-flag 1
 107 .nr an-break-flag 1
 108 .br
 109 .ps +1
 110 \fBNote\fR
 111 .ps -1
 112 .br
 113 .sp
 114 The configuration options in \fBbitmapPseudoMerge\&.*\fR are considered EXPERIMENTAL and may be subject to change or be removed entirely in the future\&. For more information about the pseudo\-merge bitmap feature, see the "Pseudo\-merge bitmaps" section of \fBgitpacking\fR(7)\&.
 115 .sp .5v
 116 .RE
 117 .PP
 118 bitmapPseudoMerge\&.<name>\&.pattern
 119 .RS 4
 120 Regular expression used to match reference names\&. Commits pointed to by references matching this pattern (and meeting the below criteria, like
 121 \fBbitmapPseudoMerge\&.<name>\&.sampleRate\fR
 122 and
 123 \fBbitmapPseudoMerge\&.<name>\&.threshold\fR) will be considered for inclusion in a pseudo\-merge bitmap\&.
 124 .sp
 125 Commits are grouped into pseudo\-merge groups based on whether or not any reference(s) that point at a given commit match the pattern, which is an extended regular expression\&.
 126 .sp
 127 Within a pseudo\-merge group, commits may be further grouped into sub\-groups based on the capture groups in the pattern\&. These sub\-groupings are formed from the regular expressions by concatenating any capture groups from the regular expression, with a
 128 \fI\-\fR
 129 dash in between\&.
 130 .sp
 131 For example, if the pattern is
 132 \fBrefs/tags/\fR, then all tags (provided they meet the below criteria) will be considered candidates for the same pseudo\-merge group\&. However, if the pattern is instead
 133 \fBrefs/remotes/([0\-9])+/tags/\fR, then tags from different remotes will be grouped into separate pseudo\-merge groups, based on the remote number\&.
 134 .RE
 135 .PP
 136 bitmapPseudoMerge\&.<name>\&.decay
 137 .RS 4
 138 Determines the rate at which consecutive pseudo\-merge bitmap groups decrease in size\&. Must be non\-negative\&. This parameter can be thought of as
 139 \fBk\fR
 140 in the function
 141 \fBf(n) = C * n^\-k\fR, where
 142 \fBf(n)\fR
 143 is the size of the `n`th group\&.
 144 .sp
 145 Setting the decay rate equal to
 146 \fB0\fR
 147 will cause all groups to be the same size\&. Setting the decay rate equal to
 148 \fB1\fR
 149 will cause the
 150 \fBn`th group to be `1/n\fR
 151 the size of the initial group\&. Higher values of the decay rate cause consecutive groups to shrink at an increasing rate\&. The default is
 152 \fB1\fR\&.
 153 .sp
 154 If all groups are the same size, it is possible that groups containing newer commits will be able to be used less often than earlier groups, since it is more likely that the references pointing at newer commits will be updated more often than a reference pointing at an old commit\&.
 155 .RE
 156 .PP
 157 bitmapPseudoMerge\&.<name>\&.sampleRate
 158 .RS 4
 159 Determines the proportion of non\-bitmapped commits (among reference tips) which are selected for inclusion in an unstable pseudo\-merge bitmap\&. Must be between
 160 \fB0\fR
 161 and
 162 \fB1\fR
 163 (inclusive)\&. The default is
 164 \fB1\fR\&.
 165 .RE
 166 .PP
 167 bitmapPseudoMerge\&.<name>\&.threshold
 168 .RS 4
 169 Determines the minimum age of non\-bitmapped commits (among reference tips, as above) which are candidates for inclusion in an unstable pseudo\-merge bitmap\&. The default is
 170 \fB1\&.week\&.ago\fR\&.
 171 .RE
 172 .PP
 173 bitmapPseudoMerge\&.<name>\&.maxMerges
 174 .RS 4
 175 Determines the maximum number of pseudo\-merge commits among which commits may be distributed\&.
 176 .sp
 177 For pseudo\-merge groups whose pattern does not contain any capture groups, this setting is applied for all commits matching the regular expression\&. For patterns that have one or more capture groups, this setting is applied for each distinct capture group\&.
 178 .sp
 179 For example, if your capture group is
 180 \fBrefs/tags/\fR, then this setting will distribute all tags into a maximum of
 181 \fBmaxMerges\fR
 182 pseudo\-merge commits\&. However, if your capture group is, say,
 183 \fBrefs/remotes/([0\-9]+)/tags/\fR, then this setting will be applied to each remote\(cqs set of tags individually\&.
 184 .sp
 185 Must be non\-negative\&. The default value is 64\&.
 186 .RE
 187 .PP
 188 bitmapPseudoMerge\&.<name>\&.stableThreshold
 189 .RS 4
 190 Determines the minimum age of commits (among reference tips, as above, however stable commits are still considered candidates even when they have been covered by a bitmap) which are candidates for a stable a pseudo\-merge bitmap\&. The default is
 191 \fB1\&.month\&.ago\fR\&.
 192 .sp
 193 Setting this threshold to a smaller value (e\&.g\&., 1\&.week\&.ago) will cause more stable groups to be generated (which impose a one\-time generation cost) but those groups will likely become stale over time\&. Using a larger value incurs the opposite penalty (fewer stable groups which are more useful)\&.
 194 .RE
 195 .PP
 196 bitmapPseudoMerge\&.<name>\&.stableSize
 197 .RS 4
 198 Determines the size (in number of commits) of a stable psuedo\-merge bitmap\&. The default is
 199 \fB512\fR\&.
 200 .RE
 201 .SS "Examples"
 202 .sp
 203 Suppose that you have a repository with a large number of references, and you want a bare\-bones configuration of pseudo\-merge bitmaps that will enhance bitmap coverage of the \fBrefs/\fR namespace\&. You may start with a configuration like so:
 204 .sp
 205 .if n \{\
 206 .RS 4
 207 .\}
 208 .nf
 209 [bitmapPseudoMerge "all"]
 210         pattern = "refs/"
 211         threshold = now
 212         stableThreshold = never
 213         sampleRate = 100
 214         maxMerges = 64
 215 .fi
 216 .if n \{\
 217 .RE
 218 .\}
 219 .sp
 220 This will create pseudo\-merge bitmaps for all references, regardless of their age, and group them into 64 pseudo\-merge commits\&.
 221 .sp
 222 If you wanted to separate tags from branches when generating pseudo\-merge commits, you would instead define the pattern with a capture group, like so:
 223 .sp
 224 .if n \{\
 225 .RS 4
 226 .\}
 227 .nf
 228 [bitmapPseudoMerge "all"]
 229         pattern = "refs/(heads/tags)/"
 230 .fi
 231 .if n \{\
 232 .RE
 233 .\}
 234 .sp
 235 Suppose instead that you are working in a fork\-network repository, with each fork specified by some numeric ID, and whose refs reside in \fBrefs/virtual/NNN/\fR (where \fBNNN\fR is the numeric ID corresponding to some fork) in the network\&. In this instance, you may instead write something like:
 236 .sp
 237 .if n \{\
 238 .RS 4
 239 .\}
 240 .nf
 241 [bitmapPseudoMerge "all"]
 242         pattern = "refs/virtual/([0\-9]+)/(heads|tags)/"
 243         threshold = now
 244         stableThreshold = never
 245         sampleRate = 100
 246         maxMerges = 64
 247 .fi
 248 .if n \{\
 249 .RE
 250 .\}
 251 .sp
 252 Which would generate pseudo\-merge group identifiers like "1234\-heads", and "5678\-tags" (for branches in fork "1234", and tags in remote "5678", respectively)\&.
 253 .SH "SEE ALSO"
 254 .sp
 255 \fBgit-pack-objects\fR(1) \fBgit-repack\fR(1)
 256 .SH "GIT"
 257 .sp
 258 Part of the \fBgit\fR(1) suite