[Monotone-devel] Re: [patch] roster-deltas (40% pull speedup)

[Graydon Hoare]

Nathaniel Smith wrote:

> Thanks for looking it over -- I know you don't have much time these
> days :-).

s/have/make/. It'd be dishonest to claim innocence; I'm just not 
allocating as much time for this stuff anymore.

> Well, it's a tricky bit of state tracking.  For instance, at one
> point, I had converted things so that rosters were indexed by
> roster_id, but hadn't actually changed their storage format or
> anything yet.  I was still caching them in the vcache.  I only
> realized much later that this meant there was a major bug -- because
> rollback() does not flush the vcache, I could have left stale rosters
> that never existed in there... this doesn't apply to files in the
> vcache, because they're indexed by content, but it did to rosters once
> I switched them over to being indexed by...index.

Well, I don't immediately see any places you're not handling. It's late 
and there's an increasing amount of state in this class, so I'm not very 
confident in that assessment, but I don't know what else to do. I read 
through the methods and their sub-methods using etags. It seems coherent.

I mean, you put them in the write-through cache during put_roster, you 
flush them to disk on commit, you cancel them all on rollback, you 
consult the cache on get_roster_version and populate it on cache-misses. 
 Sounds sufficient to me.

Three points stand out:

  1. I'm nervous about handing out shared pointers to cache entries.
     I see they're const and all, so realistically I can't imagine
     anything that'd go wrong.. it's not like we had anything in
     the old code to prevent fetching soon-to-be-cancelled writes
     either, it just seems a bit ominous.

     Is it possible that the db invalidates a cache entry and some
     caller will keep the cache entry alive, thinking it's a real
     roster? If it does, what are the possible consequences?

  2. The manifest-reconstruction stuff is still present. Soon this
     should all be deleted. Maybe now? I don't know. I'm surprised
     you kept it alive. If you're migrating the schema, why not just
     toss the manifest tables entirely? They're empty, no?

  3. Why is the delayed_files map separate from the vcache? Shouldn't
     the two be unified (and dedicated to files alone, ditching
     manifests) now that you have a proper LRUWritebackCache?

> That's the kind of bug I'm worried about -- somehow dropping a step in
> the dance between roster_cache insertion, marking things clean/dirty,
> and letting them eventually get written or not -- depending on how the
> transaction resolves, and whether a delta gets written straight to the
> db first.  I _think_ I got all this stuff right, but I would feel
> better if someone independently convinced themself of the same thing.

Again, I think this is even less likely if you make the file cache use 
LRUWritebackCache too: identical code paths and relationship to 
transactions as roster cache, less opportunity for logic mismatch.

If the delta gets "written straight to the db" it's still inside a 
transaction; it'll still get backed out if the transaction rolls back. 
The key is to ensure that everything in memory that might relate to the 
current transaction is written out before issuing "COMMIT", or discarded 
from cache before issuing "ROLLBACK". The fewer paths we have that cause 
write-out or cache-clearing, the easier this is to ensure.

> The other place I'm worried for similar reasons is in the roster delta
> code -- this is much simpler, but again, I'd appreciate it if someone
> else independently read through and convinced themselves that we
> aren't going to accidentally drop some field or whatever.

One thing that stands out here is that you're detaching and attaching in 
random order, not bottom-up / top-down like in the editable tree code.

You can add some "use std::foo" entries in here (especially make_pair) 
to cut down on some chatter.

You have a couple long lines still that need wrapping.

It seems a bit wasteful to encode the whole marking of each node that 
changes, rather than just the aspect of the marking that changed. Most 
edits are patches. You're going to write out the parent+name marking and 
all the attr marks in each such delta. This makes the deltas likely 
twice as large as they need to be. Maybe gzip will handle that?

Are the function names "delta_only_in_to" and "delta_in_both" really 
correct? It seems they're called when a given *node* is in to/both, not 
a delta. I.e. they should be called "node_only_in_to" and 
"node_in_both". (And really, using "to" as a noun sort of irritates me; 
can you call it "target", "dest" or such?)

> > Also I'm shifting 
> > commenting style towards full sentences starting with a capital letter 
> > and ending with a period. I know, ghastly. What's happening?!
>
> Who are you, and what you have you done with graydon?!?

I've moved on to deeper forms of obscurantism. Don't worry :)

> Hm.  I'm not sure.  Basically, IIUC, the difference between signed and
> unsigned is in:
>   1) comparison operators
>   2) widening coercion
>   3) IO/printing/parsing
> and in particular, arithmetic couldn't care less _which_
> representatives us silly humans think we're using for our 2^n modulo
> equivalence classes, the computer'll happily use the same bit strings
> either way?
>
> (1) and (2) are irrelevant here, because these are just uninterpreted
> blobs, we never _do_ anything with them (also, they're 64 bit, so not
> much widening going on :-)).
...
> However, I really do not care all that much, and am curious what your
> reasons are.

This is not much of an argument, and I don't *really* care in the sense 
that I'll hold you up. But you asked, so:

I generally hate signed integers. They are an unmitigated source of 
evil: something to confine to a very small corner of a program, surround 
with an iron box, and glare at.

Once you have any signed value floating around, C will go its best to 
infect everything else with signedness via promotion. It only takes one 
signedness-where-you-didn't-expect-it to cause all manner of 
memory-corrupting security bugs, from underflowing loop counters to 
negative array indices to unexpected sign-extending of "small" numbers 
when widened. I prefer to keep them in a place where they'll infect 
less, sort of like a plague.

(Note that if you complie sqlite with any level of checking for this 
stuff, it's absolutely lousy with mixed-signedness arithmetic. Makes my 
skin crawl)

> > > -database::remove_version(hexenc<id> const & target_id,
> > > -                         string const & data_table,
> > > -                         string const & delta_table)
> > I wonder if it's wise to remove this function. Isn't it useful?
>
> Its only use was so that 'db kill_rev_locally' could remove a
> killed revision's roster (and potentially files?).  I have a bit of a
> passive aggressive relationship with this feature :-).

Really? Hmm, istr having a use for it when we receive redundant storage 
edges, nuking one of the reconstruction paths to save space. I thought 
this was an important space optimization at one time. Is it no longer, 
or am I mis-remembering? Maybe that's "deltify"...

> > > @@ -2439,7 +2486,6 @@ parse_marking(basic_io::parser & pa,
> > >           pa.str(k);
> > >           pa.hex(rev);
> > >           attr_key key = attr_key(k);
> > > -          I(n->attrs.find(key) != n->attrs.end());
> > >           safe_insert(marking.attrs[key], revision_id(rev));
> > >         }
> > Slightly nervous about this. Why is it ok?
>
> Because the only caller for ros.parse_from is read_roster_and_marking,
> which immediately calls roster.check_sane_against(marking), which does
> the same check.

Eh. Unless profiles say it's expensive, I prefer leaving O(1) and 
O(lg(N)) sanity checks in cold code paths. Suppose the path gains 
another caller someday.

Otherwise looks good. Very nice work. I wish I could grant you 100% 
confidence that it's correct, but I can't. All I can say is that I've 
*certainly* pushed buggier code before; I don't have a recipe for 
avoiding bugs. "make backups" (seriously: save a database do a $2 DVD 
every few months, you'll be glad you did someday)

-graydon