Re: [Monotone-devel] partial pull #2 - gaps instead of a single horizon

[Markus Schiltknecht]

Hi,

Justin Patrin wrote:
> Only for the server. If the client has a full database then its merkle
> tree is much larger and the refinement is always going to be more
> costly than if the server contained the entire history, at least if I
> understand the idea of merkle refinement correctly. Finding a single
> missing new node vs. a mess of missing history nodes that the server
> doesn't want seems to me to be a largish difference.

You are assuming that every node builds a merkle trie for all the 
revisions it has. This does not necessarily have to be the case, as the 
existing branch conditions already show: if you only want to sync branch 
n.v.m.cvsimport-branch-reconstruction, monotone syncs only the revisions 
needed.

You can easily do the same, if the two synching nodes agree on a 
timespan, for which they are interested in. I.e. saying "all revisions 
of the last two months for n.v.m.*".

> Basically I'm trying to say that the refinement will likely take a hit
> of some kind here (most bandwidth?) and that having a smaller merkle
> tree on the server is not likely to cause any real performance gains.

Correct, but due to the restriction, which we can exchange before 
building the merkle trie, we can come up with smaller tries on both sides.

> This seems like a bit of faulty logic to me. You *could* use
> mark-merge to merge across a gap, but do we want to allow it? For
> example, take a case where the revisions to merge are both below the
> lowest horizon but the common ancestor is *within* a gap above the
> horizon above which we have more revisions and then another horizon.
> Hmmm...now that I'm thinking about this I suppose if this was "done
> right" then the gap-revision would come up as the common ancestor and
> the merge algorithm stop and forces a pull before merging.

Yes. As you are saying that the common ancestor is *within* a gap, that 
would prevent the merge.

> Here's another case, however. What if the common ancestor is above the
> gap? How will the common ancestor algorithm be able to tell this if
> there is a gap in between? To be able to figure this out the gap would
> have to be collapsed in a manner that allowed the marks to be found. I
> don't think that's going to be possible...

Why not? Let's make an example:

      A
     / \
    /   \
   B     C
   |     |
---+-----+---------
   E     |
   |     |       g
   |     E       a
   F    / \      p
   |   +   \
   G   |    H
---+---+----+------
   |   |    |
   I   K    L


So you have all the data for revisions A, B, C, I, K and L. But you 
would only have sentinels for G, E and H, with the following ancestors:

 G -> B
 K -> C
 L -> C

Say you want to merge I and K now. The common ancestor is A, which is 
certainly not in the gap, so monotone should allow the merge, as it has 
all data necessary to do the merge.

If you want to merge K and L however, the common ancestor algorithm 
would find the sentinels E and H, which both have the same ancestor C. 
In that case, monotone can't know for sure, if C really is the common 
ancestor or if the common ancestor is hidden in the gap. In that case, 
monotone would have to refuse to merge. (Probably except if the user 
forces a merge...)

Anyway, I'm not too keen on all of this merging stuff for partial 
repositories. I mainly want to get some sort of partial pull going.

Regards

Markus