| 1 | Git Commit-Graph Design Notes |
| 2 | ============================= |
| 3 | |
| 4 | Git walks the commit graph for many reasons, including: |
| 5 | |
| 6 | 1. Listing and filtering commit history. |
| 7 | 2. Computing merge bases. |
| 8 | |
| 9 | These operations can become slow as the commit count grows. The merge |
| 10 | base calculation shows up in many user-facing commands, such as 'merge-base' |
| 11 | or 'status' and can take minutes to compute depending on history shape. |
| 12 | |
| 13 | There are two main costs here: |
| 14 | |
| 15 | 1. Decompressing and parsing commits. |
| 16 | 2. Walking the entire graph to satisfy topological order constraints. |
| 17 | |
| 18 | The commit-graph file is a supplemental data structure that accelerates |
| 19 | commit graph walks. If a user downgrades or disables the 'core.commitGraph' |
| 20 | config setting, then the existing object database is sufficient. The file is stored |
| 21 | as "commit-graph" either in the .git/objects/info directory or in the info |
| 22 | directory of an alternate. |
| 23 | |
| 24 | The commit-graph file stores the commit graph structure along with some |
| 25 | extra metadata to speed up graph walks. By listing commit OIDs in |
| 26 | lexicographic order, we can identify an integer position for each commit |
| 27 | and refer to the parents of a commit using those integer positions. We |
| 28 | use binary search to find initial commits and then use the integer |
| 29 | positions for fast lookups during the walk. |
| 30 | |
| 31 | A consumer may load the following info for a commit from the graph: |
| 32 | |
| 33 | 1. The commit OID. |
| 34 | 2. The list of parents, along with their integer position. |
| 35 | 3. The commit date. |
| 36 | 4. The root tree OID. |
| 37 | 5. The generation number (see definition below). |
| 38 | |
| 39 | Values 1-4 satisfy the requirements of parse_commit_gently(). |
| 40 | |
| 41 | There are two definitions of generation number: |
| 42 | |
| 43 | 1. Corrected committer dates (generation number v2) |
| 44 | 2. Topological levels (generation number v1) |
| 45 | |
| 46 | Define "corrected committer date" of a commit recursively as follows: |
| 47 | |
| 48 | * A commit with no parents (a root commit) has corrected committer date |
| 49 | equal to its committer date. |
| 50 | |
| 51 | * A commit with at least one parent has corrected committer date equal to |
| 52 | the maximum of its committer date and one more than the largest corrected |
| 53 | committer date among its parents. |
| 54 | |
| 55 | * As a special case, a root commit with timestamp zero has corrected commit |
| 56 | date of 1, to be able to distinguish it from GENERATION_NUMBER_ZERO |
| 57 | (that is, an uncomputed corrected commit date). |
| 58 | |
| 59 | Define the "topological level" of a commit recursively as follows: |
| 60 | |
| 61 | * A commit with no parents (a root commit) has topological level of one. |
| 62 | |
| 63 | * A commit with at least one parent has topological level one more than |
| 64 | the largest topological level among its parents. |
| 65 | |
| 66 | Equivalently, the topological level of a commit A is one more than the |
| 67 | length of a longest path from A to a root commit. The recursive definition |
| 68 | is easier to use for computation and observing the following property: |
| 69 | |
| 70 | If A and B are commits with generation numbers N and M, respectively, |
| 71 | and N <= M, then A cannot reach B. That is, we know without searching |
| 72 | that B is not an ancestor of A because it is further from a root commit |
| 73 | than A. |
| 74 | |
| 75 | Conversely, when checking if A is an ancestor of B, then we only need |
| 76 | to walk commits until all commits on the walk boundary have generation |
| 77 | number at most N. If we walk commits using a priority queue seeded by |
| 78 | generation numbers, then we always expand the boundary commit with highest |
| 79 | generation number and can easily detect the stopping condition. |
| 80 | |
| 81 | The property applies to both versions of generation number, that is both |
| 82 | corrected committer dates and topological levels. |
| 83 | |
| 84 | This property can be used to significantly reduce the time it takes to |
| 85 | walk commits and determine topological relationships. Without generation |
| 86 | numbers, the general heuristic is the following: |
| 87 | |
| 88 | If A and B are commits with commit time X and Y, respectively, and |
| 89 | X < Y, then A _probably_ cannot reach B. |
| 90 | |
| 91 | In absence of corrected commit dates (for example, old versions of Git or |
| 92 | mixed generation graph chains), |
| 93 | this heuristic is currently used whenever the computation is allowed to |
| 94 | violate topological relationships due to clock skew (such as "git log" |
| 95 | with default order), but is not used when the topological order is |
| 96 | required (such as merge base calculations, "git log --graph"). |
| 97 | |
| 98 | In practice, we expect some commits to be created recently and not stored |
| 99 | in the commit-graph. We can treat these commits as having "infinite" |
| 100 | generation number and walk until reaching commits with known generation |
| 101 | number. |
| 102 | |
| 103 | We use the macro GENERATION_NUMBER_INFINITY to mark commits not |
| 104 | in the commit-graph file. If a commit-graph file was written by a version |
| 105 | of Git that did not compute generation numbers, then those commits will |
| 106 | have generation number represented by the macro GENERATION_NUMBER_ZERO = 0. |
| 107 | |
| 108 | Since the commit-graph file is closed under reachability, we can guarantee |
| 109 | the following weaker condition on all commits: |
| 110 | |
| 111 | If A and B are commits with generation numbers N and M, respectively, |
| 112 | and N < M, then A cannot reach B. |
| 113 | |
| 114 | Note how the strict inequality differs from the inequality when we have |
| 115 | fully-computed generation numbers. Using strict inequality may result in |
| 116 | walking a few extra commits, but the simplicity in dealing with commits |
| 117 | with generation number *_INFINITY or *_ZERO is valuable. |
| 118 | |
| 119 | We use the macro GENERATION_NUMBER_V1_MAX = 0x3FFFFFFF for commits whose |
| 120 | topological levels (generation number v1) are computed to be at least |
| 121 | this value. We limit at this value since it is the largest value that |
| 122 | can be stored in the commit-graph file using the 30 bits available |
| 123 | to topological levels. This presents another case where a commit can |
| 124 | have generation number equal to that of a parent. |
| 125 | |
| 126 | Design Details |
| 127 | -------------- |
| 128 | |
| 129 | - The commit-graph file is stored in a file named 'commit-graph' in the |
| 130 | .git/objects/info directory. This could be stored in the info directory |
| 131 | of an alternate. |
| 132 | |
| 133 | - The core.commitGraph config setting must be on to consume graph files. |
| 134 | |
| 135 | - The file format includes parameters for the object ID hash function, |
| 136 | so a future change of hash algorithm does not require a change in format. |
| 137 | |
| 138 | - Commit grafts and replace objects can change the shape of the commit |
| 139 | history. The latter can also be enabled/disabled on the fly using |
| 140 | `--no-replace-objects`. This leads to difficulty storing both possible |
| 141 | interpretations of a commit id, especially when computing generation |
| 142 | numbers. The commit-graph will not be read or written when |
| 143 | replace-objects or grafts are present. |
| 144 | |
| 145 | - Shallow clones create grafts of commits by dropping their parents. This |
| 146 | leads the commit-graph to think those commits have generation number 1. |
| 147 | If and when those commits are made unshallow, those generation numbers |
| 148 | become invalid. Since shallow clones are intended to restrict the commit |
| 149 | history to a very small set of commits, the commit-graph feature is less |
| 150 | helpful for these clones, anyway. The commit-graph will not be read or |
| 151 | written when shallow commits are present. |
| 152 | |
| 153 | Commit-Graphs Chains |
| 154 | -------------------- |
| 155 | |
| 156 | Typically, repos grow with near-constant velocity (commits per day). Over time, |
| 157 | the number of commits added by a fetch operation is much smaller than the |
| 158 | number of commits in the full history. By creating a "chain" of commit-graphs, |
| 159 | we enable fast writes of new commit data without rewriting the entire commit |
| 160 | history -- at least, most of the time. |
| 161 | |
| 162 | File Layout |
| 163 | ~~~~~~~~~~~ |
| 164 | |
| 165 | A commit-graph chain uses multiple files, and we use a fixed naming convention |
| 166 | to organize these files. Each commit-graph file has a name |
| 167 | `$OBJDIR/info/commit-graphs/graph-{hash}.graph` where `{hash}` is the hex- |
| 168 | valued hash stored in the footer of that file (which is a hash of the file's |
| 169 | contents before that hash). For a chain of commit-graph files, a plain-text |
| 170 | file at `$OBJDIR/info/commit-graphs/commit-graph-chain` contains the |
| 171 | hashes for the files in order from "lowest" to "highest". |
| 172 | |
| 173 | For example, if the `commit-graph-chain` file contains the lines |
| 174 | |
| 175 | ---- |
| 176 | {hash0} |
| 177 | {hash1} |
| 178 | {hash2} |
| 179 | ---- |
| 180 | |
| 181 | then the commit-graph chain looks like the following diagram: |
| 182 | |
| 183 | +-----------------------+ |
| 184 | | graph-{hash2}.graph | |
| 185 | +-----------------------+ |
| 186 | | |
| 187 | +-----------------------+ |
| 188 | | | |
| 189 | | graph-{hash1}.graph | |
| 190 | | | |
| 191 | +-----------------------+ |
| 192 | | |
| 193 | +-----------------------+ |
| 194 | | | |
| 195 | | | |
| 196 | | | |
| 197 | | graph-{hash0}.graph | |
| 198 | | | |
| 199 | | | |
| 200 | | | |
| 201 | +-----------------------+ |
| 202 | |
| 203 | Let X0 be the number of commits in `graph-{hash0}.graph`, X1 be the number of |
| 204 | commits in `graph-{hash1}.graph`, and X2 be the number of commits in |
| 205 | `graph-{hash2}.graph`. If a commit appears in position i in `graph-{hash2}.graph`, |
| 206 | then we interpret this as being the commit in position (X0 + X1 + i), and that |
| 207 | will be used as its "graph position". The commits in `graph-{hash2}.graph` use these |
| 208 | positions to refer to their parents, which may be in `graph-{hash1}.graph` or |
| 209 | `graph-{hash0}.graph`. We can navigate to an arbitrary commit in position j by checking |
| 210 | its containment in the intervals [0, X0), [X0, X0 + X1), [X0 + X1, X0 + X1 + |
| 211 | X2). |
| 212 | |
| 213 | Each commit-graph file (except the base, `graph-{hash0}.graph`) contains data |
| 214 | specifying the hashes of all files in the lower layers. In the above example, |
| 215 | `graph-{hash1}.graph` contains `{hash0}` while `graph-{hash2}.graph` contains |
| 216 | `{hash0}` and `{hash1}`. |
| 217 | |
| 218 | Merging commit-graph files |
| 219 | ~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 220 | |
| 221 | If we only added a new commit-graph file on every write, we would run into a |
| 222 | linear search problem through many commit-graph files. Instead, we use a merge |
| 223 | strategy to decide when the stack should collapse some number of levels. |
| 224 | |
| 225 | The diagram below shows such a collapse. As a set of new commits are added, it |
| 226 | is determined by the merge strategy that the files should collapse to |
| 227 | `graph-{hash1}`. Thus, the new commits, the commits in `graph-{hash2}` and |
| 228 | the commits in `graph-{hash1}` should be combined into a new `graph-{hash3}` |
| 229 | file. |
| 230 | |
| 231 | .... |
| 232 | +---------------------+ |
| 233 | | | |
| 234 | | (new commits) | |
| 235 | | | |
| 236 | +---------------------+ |
| 237 | | | |
| 238 | +-----------------------+ +---------------------+ |
| 239 | | graph-{hash2} |->| | |
| 240 | +-----------------------+ +---------------------+ |
| 241 | | | | |
| 242 | +-----------------------+ +---------------------+ |
| 243 | | | | | |
| 244 | | graph-{hash1} |->| | |
| 245 | | | | | |
| 246 | +-----------------------+ +---------------------+ |
| 247 | | tmp_graphXXX |
| 248 | +-----------------------+ |
| 249 | | | |
| 250 | | | |
| 251 | | | |
| 252 | | graph-{hash0} | |
| 253 | | | |
| 254 | | | |
| 255 | | | |
| 256 | +-----------------------+ |
| 257 | .... |
| 258 | |
| 259 | During this process, the commits to write are combined, sorted and we write the |
| 260 | contents to a temporary file, all while holding a `commit-graph-chain.lock` |
| 261 | lock-file. When the file is flushed, we rename it to `graph-{hash3}` |
| 262 | according to the computed `{hash3}`. Finally, we write the new chain data to |
| 263 | `commit-graph-chain.lock`: |
| 264 | |
| 265 | ---- |
| 266 | {hash3} |
| 267 | {hash0} |
| 268 | ---- |
| 269 | |
| 270 | We then close the lock-file. |
| 271 | |
| 272 | Merge Strategy |
| 273 | ~~~~~~~~~~~~~~ |
| 274 | |
| 275 | When writing a set of commits that do not exist in the commit-graph stack of |
| 276 | height N, we default to creating a new file at level N + 1. We then decide to |
| 277 | merge with the Nth level if one of two conditions hold: |
| 278 | |
| 279 | 1. `--size-multiple=<X>` is specified or X = 2, and the number of commits in |
| 280 | level N is less than X times the number of commits in level N + 1. |
| 281 | |
| 282 | 2. `--max-commits=<C>` is specified with non-zero C and the number of commits |
| 283 | in level N + 1 is more than C commits. |
| 284 | |
| 285 | This decision cascades down the levels: when we merge a level we create a new |
| 286 | set of commits that then compares to the next level. |
| 287 | |
| 288 | The first condition bounds the number of levels to be logarithmic in the total |
| 289 | number of commits. The second condition bounds the total number of commits in |
| 290 | a `graph-{hashN}` file and not in the `commit-graph` file, preventing |
| 291 | significant performance issues when the stack merges and another process only |
| 292 | partially reads the previous stack. |
| 293 | |
| 294 | The merge strategy values (2 for the size multiple, 64,000 for the maximum |
| 295 | number of commits) could be extracted into config settings for full |
| 296 | flexibility. |
| 297 | |
| 298 | Handling Mixed Generation Number Chains |
| 299 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 300 | |
| 301 | With the introduction of generation number v2 and generation data chunk, the |
| 302 | following scenario is possible: |
| 303 | |
| 304 | 1. "New" Git writes a commit-graph with the corrected commit dates. |
| 305 | 2. "Old" Git writes a split commit-graph on top without corrected commit dates. |
| 306 | |
| 307 | A naive approach of using the newest available generation number from |
| 308 | each layer would lead to violated expectations: the lower layer would |
| 309 | use corrected commit dates which are much larger than the topological |
| 310 | levels of the higher layer. For this reason, Git inspects the topmost |
| 311 | layer to see if the layer is missing corrected commit dates. In such a case |
| 312 | Git only uses topological level for generation numbers. |
| 313 | |
| 314 | When writing a new layer in split commit-graph, we write corrected commit |
| 315 | dates if the topmost layer has corrected commit dates written. This |
| 316 | guarantees that if a layer has corrected commit dates, all lower layers |
| 317 | must have corrected commit dates as well. |
| 318 | |
| 319 | When merging layers, we do not consider whether the merged layers had corrected |
| 320 | commit dates. Instead, the new layer will have corrected commit dates if the |
| 321 | layer below the new layer has corrected commit dates. |
| 322 | |
| 323 | While writing or merging layers, if the new layer is the only layer, it will |
| 324 | have corrected commit dates when written by compatible versions of Git. Thus, |
| 325 | rewriting split commit-graph as a single file (`--split=replace`) creates a |
| 326 | single layer with corrected commit dates. |
| 327 | |
| 328 | Deleting graph-\{hash\} files |
| 329 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 330 | |
| 331 | After a new tip file is written, some `graph-{hash}` files may no longer |
| 332 | be part of a chain. It is important to remove these files from disk, eventually. |
| 333 | The main reason to delay removal is that another process could read the |
| 334 | `commit-graph-chain` file before it is rewritten, but then look for the |
| 335 | `graph-{hash}` files after they are deleted. |
| 336 | |
| 337 | To allow holding old split commit-graphs for a while after they are unreferenced, |
| 338 | we update the modified times of the files when they become unreferenced. Then, |
| 339 | we scan the `$OBJDIR/info/commit-graphs/` directory for `graph-{hash}` |
| 340 | files whose modified times are older than a given expiry window. This window |
| 341 | defaults to zero, but can be changed using command-line arguments or a config |
| 342 | setting. |
| 343 | |
| 344 | Chains across multiple object directories |
| 345 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 346 | |
| 347 | In a repo with alternates, we look for the `commit-graph-chain` file starting |
| 348 | in the local object directory and then in each alternate. The first file that |
| 349 | exists defines our chain. As we look for the `graph-{hash}` files for |
| 350 | each `{hash}` in the chain file, we follow the same pattern for the host |
| 351 | directories. |
| 352 | |
| 353 | This allows commit-graphs to be split across multiple forks in a fork network. |
| 354 | The typical case is a large "base" repo with many smaller forks. |
| 355 | |
| 356 | As the base repo advances, it will likely update and merge its commit-graph |
| 357 | chain more frequently than the forks. If a fork updates their commit-graph after |
| 358 | the base repo, then it should "reparent" the commit-graph chain onto the new |
| 359 | chain in the base repo. When reading each `graph-{hash}` file, we track |
| 360 | the object directory containing it. During a write of a new commit-graph file, |
| 361 | we check for any changes in the source object directory and read the |
| 362 | `commit-graph-chain` file for that source and create a new file based on those |
| 363 | files. During this "reparent" operation, we necessarily need to collapse all |
| 364 | levels in the fork, as all of the files are invalid against the new base file. |
| 365 | |
| 366 | It is crucial to be careful when cleaning up "unreferenced" `graph-{hash}.graph` |
| 367 | files in this scenario. It falls to the user to define the proper settings for |
| 368 | their custom environment: |
| 369 | |
| 370 | 1. When merging levels in the base repo, the unreferenced files may still be |
| 371 | referenced by chains from fork repos. |
| 372 | |
| 373 | 2. The expiry time should be set to a length of time such that every fork has |
| 374 | time to recompute their commit-graph chain to "reparent" onto the new base |
| 375 | file(s). |
| 376 | |
| 377 | 3. If the commit-graph chain is updated in the base, the fork will not have |
| 378 | access to the new chain until its chain is updated to reference those files. |
| 379 | (This may change in the future [5].) |
| 380 | |
| 381 | Related Links |
| 382 | ------------- |
| 383 | [0] https://bugs.chromium.org/p/git/issues/detail?id=8 |
| 384 | Chromium work item for: Serialized Commit Graph |
| 385 | |
| 386 | [1] https://lore.kernel.org/git/20110713070517.GC18566@sigill.intra.peff.net/ |
| 387 | An abandoned patch that introduced generation numbers. |
| 388 | |
| 389 | [2] https://lore.kernel.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/ |
| 390 | Discussion about generation numbers on commits and how they interact |
| 391 | with fsck. |
| 392 | |
| 393 | [3] https://lore.kernel.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/ |
| 394 | More discussion about generation numbers and not storing them inside |
| 395 | commit objects. A valuable quote: |
| 396 | |
| 397 | "I think we should be moving more in the direction of keeping |
| 398 | repo-local caches for optimizations. Reachability bitmaps have been |
| 399 | a big performance win. I think we should be doing the same with our |
| 400 | properties of commits. Not just generation numbers, but making it |
| 401 | cheap to access the graph structure without zlib-inflating whole |
| 402 | commit objects (i.e., packv4 or something like the "metapacks" I |
| 403 | proposed a few years ago)." |
| 404 | |
| 405 | [4] https://lore.kernel.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u |
| 406 | A patch to remove the ahead-behind calculation from 'status'. |
| 407 | |
| 408 | [5] https://lore.kernel.org/git/f27db281-abad-5043-6d71-cbb083b1c877@gmail.com/ |
| 409 | A discussion of a "two-dimensional graph position" that can allow reading |
| 410 | multiple commit-graph chains at the same time. |