commit-graph: allow cross-alternate chains
[git/git.git] / Documentation / technical / commit-graph.txt
CommitLineData
ae30d7b1
DS
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
4c399442 18The commit-graph file is a supplemental data structure that accelerates
ae30d7b1
DS
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
4c399442 24The commit-graph file stores the commit graph structure along with some
ae30d7b1
DS
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
1472978e
DS
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
ae30d7b1
DS
103Design Details
104--------------
105
4c399442 106- The commit-graph file is stored in a file named 'commit-graph' in the
ae30d7b1
DS
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
950c62bd
DS
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
890345ac
DS
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
1771be90
DS
189Each commit-graph file (except the base, `graph-{hash0}.graph`) contains data
190specifying the hashes of all files in the lower layers. In the above example,
191`graph-{hash1}.graph` contains `{hash0}` while `graph-{hash2}.graph` contains
192`{hash0}` and `{hash1}`.
193
194## Merging commit-graph files
195
196If we only added a new commit-graph file on every write, we would run into a
197linear search problem through many commit-graph files. Instead, we use a merge
198strategy to decide when the stack should collapse some number of levels.
199
200The diagram below shows such a collapse. As a set of new commits are added, it
201is determined by the merge strategy that the files should collapse to
202`graph-{hash1}`. Thus, the new commits, the commits in `graph-{hash2}` and
203the commits in `graph-{hash1}` should be combined into a new `graph-{hash3}`
204file.
205
206 +---------------------+
207 | |
208 | (new commits) |
209 | |
210 +---------------------+
211 | |
212 +-----------------------+ +---------------------+
213 | graph-{hash2} |->| |
214 +-----------------------+ +---------------------+
215 | | |
216 +-----------------------+ +---------------------+
217 | | | |
218 | graph-{hash1} |->| |
219 | | | |
220 +-----------------------+ +---------------------+
221 | tmp_graphXXX
222 +-----------------------+
223 | |
224 | |
225 | |
226 | graph-{hash0} |
227 | |
228 | |
229 | |
230 +-----------------------+
231
232During this process, the commits to write are combined, sorted and we write the
233contents to a temporary file, all while holding a `commit-graph-chain.lock`
234lock-file. When the file is flushed, we rename it to `graph-{hash3}`
235according to the computed `{hash3}`. Finally, we write the new chain data to
236`commit-graph-chain.lock`:
237
238```
239 {hash3}
240 {hash0}
241```
242
243We then close the lock-file.
244
245## Merge Strategy
246
247When writing a set of commits that do not exist in the commit-graph stack of
248height N, we default to creating a new file at level N + 1. We then decide to
249merge with the Nth level if one of two conditions hold:
250
251 1. The expected file size for level N + 1 is at least half the file size for
252 level N.
253
254 2. Level N + 1 contains more than 64,0000 commits.
255
256This decision cascades down the levels: when we merge a level we create a new
257set of commits that then compares to the next level.
258
259The first condition bounds the number of levels to be logarithmic in the total
260number of commits. The second condition bounds the total number of commits in
261a `graph-{hashN}` file and not in the `commit-graph` file, preventing
262significant performance issues when the stack merges and another process only
263partially reads the previous stack.
264
265The merge strategy values (2 for the size multiple, 64,000 for the maximum
266number of commits) could be extracted into config settings for full
267flexibility.
268
c523035c
DS
269## Chains across multiple object directories
270
271In a repo with alternates, we look for the `commit-graph-chain` file starting
272in the local object directory and then in each alternate. The first file that
273exists defines our chain. As we look for the `graph-{hash}` files for
274each `{hash}` in the chain file, we follow the same pattern for the host
275directories.
276
277This allows commit-graphs to be split across multiple forks in a fork network.
278The typical case is a large "base" repo with many smaller forks.
279
280As the base repo advances, it will likely update and merge its commit-graph
281chain more frequently than the forks. If a fork updates their commit-graph after
282the base repo, then it should "reparent" the commit-graph chain onto the new
283chain in the base repo. When reading each `graph-{hash}` file, we track
284the object directory containing it. During a write of a new commit-graph file,
285we check for any changes in the source object directory and read the
286`commit-graph-chain` file for that source and create a new file based on those
287files. During this "reparent" operation, we necessarily need to collapse all
288levels in the fork, as all of the files are invalid against the new base file.
289
290It is crucial to be careful when cleaning up "unreferenced" `graph-{hash}.graph`
291files in this scenario. It falls to the user to define the proper settings for
292their custom environment:
293
294 1. When merging levels in the base repo, the unreferenced files may still be
295 referenced by chains from fork repos.
296
297 2. The expiry time should be set to a length of time such that every fork has
298 time to recompute their commit-graph chain to "reparent" onto the new base
299 file(s).
300
301 3. If the commit-graph chain is updated in the base, the fork will not have
302 access to the new chain until its chain is updated to reference those files.
303 (This may change in the future [5].)
304
ae30d7b1
DS
305Related Links
306-------------
307[0] https://bugs.chromium.org/p/git/issues/detail?id=8
308 Chromium work item for: Serialized Commit Graph
309
310[1] https://public-inbox.org/git/20110713070517.GC18566@sigill.intra.peff.net/
311 An abandoned patch that introduced generation numbers.
312
313[2] https://public-inbox.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/
314 Discussion about generation numbers on commits and how they interact
315 with fsck.
316
317[3] https://public-inbox.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/
318 More discussion about generation numbers and not storing them inside
319 commit objects. A valuable quote:
320
321 "I think we should be moving more in the direction of keeping
322 repo-local caches for optimizations. Reachability bitmaps have been
323 a big performance win. I think we should be doing the same with our
324 properties of commits. Not just generation numbers, but making it
325 cheap to access the graph structure without zlib-inflating whole
326 commit objects (i.e., packv4 or something like the "metapacks" I
327 proposed a few years ago)."
328
329[4] https://public-inbox.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u
330 A patch to remove the ahead-behind calculation from 'status'.
c523035c
DS
331
332[5] https://public-inbox.org/git/f27db281-abad-5043-6d71-cbb083b1c877@gmail.com/
333 A discussion of a "two-dimensional graph position" that can allow reading
334 multiple commit-graph chains at the same time.