Re: [PATCH 01/14] graph: add packed graph design document

[Derrick Stolee <stolee@gmail.com>]

On 1/25/2018 4:14 PM, Junio C Hamano wrote:
> Derrick Stolee <stolee@gmail.com> writes:
>
>> Add Documentation/technical/packed-graph.txt with details of the planned
>> packed graph feature, including future plans.
>>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>> ---
>>   Documentation/technical/packed-graph.txt | 185 +++++++++++++++++++++++++++++++
>>   1 file changed, 185 insertions(+)
>>   create mode 100644 Documentation/technical/packed-graph.txt
> I really wanted to like having this patch at the beginning, but
> unfortunatelly I didn't see the actual file format description,
> which was a bit disappointing.  An example of the things that I was
> curious about was how the "integer ID" is used to access into the
> file.  If we could somehow use "integer ID" as an index into an
> array of fixed size elements, it would be ideal to gain "fast
> lookups", but because of the "list of parents" thing, it needs some
> trickery to do so, and that was among the things that I wanted to
> see how much thought went into the design, for example.

There is definitely a chicken-or-the-egg situation here. I'm happy to 
start with the format before the design document.

I can try to expand this "integer ID" concept, but you can see how I use 
it in the following method from patch 11/14:

+int parse_packed_commit(struct commit *item)
+{
+        if (!core_graph)
+                return 0;
+        if (item->object.parsed)
+                return 1;
+
+        prepare_packed_graph();
+        if (packed_graph) {
+                uint32_t pos;
+                int found;
+                if (item->graphId != 0xFFFFFFFF) {
+                        pos = item->graphId;
+                        found = 1;
+                } else {
+                        found = bsearch_graph(packed_graph, 
&(item->object.oid), &pos);
+                }
+
+                if (found)
+                        return fill_packed_commit(item, packed_graph, pos);
+        }
+
+        return 0;
+}

Note that if item->graphId has a "real" value (not 0xFFFFFFFF which in 
hindsight should be a macro) then we navigate directly to that position 
in the graph. Otherwise, we use binary search to query the graph's 
commit list to find the position (if the commit is packed).

>> diff --git a/Documentation/technical/packed-graph.txt b/Documentation/technical/packed-graph.txt
>> new file mode 100644
>> index 0000000000..fcc0c83874
>> --- /dev/null
>> +++ b/Documentation/technical/packed-graph.txt
>> @@ -0,0 +1,185 @@
>> +Git Packed 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 above 100K.
>> +The merge base calculation shows up in many user-facing commands, such
>> +as 'status' and 'fetch' and can take minutes to compute depending on
>> +data shape. There are two main costs here:
> s/data shape/history shape/ may make it even clearer.
>
>> +1. The commit OID.
>> +2. The list of parents.
>> +3. The commit date.
>> +4. The root tree OID.
>> +5. An integer ID for fast lookups in the graph.
>> +6. The generation number (see definition below).
>> +
>> +Values 1-4 satisfy the requirements of parse_commit_gently().
>> +
>> +By providing an integer ID we can avoid lookups in the graph as we walk
>> +commits. Specifically, we need to provide the integer ID of the parent
>> +commits so we navigate directly to their information on request.
> Commits created after a packed graph file is built may of course not
> appear in a packed graph file, but that is OK because they never need
> to be listed as parents of commits in the file.  So "list of parents"
> can always refer to the parents using the "integer ID for fast lookup".

One thing I need to test locally is what happens with boundary commits 
of a shallow clone. The commit's parents are not in the repo, so they 
will not be in the graph. I think that parse_commit_buffer() drops the 
parents, so the graph will treat them as root commits.

> Makes sense.  Item 2. might want to say "The list of parents, using
> the fast lookup integer ID (see 5.) as reference instead of OID",
> though.

That will be more specific, thanks.

>> +Define the "generation number" of a commit recursively as follows:
>> + * A commit with no parents (a root commit) has generation number 1.
>> + * A commit with at least one parent has generation number 1 more than
>> +   the largest generation number among its parents.
>> +Equivalently, the generation number is one more than the length of a
>> +longest path from the commit to a root commit.
> When a commit A can reach roots X and Y, and Y is further than X,
> the distance between Y and A becomes A's generation number.  "One
> more than the length of the path from the commit to the furthest
> root commit it can reach", in other words.

My "Equivalently,..." sentence is mangled. What I mean is:

     Equivalently, the generation number of A is one more than
     the length of a longest path from A to a root commit.

I intended to make a non-recursive definition, and the "one more than" 
here could easily be conflated with the "one more than" in the recursive 
definition. The reason for "one more than" is that root commits have a 
path of length zero but generation number one.

Reminder to self: use "one" instead of "1" in the recursive definition.

>> +The recursive definition
>> +is easier to use for computation and 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.
> These are both true.  It would be nice if an optimized walker
> algorithm can also deal with history with recent commits for which
> we do not yet know the generation numbers (i.e. you first traverse
> and assign generation numbers and record in packed graph, then
> history grows but we haven't added the new commits to the packed
> graph yet).

My forward-thinking intention is that we will perform walks using a 
priority queue whose priority first compares generation number (which 
will be 0xFFFFFFFF for commits not in the graph) and then compares by 
commit date on equal generation number. For walks that require 
topological constraints, we cannot stop the walk until all commits in 
the queue have a "real" generation number. This will allow our 
algorithms to work with a mix of packed commits and unpacked commits.

>
>> +- A graph file is stored in a file named 'graph-<oid>.graph' in the pack
>> +  directory. This could be stored in an alternate.
> Is that <oid> really an object name?  The <hash> that appears in the
> name of a packfile pack-<hash>.pack is *not* an <oid>, and I somehow
> suspect that you are doing a similar "use hash of (some) contents to
> make it uniquely identify the content", not "information about a
> single object that is identified by the <oid>".

This is definitely a mistake on my part and I'll switch this to use 
<hash> in the documents. I do use 'struct object_id' in the code for 
this value. Is that OK?

>
>> +- The graph file is only a supplemental structure. If a user downgrades
>> +  or disables the 'core.graph' config setting, then the existing ODB is
>> +  sufficient.
> OK, that is exactly what I meant to say in a few paragraphs above
> that I wanted to see.

I'll move this to the top!

>
>> +Current Limitations
>> +-------------------
>> +
>> +- Only one graph file is used at one time. This allows the integer ID 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 'graph' builtin. These are not
>> +  updated automatically during clone or fetch.
> In addition to "clone or fetch", I presume operations that locally
> create commits do not automatically create them, right?

No. Writing a graph file is too expensive for one commit operation. 
Perhaps some threshold of new commits could trigger the graph calculation.

>
>> +- After computing and storing generation numbers, we must make graph
>> +  walks aware of generation numbers to gain performance benefits. 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'
> Do you mean that this round only writes "graph" without any actualy
> consumers?  It is somewhat hard to assess the value of what is
> stored in the new file without the consumers.
>
> Anyway, thanks for starting this.  Let's read on.
>

See Patch 11/14 for consumption by EVERY commit-graph walk. This patch 
includes significant performance improvements for every walk by avoiding 
parsing, but to get the benefit of generation numbers we will need to 
change the algorithms that operate on the commit graph.

While that integration with algorithms may seem daunting, the good news 
is that we can make iterative changes to improve each algorithm one-by-one.

Thanks,
-Stolee