git.oblomov.eu Git - git/blob - 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 avoid topological order mistakes.
  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 either in the .git/objects/info directory or in the info directory of an
  22 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 can make
  71 mistakes with topological orders (such as "git log" with default order),
  72 but is not used when the topological order is required (such as merge
  73 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 Design Details
  81 --------------
  82
  83 - A graph file is stored in a file named 'graph-<hash>.graph' in the
  84   .git/objects/info directory. This could be stored in the info directory
  85   of an alternate.
  86
  87 - The latest graph file name is stored in a 'graph-latest' file next to
  88   the graph files. This allows atomic swaps of latest graph files without
  89   race conditions with concurrent processes.
  90
  91 - The core.commitGraph config setting must be on to consume graph files.
  92
  93 - The file format includes parameters for the object ID hash function,
  94   so a future change of hash algorithm does not require a change in format.
  95
  96 Current Limitations
  97 -------------------
  98
  99 - Only one graph file is used at one time. This allows the integer position
 100   to seek into the single graph file. It is possible to extend the model
 101   for multiple graph files, but that is currently not part of the design.
 102
 103 - .graph files are managed only by the 'commit-graph' builtin. These are not
 104   updated automatically during clone, fetch, repack, or creating new commits.
 105
 106 - There is no 'verify' subcommand for the 'commit-graph' builtin to verify
 107   the contents of the graph file agree with the contents in the ODB.
 108
 109 - Generation numbers are not computed in the current version. The file
 110   format supports storing them, along with a mechanism to upgrade from
 111   a file without generation numbers to one that uses them.
 112
 113 Future Work
 114 -----------
 115
 116 - The file format includes room for precomputed generation numbers. These
 117   are not currently computed, so all generation numbers will be marked as
 118   0 (or "uncomputed"). A later patch will include this calculation.
 119
 120 - The commit graph is currently incompatible with commit grafts. This can be
 121   remedied by duplicating or refactoring the current graft logic.
 122
 123 - After computing and storing generation numbers, we must make graph
 124   walks aware of generation numbers to gain the performance benefits they
 125   enable. This will mostly be accomplished by swapping a commit-date-ordered
 126   priority queue with one ordered by generation number. The following
 127   operations are important candidates:
 128
 129     - paint_down_to_common()
 130     - 'log --topo-order'
 131
 132 - The graph currently only adds commits to a previously existing graph.
 133   When writing a new graph, we could check that the ODB still contains
 134   the commits and choose to remove the commits that are deleted from the
 135   ODB. For performance reasons, this check should remain optional.
 136
 137 - Currently, parse_commit_gently() requires filling in the root tree
 138   object for a commit. This passes through lookup_tree() and consequently
 139   lookup_object(). Also, it calls lookup_commit() when loading the parents.
 140   These method calls check the ODB for object existence, even if the
 141   consumer does not need the content. For example, we do not need the
 142   tree contents when computing merge bases. Now that commit parsing is
 143   removed from the computation time, these lookup operations are the
 144   slowest operations keeping graph walks from being fast. Consider
 145   loading these objects without verifying their existence in the ODB and
 146   only loading them fully when consumers need them. Consider a method
 147   such as "ensure_tree_loaded(commit)" that fully loads a tree before
 148   using commit->tree.
 149
 150 - The current design uses the 'commit-graph' builtin to generate the graph.
 151   When this feature stabilizes enough to recommend to most users, we should
 152   add automatic graph writes to common operations that create many commits.
 153   For example, one coulde compute a graph on 'clone', 'fetch', or 'repack'
 154   commands.
 155
 156 - A server could provide a commit graph file as part of the network protocol
 157   to avoid extra calculations by clients.
 158
 159 Related Links
 160 -------------
 161 [0] https://bugs.chromium.org/p/git/issues/detail?id=8
 162     Chromium work item for: Serialized Commit Graph
 163
 164 [1] https://public-inbox.org/git/20110713070517.GC18566@sigill.intra.peff.net/
 165     An abandoned patch that introduced generation numbers.
 166
 167 [2] https://public-inbox.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/
 168     Discussion about generation numbers on commits and how they interact
 169     with fsck.
 170
 171 [3] https://public-inbox.org/git/20170907094718.b6kuzp2uhvkmwcso@sigill.intra.peff.net/t/#m7a2ea7b355aeda962e6b86404bcbadc648abfbba
 172     More discussion about generation numbers and not storing them inside
 173     commit objects. A valuable quote:
 174
 175     "I think we should be moving more in the direction of keeping
 176      repo-local caches for optimizations. Reachability bitmaps have been
 177      a big performance win. I think we should be doing the same with our
 178      properties of commits. Not just generation numbers, but making it
 179      cheap to access the graph structure without zlib-inflating whole
 180      commit objects (i.e., packv4 or something like the "metapacks" I
 181      proposed a few years ago)."
 182
 183 [4] https://public-inbox.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u
 184     A patch to remove the ahead-behind calculation from 'status'.