[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] A couple questions...
From: |
Timothy Brownawell |
Subject: |
Re: [Monotone-devel] A couple questions... |
Date: |
Thu, 03 Jun 2010 20:37:36 -0500 |
User-agent: |
Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.9) Gecko/20100515 Icedove/3.0.4 |
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