[Monotone-devel] Graveyards vs reconstruction for liveness merging (was: resolving name conflicts; file suturing vs drop)

[William Uther]

On 07/05/2008, at 4:57 PM, Thomas Moschny wrote:

> The death markings ((ii) from above) can also be easily  
> reconstructed, but
> this would impose a perfomance penalty. That's why we have to think  
> about way
> of also caching that information, be it as part of the roster, or as a
> separate graveyard, or whatever.

You only need to reconstruct that information for nodes that are alive  
on at
least one side of the merge.  This means that the reconstruction  
cannot grow
without bound.

Furthermore, I think you only need to reconstruct the marks for the  
uncommon
ancestors.  The marks for the common ancestors must be known in the
roster of the node on the 'live' side of the merge.

I started on this in the net.venge.monotone.mark-merge-existence branch.
(before I ran out of time - there isn't actually much there.)

I was planning to make a set of node_ids which is the union of the  
node-ids
in the roster on each side of the merge.  This set would then be  
passed in
when the marking_map is constructed, and the markings would be  
recorded for
all node_ids in that set, not just the ones in the current roster.

It got a little confusing because the marking map is constructed in
app.db.get_roster(), and that is in a deltified cache format that I
didn't get around to grokking fully.

Cheers,

Will        :-}