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

[Markus Schiltknecht]

Hi,

Timothy Brownawell wrote:
> I'm trying to think how we could do it with minimal invasiveness to what
> we already have. So instead of adding however many new pseudo-revision
> objects and transmitting node-ids over netsync (which makes them a
> permanent concept, instead of a local cache), just have the server
> generate a new revision from a string of actual revisions and somehow
> instruct the client that that revision can be used in place of the
> actual most recent revision that was collapsed.

Hm.. okay, I can see where you're coming from. That would make 
History-Collapsed-revisions look even more like a real revision... But 
it would still be possible to remove those HC-revs and add the real ones.

And yes, I agree that having to send node ids is not terribly charming.

> We can't verify it, so we have to trust it. Which means we need to know
> who it comes from, so that that can be an informed decision. Which means
> that it either needs to be signed, or we need to track which server it
> came from and not allow servers to provide this data unless they
> generate it from a full history graph themselves.

Wow. Do you really want to have all that trust stuff for partial pull? I 
mean, it's quite simple to verify your data, you just need to download 
the whole history...

OTOH, for my extended use cases, like hot server or such, that would 
probably make sense.

> > Though I don't quite get your argument about rewriting history. In what 
> > way would history-collapsing allow something that's impossible otherwise?
>
> If there are gaps in the history graph, we can't know that it's
> well-formed. We can usually verify this because a child contains the
> hash of the parents, but if we allow holes in the graph we need some
> other means to connect ancestor<->descendant across the hole. And since
> we can't *know* that it's correct without having all intermediate
> revisions, whoever tells us what that relationship is has the power to
> rewrite history.

Well, at least he would still have to break the hash. So that's not such 
a big concern, IMO.

> > > > But theoretically, think of replacing all revs in a gap with a single 
> > > > revision. You could have committed it all in one go, no? That's how I'm 
> > > > thinking the sentinel could 'trick' the merge algorithm (and a lot of 
> > > > the rest of the monotone machinery).
> > > What about a wide gap?
> > >
> > > a       b   c
> > >  \     /    |
> > > ------------------
> > >    \ /      |    ^
> > >     d       e    |
> > >     |\    /      G
> > >     |  \ /       A
> > >     f   g        P
> > >     |   |        |
> > >     :   :        |
> > >     |   |        v
> > > -------------------
> > >     h   i
> > >
> > > The gap has two heads, so it needs at least two revisions to replace it.
> > Sure, so what's the problem?  You would simply add sentinels for f and 
> > g, while h and i are the first real revisions you have. Both sentinels 
> > would have the very same set of ancestors, namely a, b and c.
>
> ...But f is not descended from c?

Ups, yeah, sorry. So h has ancestors a and b, i has ancestors a, b and 
c.  (Trying to merge h and i could even succeed, because the common 
ancestor is one of the ancestors of a, b and c - and thus out of the gap).

> > Nope. G1 and G2 would both have the same node id for the added file. 
> > Thus monotone should be able to not add it twice.
>
> This requires that node-ids be transmitted over the network, which is
> one of the things I'm trying to find a way to avoid.

That's an argument. But making the server serve single gaps - possibly 
one per added file - sounds expensive to me. For larger histories, that 
would result in quite a lot of gaps for pulling only the newest 
revision. (And there are strange people around who add a new file with 
every commit and the like.)

As the netsync protocol needs to change anyway, to support partial pull, 
I'm in favor of adding those node ids (note that they don't necessarily 
need to be the same as any one peer's local node ids).

I'll think more about those full blown HC-revs, as you proposed. The 
ability to cert them and all that sounds interesting...

Regards

Markus