← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to doc/developers/inventory.txt

  • Committer: Andrew Bennetts
  • Date: 2009-10-08 01:55:33 UTC
  • mto: This revision was merged to the branch mainline in revision 4732.
  • Revision ID: andrew.bennetts@canonical.com-20091008015533-pfzig4dpr3kqt2cc
Add NEWS entry.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/inventory.txt
49
49
that an inventory is stored as. We have a number of goals we want to achieve:
50
50
 
51
51
 1. Allow commit to write less than the full tree's data in to the repository
52
 
    in the general case.
 
52
    in the general case. 
53
53
 2. Allow the data that is written to be calculated without examining every
54
54
    versioned path in the tree.
55
55
 3. Generate the exact same representation for a given inventory regardless of
83
83
-----------------
84
84
 
85
85
The xml based implementation we use today layers the inventory as a bytestring
86
 
which is stored under a single key; the bytestring is then compressed as a
 
86
which is stored under a single key; the bytestring is then compressed as a 
87
87
delta against the bytestring of its left hand parent by the knit code.
88
88
 
89
89
Gap analysis:
140
140
-------------------------------------------------------------------------
141
141
 
142
142
 * Split up the logical document into smaller serialised fragements. For
143
 
   instance hash buckets or nodes in a tree of some sort. By serialising in
144
 
   smaller units, we can increase the number of smaller units rather than
 
143
   instance hash buckets or nodes in a tree of some sort. By serialising in 
 
144
   smaller units, we can increase the number of smaller units rather than 
145
145
   their size as the tree grows; as long as two similar trees have similar
146
146
   serialised forms, the amount of different content should be quite high.
147
147
 
166
166
 
167
167
 * Working tree to arbitrary history revision deltas/comparisons can be scaled
168
168
   up by doing a two-step (fixed at two!) delta combining - delta(tree, basis)
169
 
   and then combine that with delta(basis, arbitrary_revision) using the
 
169
   and then combine that with delta(basis, arbitrary_revision) using the 
170
170
   repositories ability to get a delta cheaply.
171
171
 
172
172
 * The key primitives we need seem to be:
263
263
 
264
264
The path and content maps are populated simply by serialising every inventory
265
265
entry and inserting them into both the path map and the content map. The maps
266
 
start with just a single leaf node with an empty prefix.
 
266
start with just a single leaf node with an empty prefix. 
267
267
 
268
268
 
269
269
Apply
439
439
   formerly linked. (This will normally bubble down due to keeping densely
440
440
   packed nodes).
441
441
   To shrink the prefix of a leaf node, create an internal node with the same
442
 
   prefix, then choose a width for the internal node such that the contents
 
442
   prefix, then choose a width for the internal node such that the contents 
443
443
   of the leaf all fit into new leaves obeying the min_size and max_size rules.
444
444
   The largest prefix possible should be chosen, to obey the
445
 
   higher-nodes-are-denser rule. That rule also gives room in leaf nodes for
 
445
   higher-nodes-are-denser rule. That rule also gives room in leaf nodes for 
446
446
   growth without affecting the parent node packing.
447
447
#. Update the CHK pointers - serialise every altered node to generate a CHK,
448
448
   and update the CHK placeholder in the nodes parent; then reserialise the
590
590
 
591
591
Different trees can use different algorithms to expand the request as long as
592
592
they produce consistent deltas. As part of getting a consistent UI we require
593
 
that all trees expand the paths requested downwards. Beyond that as long as
 
593
that all trees expand the paths requested downwards. Beyond that as long as 
594
594
the delta is consistent it is up to the tree.
595
595
 
596
596
Given two trees, source and target, and a set of selected file ids to check for
598
598
the following rules, to get consistent deltas. The test for consistency is that
599
599
if the resulting delta is applied to source, to create a third tree 'output',
600
600
and the paths in the delta match the paths in source and output, only one file
601
 
id is at each path in output, and no file ids are missing parents, then the
 
601
id is at each path in output, and no file ids are missing parents, then the 
602
602
delta is consistent.
603
603
 
604
604
Firstly, the parent ids to the root for all of the file ids that have actually