← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to doc/developers/inventory.txt

  • Committer: John Arbash Meinel
  • Date: 2009-06-19 17:53:37 UTC
  • mto: This revision was merged to the branch mainline in revision 4466.
  • Revision ID: john@arbash-meinel.com-20090619175337-uozt3bntdd48lh4z
Update time_graph to use X:1 ratios rather than 0.xxx ratios.
It is just easier to track now that the new code is much faster.

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
498
498
delta, the only other valid fields are OLDPATH and 'file-id'. PARENT_ID is ''
499
499
when a delete has been recorded or when recording a new root entry.
500
500
 
501
 
 
502
 
Delta consistency
503
 
=================
504
 
 
505
 
Inventory deltas and more broadly changes between trees are a significant part
506
 
of bzr's core operations: they are key components in status, diff, commit,
507
 
and merge (although merge uses tree transform, deltas contain the changes that
508
 
are applied to the transform). Our ability to perform a given operation depends
509
 
on us creating consistent deltas between trees. Inconsistent deltas lead to
510
 
errors and bugs, or even just unexpected conflicts.
511
 
 
512
 
An inventory delta is a transform to change an inventory A into another
513
 
inventory B (in patch terms its a perfect patch). Sometimes, for instance in a
514
 
regular commit, inventory B is known at the time we create the delta. Other
515
 
times, B is not known because the user is requesting that some parts of the
516
 
second inventory they have are masked out from consideration. When this happens
517
 
we create a delta that when applied to A creates a B we haven't seen in total
518
 
before. In this situation we need to ensure that B will be internally
519
 
consistent. Deltas are unidirectional, a delta(A, B) creates B from A, but
520
 
cannot be used to create A from B.
521
 
 
522
 
Deltas are expressed as a list of (oldpath, newpath, fileid, entry) tuples. The
523
 
fileid, entry elements are normative; the old and new paths are strong hints
524
 
but not currently guaranteed to be accurate. (This is a shame and something we
525
 
should tighten up). Deltas are required to list all removals explicitly -
526
 
removing the parent of an entry doesn't remove the entry.
527
 
 
528
 
Applying a delta to an inventory consists of:
529
 
 - removing all fileids for which entry is None
530
 
 - adding or replacing all other fileids
531
 
 - detecting consistency errors
532
 
 
533
 
An interesting aspect of delta inconsistencies is when we notice them:
534
 
 - Silent errors which our application logic misses
535
 
 - Visible errors we catch during application, so bad data isn't stored in
536
 
   the system.
537
 
 
538
 
The minimum safe level for our application logic would be to catch all errors
539
 
during application. Making generation never generate inconsistent deltas is
540
 
a seperate but necessary condition for robust code.
541
 
 
542
 
An inconsistent delta is one which:
543
 
 - after application to an inventory the inventory is an impossible state.
544
 
 - has the same fileid, or oldpath(not-None), or newpath(not-None) multiple
545
 
   times.
546
 
 - has a fileid field different to the entry.fileid in the same item in the
547
 
   delta.
548
 
 - has an entry that is in an impossible state (e.g. a directory with a text
549
 
   size)
550
 
 
551
 
Forms of inventory inconsistency deltas can carry/cause:
552
 
 - An entry newly introduced to a path without also removing or relocating any
553
 
   existing entry at that path. (Duplicate paths)
554
 
 - An entry whose parent id isn't present in the tree. (Missing parent).
555
 
 - Having oldpath or newpath not be actual original path or resulting path.
556
 
   (Wrong path)
557
 
 - An entry whose parent is not a directory. (Under non-directory).
558
 
 - An entry that is internally inconsistent.
559
 
 - An entry that is already present in the tree (Duplicate id)
560
 
 
561
 
Known causes of inconsistency:
562
 
 - A 'new' entry which the inventory already has - when this is a directory
563
 
   even arbitrary file ids under the 'new' entry are more likely to collide on
564
 
   paths.
565
 
 - Removing a directory without recursively removing its children - causes
566
 
   Missing parent.
567
 
 - Recording a change to an entry without including all changed entries found
568
 
   following its parents up to and includin the root - can cause duplicate
569
 
   paths, missing parents, wrong path, under non-directory.
570
 
 
571
 
Avoiding inconsistent deltas
572
 
----------------------------
573
 
 
574
 
The simplest thing is to never create partial deltas, as it is trivial to
575
 
be consistent when all data is examined every time. However users sometimes
576
 
want to specify a subset of the changes in their tree when they do an operation
577
 
which needs to create a delta - such as commit.
578
 
 
579
 
We have a choice about handling user requests that can generate inconsistent
580
 
deltas. We can alter or interpret the request in such a way that the delta will
581
 
be consistent, but perhaps larger than the user had intended. Or we can
582
 
identify problematic situations and abort, specifying to the user why we have
583
 
aborted and likely things they can do to make their request generate a
584
 
consistent delta.
585
 
 
586
 
Currently we attempt to expand/interpret the request so that the user is not
587
 
required to understand all the internal constraints of the system: if they
588
 
request 'foo/bar' we automatically include foo. This works but can surprise
589
 
the user sometimes when things they didn't explicitly request are committed.
590
 
 
591
 
Different trees can use different algorithms to expand the request as long as
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
594
 
the delta is consistent it is up to the tree.
595
 
 
596
 
Given two trees, source and target, and a set of selected file ids to check for
597
 
changes and if changed in a delta between them, we have to expand that set by
598
 
the following rules, to get consistent deltas. The test for consistency is that
599
 
if the resulting delta is applied to source, to create a third tree 'output',
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
602
 
delta is consistent.
603
 
 
604
 
Firstly, the parent ids to the root for all of the file ids that have actually
605
 
changed must be considered. Unless they are all examined the paths in the delta
606
 
may be wrong.
607
 
 
608
 
Secondly, when an item included in the delta has a new path which is the same
609
 
as a path in source, the fileid of that path in source must be included.
610
 
Failing to do this leads to multiple ids tryin to share a path in output.
611
 
 
612
 
Thirdly, when an item changes its kind from 'directory' to anything else in the
613
 
delta, all of the direct children of the directory in source must be included.