Prototype "improved_chk_index"

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Robert Collins wrote:
> On Wed, 2009-10-28 at 23:42 -0500, John Arbash Meinel wrote:
>> On IRC Robert asked me why I thought this was worthwhile.
> 
> I was asking in the light of the format moratorium, not overall - Even
> before 2.0 your back of envelope numbers were compelling.
> 

In light of the format moratorium... This was scratching an itch that
has been bothering me for a while. I think it came up a few times in my
head as I was poking around the btree code. I actually started with just
an afternoon where I figured I'd see what I could put together.

I ended up getting all of "CHKIndexBuilder" written, to the point that I
could generate the files in about 3 hours. So it motivated me to poke at
it some more.

>> 3) Still stands. All told,  We have 16MB .cix, 10MB .tix, and 2.3MB
>>    .iix and .rix, and 1.4MB .six. For a total of 31MB of indexes. 31MB
>>    of index for 100MB of content seems a bit skewed.
> 
> Yup.
> 
> ..
>> I don't know about the time to *build* an index, but there could be
>> some
>> significant gains there as well. (Traditionally compress() is
>> significantly slower than decompress(), especially with our current
>> sync
>> and try again implementation.)
> 
> I'm sure we can win there too.
> 
> I'd like to inline all the indices into the pack, so we only have one
> file to rename and manage. bzr-search does this and it works well.
> 

I agree that it would be nice to do. As we go further this way, I'd like
to have some tools for picking these things apart again. One thing I
miss with packs is the simple "ls .bzr/repository/inventory.knit" to
compare how much data is in X versus Y for storage.

'bzr repository-details' is nice, but it actually is a bit *too* much
right now, because it extracts all of the content. (Mostly this is 'ls
takes 0.5s', 'repo-details' takes 5min)


> Related to that I've been considering putting small objects inline in
> the index. E.g. putting a revision inline in the revision index; may be
> a silly idea, I'm not sure.

That *is* how Mercurial handles small content in their mixed
index+content files. I think they have a specific "if content+index <
128K, create 1 file".

However, with 'groups' I don't think it is going to be a great fit for
us. I think it would be better to put the index into the pack file, and
then you have them both in the same file object.

In theory over 'dumb' transports, you can then query multiple parts of
the file in one request. However, I personally have decided to stop
optimizing for 'http' access, rather than what would be best for local
and smart operations.

> 
> One thing to consider with the .tix index is what we want to end up
> with. I can see indirecting via .cix for file content, but still we'd
> want per file graphs, I think.
> 
> -Rob

Yeah, I'm still trying to sort that out myself. I agree we want to keep
the per-file graph, but I'm thinking we might consider storing it
differently. I haven't really thought of it enough to give good answers
here.

I think we want to move content into chk *mostly* because of observed
redundancies. Stuff like the Samba import where they have 100 identical
copies of the 'green_checkmark.png' in several different filenames in
different directories over history, etc.

I can think of ways to compact the per-file ancestry. Like splitting it
up by file-id, so you have a 'section' with a given file-id, so you
don't have to repeat the actual file-id string. And a lookup table in
the beginning to revision-ids, so they can be stored as simple integers.
 Then you can create the file-id graph as just a bunch of chained integers.

Also, if you change to store *just* the per file graph, the you save the
space for pointers into the .pack file. Instead, when streaming data,
the sha hash for the file content is extracted from the chk pages, and
sent as just more chk data. In my naive approach, we would still
occasionally transmit redundant data (sha1 was changed to X then Y then
X again. Comparing versus parent would see 'X new versus Y'), but not
enough that I would worry about it.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkrpqWUACgkQJdeBCYSNAAN1WgCgzgZI2m9rXl3G5HbKQK7sLSUb
ViEAoIqfS7+j5cLuyEg2hASVlCOOuIkB
=1R8A
-----END PGP SIGNATURE-----