10
Inventories provide an abstraction for talking about the shape of a tree.
11
Generally only tree object implementors should be concerned about entire
12
inventory objects and their implementation. Other common exceptions are
13
full-tree operations such as 'checkout', 'export' and 'import'.
18
In memory inventories are often used in diff and status operations between
19
trees. We are working to reduce the number of times this occurs with 'full
20
tree' inventory objects, and instead use more custom tailored data structures
21
that allow operations on only a small amount of data regardless of the size of
28
There are several variants of serialised tree shape in use by bzr. To date
29
these have been mostly xml based, though plugins have offered non-xml versions.
34
The dirstate file in a working tree includes many different tree shapes - one
35
for the working tree and one for each parent tree, interleaved to allow
36
efficient diff and status operations.
41
All the xml serialized forms write to and read from a single byte string, whose
42
hash is then the inventory validator for the commit object.
45
Serialization scaling and future designs
46
========================================
48
Overall efficiency and scaling is constrained by the bottom level structure
49
that an inventory is stored as. We have a number of goals we want to achieve:
51
1. Allow commit to write less than the full tree's data in to the repository
53
2. Allow the data that is written to be calculated without examining every
54
versioned path in the tree.
55
3. Generate the exact same representation for a given inventory regardless of
56
the amount of history available.
57
4. Allow in memory deltas to be generated directly from the serialised form
58
without upcasting to a full in-memory representation or examining every
59
path in the tree. Ideally the work performed will be proportional to the
60
amount of changes between the trees being compared.
61
5. Allow fetch to determine the file texts that need to be pulled to ensure
62
that the entire tree can be reconstructed without having to probe every
64
6. Allow bzr to map paths to file ids without reading the entire serialised
65
form. This is something that is used by commands such as merge PATH and
67
7. Let bzr map file ids to paths without reading the entire serialised form.
68
This is used by commands that are presenting output to the user such as
69
loggerhead, bzr-search, log FILENAME.
70
8. We want a strong validator for inventories which is cheap to generate.
71
Specifically we should be able to create the generator for a new commit
72
without processing all the data of the basis commit.
73
9. Testaments generation is currently size(tree), we would like to create a
74
new testament standard which requires less work so that signed commits
75
are not significantly slower than regular commits.
78
We have current performance and memory bugs in log -v, merge, commit, diff -r,
79
loggerhead and status -r which can be addressed by an inventory system
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
87
delta against the bytestring of its left hand parent by the knit code.
92
2. Fails - generating a new xml representation needs full tree data.
93
3. Succeeds - the inventory layer accesses the bytestring, which is
95
4. Fails - we have to reconstruct both inventories as trees and then delta
96
the resulting in memory objects.
97
5. Partial success - the revision field in the inventory can be scanned for
98
in both text-delta and full-bytestring form; other revision values than
99
those revisions which are being pulled are by definition absent.
100
6. Partially succeeds - with appropriate logic a path<->id map can be generated
101
just-in-time, but it is complex and still requires reconstructing the
104
8. Fails - we have to hash the entire tree in serialised form to generate
111
Some things are likely harder to fix incrementally than others. In particular,
112
goal 3 (constant canonical form) is arguably only achieved if we remove all
113
derived data such as the last-modified revision from the inventory itself. That
114
said, the last-modified appears to be in a higher level than raw serialization.
115
So in the medium term we will not alter the contents of inventories, only the
116
way that the current contents are mapped to and from disk.
122
We desire clear and clean layers. Each layer should be as simple as we can make
123
it to aid in debugging and performance tuning. So where we can choose to either
124
write a complex layer and something simple on top of it, or two layers with
125
neither being as complex - then we should consider the latter choice better in
126
the absence of compelling reasons not to.
128
Some key layers we have today and can look at using or tweaking are:
130
* Tree objects - the abstract interface bzrlib code works in
131
* VersionedFiles - the optionally delta compressing key->bytes storage
133
* Inventory - the abstract interface that many tree operations are written in.
135
These layers are probably sufficient with minor tweaking. We may want to add
136
additional modules/implementations of one or more layers, but that doesn't
137
really require new layers to be exposed.
139
Design elements to achieve the goals in a future inventory implementation
140
-------------------------------------------------------------------------
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
145
their size as the tree grows; as long as two similar trees have similar
146
serialised forms, the amount of different content should be quite high.
148
* Use fragment identifiers that are independent of revision id, so that
149
serialisation of two related trees generates overlap in the keyspace
150
for fragments without requiring explicit delta logic. Content Hash Keys
151
(e.g. ('sha1:ABCDEF0123456789...',) are useful here because of the ability
152
to assign them without reference to history.)
154
* Store the fragments in our existing VersionedFiles store. Adding an index
155
for them. Have the serialised form be uncompressed utf8, so that delta logic
156
in the VersionedFiles layer can be used. We may need to provide some sort
157
of hinting mechanism to get good compression - but the trivially available
158
zlib compression of knits-with-no-deltas is probably a good start.
160
* Item_keys_introduced_by is innately a history-using function; we can
161
reproduce the text-key finding logic by doing a tree diff between any tree
162
and an older tree - that will limit the amount of data we need to process
163
to something proportional to the difference and the size of each fragment.
164
When checking many versions we can track which fragments we have examined
165
and only look at new unique ones as each version is examined in turn.
167
* Working tree to arbitrary history revision deltas/comparisons can be scaled
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
170
repositories ability to get a delta cheaply.
172
* The key primitives we need seem to be:
173
* canonical_form(inventory) -> fragments
174
* delta(inventory, inventory) -> inventory_delta
175
* apply(inventory_delta, canonical_form) -> fragments
177
* Having very many small fragments is likely to cause a high latency
178
multiplier unless we are careful.
180
* Possible designs to investigate - a hash bucket approach, radix trees,
181
B+ trees, directory trees (with splits inside a directory?).
184
Hash bucket based inventories
185
=============================
190
We store two maps - fileid:inventory_entry and path:fileid, in a stable
191
hash trie, stored in densly packed fragments. We pack keys into the map
192
densely up the tree, with a single canonical form for any given tree. This is
193
more stable than simple fixed size buckets, which prevents corner cases where
194
the tree size varies right on a bucket size border. (Note that such cases are
195
not a fatal flaw - the two forms would both be present in the repository, so
196
only a small amount of data would be written at each transition - but a full
197
tree reprocess would be needed at each tree operation across the boundary, and
206
4. Success, though each change will need its parents looked up as well
207
so it will be proportional to the changes + the directories above
209
5. Success - looking at the difference against all parents we can determine
210
new keys without reference to the repository content will be inserted
212
6. This probably needs a path->id map, allowing a 2-step lookup.
213
7. If we allocate buckets by hashing the id, then this is succeed, though,
214
as per 4 it will need recursive lookups.
216
9. Fail - data beyond that currently included in testaments is included
217
in the strong validator.
222
1. Tuning the fragment size needs doing.
225
1. Separate root node, or inline into revision?
226
1. Cannot do 'ls' efficiently in the current design.
227
1. Cannot detect invalid deltas easily.
228
1. What about LCA merge of inventories?
233
There are three fragment types for the canonical form. Each fragment is
234
addressed using a Content Hash Key (CHK) - for instance
235
"sha1:12345678901234567890".
237
root_node: (Perhaps this should be inlined into the revision object).
238
HASH_INVENTORY_SIGNATURE
239
path_map: CHK to root of path to id map
240
content_map: CHK to root of id to entry map
242
map_node: INTERNAL_NODE or LEAF_NODE
244
INTERNAL_NODE_SIGNATURE
248
PREFIX CHK TYPE SIZE ...
250
(Where TYPE is I for internal or L for leaf).
255
HASH\x00KEY\x00 VALUE
257
For path maps, VALUE is::
260
For content maps, VALUE::
261
fileid basename kind last-changed kind-specific-details
264
The path and content maps are populated simply by serialising every inventory
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.
272
Given an inventory delta - a list of (old_path, new_path, InventoryEntry)
273
items, with a None in new_path indicating a delete operation, and recursive
274
deletes not being permitted - all entries to be deleted must be explicitly
275
listed, we can transform a current inventory directly. We can't trivially
276
detect an invalid delta though.
278
To perform an application, naively we can just update both maps. For the path
279
map we would remove all entries where the paths in the delta do not match, then
280
insert those with a new_path again. For the content map we would just remove
281
all the fileids in the delta, then insert those with a new_path that is not
287
To generate a delta between two inventories, we first generate a list of
288
altered fileids, and then recursively look up their parents to generate their
289
old and new file paths.
291
To generate the list of altered file ids, we do an entry by entry comparison of
292
the full contents of every leaf node that the two inventories do not have in
293
common. To do this, we start at the root node, and follow every CHK pointer
294
that is only in one tree. We can then bring in all the values from the leaf
295
nodes and do a set difference to get the altered ones, which we would then
299
Radix tree based inventories
300
============================
305
We store two maps - fileid:path and path:inventory_entry. The fileid:path map
306
is a hash trie (as file ids have no useful locality of reference). The
307
path:inventory_entry map is stored as a regular trie. As for hash tries we
308
define a single canonical representation for regular tries similar to that
309
defined above for hash tries.
318
5. Success - looking at the difference against all parents we can determine
319
new keys without reference to the repository content will be inserted
324
9. Fail - data beyond that currently included in testaments is included
325
in the strong validator.
330
1. Tuning the fragment size needs doing.
333
1. Separate root node, or inline into revision?
334
1. What about LCA merge of inventories?
339
There are five fragment types for the canonical form:
341
The root node, hash trie internal and leaf nodes as previous.
343
Then we have two more, the internal and leaf node for the radix tree.
345
radix_node: INTERNAL_NODE or LEAF_NODE
348
INTERNAL_NODE_SIGNATURE
351
suffix CHK TYPE SIZE ...
353
(Where TYPE is I for internal or L for leaf).
360
For the content map we use the same value as for hashtrie inventories.
363
Node splitting and joining in the radix tree are managed in the same fashion as
364
as for the internal nodes of the hashtries.
370
Apply is implemented as for hashtries - we just remove and reinsert the
371
fileid:paths map entries, and likewise for the path:entry map. We can however
372
cheaply detect invalid deltas where a delete fails to include its children.
377
Delta generation is very similar to that with hash tries, except we get the
378
path of nodes as part of the lookup process.
384
The canonical form for a hash trie is a tree of internal nodes leading down to
385
leaf nodes, with no node exceeding some threshold size, and every node
386
containing as much content as it can, but no leaf node containing less than
387
its lower size threshold. (In the event that an imbalance in the hash function
388
causes a tree where an internal node is needed, but any prefix generates a
389
child with less than the lower threshold, the smallest prefix should be taken).
390
An internal node holds some number of key prefixes, all with the same bit-width.
391
A leaf node holds the actual values. As trees do not spring fully-formed, the
392
canonical form is defined iteratively - by taking every item in a tree and
393
inserting it into a new tree in order you can determine what canonical form
394
would look like. As that is an expensive operation, it should only be done
397
Updates to a tree that is in canonical form can be done preserving canonical
398
form if we can prove that our rules for insertion are order-independent,
399
and that our rules for deletion generate the same tree as if we never
400
inserted those nodes.
402
Our hash tries are balanced vertically but not horizontally. That is, one leg
403
of a tree can be arbitrarily deeper than adjacent legs. We require that each
404
node along a path within the tree be densely packed, with the densest nodes
405
near the top of the tree, and the least dense at the bottom. Except where the
406
tree cannot support it, no node is smaller than a minimum_size, and none
407
larger than maximum_size. The minimum size constraint is only applied when
408
there are enough entries under a prefix to meet that minimum. The maximum
409
size constraint is always applied except when a node with a single entry
410
is larger than the maximum size. Loosely, the maximum size constraint wins
411
over the minimum size constraint, and if the minimum size contraint is to
412
be ignored, a deeper prefix can be chosen to pack the containing node more
413
densely, as long as no additional minimum sizes checks on child nodes are
419
#. Hash the entry, and insert the entry in the leaf node with a matching
420
prefix, creating that node and linking it from the internal node containing
421
that prefix if there is no appropriate leaf node.
422
#. Starting at the highest node altered, for all altered nodes, check if it has
423
transitioned across either size boundary - 0 < min_size < max_size. If it
424
has not, proceed to update the CHK pointers.
425
#. If it increased above min_size, check the node above to see if it can be
426
more densely packed. To be below the min_size the node's parent must
427
have hit the max size constraint and been forced to split even though this
428
child did not have enough content to support a min_size node - so the prefix
429
chosen in the parent may be shorter than desirable and we may now be able
430
to more densely pack the parent by splitting the child nodes more. So if the
431
parent node can support a deeper prefix without hitting max_size, and the
432
count of under min_size nodes cannot be reduced, the parent should be given
434
#. If it increased above max_size, shrink the prefix width used to split out
435
new nodes until the node is below max_size (unless the prefix width is
436
already 1 - the minimum).
437
To shrink the prefix of an internal node, create new internal nodes for each
438
new prefix, and populate them with the content of the nodes which were
439
formerly linked. (This will normally bubble down due to keeping densely
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
443
of the leaf all fit into new leaves obeying the min_size and max_size rules.
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
446
growth without affecting the parent node packing.
447
#. Update the CHK pointers - serialise every altered node to generate a CHK,
448
and update the CHK placeholder in the nodes parent; then reserialise the
449
parent. CHK pointer propogation can be done lazily when many updates are
452
Multiple versions of nodes for the same PREFIX and internal prefix width should
453
compress well for the same tree.
added
removed
doc/developers/inventory.txt
