1dca3bd8fe90a189e52008212d8aa8d9bd094eff
   1Git Commit Graph Design Notes
   2=============================
   3
   4Git walks the commit graph for many reasons, including:
   5
   61. Listing and filtering commit history.
   72. Computing merge bases.
   8
   9These operations can become slow as the commit count grows. The merge
  10base calculation shows up in many user-facing commands, such as 'merge-base'
  11or 'status' and can take minutes to compute depending on history shape.
  12
  13There are two main costs here:
  14
  151. Decompressing and parsing commits.
  162. Walking the entire graph to satisfy topological order constraints.
  17
  18The commit-graph file is a supplemental data structure that accelerates
  19commit graph walks. If a user downgrades or disables the 'core.commitGraph'
  20config setting, then the existing ODB is sufficient. The file is stored
  21as "commit-graph" either in the .git/objects/info directory or in the info
  22directory of an alternate.
  23
  24The commit-graph file stores the commit graph structure along with some
  25extra metadata to speed up graph walks. By listing commit OIDs in lexi-
  26cographic order, we can identify an integer position for each commit and
  27refer to the parents of a commit using those integer positions. We use
  28binary search to find initial commits and then use the integer positions
  29for fast lookups during the walk.
  30
  31A consumer may load the following info for a commit from the graph:
  32
  331. The commit OID.
  342. The list of parents, along with their integer position.
  353. The commit date.
  364. The root tree OID.
  375. The generation number (see definition below).
  38
  39Values 1-4 satisfy the requirements of parse_commit_gently().
  40
  41Define the "generation number" of a commit recursively as follows:
  42
  43 * A commit with no parents (a root commit) has generation number one.
  44
  45 * A commit with at least one parent has generation number one more than
  46   the largest generation number among its parents.
  47
  48Equivalently, the generation number of a commit A is one more than the
  49length of a longest path from A to a root commit. The recursive definition
  50is easier to use for computation and observing the following property:
  51
  52    If A and B are commits with generation numbers N and M, respectively,
  53    and N <= M, then A cannot reach B. That is, we know without searching
  54    that B is not an ancestor of A because it is further from a root commit
  55    than A.
  56
  57    Conversely, when checking if A is an ancestor of B, then we only need
  58    to walk commits until all commits on the walk boundary have generation
  59    number at most N. If we walk commits using a priority queue seeded by
  60    generation numbers, then we always expand the boundary commit with highest
  61    generation number and can easily detect the stopping condition.
  62
  63This property can be used to significantly reduce the time it takes to
  64walk commits and determine topological relationships. Without generation
  65numbers, the general heuristic is the following:
  66
  67    If A and B are commits with commit time X and Y, respectively, and
  68    X < Y, then A _probably_ cannot reach B.
  69
  70This heuristic is currently used whenever the computation is allowed to
  71violate topological relationships due to clock skew (such as "git log"
  72with default order), but is not used when the topological order is
  73required (such as merge base calculations, "git log --graph").
  74
  75In practice, we expect some commits to be created recently and not stored
  76in the commit graph. We can treat these commits as having "infinite"
  77generation number and walk until reaching commits with known generation
  78number.
  79
  80We use the macro GENERATION_NUMBER_INFINITY = 0xFFFFFFFF to mark commits not
  81in the commit-graph file. If a commit-graph file was written by a version
  82of Git that did not compute generation numbers, then those commits will
  83have generation number represented by the macro GENERATION_NUMBER_ZERO = 0.
  84
  85Since the commit-graph file is closed under reachability, we can guarantee
  86the following weaker condition on all commits:
  87
  88    If A and B are commits with generation numbers N amd M, respectively,
  89    and N < M, then A cannot reach B.
  90
  91Note how the strict inequality differs from the inequality when we have
  92fully-computed generation numbers. Using strict inequality may result in
  93walking a few extra commits, but the simplicity in dealing with commits
  94with generation number *_INFINITY or *_ZERO is valuable.
  95
  96We use the macro GENERATION_NUMBER_MAX = 0x3FFFFFFF to for commits whose
  97generation numbers are computed to be at least this value. We limit at
  98this value since it is the largest value that can be stored in the
  99commit-graph file using the 30 bits available to generation numbers. This
 100presents another case where a commit can have generation number equal to
 101that of a parent.
 102
 103Design Details
 104--------------
 105
 106- The commit-graph file is stored in a file named 'commit-graph' in the
 107  .git/objects/info directory. This could be stored in the info directory
 108  of an alternate.
 109
 110- The core.commitGraph config setting must be on to consume graph files.
 111
 112- The file format includes parameters for the object ID hash function,
 113  so a future change of hash algorithm does not require a change in format.
 114
 115- Commit grafts and replace objects can change the shape of the commit
 116  history. The latter can also be enabled/disabled on the fly using
 117  `--no-replace-objects`. This leads to difficultly storing both possible
 118  interpretations of a commit id, especially when computing generation
 119  numbers. The commit-graph will not be read or written when
 120  replace-objects or grafts are present.
 121
 122- Shallow clones create grafts of commits by dropping their parents. This
 123  leads the commit-graph to think those commits have generation number 1.
 124  If and when those commits are made unshallow, those generation numbers
 125  become invalid. Since shallow clones are intended to restrict the commit
 126  history to a very small set of commits, the commit-graph feature is less
 127  helpful for these clones, anyway. The commit-graph will not be read or
 128  written when shallow commits are present.
 129
 130Commit Graphs Chains
 131--------------------
 132
 133Typically, repos grow with near-constant velocity (commits per day). Over time,
 134the number of commits added by a fetch operation is much smaller than the
 135number of commits in the full history. By creating a "chain" of commit-graphs,
 136we enable fast writes of new commit data without rewriting the entire commit
 137history -- at least, most of the time.
 138
 139## File Layout
 140
 141A commit-graph chain uses multiple files, and we use a fixed naming convention
 142to organize these files. Each commit-graph file has a name
 143`$OBJDIR/info/commit-graphs/graph-{hash}.graph` where `{hash}` is the hex-
 144valued hash stored in the footer of that file (which is a hash of the file's
 145contents before that hash). For a chain of commit-graph files, a plain-text
 146file at `$OBJDIR/info/commit-graphs/commit-graph-chain` contains the
 147hashes for the files in order from "lowest" to "highest".
 148
 149For example, if the `commit-graph-chain` file contains the lines
 150
 151```
 152        {hash0}
 153        {hash1}
 154        {hash2}
 155```
 156
 157then the commit-graph chain looks like the following diagram:
 158
 159 +-----------------------+
 160 |  graph-{hash2}.graph  |
 161 +-----------------------+
 162          |
 163 +-----------------------+
 164 |                       |
 165 |  graph-{hash1}.graph  |
 166 |                       |
 167 +-----------------------+
 168          |
 169 +-----------------------+
 170 |                       |
 171 |                       |
 172 |                       |
 173 |  graph-{hash0}.graph  |
 174 |                       |
 175 |                       |
 176 |                       |
 177 +-----------------------+
 178
 179Let X0 be the number of commits in `graph-{hash0}.graph`, X1 be the number of
 180commits in `graph-{hash1}.graph`, and X2 be the number of commits in
 181`graph-{hash2}.graph`. If a commit appears in position i in `graph-{hash2}.graph`,
 182then we interpret this as being the commit in position (X0 + X1 + i), and that
 183will be used as its "graph position". The commits in `graph-{hash2}.graph` use these
 184positions to refer to their parents, which may be in `graph-{hash1}.graph` or
 185`graph-{hash0}.graph`. We can navigate to an arbitrary commit in position j by checking
 186its containment in the intervals [0, X0), [X0, X0 + X1), [X0 + X1, X0 + X1 +
 187X2).
 188
 189Related Links
 190-------------
 191[0] https://bugs.chromium.org/p/git/issues/detail?id=8
 192    Chromium work item for: Serialized Commit Graph
 193
 194[1] https://public-inbox.org/git/20110713070517.GC18566@sigill.intra.peff.net/
 195    An abandoned patch that introduced generation numbers.
 196
 197[2] https://public-inbox.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/
 198    Discussion about generation numbers on commits and how they interact
 199    with fsck.
 200
 201[3] https://public-inbox.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/
 202    More discussion about generation numbers and not storing them inside
 203    commit objects. A valuable quote:
 204
 205    "I think we should be moving more in the direction of keeping
 206     repo-local caches for optimizations. Reachability bitmaps have been
 207     a big performance win. I think we should be doing the same with our
 208     properties of commits. Not just generation numbers, but making it
 209     cheap to access the graph structure without zlib-inflating whole
 210     commit objects (i.e., packv4 or something like the "metapacks" I
 211     proposed a few years ago)."
 212
 213[4] https://public-inbox.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u
 214    A patch to remove the ahead-behind calculation from 'status'.