Documentation/technical/commit-graph.txt

   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 ODB 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 lexi-
  26 cographic order, we can identify an integer position for each commit and
  27 refer to the parents of a commit using those integer positions. We use
  28 binary search to find initial commits and then use the integer positions
  29 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 Define 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
  48 Equivalently, the generation number of a commit A is one more than the
  49 length of a longest path from A to a root commit. The recursive definition
  50 is 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
  63 This property can be used to significantly reduce the time it takes to
  64 walk commits and determine topological relationships. Without generation
  65 numbers, 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
  70 This heuristic is currently used whenever the computation is allowed to
  71 violate topological relationships due to clock skew (such as "git log"
  72 with default order), but is not used when the topological order is
  73 required (such as merge base calculations, "git log --graph").
  74
  75 In practice, we expect some commits to be created recently and not stored
  76 in the commit graph. We can treat these commits as having "infinite"
  77 generation number and walk until reaching commits with known generation
  78 number.
  79
  80 We use the macro GENERATION_NUMBER_INFINITY = 0xFFFFFFFF to mark commits not
  81 in the commit-graph file. If a commit-graph file was written by a version
  82 of Git that did not compute generation numbers, then those commits will
  83 have generation number represented by the macro GENERATION_NUMBER_ZERO = 0.
  84
  85 Since the commit-graph file is closed under reachability, we can guarantee
  86 the 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
  91 Note how the strict inequality differs from the inequality when we have
  92 fully-computed generation numbers. Using strict inequality may result in
  93 walking a few extra commits, but the simplicity in dealing with commits
  94 with generation number *_INFINITY or *_ZERO is valuable.
  95
  96 We use the macro GENERATION_NUMBER_MAX = 0x3FFFFFFF to for commits whose
  97 generation numbers are computed to be at least this value. We limit at
  98 this value since it is the largest value that can be stored in the
  99 commit-graph file using the 30 bits available to generation numbers. This
 100 presents another case where a commit can have generation number equal to
 101 that of a parent.
 102
 103 Design 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 Future Work
 116 -----------
 117
 118 - The commit graph feature currently does not honor commit grafts. This can
 119   be remedied by duplicating or refactoring the current graft logic.
 120
 121 - After computing and storing generation numbers, we must make graph
 122   walks aware of generation numbers to gain the performance benefits they
 123   enable. This will mostly be accomplished by swapping a commit-date-ordered
 124   priority queue with one ordered by generation number. The following
 125   operations are important candidates:
 126
 127     - 'log --topo-order'
 128     - 'tag --merged'
 129
 130 - A server could provide a commit graph file as part of the network protocol
 131   to avoid extra calculations by clients. This feature is only of benefit if
 132   the user is willing to trust the file, because verifying the file is correct
 133   is as hard as computing it from scratch.
 134
 135 Related Links
 136 -------------
 137 [0] https://bugs.chromium.org/p/git/issues/detail?id=8
 138     Chromium work item for: Serialized Commit Graph
 139
 140 [1] https://public-inbox.org/git/20110713070517.GC18566@sigill.intra.peff.net/
 141     An abandoned patch that introduced generation numbers.
 142
 143 [2] https://public-inbox.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/
 144     Discussion about generation numbers on commits and how they interact
 145     with fsck.
 146
 147 [3] https://public-inbox.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/
 148     More discussion about generation numbers and not storing them inside
 149     commit objects. A valuable quote:
 150
 151     "I think we should be moving more in the direction of keeping
 152      repo-local caches for optimizations. Reachability bitmaps have been
 153      a big performance win. I think we should be doing the same with our
 154      properties of commits. Not just generation numbers, but making it
 155      cheap to access the graph structure without zlib-inflating whole
 156      commit objects (i.e., packv4 or something like the "metapacks" I
 157      proposed a few years ago)."
 158
 159 [4] https://public-inbox.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u
 160     A patch to remove the ahead-behind calculation from 'status'.