Re: [Monotone-devel] A couple questions...

[Timothy Brownawell]

On 06/03/2010 04:21 PM, J Decker wrote:
> Why does monotone read all revisions and certs in the database on a sync?

One fairly basic feature monotone has is that certs can be added to 
arbitrarily old revisions. What this means for netsync is that just 
synchronizing the revision graph isn't enough, you also need to check 
information from every node.

> At least 90% of the time, a comparison between the heads of branches
> to sync(A) vs the heads of branches to sync against(B) will result in
> either A is before B or B is before A and occasionally neither A or B
> is known to the respective opposite side, but then perhaps a revision
> C could be stored per branch in the repository that A is in that is
> the last point(s) [it may be multiple heads] that was known to sync...
> then C will be before B in this third case.

I think we don't want to store that kind of per-peer information just on 
general principle.

What would probably work is to store a skip-list over the revision 
graph, and synchronize on first the leaves (well, probably near-leaves, 
say anything not covered by a higher skip-node) at each level and then 
either prune/iterate or just synchronize on all unknown-state revisions. 
The skip nodes could have a hash over all certs that they skip over.

> probably less than 1% of synchronizations are new pulls, which would
> require reading all revisions in the branches of interest.  (in which
> case revision C will be blank or null).

Further, most pulls are going to have a few (or possibly no) new 
revisions on one side and no new revisions on the other. While it's 
fairly common that two people are commiting on the same branch at the 
same time, I think this is merely a significant minority of commits (and 
syncs).

> I would think it would be a SIGNIFICANT reduction in sync time (which
> isn't really that long for 30,000 revisions in assorted branches which
> takes about 10 seconds to read on a netbook) to do a quick check and
> just pull from the last known revision to the tip on both sides to
> sync, instead of reading the entire revision structure.

It's not quite that simple, but a graph-aware synchronization (with 
appropriate cert summarization) would definitely speed up figuring out 
what to send. It's on my to-do list somewhere, I promise. :)

--
Timothy

Free public monotone hosting: http://mtn-host.prjek.net