~bzr-pqm/bzr/bzr.dev

Directory fingerprints

======================

.. contents:: :local:

Introduction

------------

The basic idea is that for a directory in a tree (committed or otherwise), we

will have a single scalar value.  If these values are the same, the contents of

the subtree under that directory are necessarily the same.

This is intended to help with these use cases, by allowing them to quickly skip

over directories with no relevant changes, and to detect when a directory has

changed:

* diff/status (both local trees and historical trees)

* merge

* log -v

* log on a directory

* commit

Use-case oriented APIs

----------------------

Most of this will be hidden behind the Tree interface.  This should cover

``log -v``, ``diff``, ``status``, ``merge`` (and implicit merge during

push, pull, update)::

  tree.iter_changes(other_tree)

  tree.get_file_lines(file_id)   # and get_file, get_file_text

``commit``

~~~~~~~~~~

Commit is similar to ``iter_changes``, but different because it needs to

compare to all the trees.  Commit currently needs to compare the working

tree to all the parent trees, which is needed to update the last_modified

field and would be unnecessary if we removed that field (for both files

and directories) and did not store per-file graphs.

This would potentially speed up commit after merge.

Verbose commit also displays the merged files, which does

require looking at all parents of files that aren't identical

to the left-hand parent.

``log``

~~~~~~~

Log is interested in two operations: finding the revisions that touched

anything inside a directory, and getting the differences between

consecutive revisions (possibly filtered to a directory)::

  find_touching_revisions(branch, file_id) # should be on Branch?

Log shows the revisions that merged a change.  At the moment that is not

included in the per-file graph, and it would also not be visible if the

directories were hashed.

Open questions

--------------

* Is this a good idea at all?

  If changing a file changes all its parent directories up to the root it

  will cause more churn on commit.  (We currently update the all-in-one

  inventory, but only have to update one line of it.)

  Every time a child changes, we'll get a new node in the per-directory

  graph.  This is generally useful: it allows bzr log to do the default

  mode easily, which is to show all changes under that directory.  The

  less common operation, ``log --no-recursive`` is still possible by

  looking only at when the directory itself was renamed, added or removed.

  (That is what the directory graph describes in bzr 0.18 and it is rarely

  useful.)

* Should these be hashes or revision ids or something else?

  Pros of using hashes: hashes are easy to generate by a foreign branch

  plugin (e.g. bzr-svn).  They don't need to get recursive last-changed

  from the foreign branch, or to walk back through history.  They just

  need the relevant directory state, which any system we support can

  answer.

  Hashes converge: if you modify and then modify back, you get the same

  hash.  This is a pro because you can detect that there were ultimately

  no significant changes.  And also a con: you cannot use these hashes to form a graph

  because they get cycles.

* Are the values unique across the whole tree, or only when comparing

  different versions of the same object?

  If we use last-changed revisions, then they will be very not unique

  across the whole tree.  To look up the contents, you must pass a

  composite key like ``(file_id, last_changed)``.

  If we use hashes they will be same only when the two contain the same

  contents.  Since we say that file ids must be unique, this

  means they will match if and only if they are empty.  We might relax

  that in future when we introduce path tokens.

* Is it reasonable to assume hashes won't collide?

  The odds of SHA-1 hashes colliding "accidentally" are vanishingly small.

  It is possible that a `preimage attack`_ against SHA-1 may be discovered

  in the future.  Since we're not proposing in this document to make

  revision-ids be SHA-1, if SHA-1 was obsoleted then we could rewrite the

  contents of revisions but would not need to rename revisions.  So the

  impact of such a migration should just be a format upgrade, and a

  recommendation (but not requirement) to re-sign revisions.

.. _`preimage attack`: http://tools.ietf.org/html/rfc4270

* If we use hashes, should it be the hash of the

  representation stored for a directory?

  In other words, should we pun the representation of the directory with

  the form used for validation.

  If there's some data stored that's not in the hash it's problematic.

  The hash in no longer (effectively) uniquely identifies the

  representation.

  It is desirable that we have a hash that covers all data, to guard

  against bugs, transmission errors, or users trying to hand-hack files.

  Since we need one hash of everything in the tree, perhaps we should also

  use it for the fingerprint.

  Testaments explicitly separate the form used for hashing/signing from

  the form used for storage.  This allows us to change the storage form

  without breaking existing GPG signatures.  The downside is that we need

  to do work O(tree) to make a testament, and this slows down signing,

  verifying and generating bundles.  It also means that there is some

  stored data which is not protected by the signature: this data is less

  important, but corruption of it would still cause problems.

  We have encountered some specific problems with disagreement between

  inventories as to the last-change of files, which is currently unsigned.

  These problems can be introduced by ghosts.

  If we hash the representation, there is still a way to support old

  signatures, assuming that we never discard irreplaceable information.

  The signature should say what format it applies to (similar to

  testaments), and we could transform in memory the tree back to that

  format.

* Is hashing substantially slower than other possible approaches?

  We already hash all the plain files.  Except in unusual cases, the

  directory metadata will be substantially smaller: perhaps 200:1 as a

  rule of thumb.

  When building a bzr tree, we spend on the order of 100ms hashing all the

  source lines to validate them (about 13MB of source).

* Can you calculate one from a directory in the working tree?  Without a basis?

  This seems possible with either hashes or revision ids.

  Using last_changed means that calculating the fingerprint from a working

  tree necessarily requires reading the inventory for the basis

  revision, so that we know when unchanged files were last changed.  With

  hashes we could calculate them using the working tree information alone.

  It's true that we will often then compare that information to the basis

  tree (e.g. for simple ``bzr diff``), but we may only have to compare at

  the top level, and sometimes we're comparing to a

  different tree.  This also touches on whether we should store

  ``last_modified`` for files, rather than directories.

  For revision ids we need to assign a value to use for uncommitted

  changes, but see below about the problems of this.

  In some ways it would be elegant to say (hypothetical)::

    wt.get_root().get_last_modified() == branch.get_last_revision()

  to know that nothing was changed; but this may not be much better than

  ::

    wt.get_root().get_hash() ==

      branch.get_basis().get_root().get_hash()

* Can you use this to compare (directories from) two working trees?

  If you can generate it from a working tree, you should be able to use it

  to compare them.

  This does rule out for example using ``last_modified=None`` or

  ``='current:'`` to mean "changed in the working tree."  Even if this is

  not supported there seems some risk that we would get the same

  fingerprint for trees that are actually different.

  We could assign a

  hypothetical revision id to the tree for uncommitted files.  In that

  case there is some risk that the not-yet-committed id would become

  visible or committed.

* Can we use an "approximate basis"?

  When using radix trees, you may need context beyond the specific

  directory being compared.

* Can you get the fingerprint of parents directories with only selected file ids

  taken from the working tree?

  With hashes, we'd want to carry through the unselected files and

  directories from the values they had in the parent revision.

* Are unbalanced trees a significant problem?  Trees can be unbalanced by having

  many directories (deep or wide), or many files per directory.

  For small trees like bzr, 744 of 874 are in the bzrlib subtree.  In

  general, larger trees are more balanced, because humans, editors and

  other tools have trouble managing very unbalanced trees.  But there are

  exceptions: Aaron has one tree with 20,000 generated but versioned

  entries in one directory.

* Should we use a radix tree approach where fingerprints are calculated on a synthetic

  tree that is by definition balanced, even when the actual tree is unbalanced?

* What are the specific advantages of using recursive-last-modified rather than

  hashes?

  It may be a smaller step change.

  It's a bidirectional link: given a directory text identifier ``(file_id,

  last_changed)`` you can look up the revision that last changed it.

  From the preceding, even without the per-file graph you can skip through

  the history of this file: go to the last-changed revision, look at all

  its parents and repeat.

* Is it a smaller change to use recursive-last-modified on directories?

  Probably yes:

  1. We can just put it into the current inventory format without changing

     anything else.

     By contrast to use a hash we'd have to either split up the inventory

     as stored, or change the sort order for the inventory, or synthesize

     per-directory inventories in memory for hashing.

     However, XML is somewhat redundant and slow to parse/generate; and

     reading the whole thing before comparing some sections is only a

     partial win.  It may be a smaller change but we'd be preserving

     things we want to change.

  1. At present we rarely hash storage representations, only file texts.

     This is not a large technical change, but it is a conceptual change.

     This has some consequences for how we can upgrade it in future: all

     the changed directories need to be rewritten up to the revision level.

  1. If we address directories by hash we need hash-addressed

     storage.

  1. If we address directories by hash then for consistency we'd probably

     (not necessarily) want to address file texts by hash.

  1. The per-file graph can't be indexed by hash because they can converge, so we

     need to either rework or dispose of the per-file graph.

* Any possibilities for avoiding hashes recurring?

  1. Hash along with an identification of the parents (as in hg).  Then you

     can't convert a tree without all its basis trees, and there is still

     convergence when the same merge is done by two people, and you can't

     create it directly from the working tree.

  1. Include last-modified revision id in the hash.

  1. Index by ``(revision, hash)`` or vice versa.

  1. Store a per-file graph and allow it to have repeated keys.  The graph

     would tell you about all the parent texts ever seen; you would need

     to use revision graph information to resolve ambiguities.

* What are the specific disadvantages of using recursive-last-modified rather than

  hashes?

  To calculate the last-changed revision, given the last-changed

  information of the contained files, you need to look at the revision

  graph.  They're not enough because you need to know the relations

  between the mentioned revisions.  In a merge it's possible the correct

  directory last-modified will not be the same as that of any of the files

  within it.  This can also happen when a file is removed (deleted or

  renamed) from a directory.

* Should we split up storage of the inventories?

  This is not quite the same but connected.

* How does this relate to per-file/per-directory hashes?

  If the version of a file or directory is identified by a hash, we can't

  use that to point into a per-file graph.  We can have a graph indexed by

  ``(file_id, hash, revision_id)``.  The last-modified could be stored as

  part of this graph.

  The graph would no longer be core data; it could be always present but

  might be rebuilt.  Treating it as non-core data may make some changes

  like shallow branches easier?

* How do you ask a tree for a given text?

  Right now we say ::

    revision_tree.get_file_lines(file_id)

  so the choice of storage is hidden behind the revision tree: it could be

  accessed by ``(file_id, last_changed)`` or by hash or otherwise.

  At the moment the Repository exports a friend api to RevisionTree,

  currently usually talking in VersionedFiles.

  We probably wouldn't want Repository to expose a ``get_text_for_sha1()``

  interface because that would be very difficult to support on old

  repositories or on foreign branches.

Conclusions

-----------

Design changes

--------------

API changes

-----------

..

  vim: filetype=rst textwidth=78 expandtab spelllang=en spell