monotone-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Monotone-devel] Re: nuskool & certs created after a revision


From: Graydon Hoare
Subject: [Monotone-devel] Re: nuskool & certs created after a revision
Date: Thu, 01 May 2008 23:46:55 -0700
User-agent: Thunderbird 2.0.0.12 (Windows/20080213)

William Uther wrote:

Hrm. I certainly didn't give it a huge amount of thought. My disquiet stemmed from the fact that the cert creation time information is mixed up in this new cert DAG.

Sure, the cert DAG winds up reflecting the mixture of the structure of the revision graph and the structure of communication events. But the nodes in it are irrelevant and never have to be seen by anyone outside the sync system.

The actual "creation times" of certs aren't involved, though I think sorting by the timestamps *on* the certs will probably make for the tidiest clustering into buckets in the file tree you synthesize.

(Of course, that sort order is not *quite* as easy to determine with the existing cert system, since only date certs have a timestamp. I was hoping to mix this with the cert upgrade that was going to collect the standard commit certs, including timestamp, into a single "combo cert". But that's not required. You could still group the existing certs by putting all certs on revision R in the bucket for the timestamp that is the lower bound of all date certs on R, with the corner case of "revision R has no date certs" mapped to timestamp 0. Crude, but it'd work well.)

The difference in our methods then consists of how these sets are sync'd. I was thinking of using the revision DAG structure. You were thinking of introducing a new parallel DAG structure based on cert creation times. Both use a nukool-like algorithm over that structure.

Yeah, but your plan requires recomputing all the descendant synthetic hashes and re-running the sync algorithm for each cert that's transmitted. That will scale as the product of the size of the unreconciled set of certs and the average depth of them in the history graph. Not a pretty number. And the sync algorithm itself involves different parameters for searching and reconciling nodes in the sync'ed graph.

If you store the certs in buckets and stick them in a synthetic file tree, you'll calculate what to send using a single gsync pass -- just like the normal revision graph -- and reuse all the existing revision- and file-syncing machinery, unmodified; you'll just run a post-process that inspects the pseudo-files that were transmitted and updates the certs in the database from their contents. All you need to write is the code to synthesize the tree, the code to run a (simple union) merge, and the code to run the post-sync digestion of the files.

IMO this is much less work, and less tangle to debug. But I guess I'm not doing it, so ... the advice is only worth the electrons that carry it :)

-Graydon





reply via email to

[Prev in Thread] Current Thread [Next in Thread]