[Monotone-devel] [RFC] piece cache design

[Nathaniel Smith]

I've been thinking about piece caches lately, as a possible next step
in my quest to trim all the fat off our common code paths.  The idea
of a piece cache comes when doing reconstruction of xdelta chains.
What we do now is cache recently accessed full-texts, but this is sort
of silly; the way xdelta works is that it describes how to build a
file by taking extents from some other strings you may have around
(e.g., the delta text itself, plus previous deltas, plus eventually
some full-text base).  Instead of jamming a bunch of these together
in a linear chunk of memory and caching particular whole files, it's
more effective to cache the base strings plus the information on how
to use them to reconstruct things.

This is especially critical if you want to try using forward-deltas on
disk to make netsync happier.

I don't really know how to go about designing a piece cache, though.
For the existing full-text cache (see global 'vcache' in database.cc),
we just use LRU on the full-texts.  For a piece cache, though, there
are dependencies to muck things up; any given file requires lots of
pieces to reconstruct, and any given piece is required by lots of
files.  So it's not as obvious when you should throw something out of
memory.

I scribbled down one design here:
  http://venge.net/monotone/wiki/PieceCache
And would very much appreciate feedback.  Graydon, I know you know
more about this than I do, having actually written caches before ;-).

-- Nathaniel

-- 
When the flush of a new-born sun fell first on Eden's green and gold,
Our father Adam sat under the Tree and scratched with a stick in the mould;
And the first rude sketch that the world had seen was joy to his mighty heart,
Till the Devil whispered behind the leaves, "It's pretty, but is it Art?"
  -- The Conundrum of the Workshops, Rudyard Kipling