Re: [Monotone-devel] ideas to speed up monotone SQLite database access

[Nathaniel Smith]

On Tue, Feb 07, 2006 at 09:11:27AM -0600, Brian Downing wrote:
> On Tue, Feb 07, 2006 at 03:32:22AM -0800, Nathaniel Smith wrote:
> > In particular, netsync wants to send forward deltas, but if we store
> > forward deltas on disk, we have to traverse (potentially long) delta
> > chains when reconstructing files at 'checkout' time.
> > 
> > Actually, using backwards deltas, we have the same problem right now
> > if someone checks out _old_ versions, but I don't think we've ever
> > gotten a complaint about this, so we haven't put it at the top of the
> > priority list.  If we switch to forward deltas, though, then suddenly
> > checking out head becomes slow, and people are... more likely to
> > notice that :-).
> 
> Would making the storage format be weaves alleviate any of this?  Weaves
> seem to be a nice middle ground, as it should be easy to go to and from
> forward and reverse deltas.  Also, if I'm not misunderstanding, most of
> the proposed merge formats need something like a weave to be built up to
> work anyway.

Weaves are an interesting approach.  I believe they get extremely good
compression (which makes sense, because you basically chunk all the
deltas for a single file and then compress them all at once), but for
updating them you have to rewrite the whole file each time you update
it.  This is hard to do transactionally in the filesystem, and it is
hard to do efficiently in SQL.  More to the point, it's especially
hard to do in netsync -- maybe there is some clever way to do it (the
source could say "here, have 100 deltas for file <blah>" and the
sink could batch them all up before writing any out?), but the naive
way anyway has the same problem we do now -- we end up rewriting a
large database object on every packet...

Merging is another issue too, yeah.  All of the weave mergers I know
about still have theoretical issues -- places where they'll silently
mismerge :-(.  Clearly a better solution to content merging is needed,
but I am not sure what it will look like -- maybe weaves, maybe not!

So, umm, to summarize -- weaves are interesting, and I don't have
answers :-).

-- Nathaniel

-- 
So let us espouse a less contested notion of truth and falsehood, even
if it is philosophically debatable (if we listen to philosophers, we
must debate everything, and there would be no end to the discussion).
  -- Serendipities, Umberto Eco