[MERGE] Notes on a customized chk+gc index

[John Arbash Meinel]

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

I was thinking about how our current indexes scale (approx 38 bytes per
record after compression), and what it would take to get a better index
for a chk+groupcompress index. The naive fixed-width form takes 40-bytes
per record (20-byte sha, 8-byte start of group, 4-byte group len, 4-byte
in-group start, 4-byte in-group end/len).

However, the more I thought about it the more I was able to put
something together that scaled *really* well. I ran the numbers, and did
the checks, and we can do 10-bytes per entry, and still handle 100M+
keys. (We want to scale to 1M files by 1M revisions by at least 10
changes per commit, and that will likely cost at least 20M chk nodes, at
most 100M.)

With 10M keys in the index, we end up with only a 1 in 1000 chance of
having a single collision in any of those entries (with only a 10 byte
record). And the layout actually lends itself to gracefully handle
collisions. You just give 2 records instead of 1 in the appropriate
spot, and then the outer-info has to go check 2 nodes for an exact match
instead of just one.

This would also handle one of my main concerns with the current index.
It stores ~40 bytes per record, but a compressed chk node averages just
100 bytes. Dropping it down to 10 bytes gets us into the 10% overhead
for an index, which feels reasonable to me. With the python conversion,
the compressed inventory data is only 18.7MB, but the .cix is 12MB, (it
would drop to just 2.9MB).

I'm interested in having someone look the document over, and seeing if
they can come up with any holes to poke in it. Based on my numbers, this
would actually drop the size of the .cix down to smaller than the .tix.
(For python not as dramatically, because it uses the practically
0-entropy ids from bzr-svn.)

For Launchpad, we would get a 13MB => 3.3MB cix, which has a 8.0MB btree
.tix. Which is cutting about 10MB off the total size, which is almost
10% of the total size of a packed Launchpad repository, and is also 10%
of the on-disk size of the python conversion (now down to 96MB).

The way it is designed would require a small change to the group block
header, or we can add 2-bytes to each index entry and a restructuring of
the group data, or on average 4 bytes to the index entry and keep the
current data. It would introduce variable sizes in the actual index
entry, but that can be handled fairly easily.

The cix is also fully reconstructible from the content, so even though
the data is rather tightly packed, we could regenerate it if we got bit
errors.

This certainly isn't something that should cause us to block on
releasing brisbane-core, but it is certainly high up on the "nice to
have" list.

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

iEYEARECAAYFAknEV84ACgkQJdeBCYSNAAMpHwCgsfBwrn27z2DIyFm1Cyhl4WHP
BCUAn1C/MF+LRz37pMvVqLC5OxQTA+6H
=MHJt
-----END PGP SIGNATURE-----
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: improved_chk_index.patch
Url: https://lists.ubuntu.com/archives/bazaar/attachments/20090320/758230d4/attachment-0001.diff