[chord] Re: more merkle stuff

[Josh I Cates]

Benjie,

>so i was not completely correct when i say it was iterating thru the
>entire DB. it seems that the database_get_keys method is able to skip
>to the start of the region w/ some DB3 magic (hopefully the db3 is
>actually do this correctly), but could we also terminate the traversal
>when we hit the end of the region?

I just looked at the database_get_keys() function and you are exactly
right: this function traverses to the end of the DB.  This is very
bad.  It should terminate the traversal at the end of the region.  In
fact, the function was coded correctly originally.

It looks like this inefficiency was introduced when the function was
moved from merkle_misc.h (v1.15 -> v1.16) to merkle_misc.C (v1.2 ->
v1.3).  Compare the implementations of this function in
merkle_misc.h:1.15 and merkle_misc.C:v.13; the former is the pre-move
implementation and the latter is the post-move implementation.

I'd be interested to know if the performance is a lot better after
this function is reverted.

>also, wouldn't it be better to do
>merkle tree maintenance in the background, rather than in the path of
>a block insert? since the merkle tree is more or less a soft state.

The block insert was designed to be cheap enough so that it can happen
in the foreground.  This strategy avoids all the
vagaries/nuances/complications/etc that might arise from having
different on disk state and in-memory state.  


--josh