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

[Markus Schiltknecht]

...continuing my thoughts on partial pull.

I came to think about that single horizon. Why do we limit to only one 
horizon? That poses the problem, that on subsequent partial-pulls which 
move the horizon, monotone would have to throw away revision data it has 
already fetched. That seems wasteful. Can't we have multiple horizons, 
i.e. gaps of missing revisions?

Let's see: if we want gaps, we have to keep track of the beginning and 
ending of the gap. A sentinel, as in partial pull, already covers the 
beginning. Let's just add the ending information to it. To do the same 
as partial pull currently does, we'd just add the magic rev id [] as the 
ending.

If a client does multiple partial-pulls and finally decides to fetch the 
whole repository, that would save him from transferring some revisions. 
But more importantly, I can see use for gaps to solve other problems. 
Namely legal problems, where you want to stop serving certain revisions, 
but still want to have an intact repository. Another possibility gaps 
would open are 'hot' servers, which serve only the last few months worth 
of revisions, but serve those very quickly as they aren't burdened with 
years of history (i.e. resulting in much smaller merkle tries).

I've had a look at implementing those gaps. I think we could simply 
build rosters for complete gaps and process normally from there on. I 
would even add the necessary (parent, child) tuples in revision_ancestry 
for the gaps. So you could still build an ancestry tree. Just one which 
has revisions in it, which stand for a whole gap, i.e. multiple 
(missing) revisions. For mtn log or mtn annotate, you wouldn't have to 
care about bailing out as soon as you hit the horizon, but you'd just 
get a special revision_t, which stands for a whole set of missing 
revisions. If you ask me, the issue gets a tad simpler, as soon as you 
start to think of gaps instead of a (single) horizon.

Of course, gaps also don't come for free. The hardest problem probably 
is, that a gap can perfectly well have more than two ending revisions, 
i.e. ancestors. Our current roster and merge code doesn't support that. 
(Hm, I remember having raised that issue before...) We could either add 
support for more than two ancestors or work around the issue by letting 
monotone insert multiple cascaded sentinels, sort of a binary tree. I 
still prefer the first option, but the second is probably easier to do 
and doesn't pose problems with the mark merge algorithm.

While talking about merging: in the presence of gaps, merging is not 
always possible. Of course, you'd have to have the two revisions you 
want to merge - we need their rosters. Additionally, we need the common 
ancestor. As long as that does not lie within a gap, we can do the 
merge. Even if there are gaps in between, since we have a valid roster 
for the gap. (In case of a partial pull, where the gap ends at the magic 
revision id [], that could probably be the common ancestor. Of course we 
should prevent a merge in that case, too.)

We could easily implement partial pull using gaps, but to gain the other 
features, we would also have to adjust netsync to be able to serve 
partial repositories. AFAIK, partial pull currently doesn't plan on 
supporting that.

What gaps clearly wouldn't solve is, wanting to remove only parts of a 
revision - which admittedly is much more common than wanting to remove a 
whole revision.


What do you think? Does that make sense? Is it worth implementing gaps? 
Do you foresee other problems?


To be continued...

Markus