Re: [PATCH v4 02/13] graph: add commit graph design document

[Derrick Stolee]

On 2/20/2018 4:42 PM, Junio C Hamano wrote:

Derrick Stolee  writes:


+2. Walking the entire graph to avoid topological order mistakes.

You have at least one more mention of "topological order mistakes"
below, but we commonly refer to this issue and blame it for "clock
skew".  Using the word highlights that there is no "mistake" in topo
order algorithm and mistakes are in the commit timestamps.


I'll drop the word "mistakes" and instead here say:

  2. Walking the entire graph to satisfy topological order constraints.

and later say

  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.

Hmm, "pretend infinity" is an interesting approach---I need to think
about it a bit more if it is sufficient.


Since we require the commit graph file to be closed under reachability, 
the commits reachable from the file all have "finite" generation number.





+- .graph files are managed only by the 'commit-graph' builtin. These are not
+  updated automatically during clone, fetch, repack, or creating new commits.

OK.  s/builtin/subcommand/; it does not make much difference if it
is a built-in or standalone command.


+- There is no 'verify' subcommand for the 'commit-graph' builtin to verify
+  the contents of the graph file agree with the contents in the ODB.

I am not entirely sure about the merit of going into this level of
detail.  Being able to use only a single file looks like a more
fundamental design limitation, which deserves to be decribed in this
section, and we could ship the subsystem with that limitation.

But the lack of verify that can be called from fsck is merely the
matter of not the subsystem being mature enough (to be written,
reviewed and tested) and not a fundamental one, and we will not be
shipping the subsystem until that limitation is lifted.

So I'd guess that we prefer this bullet item to be in the commit log
message, not here, that describes the current status of the
development (as opposed to the state of the subsystem).


I was treating this design document as a living document that will be 
updated as the feature matures. It is difficult to time when to discuss 
these limitations, since in this commit the graph feature is not 
implemented at all. But, it is important to have _some_ design document 
before continuing to implement the feature.


I can remove this bullet, but I'm not sure which commit message would be 
appropriate to contain that information.


I do intend to remove these limitations and future work bullets as they 
are implemented in later patches.





+- 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.

Exactly the same comment as above applies to this item.


+- The commit graph is currently incompatible with commit grafts. This can be
+  remedied by duplicating or refactoring the current graft logic.

Hmm.  Can it be lifted without first allowing us to use more than
one commit graph file (i.e. one for "traverse while honoring the
grafts", the other for "traverse while ignoring the grafts")?


I consider this list unordered, but will move this bullet to the top and 
replace its first sentence with:


  The commit graph feature currently does not honor commit grafts.




+- 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'

Yes.


+- 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.

The last sentence is somehow unconvincing.  It probably is not
appropriate for the "Future Work" section to be making a hurried
design decision before having any working verification code to run
benchmark on.


I'll remove this entire block, since it is not relevant starting at v4. 
I dropped this "additive only" step in v4 and forgot to remove the bullet.





+- Currently, parse_commit_gently() requires filling in the root tree
+  object for a commit. This passes through lookup_tree() and consequently
+  

Re: [PATCH v4 02/13] graph: add commit graph design document

[Stefan Beller]

> +[3] 
> https://public-inbox.org/git/20170907094718.b6kuzp2uhvkmw...@sigill.intra.peff.net/t/#m7a2ea7b355aeda962e6b86404bcbadc648abfbba
> +More discussion about generation numbers and not storing them inside
> +commit objects. A valuable quote:

Unlike the other public inbox links this links to a discussion with
all messages on one page,
https://public-inbox.org/git/20170908034739.4op3w4f2ma5s6...@sigill.intra.peff.net/
would
have this be more inline with the other links. (this is a super small
nit, which I am not sure if
we care about at all; the rest of the doc is awesome!)

Re: [PATCH v4 02/13] graph: add commit graph design document

[Junio C Hamano]

Derrick Stolee  writes:

> +2. Walking the entire graph to avoid topological order mistakes.

You have at least one more mention of "topological order mistakes"
below, but we commonly refer to this issue and blame it for "clock
skew".  Using the word highlights that there is no "mistake" in topo
order algorithm and mistakes are in the commit timestamps.

> +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.

Hmm, "pretend infinity" is an interesting approach---I need to think
about it a bit more if it is sufficient.

> +- .graph files are managed only by the 'commit-graph' builtin. These are not
> +  updated automatically during clone, fetch, repack, or creating new commits.

OK.  s/builtin/subcommand/; it does not make much difference if it
is a built-in or standalone command.

> +- There is no 'verify' subcommand for the 'commit-graph' builtin to verify
> +  the contents of the graph file agree with the contents in the ODB.

I am not entirely sure about the merit of going into this level of
detail.  Being able to use only a single file looks like a more
fundamental design limitation, which deserves to be decribed in this
section, and we could ship the subsystem with that limitation.

But the lack of verify that can be called from fsck is merely the
matter of not the subsystem being mature enough (to be written,
reviewed and tested) and not a fundamental one, and we will not be
shipping the subsystem until that limitation is lifted.

So I'd guess that we prefer this bullet item to be in the commit log
message, not here, that describes the current status of the
development (as opposed to the state of the subsystem).

> +- 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.

Exactly the same comment as above applies to this item.

> +- The commit graph is currently incompatible with commit grafts. This can be
> +  remedied by duplicating or refactoring the current graft logic.

Hmm.  Can it be lifted without first allowing us to use more than
one commit graph file (i.e. one for "traverse while honoring the
grafts", the other for "traverse while ignoring the grafts")?

> +- 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'

Yes.

> +- 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.

The last sentence is somehow unconvincing.  It probably is not
appropriate for the "Future Work" section to be making a hurried
design decision before having any working verification code to run
benchmark on.

> +- 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.

Very good idea.

> +- 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.

s/coulde/could/.

Also do not forget "fsck" that calls "verify".  That is more urgent
than intergration with any other subcommand.

> +- A server could provide a commit graph file as part of the network protocol
> +  to avoid extra calculations by clients.

We need to assess the riskiness and threat models regarding this, if
we really want to follow this "could" through.  I would imagine that
the cost for verification is comparable 

[PATCH v4 02/13] graph: add commit graph design document

[Derrick Stolee]

Add Documentation/technical/commit-graph.txt with details of the planned
commit graph feature, including future plans.

Signed-off-by: Derrick Stolee 
---
 Documentation/technical/commit-graph.txt | 185 +++
 1 file changed, 185 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 000..e52ab23
--- /dev/null
+++ b/Documentation/technical/commit-graph.txt
@@ -0,0 +1,185 @@
+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 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
+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 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-.graph' in the
+  .git/objects/info directory. This could be stored in the info directory
+  of an alternate.
+
+- The latest graph file name is stored in a 'graph-latest' file next to
+  the graph files. This allows atomic swaps of latest graph files without
+  race conditions with concurrent processes.
+
+- 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.
+
+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