← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to doc/developers/improved_chk_index.txt

  • Committer: John Arbash Meinel
  • Date: 2009-03-24 16:35:22 UTC
  • mto: This revision was merged to the branch mainline in revision 4198.
  • Revision ID: john@arbash-meinel.com-20090324163522-p0p9s5ahzsnem1oc
A few notes, some updates from ian.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/improved_chk_index.txt
3
3
===================
4
4
 
5
5
Our current btree style index is nice as a general index, but it is not optimal
6
 
for Content-Hask-Key based content. With CHK, the keys themselves are hashes,
 
6
for Content-Hash-Key based content. With CHK, the keys themselves are hashes,
7
7
which means they are randomly distributed (similar keys do not refer to
8
8
similar content), and they do not compress well. However, we can create an
9
9
index which takes advantage of these abilites, rather than suffering from
296
296
----------
297
297
 
298
298
We have said we want to be able to scale to a tree with 1M files and 1M
299
 
commits. With a 255-way fan out for chk pages, you need a 2 internal nodes,
 
299
commits. With a 255-way fan out for chk pages, you need 2 internal nodes,
300
300
and a leaf node with 16 items. (You maintain 2 internal nodes up until 16.5M
301
301
nodes, when you get another internal node, and your leaf nodes shrink down to
302
302
1 again.) If we assume every commit averages 10 changes (large, but possible,
321
321
revisions, and something less than 100k files (and probably 4-5 changes per
322
322
commit, but their history has very few merges, being a conversion from CVS).
323
323
At 100k files, they are probably just starting to hit 2-internal nodes, so
324
 
they would end up with 10 pages per commit (as an fair-but-high estimate), and
 
324
they would end up with 10 pages per commit (as a fair-but-high estimate), and
325
325
at 170k revs, that would be 1.7M chk nodes.
326
326
 
327
327
 
404
404
------------------------------------
405
405
 
406
406
To get the smallest index possible, we store only a 2-byte 'record indicator'
407
 
inside the index, and then assume that it can be decode once we've read the
 
407
inside the index, and then assume that it can be decoded once we've read the
408
408
actual group. This is certainly possible, but it represents yet another layer
409
409
of indirection before you can actually get content. If we went with
410
410
variable-length index entries, we could probably get most of the benefit with
434
434
after 16MiB, which doesn't work for the ISO case. Though it works *absolutely*
435
435
fine for the CHK inventory cases (what we have today).
436
436
 
437
 
If we change the analysis
438
437
 
439
438
null content
440
439
------------
461
460
can just use ``index.key_count()`` for the former, we could just properly
462
461
handle ``AbsentContentFactory``.
463
462
 
 
463
 
 
464
More than 64k groups
 
465
--------------------
 
466
Doing a streaming conversion all at once is still something to consider. As it
 
467
would default to creating all chk pages in separate groups (300-400k easily).
 
468
However, just making the number of group block entries variable, and allowing
 
469
the pointer in each entry to be variable should suffice. At 3 bytes for the
 
470
group pointer, we can refer to 16.7M groups. It does add complexity, but it is
 
471
likely necessary to allow for arbitrary cases.
 
472
 
464
473
.. 
465
474
  vim: ft=rst tw=78 ai