11
$\begingroup$

In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in hearing about theoretical work that discuss the time- and network-complexity of comparing two DAGs.

The DAGs in question are formed by the revisions recorded. Revisions are uniquely identified by a hash value. Each revisions depend on zero (initial commit), one (normal commit) or more (merge commit) of the previous revisions. Here is an example where revisions a to e were made one after each other:

a --- b --- c --- d --- e

The graph comparison comes into the picture when someone has only part of the history and wants to retrieve the missing part. Imagine I had a to c and made x and y based on c:

a --- b --- c --- x --- y

In Mercurial, I would do hg pull and download d and e:

a --- b --- c --- x --- y
              \
                d --- e

The goal is to identify d and e efficiently when the graph has many (say, more than 100,000) nodes. Efficiency concerns both

  • network complexity: the number of bytes transferred and the number of network round-trips needed
  • time complexity: the amount of computation done by the two servers that exchange changesets

Typical graphs will be narrow with few parallel tracks like above. There will also typically be only a handful of leaf nodes (we call them heads in Mercurial) like e and y above. Finally, when a central server is used, the client will often have a couple of changesets that are not on the server, while the server can have 100+ new changesets for the clients, depending on who long ago the client last pulled from the server. An asymmetric solution is preferred: a centralized server should do little computation in comparison to its clients.

Improve this question
$\endgroup$
1
13
$\begingroup$

In this context, the graph nodes have some sort of unique identifier (a hash or checksum), right? So you don't need to do any kind of subgraph isomorphism testing, you just need a list of the nodes that differ between your two versions, and the edges aren't really useful at all for this step. My SIGCOMM 2011 paper "What's the difference? Efficient set reconciliation without prior context" (with Goodrich, Uyeda, and Varghese) considers exactly this problem: it turns out that you can determine the identities of the nodes that are held by one but not both of the two communicating servers, using an amount of communication that is proportional only to the number of changed nodes and using only a single round-trip. Once you have that information, it's easy to pull the changes themselves in a second round-trip, again with optimal communication.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Uh, this sounds interesting! You're right that a direct comparison of the changeset IDs (yes,they're hash values) will work. We've just always tries to use the graph structure too: if we both know X, then I also know that you know all ancestors of X. That seems like important information, but maybe it isn't. I'll read your paper now, thanks for the pointer! $\endgroup$ – Martin Geisler Oct 26 '11 at 9:20
  • $\begingroup$ @David: A precision (I am one of the author of the algorithm currently used by Mercurial). We actually care about the set of "common" nodes, no need to know the value of the missing node. $\endgroup$ – tonfa Oct 26 '11 at 20:05
  • 1
    $\begingroup$ If you know what's different, then you also know what's in common: it's everything you have a copy of that's not part of the difference. But the difference should typically be relatively small even when the common part is large, so communicating only an amount of data proportional to the difference is better than communicating the whole history DAG or the common part. $\endgroup$ – David Eppstein Oct 27 '11 at 0:20
  • $\begingroup$ @David: because of the ancestor relationship, we actually compute the heads (leaf nodes) of the common region. So that is still a small amount of data, even if there is a huge shared history. $\endgroup$ – Martin Geisler Oct 28 '11 at 7:48
  • $\begingroup$ I updated my answer to include also the number of round trips used (which turns out to be very small). $\endgroup$ – David Eppstein Oct 28 '11 at 22:11
3
$\begingroup$

In the solution we implemented for Mercurial, another concern was asymmetry: the server's load should be minimized for both outgoing bandwidth and CPU time, at the cost of the client's load.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks, I've updated the question a little to note this. $\endgroup$ – Martin Geisler Oct 26 '11 at 10:31
0
$\begingroup$

Sounds like a two step process to me.

  1. ask all clients if they have commits where the parent is c
  2. if so, find all childs of c

The task of 1. I think is mainly processed on the client side, and all the client need the the commit hash over the net.

Improve this answer
$\endgroup$
1
  • $\begingroup$ What scenario are you describing? The case where I made x and y and need to pull e and d from the server? The inital problem there is that I (as a client) don't know the "branch point" c. $\endgroup$ – Martin Geisler Oct 18 '11 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.