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