diff options
Diffstat (limited to 'third_party/git/Documentation/technical/commit-graph.txt')
| -rw-r--r-- | third_party/git/Documentation/technical/commit-graph.txt | 350 |
1 files changed, 0 insertions, 350 deletions
diff --git a/third_party/git/Documentation/technical/commit-graph.txt b/third_party/git/Documentation/technical/commit-graph.txt deleted file mode 100644 index f14a7659aa87..000000000000 --- a/third_party/git/Documentation/technical/commit-graph.txt +++ /dev/null @@ -1,350 +0,0 @@ -Git Commit Graph Design Notes -============================= - -Git walks the commit graph for many reasons, including: - -1. Listing and filtering commit history. -2. Computing merge bases. - -These operations can become slow as the commit count grows. The merge -base calculation shows up in many user-facing commands, such as 'merge-base' -or 'status' and can take minutes to compute depending on history shape. - -There are two main costs here: - -1. Decompressing and parsing commits. -2. Walking the entire graph to satisfy topological order constraints. - -The commit-graph file is a supplemental data structure that accelerates -commit graph walks. If a user downgrades or disables the 'core.commitGraph' -config setting, then the existing ODB is sufficient. The file is stored -as "commit-graph" either in the .git/objects/info directory or in the info -directory of an alternate. - -The commit-graph file stores the commit graph structure along with some -extra metadata to speed up graph walks. By listing commit OIDs in -lexicographic order, we can identify an integer position for each commit -and refer to the parents of a commit using those integer positions. We -use binary search to find initial commits and then use the integer -positions for fast lookups during the walk. - -A consumer may load the following info for a commit from the graph: - -1. The commit OID. -2. The list of parents, along with their integer position. -3. The commit date. -4. The root tree OID. -5. The generation number (see definition below). - -Values 1-4 satisfy the requirements of parse_commit_gently(). - -Define the "generation number" of a commit recursively as follows: - - * A commit with no parents (a root commit) has generation number one. - - * A commit with at least one parent has generation number one more than - the largest generation number among its parents. - -Equivalently, the generation number of a commit A is one more than the -length of a longest path from A to a root commit. The recursive definition -is easier to use for computation and observing the following property: - - If A and B are commits with generation numbers N and M, respectively, - and N <= M, then A cannot reach B. That is, we know without searching - that B is not an ancestor of A because it is further from a root commit - than A. - - Conversely, when checking if A is an ancestor of B, then we only need - to walk commits until all commits on the walk boundary have generation - number at most N. If we walk commits using a priority queue seeded by - generation numbers, then we always expand the boundary commit with highest - generation number and can easily detect the stopping condition. - -This property can be used to significantly reduce the time it takes to -walk commits and determine topological relationships. Without generation -numbers, the general heuristic is the following: - - If A and B are commits with commit time X and Y, respectively, and - X < Y, then A _probably_ cannot reach B. - -This heuristic is currently used whenever the computation is allowed to -violate topological relationships due to clock skew (such as "git log" -with default order), but is not used when the topological order is -required (such as merge base calculations, "git log --graph"). - -In practice, we expect some commits to be created recently and not stored -in the commit graph. We can treat these commits as having "infinite" -generation number and walk until reaching commits with known generation -number. - -We use the macro GENERATION_NUMBER_INFINITY = 0xFFFFFFFF to mark commits not -in the commit-graph file. If a commit-graph file was written by a version -of Git that did not compute generation numbers, then those commits will -have generation number represented by the macro GENERATION_NUMBER_ZERO = 0. - -Since the commit-graph file is closed under reachability, we can guarantee -the following weaker condition on all commits: - - If A and B are commits with generation numbers N and M, respectively, - and N < M, then A cannot reach B. - -Note how the strict inequality differs from the inequality when we have -fully-computed generation numbers. Using strict inequality may result in -walking a few extra commits, but the simplicity in dealing with commits -with generation number *_INFINITY or *_ZERO is valuable. - -We use the macro GENERATION_NUMBER_MAX = 0x3FFFFFFF to for commits whose -generation numbers are computed to be at least this value. We limit at -this value since it is the largest value that can be stored in the -commit-graph file using the 30 bits available to generation numbers. This -presents another case where a commit can have generation number equal to -that of a parent. - -Design Details --------------- - -- The commit-graph file is stored in a file named 'commit-graph' in the - .git/objects/info directory. This could be stored in the info directory - of an alternate. - -- The core.commitGraph config setting must be on to consume graph files. - -- The file format includes parameters for the object ID hash function, - so a future change of hash algorithm does not require a change in format. - -- Commit grafts and replace objects can change the shape of the commit - history. The latter can also be enabled/disabled on the fly using - `--no-replace-objects`. This leads to difficultly storing both possible - interpretations of a commit id, especially when computing generation - numbers. The commit-graph will not be read or written when - replace-objects or grafts are present. - -- Shallow clones create grafts of commits by dropping their parents. This - leads the commit-graph to think those commits have generation number 1. - If and when those commits are made unshallow, those generation numbers - become invalid. Since shallow clones are intended to restrict the commit - history to a very small set of commits, the commit-graph feature is less - helpful for these clones, anyway. The commit-graph will not be read or - written when shallow commits are present. - -Commit Graphs Chains --------------------- - -Typically, repos grow with near-constant velocity (commits per day). Over time, -the number of commits added by a fetch operation is much smaller than the -number of commits in the full history. By creating a "chain" of commit-graphs, -we enable fast writes of new commit data without rewriting the entire commit -history -- at least, most of the time. - -## File Layout - -A commit-graph chain uses multiple files, and we use a fixed naming convention -to organize these files. Each commit-graph file has a name -`$OBJDIR/info/commit-graphs/graph-{hash}.graph` where `{hash}` is the hex- -valued hash stored in the footer of that file (which is a hash of the file's -contents before that hash). For a chain of commit-graph files, a plain-text -file at `$OBJDIR/info/commit-graphs/commit-graph-chain` contains the -hashes for the files in order from "lowest" to "highest". - -For example, if the `commit-graph-chain` file contains the lines - -``` - {hash0} - {hash1} - {hash2} -``` - -then the commit-graph chain looks like the following diagram: - - +-----------------------+ - | graph-{hash2}.graph | - +-----------------------+ - | - +-----------------------+ - | | - | graph-{hash1}.graph | - | | - +-----------------------+ - | - +-----------------------+ - | | - | | - | | - | graph-{hash0}.graph | - | | - | | - | | - +-----------------------+ - -Let X0 be the number of commits in `graph-{hash0}.graph`, X1 be the number of -commits in `graph-{hash1}.graph`, and X2 be the number of commits in -`graph-{hash2}.graph`. If a commit appears in position i in `graph-{hash2}.graph`, -then we interpret this as being the commit in position (X0 + X1 + i), and that -will be used as its "graph position". The commits in `graph-{hash2}.graph` use these -positions to refer to their parents, which may be in `graph-{hash1}.graph` or -`graph-{hash0}.graph`. We can navigate to an arbitrary commit in position j by checking -its containment in the intervals [0, X0), [X0, X0 + X1), [X0 + X1, X0 + X1 + -X2). - -Each commit-graph file (except the base, `graph-{hash0}.graph`) contains data -specifying the hashes of all files in the lower layers. In the above example, -`graph-{hash1}.graph` contains `{hash0}` while `graph-{hash2}.graph` contains -`{hash0}` and `{hash1}`. - -## Merging commit-graph files - -If we only added a new commit-graph file on every write, we would run into a -linear search problem through many commit-graph files. Instead, we use a merge -strategy to decide when the stack should collapse some number of levels. - -The diagram below shows such a collapse. As a set of new commits are added, it -is determined by the merge strategy that the files should collapse to -`graph-{hash1}`. Thus, the new commits, the commits in `graph-{hash2}` and -the commits in `graph-{hash1}` should be combined into a new `graph-{hash3}` -file. - - +---------------------+ - | | - | (new commits) | - | | - +---------------------+ - | | - +-----------------------+ +---------------------+ - | graph-{hash2} |->| | - +-----------------------+ +---------------------+ - | | | - +-----------------------+ +---------------------+ - | | | | - | graph-{hash1} |->| | - | | | | - +-----------------------+ +---------------------+ - | tmp_graphXXX - +-----------------------+ - | | - | | - | | - | graph-{hash0} | - | | - | | - | | - +-----------------------+ - -During this process, the commits to write are combined, sorted and we write the -contents to a temporary file, all while holding a `commit-graph-chain.lock` -lock-file. When the file is flushed, we rename it to `graph-{hash3}` -according to the computed `{hash3}`. Finally, we write the new chain data to -`commit-graph-chain.lock`: - -``` - {hash3} - {hash0} -``` - -We then close the lock-file. - -## Merge Strategy - -When writing a set of commits that do not exist in the commit-graph stack of -height N, we default to creating a new file at level N + 1. We then decide to -merge with the Nth level if one of two conditions hold: - - 1. `--size-multiple=<X>` is specified or X = 2, and the number of commits in - level N is less than X times the number of commits in level N + 1. - - 2. `--max-commits=<C>` is specified with non-zero C and the number of commits - in level N + 1 is more than C commits. - -This decision cascades down the levels: when we merge a level we create a new -set of commits that then compares to the next level. - -The first condition bounds the number of levels to be logarithmic in the total -number of commits. The second condition bounds the total number of commits in -a `graph-{hashN}` file and not in the `commit-graph` file, preventing -significant performance issues when the stack merges and another process only -partially reads the previous stack. - -The merge strategy values (2 for the size multiple, 64,000 for the maximum -number of commits) could be extracted into config settings for full -flexibility. - -## Deleting graph-{hash} files - -After a new tip file is written, some `graph-{hash}` files may no longer -be part of a chain. It is important to remove these files from disk, eventually. -The main reason to delay removal is that another process could read the -`commit-graph-chain` file before it is rewritten, but then look for the -`graph-{hash}` files after they are deleted. - -To allow holding old split commit-graphs for a while after they are unreferenced, -we update the modified times of the files when they become unreferenced. Then, -we scan the `$OBJDIR/info/commit-graphs/` directory for `graph-{hash}` -files whose modified times are older than a given expiry window. This window -defaults to zero, but can be changed using command-line arguments or a config -setting. - -## Chains across multiple object directories - -In a repo with alternates, we look for the `commit-graph-chain` file starting -in the local object directory and then in each alternate. The first file that -exists defines our chain. As we look for the `graph-{hash}` files for -each `{hash}` in the chain file, we follow the same pattern for the host -directories. - -This allows commit-graphs to be split across multiple forks in a fork network. -The typical case is a large "base" repo with many smaller forks. - -As the base repo advances, it will likely update and merge its commit-graph -chain more frequently than the forks. If a fork updates their commit-graph after -the base repo, then it should "reparent" the commit-graph chain onto the new -chain in the base repo. When reading each `graph-{hash}` file, we track -the object directory containing it. During a write of a new commit-graph file, -we check for any changes in the source object directory and read the -`commit-graph-chain` file for that source and create a new file based on those -files. During this "reparent" operation, we necessarily need to collapse all -levels in the fork, as all of the files are invalid against the new base file. - -It is crucial to be careful when cleaning up "unreferenced" `graph-{hash}.graph` -files in this scenario. It falls to the user to define the proper settings for -their custom environment: - - 1. When merging levels in the base repo, the unreferenced files may still be - referenced by chains from fork repos. - - 2. The expiry time should be set to a length of time such that every fork has - time to recompute their commit-graph chain to "reparent" onto the new base - file(s). - - 3. If the commit-graph chain is updated in the base, the fork will not have - access to the new chain until its chain is updated to reference those files. - (This may change in the future [5].) - -Related Links -------------- -[0] https://bugs.chromium.org/p/git/issues/detail?id=8 - Chromium work item for: Serialized Commit Graph - -[1] https://lore.kernel.org/git/20110713070517.GC18566@sigill.intra.peff.net/ - An abandoned patch that introduced generation numbers. - -[2] https://lore.kernel.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/ - Discussion about generation numbers on commits and how they interact - with fsck. - -[3] https://lore.kernel.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/ - More discussion about generation numbers and not storing them inside - commit objects. A valuable quote: - - "I think we should be moving more in the direction of keeping - repo-local caches for optimizations. Reachability bitmaps have been - a big performance win. I think we should be doing the same with our - properties of commits. Not just generation numbers, but making it - cheap to access the graph structure without zlib-inflating whole - commit objects (i.e., packv4 or something like the "metapacks" I - proposed a few years ago)." - -[4] https://lore.kernel.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u - A patch to remove the ahead-behind calculation from 'status'. - -[5] https://lore.kernel.org/git/f27db281-abad-5043-6d71-cbb083b1c877@gmail.com/ - A discussion of a "two-dimensional graph position" that can allow reading - multiple commit-graph chains at the same time. |