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

[Timothy Brownawell]

On 06/03/2010 06:09 PM, J Decker wrote:

> > 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.
>
> But then you'd need to mark 'I definatly changed this revision way
> back in history' ... but then when is that status cleared, since I may
> have to push that to 3 servers....

I'm thinking something like this (but probably with a factor more like 
16 or 64 instead of 2)
        A2------B2      <- skip nodes
        |       |
    z1  A1--B1  C1--D1  <- skip nodes
    |   |   |   |   |
  z-y-x-A-B-C-D-E-F-G-H <- revisions
where each of the skip nodes has two hashes, one for the lower nodes it 
covers and one for both hashes of each of its "parents". So:
 * D1 has a hash over the certs on G and H, and an empty hash.
 * C1 has a hash over the certs on E and F, and one over the two
   hashes on D1
 * B1 has a hash over the certs on C and D, and an empty hash. (It can
   still note C1 as an ancestor, but just doesn't hash over it.) The
   empty hash is to limit the number of skip-node hashes that cover the
   certs on any given revision.
 ...
 * B2 has a hash over the hashes on C1 and D1, and an empty hash
 * A2 has a hash over the hashes on A1 and B1, and one over the
   hashes on B2.
 ...
So you take the certs on z, and the pairs of hashes on z1 and A2, and 
this represents the list of all certs on all revisions. (z covers 
itself, z1 covers y and x, and A2 covers A-H). Say there's a new cert on 
G: this would show up as a difference in A2's ancestor hash so you check 
it's ancestors (in this linear case just B2), then as a difference in 
B2's covered-nodes hash so you check C1 and D1, and it's a difference in 
D1's covered-nodes hash so you check G and H and see that G is missing a 
cert.

In order to keep this consistent, it would require updating appropriate 
skip nodes when you add a cert on an older revision, for example adding 
a new cert on H would require updating hashes on D1, C1, B2, and A2. So 
really it's trading O(log(graph-depth)) on getting certs on old 
revisions which is rare, to get rid of O(graph-size) on sync refinement 
which is common.

Everything's still nice and stateless, just some older data is cached in 
summary form.

--
Timothy

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