~bzr-pqm/bzr/bzr.dev

********

Revfiles

********

The unit for compressed storage in bzr is a *revfile*, whose design

was suggested by Matt Mackall.

This document describes version 1 of the file, and has some notes on

what might be done in version 2.

Requirements

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

Compressed storage is a tradeoff between several goals:

* Reasonably compact storage of long histories.

* Robustness and simplicity.

* Fast extraction of versions and addition of new versions (preferably

  without rewriting the whole file, or reading the whole history.)

* Fast and precise annotations.

* Storage of files of at least a few hundred MB.

* Lossless in useful ways: we can extract a series of texts and write

  them back out without losing any information.

Design

======

revfiles store the history of a single logical file, which is

identified in bzr by its file-id.  In this sense they are similar to

an RCS or CVS ``,v`` file or an SCCS sfile.

Each state of the file is called a *text*. 

Renaming, adding and deleting this file is handled at a higher level

by the inventory system, and is outside the scope of the revfile.  The

revfile name is typically based on the file id which is itself

typically based on the name the file had when it was first added.  But

this is purely cosmetic.

    For example a file now called ``frob.c`` may have the id

    ``frobber.c-12873`` because it was originally called

    ``frobber.c``.  Its texts are kept in the revfile

    ``.bzr/revfiles/frobber.c-12873.revs``.

When the file is deleted from the inventory the revfile does not

change.  It's just not used in reproducing trees from that point

onwards.

The revfile does not record the date when the text was added, a commit

message, properties, or any other metadata.  That is handled in the

higher-level revision history.

Inventories and other metadata files that vary from one version to the

next can themselves be stored in revfiles.

revfiles store files as simple byte streams, with no consideration of

translating character sets, line endings, or keywords.  Those are also

handled at a higher level.  However, the revfile may make use of

knowledge that a file is line-based in generating a diff.  

   (The Python builtin difflib is too slow when generating a purely

   byte-by-byte delta so we always make a line-by-line diff; when this

   is fixed it may be feasible to use line-by-line diffs for all

   files.)

Files whose text does not change from one revision to the next are

stored as just a single text in the revfile.  This can happen even if

the file was renamed or other properties were changed in the

inventory.

The revfile is held on disk as two files: an *index* and a *data*

file.  The index file is short and always read completely into memory;

the data file is much longer and only the relevant bits of it,

identified by the index file, need to be read.

  This design is similar to that of Netscape `mail summary files`_, in

  that there is a small index which can always be read into memory and

  that quickly identifies where to look in the main file.  They differ

  in many other ways though, most particularly that the index is not

  just a cache but holds precious data in its own right.

.. _`mail summary files`: http://www.jwz.org/doc/mailsum.html

This is meant to scale to hold 100,000 revisions of a single file, by

which time the index file will be ~4.8MB and a bit big to read

sequentially.

Some of the reserved fields could be used to implement a (semi?)

balanced tree indexed by SHA1 so we can much more efficiently find the

index associated with a particular hash.  For 100,000 revs we would be

able to find it in about 17 random reads, which is not too bad.  On

the other hand that would compromise the append-only indexing, and

100,000 revs is a fairly extreme case.

This performs pretty well except when trying to calculate deltas of

really large files.  For that the main thing would be to plug in

something faster than difflib, which is after all pure Python.

Another approach is to just store the gzipped full text of big files,

though perhaps that's too perverse?

Identifying texts

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

In the current version, texts are identified by their SHA-1.  

Skip-deltas

-----------

Because the basis of a delta does not need to be the text's logical

predecessor, we can adjust the deltas to avoid ever needing to apply

too many deltas to reproduce a particular file.  

Tools

-----

The revfile module can be invoked as a program to give low-level

access for data recovery, debugging, etc.

Open issues

===========

* revfiles use unsigned 32-bit integers both in diffs and the index.

  This should be more than enough for any reasonable source file but

  perhaps not enough for large binaries that are frequently committed.

  Perhaps for those files there should be an option to continue to use

  the text-store.  There is unlikely to be any benefit in holding

  deltas between them, and deltas will anyhow be hard to calculate. 

* The append-only design does not allow for destroying committed data,

  as when confidential information is accidentally added.  That could

  be fixed by creating the fixed repository as a separate branch, into

  which only the preserved revisions are exported.

* Should we also store full-texts as a transitional step?