From: Stefan Beller <sbeller@google.com>
To: Derrick Stolee <stolee@gmail.com>
Cc: git <git@vger.kernel.org>, Junio C Hamano <gitster@pobox.com>,
Jeff King <peff@peff.net>, Jeff Hostetler <git@jeffhostetler.com>,
Derrick Stolee <dstolee@microsoft.com>
Subject: Re: [PATCH v2 02/14] graph: add commit graph design document
Date: Tue, 30 Jan 2018 18:19:48 -0800 [thread overview]
Message-ID: <CAGZ79kaAnQYQ2pn+=R6pKdESvxaFRLsiXJ4oMf8cD00fRyyNxA@mail.gmail.com> (raw)
In-Reply-To: <1517348383-112294-3-git-send-email-dstolee@microsoft.com>
On Tue, Jan 30, 2018 at 1:39 PM, Derrick Stolee <stolee@gmail.com> wrote:
> Add Documentation/technical/commit-graph.txt with details of the planned
> commit graph feature, including future plans.
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
> Documentation/technical/commit-graph.txt | 189 +++++++++++++++++++++++++++++++
> 1 file changed, 189 insertions(+)
> create mode 100644 Documentation/technical/commit-graph.txt
>
> diff --git a/Documentation/technical/commit-graph.txt b/Documentation/technical/commit-graph.txt
> new file mode 100644
> index 0000000000..cbf88f7264
> --- /dev/null
> +++ b/Documentation/technical/commit-graph.txt
> @@ -0,0 +1,189 @@
> +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 'git show --remerge-diff' and can take minutes to compute depending on
> +history shape.
Sorry for appearing more authoritative than I am here. The --remerge-diff flag
is just floating around the mailing list, and was never merged. (It is
such a cool
feature though, but it would actually confuse users looking for it,
not finding it)
> +There are two main costs here:
> +
> +1. Decompressing and parsing commits.
> +2. Walking the entire graph to avoid topological order mistakes.
> +
> +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
> +next to packfiles either in the .git/objects/pack directory or in the pack
> +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 lexi-
> +cographic 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 can make
> +mistakes with topological orders (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.
> +
> +Design Details
> +--------------
> +
> +- A graph file is stored in a file named 'graph-<hash>.graph' in the pack
> + directory. This could be stored in an alternate.
> +
> +- The most-recent graph file hash is stored in a 'graph-head' file for
> + immediate access and storing backup graphs. This could be stored in an
> + alternate, and refers to a 'graph-<hash>.graph' file in the same pack
> + directory.
> +
> +- The core.commitgraph config setting must be on to consume graph files.
> +
> +- The file format includes parameters for the object id length and hash
> + algorithm, so a future change of hash algorithm does not require a change
> + in format.
> +
> +Current Limitations
> +-------------------
> +
> +- Only one graph file is used at one time. This allows the integer position
> + to seek into the single graph file. It is possible to extend the model
> + for multiple graph files, but that is currently not part of the design.
> +
> +- .graph files are managed only by the 'commit-graph' builtin. These are not
> + updated automatically during clone, fetch, repack, or creating new commits.
> +
> +- There is no '--verify' option for the 'commit-graph' builtin to verify the
> + contents of the graph file agree with the contents in the ODB.
> +
> +- When rewriting the graph, we do not check for a commit still existing
> + in the ODB, so garbage collection may remove commits.
> +
> +- Generation numbers are not computed in the current version. The file
> + format supports storing them, along with a mechanism to upgrade from
> + a file without generation numbers to one that uses them.
> +
> +Future Work
> +-----------
> +
> +- The file format includes room for precomputed generation numbers. These
> + are not currently computed, so all generation numbers will be marked as
> + 0 (or "uncomputed"). A later patch will include this calculation.
> +
> +- The commit graph is currently incompatible with commit grafts. This can be
> + remedied by duplicating or refactoring the current graft logic.
> +
> +- After computing and storing generation numbers, we must make graph
> + walks aware of generation numbers to gain the performance benefits they
> + enable. This will mostly be accomplished by swapping a commit-date-ordered
> + priority queue with one ordered by generation number. The following
> + operations are important candidates:
> +
> + - paint_down_to_common()
> + - 'log --topo-order'
> +
> +- The graph currently only adds commits to a previously existing graph.
> + When writing a new graph, we could check that the ODB still contains
> + the commits and choose to remove the commits that are deleted from the
> + ODB. For performance reasons, this check should remain optional.
> +
> +- Currently, parse_commit_gently() requires filling in the root tree
> + object for a commit. This passes through lookup_tree() and consequently
> + lookup_object(). Also, it calls lookup_commit() when loading the parents.
> + These method calls check the ODB for object existence, even if the
> + consumer does not need the content. For example, we do not need the
> + tree contents when computing merge bases. Now that commit parsing is
> + removed from the computation time, these lookup operations are the
> + slowest operations keeping graph walks from being fast. Consider
> + loading these objects without verifying their existence in the ODB and
> + only loading them fully when consumers need them. Consider a method
> + such as "ensure_tree_loaded(commit)" that fully loads a tree before
> + using commit->tree.
> +
> +- The current design uses the 'commit-graph' builtin to generate the graph.
> + When this feature stabilizes enough to recommend to most users, we should
> + add automatic graph writes to common operations that create many commits.
> + For example, one coulde compute a graph on 'clone', 'fetch', or 'repack'
> + commands.
> +
> +- A server could provide a commit graph file as part of the network protocol
> + to avoid extra calculations by clients.
> +
> +Related Links
> +-------------
> +[0] https://bugs.chromium.org/p/git/issues/detail?id=8
> + Chromium work item for: Serialized Commit Graph
> +
> +[1] https://public-inbox.org/git/20110713070517.GC18566@sigill.intra.peff.net/
> + An abandoned patch that introduced generation numbers.
> +
> +[2] https://public-inbox.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/
> + Discussion about generation numbers on commits and how they interact
> + with fsck.
> +
> +[3] https://public-inbox.org/git/20170907094718.b6kuzp2uhvkmwcso@sigill.intra.peff.net/t/#m7a2ea7b355aeda962e6b86404bcbadc648abfbba
> + 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://public-inbox.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u
> + A patch to remove the ahead-behind calculation from 'status'.
> --
> 2.16.0.15.g9c3cf44.dirty
>
next prev parent reply other threads:[~2018-01-31 2:20 UTC|newest]
Thread overview: 146+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-01-30 21:39 [PATCH v2 00/14] Serialized Git Commit Graph Derrick Stolee
2018-01-30 21:39 ` [PATCH v2 01/14] commit-graph: add format document Derrick Stolee
2018-02-01 21:44 ` Jonathan Tan
2018-01-30 21:39 ` [PATCH v2 02/14] graph: add commit graph design document Derrick Stolee
2018-01-31 2:19 ` Stefan Beller [this message]
2018-01-30 21:39 ` [PATCH v2 03/14] commit-graph: create git-commit-graph builtin Derrick Stolee
2018-02-02 0:53 ` SZEDER Gábor
2018-01-30 21:39 ` [PATCH v2 04/14] commit-graph: implement construct_commit_graph() Derrick Stolee
2018-02-01 22:23 ` Jonathan Tan
2018-02-01 23:46 ` SZEDER Gábor
2018-02-02 15:32 ` SZEDER Gábor
2018-02-05 16:06 ` Derrick Stolee
2018-02-07 15:08 ` SZEDER Gábor
2018-02-07 15:10 ` Derrick Stolee
2018-01-30 21:39 ` [PATCH v2 05/14] commit-graph: implement git-commit-graph --write Derrick Stolee
2018-02-01 23:33 ` Jonathan Tan
2018-02-02 18:36 ` Stefan Beller
2018-02-02 22:48 ` Junio C Hamano
2018-02-03 1:58 ` Derrick Stolee
2018-02-03 9:28 ` Jeff King
2018-02-05 18:48 ` Junio C Hamano
2018-02-06 18:55 ` Derrick Stolee
2018-02-01 23:48 ` SZEDER Gábor
2018-02-05 18:07 ` Derrick Stolee
2018-02-02 1:47 ` SZEDER Gábor
2018-01-30 21:39 ` [PATCH v2 06/14] commit-graph: implement git-commit-graph --read Derrick Stolee
2018-01-31 2:22 ` Stefan Beller
2018-02-02 0:02 ` SZEDER Gábor
2018-02-02 0:23 ` Jonathan Tan
2018-02-05 19:29 ` Derrick Stolee
2018-01-30 21:39 ` [PATCH v2 07/14] commit-graph: implement git-commit-graph --update-head Derrick Stolee
2018-02-02 1:35 ` SZEDER Gábor
2018-02-05 21:01 ` Derrick Stolee
2018-02-02 2:45 ` SZEDER Gábor
2018-01-30 21:39 ` [PATCH v2 08/14] commit-graph: implement git-commit-graph --clear Derrick Stolee
2018-02-02 4:01 ` SZEDER Gábor
2018-01-30 21:39 ` [PATCH v2 09/14] commit-graph: teach git-commit-graph --delete-expired Derrick Stolee
2018-02-02 15:04 ` SZEDER Gábor
2018-01-30 21:39 ` [PATCH v2 10/14] commit-graph: add core.commitgraph setting Derrick Stolee
2018-01-31 22:44 ` Igor Djordjevic
2018-02-02 16:01 ` SZEDER Gábor
2018-01-30 21:39 ` [PATCH v2 11/14] commit: integrate commit graph with commit parsing Derrick Stolee
2018-02-02 1:51 ` Jonathan Tan
2018-02-06 14:53 ` Derrick Stolee
2018-01-30 21:39 ` [PATCH v2 12/14] commit-graph: read only from specific pack-indexes Derrick Stolee
2018-01-30 21:39 ` [PATCH v2 13/14] commit-graph: close under reachability Derrick Stolee
2018-01-30 21:39 ` [PATCH v2 14/14] commit-graph: build graph from starting commits Derrick Stolee
2018-01-30 21:47 ` [PATCH v2 00/14] Serialized Git Commit Graph Stefan Beller
2018-02-01 2:34 ` Stefan Beller
2018-02-08 20:37 ` [PATCH v3 " Derrick Stolee
2018-02-08 20:37 ` [PATCH v3 01/14] commit-graph: add format document Derrick Stolee
2018-02-08 21:21 ` Junio C Hamano
2018-02-08 21:33 ` Derrick Stolee
2018-02-08 23:16 ` Junio C Hamano
2018-02-08 20:37 ` [PATCH v3 02/14] graph: add commit graph design document Derrick Stolee
2018-02-08 20:37 ` [PATCH v3 03/14] commit-graph: create git-commit-graph builtin Derrick Stolee
2018-02-08 21:27 ` Junio C Hamano
2018-02-08 21:36 ` Derrick Stolee
2018-02-08 23:21 ` Junio C Hamano
2018-02-08 20:37 ` [PATCH v3 04/14] commit-graph: implement write_commit_graph() Derrick Stolee
2018-02-08 22:14 ` Junio C Hamano
2018-02-15 18:19 ` Junio C Hamano
2018-02-15 18:23 ` Derrick Stolee
2018-02-08 20:37 ` [PATCH v3 05/14] commit-graph: implement 'git-commit-graph write' Derrick Stolee
2018-02-13 21:57 ` Jonathan Tan
2018-02-08 20:37 ` [PATCH v3 06/14] commit-graph: implement 'git-commit-graph read' Derrick Stolee
2018-02-08 23:38 ` Junio C Hamano
2018-02-08 20:37 ` [PATCH v3 07/14] commit-graph: update graph-head during write Derrick Stolee
2018-02-12 18:56 ` Junio C Hamano
2018-02-12 20:37 ` Junio C Hamano
2018-02-12 21:24 ` Derrick Stolee
2018-02-13 22:38 ` Jonathan Tan
2018-02-08 20:37 ` [PATCH v3 08/14] commit-graph: implement 'git-commit-graph clear' Derrick Stolee
2018-02-13 22:49 ` Jonathan Tan
2018-02-08 20:37 ` [PATCH v3 09/14] commit-graph: implement --delete-expired Derrick Stolee
2018-02-08 20:37 ` [PATCH v3 10/14] commit-graph: add core.commitGraph setting Derrick Stolee
2018-02-08 20:37 ` [PATCH v3 11/14] commit: integrate commit graph with commit parsing Derrick Stolee
2018-02-14 0:12 ` Jonathan Tan
2018-02-14 18:08 ` Derrick Stolee
2018-02-15 18:25 ` Junio C Hamano
2018-02-08 20:37 ` [PATCH v3 12/14] commit-graph: close under reachability Derrick Stolee
2018-02-08 20:37 ` [PATCH v3 13/14] commit-graph: read only from specific pack-indexes Derrick Stolee
2018-02-08 20:37 ` [PATCH v3 14/14] commit-graph: build graph from starting commits Derrick Stolee
2018-02-09 13:02 ` SZEDER Gábor
2018-02-09 13:45 ` Derrick Stolee
2018-02-14 18:15 ` [PATCH v3 00/14] Serialized Git Commit Graph Derrick Stolee
2018-02-14 18:27 ` Stefan Beller
2018-02-14 19:11 ` Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 00/13] " Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 01/13] commit-graph: add format document Derrick Stolee
2018-02-20 20:49 ` Junio C Hamano
2018-02-21 19:23 ` Stefan Beller
2018-02-21 19:45 ` Derrick Stolee
2018-02-21 19:48 ` Stefan Beller
2018-03-30 13:25 ` Jakub Narebski
2018-04-02 13:09 ` Derrick Stolee
2018-04-02 14:09 ` Jakub Narebski
2018-02-19 18:53 ` [PATCH v4 02/13] graph: add commit graph design document Derrick Stolee
2018-02-20 21:42 ` Junio C Hamano
2018-02-23 15:44 ` Derrick Stolee
2018-02-21 19:34 ` Stefan Beller
2018-02-19 18:53 ` [PATCH v4 03/13] commit-graph: create git-commit-graph builtin Derrick Stolee
2018-02-20 21:51 ` Junio C Hamano
2018-02-21 18:58 ` Junio C Hamano
2018-02-23 16:07 ` Derrick Stolee
2018-02-26 16:25 ` SZEDER Gábor
2018-02-26 17:08 ` Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 04/13] commit-graph: implement write_commit_graph() Derrick Stolee
2018-02-20 22:57 ` Junio C Hamano
2018-02-23 17:23 ` Derrick Stolee
2018-02-23 19:30 ` Junio C Hamano
2018-02-23 19:48 ` Junio C Hamano
2018-02-23 20:02 ` Derrick Stolee
2018-02-26 16:10 ` SZEDER Gábor
2018-02-28 18:47 ` Junio C Hamano
2018-02-19 18:53 ` [PATCH v4 05/13] commit-graph: implement 'git-commit-graph write' Derrick Stolee
2018-02-21 19:25 ` Junio C Hamano
2018-02-19 18:53 ` [PATCH v4 06/13] commit-graph: implement git commit-graph read Derrick Stolee
2018-02-21 20:11 ` Junio C Hamano
2018-02-22 18:25 ` Junio C Hamano
2018-02-19 18:53 ` [PATCH v4 07/13] commit-graph: implement --set-latest Derrick Stolee
2018-02-22 18:31 ` Junio C Hamano
2018-02-23 17:53 ` Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 08/13] commit-graph: implement --delete-expired Derrick Stolee
2018-02-21 21:34 ` Stefan Beller
2018-02-23 17:43 ` Derrick Stolee
2018-02-22 18:48 ` Junio C Hamano
2018-02-23 17:59 ` Derrick Stolee
2018-02-23 19:33 ` Junio C Hamano
2018-02-23 19:41 ` Derrick Stolee
2018-02-23 19:51 ` Junio C Hamano
2018-02-19 18:53 ` [PATCH v4 09/13] commit-graph: add core.commitGraph setting Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 10/13] commit-graph: close under reachability Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 11/13] commit: integrate commit graph with commit parsing Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 12/13] commit-graph: read only from specific pack-indexes Derrick Stolee
2018-02-21 22:25 ` Stefan Beller
2018-02-23 19:19 ` Derrick Stolee
2018-02-19 18:53 ` [PATCH v4 13/13] commit-graph: build graph from starting commits Derrick Stolee
2018-03-30 11:10 ` [PATCH v4 00/13] Serialized Git Commit Graph Jakub Narebski
2018-04-02 13:02 ` Derrick Stolee
2018-04-02 14:46 ` Jakub Narebski
2018-04-02 15:02 ` Derrick Stolee
2018-04-02 17:35 ` Stefan Beller
2018-04-02 17:54 ` Derrick Stolee
2018-04-02 18:02 ` Stefan Beller
2018-04-07 22:37 ` Jakub Narebski
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAGZ79kaAnQYQ2pn+=R6pKdESvxaFRLsiXJ4oMf8cD00fRyyNxA@mail.gmail.com' \
--to=sbeller@google.com \
--cc=dstolee@microsoft.com \
--cc=git@jeffhostetler.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=peff@peff.net \
--cc=stolee@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).