~bzr-pqm/bzr/bzr.dev

*****************
Bazaar-NG formats
*****************

.. contents::

Since branches are working directories there is just a single
directory format.

There is one metadata directory called ``.bzr`` at the top of each
tree.  Control files inside ``.bzr`` are never touched by patches and
should not normally be edited by the user.

These files are designed so that repository-level operations are ACID
without depending on atomic operations spanning multiple files.  There
are two particular cases: aborting a transaction in the middle, and
contention from multiple processes.  We also need to be careful to
flush files to disk at appropriate points; even this may not be
totally safe if the filesystem does not guarantee ordering between
multiple file changes, so we need to be sure to roll back.

The design must also be such that the directory can simply be copied
and that hardlinked directories will work.  (So we must always replace
files, never just append.)

A cache is kept under here of easily-accessible information about
previous revisions.  This should be under a single directory so that
it can be easily identified, excluded from backups, removed, etc.
This might contain pristine tree from previous revisions, manifests
and inventories, etc.  It might also contain working directories when
building a commit, etc.  Call this maybe ``cache`` or ``tmp``.

I wonder if we should use .zip files for revisions and cacherevs
rather than tar files so that random access is easier/more efficient.
There is a Python library ``zipfile``.


Signing XML files
*****************

bzr relies on storing hashes or GPG signatures of various XML files.
There can be multiple equivalent representations of the same XML tree,
but these will have different byte-by-byte hashes.

Once signed files are written out, they must be stored byte-for-byte
and never re-encoded or renormalized, because that would break their
hash or signature.




Branch metadata
***************

All inside ``.bzr``

``README``
  Tells people not to touch anything here.

``branch-format``
  Identifies the parent as a Bazaar-NG branch; contains the overall
  branch metadata format as a string.

``pristine-directory``
  Identifies that this is a pristine directory and may not be
  committed to.

``patches/``
  Directory containing all patches applied to this branch, one per
  file.  Patches are stored as compressed deltas.  We also store the
  hash of the delta, hash of the before and after manifests, and
  optionally a GPG signature.

``cache/``
  Contains various cached data that can be destroyed and will be
  recreated.  (It should not be modified.)

``cache/pristine/``
  Contains cached full trees for selected previous revisions, used
  when generating diffs, etc.

``cache/inventory/``
  Contains cached inventories of previous revisions.

``cache/snapshot/``
  Contains tarballs of cached revisions of the tree, named by their
  revision id.  These can also be removed, but 

``patch-history``
  File containing the UUIDs of all patches taken in this branch,
  in the order they were taken.
  Each commit adds exactly one line to this file; lines are
  never removed or reordered.

``merged-patches``
  List of foreign patches that have been merged into this branch.
  Must have no entries in common with ``patch-history``.  Commits that
  include merges add to this file; lines are never removed or
  reordered.

``pending-merges`` 
  List (one per line) of non-mainline revisions that
  have been merged and are waiting to be committed.

``branch-name``
  User-qualified name of the branch, for the purpose of describing the
  origin of patches, e.g. ``mbp@sourcefrog.net/distcc--main``.

``friends``
  List of branches from which we have pulled; file containing a list
  of pairs of branch-name and location.

``parent``
  Default pull/push target.

``pending-inventory``
  Mapping from UUIDs to file name in the current working directory.  

``branch-lock``
  Lock held while modifying the branch, to protect against clashing
  updates.


Locking
*******

Is locking a good strategy?  Perhaps somekind of read-copy-update or
seq-lock based mechanism would work better?

If we do use a locking algorithm, is it OK to rely on filesystem
locking or do we need our own mechanism?  I think most hosts should
have reasonable ``flock()`` or equivalent, even on NFS.  One risk is
that on NFS it is easy to have broken locking and not know it, so it
might be better to have something that will fail safe.

Filesystem locks go away if the machine crashes or the process is
terminated; this can be a feature in that we do not need to deal with
stale locks but also a feature in that the lock itself does not
indicate cleanup may be needed.

robertc points out that tla converged on renaming a directory as a
mechanism: this is one thing which is known to be atomic on almost all
filesystems.  Apparently renaming files, creating directories, making
symlinks etc are not good enough.



Delta
*****

XML document plus a bag of patches, expressing the difference between
two revisions.  May be a partial delta.

* list of entries

  * entry
  
    * parent directory (if any)
    * before-name or null if new
    * after-name or null if deleted
    * uuid
    * type (dir, file, symlink, ...)
    * patch type (patch, full-text, xdelta, ...)
    * patch filename (?)


Inventory
*********

XML document; series of entries.  (Quite similar to the svn
``entries`` file; perhaps should even have that name.)
Stored identified by its hash.

An inventory is stored for recorded revisions, also a
``pending-inventory`` for a working directory.

Inventories always have the same id as the revision they correspond
to.  bzr up to 0.0.5 explicitly stores an inventory-id; in future
versions this may be implied.



Revision
********

XML document.  Stored identified by its hash.

committer
  RFC-2822-style name of the committer.  Should match the key used to
  sign the revision.

comment
  multi-line free-form text; whitespace and line breaks preserved

timestamp
  As floating-point seconds since epoch.

branch name
  Name of the branch to which this was originally committed.    

  (I'm not totally satisfied that this is the right way to do it; the
  results will be a bit weird when a series of revisions pass through
  variously named branches.)

inventory_hash
  Acts as a pointer to the inventory for this revision.

parents
  Zero, one, or more references to parent revisions.   For each 
  the revision-id and the revision file's hash are given.  The first
  parent is by convention the revision in whose working tree the
  new revision was created.

precursor
  Must be equal to the first parent, if any are given.  For
  compatibility with bzr 0.0.5 and earlier; eventually will be
  removed. 

merged-branches
  Revision ids of complete branches merged into this revision.  If a
  revision is listed, that revision and transitively its predecessor
  and all other merged-branches are merged.  This is empty except
  where cherry-picks have occurred.

merged-patches
  Revision ids of cherry-picked patches.  Patches whose branches are
  merged need not be listed here.  Listing a revision ID implies that
  only the change of that particular revision from its predecessor has
  been merged in.   This is empty except where cherry-picks have
  occurred.

The transitive closure avoids Arch's problem of needing to list a
large number of previous revisions.  As ddaa writes:

    Continuation revisions (created by tla tag or baz branch) are associated
    to a patchlog whose New-patches header lists the revisions associated to
    all the patchlogs present in the tree. That was introduced as an
    optimisation so the set of patchlogs in any revision could be determined
    solely by examining the patchlogs of ancestor revisions in the same
    branch. This behaves well as long as the total count of patchlog is
    reasonably small or new branches are not very frequent.

    A continuation revision on $tree currently creates a patchlog of
    about 500K. This patchlog is present in all descendent of the revision,
    and all revisions that merges it.

It may be useful at some times to keep a cache of all the branches, or
all the revisions, present in the history of a branch, so that we do
need to walk the whole history of the branch to build this list.
  

----

Proposed changes
****************

* Don't store parent-id in all revisions, but rather have <DIRECTORY>
  nodes that contain entries for children?

* Assign an id to the root of the tree, perhaps listed in the top of
  the inventory?