journalled inventories

[Robert Collins]

This is a proposal for an inventory serialiser/deserialiser for
persistent storage that will not require a full text diff to add the
content to the repository, and is differently intrusive than the split
inventory work which may allow it to be a good initial step in that
direction.

Motivation
----------

During commit storage of our new inventory requires two steps:
serialisation (13% of commit on a 55K path tree), and knit delta
creation/insertion (2.5% of the same commit).

Most of that 15.5% is wasted effort because we already know the changes
that are required in the inventory as we generate a delta during commit.

Possible alternative approaches
-------------------------------

Martin's split-inventory work allows us to serialise (and optionally
delta) directories at a time, rather than entire trees, but that still
scales by the directory size in its current implementation, and has
potentially significant impact on the number of round trips required to
generate a full inventory, nor does it [yet] give us partial inventory
reads to check invariants such as 'file ids are not repeated in an
inventory'.

A variation on Martin's work is the generic tree concept I proposed in
London, which has the same issues as Martins proof of concept
implementation in terms of latency, but is not coupled to the size of
any individual directory.

There is a third alternative approach which builds on this one to reduce
storage requirements by combining information from multiple inventories
when merges have occurred. However I have not considered this in
significant depth; and it is something we could well do as future work.

Constraints
-----------

This proposal was put together with the following constraints/goals in
mind:

We require a validator of the inventory for the revision object to use,
which can be used to detect attacks or data corruption.

Reconstructing the full text of an individual inventory should not
require more data or round trips than we currently incur.

Proposal
--------

We structure the journalled inventory as an tree of inventory lines
texts. A given journalled inventory has three data items: A basis
inventory pointer, a current lines pointer, and a validator. As the
definition is recursive we need to supply a starting point - the empty
journalled inventory. 

An empty journalled inventory has no basis inventory pointer, a constant
empty inventory lines text, and a constant validator which is the secure
hash (we might choose sha1 for this) of its empty inventory lines text.

To create a new inventory, one takes an existing inventory, which
becomes the basis inventory, and a inventory lines object which is a
serialised inventory delta to update the inventory to a new state. The
validator for this new inventory is obtained by creating a secure hash
from the validator of the basis inventory, and the current inventory
lines.

If we create a new journalled inventory with every commit we build up a
structure like so:


EMPTY   rev1lines        rev2lines   rev3lines
  |        |                 |            |
  +--------+-----------------+------------+
     rev1validator    rev2validator rev3validator

etc.


We can truncate this at any commit by starting with a pointer to EMPTY
again. Using a heuristic to decide when to do this can limit the depth
of the chain that we need to process to reconstruct a given revision. A
similar heuristic to knits, where we store a full text when the size of
the full text is roughly the same size as the size of the aggregate
deltas (so on average we read 1.5 times the full text size after
compression to reconstruct any given text) should give similarly good
results.

We will serialise the lines text for a new inventory as:
'format: bzr journalled inventory v1' NL
'parent:' BASIS_INVENTORY NL
DELTA_LINES

DELTA_LINES is lexographically sorted.

where
DELTA_LINES ::= DELTA_LINE (NL DELTA_LINE)*
DELTA_LINE ::= OLDPATH NEWPATH file-id parent-id name last-mod CONTENT
OLDPATH ::= NONE | PATH
NEWPATH ::= NONE | PATH
NONE ::= 'None'
PATH ::= '/' path
CONTENT ::= FILE_CONTENT | DIR_CONTENT | TREE_CONTENT | LINK_CONTENT
FILE_CONTENT ::= 'file' text_size text_sha1
DIR_CONTENT ::= 'dir'
TREE_CONTENT ::= 'tree' tree-revision
LINK_CONTENT ::= 'link' link-target

At any commit the validator is the root of a tree. Changing the deltas -
e.g. by rewriting an inventory in the history to be a full inventory
itself will change validators for all inventories built upon that one.

Performance
-----------

Diff
^^^^

We can diff between two adjacent inventories by examining their
serialised deltas. This scales with size of change, not size of
inventory - a significant win. We can diff between inventories that can
be reached via the tree of different inventories by composing deltas.
This will scale with the amount of history back to their common
ancestor. And we can of course generate both inventories and perform our
current diff as a fallback.

Commit
^^^^^^

There are two ways that we could create new journalled inventories. We
could take the in memory inventory that we create during commit, and
that for the basis, then make a new delta and serialise it to create the
new inventory text lines and validator that we incorporate into the
revision. Additionally doing this we could serialise the inventory in
its regular form to get a legacy validator that has no reference to
existing data.

Alternatively, we already generate an inventory delta during commit for
updating the working tree. This delta can be serialised directly and
should produce identical results. We will not get a standalone validator
for this inventory though. On the other hand the memory and effort
required to create this representation is proportional to changes in the
inventory rather than to the size of the inventory, and as such should
outperform our current serialisation significantly.

Fetch
^^^^^

Fetching with a history horizon where some revisions are not fetched
will need to copy the inventory components that make up the aggregate
journalled inventory even if the revision objects are not being copied.
As the validator in each revision is derived from the data in the
inventories there is no need to copy the revision objects too, so our
fetch invariants are able to be safely preserved. There may be some
additional round trips to query for inventory components to copy during
fetch, but the common case will be that we are copying the revision
objects so our first query will find all inventory components that we
need.

Check/reconcile
^^^^^^^^^^^^^^^

The definition of 'garbage inventory' changes with this, but it should
be trivial to accomodate. We can cache the validators of each inventory
we process and that will be more efficient than the current requirement
of parsing every inventory.

Access a single inventory
^^^^^^^^^^^^^^^^^^^^^^^^^

By using the same hueristic as knits do, we need to read the same amount
of data to construct a given inventory. We will need to parse the entire
data set of data rather than just the result of applying the text data.
On the other hand we will not have to parse knit hunks which will save
the current double-parsing that occurs.

Iter-inventories
^^^^^^^^^^^^^^^^
We can apply deltas forward or backwards to move along a chain of
inventories trivially, rather than the current requirement of
deserialising them all individually.

-Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20071025/9a188f65/attachment.pgp