← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to doc/compression.txt

  • Committer: Martin Pool
  • Date: 2005-06-28 03:02:31 UTC
  • Revision ID: mbp@sourcefrog.net-20050628030231-d311e4ebcd467ef4
Merge John's import-speedup branch:

                                                                                         
  777 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:32 -0500
      revision-id: john@arbash-meinel.com-20050627032031-e82a50db3863b18e
      bzr selftest was not using the correct bzr

  776 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:20:22 -0500
      revision-id: john@arbash-meinel.com-20050627032021-c9f21fde989ddaee
      Add was using an old mutter

  775 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 22:02:33 -0500
      revision-id: john@arbash-meinel.com-20050627030233-9165cfe98fc63298
      Cleaned up to be less different

  774 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:54:53 -0500
      revision-id: john@arbash-meinel.com-20050627025452-4260d0e744edef43
      Allow BZR_PLUGIN_PATH='' to negate plugin loading.

  773 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:49:34 -0500
      revision-id: john@arbash-meinel.com-20050627024933-b7158f67b7b9eae5
      Finished the previous cleanup (allowing load_plugins to be called twice)

  772 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:45:08 -0500
      revision-id: john@arbash-meinel.com-20050627024508-723b1df510d196fc
      Work on making the tests pass. versioning.py is calling run_cmd directly, but plugins have been loaded.

  771 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:32:29 -0500
      revision-id: john@arbash-meinel.com-20050627023228-79972744d7c53e15
      Got it down a little bit more by removing import of tree and inventory.

  770 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 21:26:05 -0500
      revision-id: john@arbash-meinel.com-20050627022604-350b9773ef622f95
      Reducing the number of import from bzrlib/__init__.py and bzrlib/branch.py

  769 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:32:25 -0500
      revision-id: john@arbash-meinel.com-20050627013225-32dd044f10d23948
      Updated revision.py and xml.py to include SubElement.

  768 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:56 -0500
      revision-id: john@arbash-meinel.com-20050627010356-ee66919e1c377faf
      Minor typo

  767 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 20:03:13 -0500
      revision-id: john@arbash-meinel.com-20050627010312-40d024007eb85051
      Caching the import

  766 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:51:47 -0500
      revision-id: john@arbash-meinel.com-20050627005147-5281c99e48ed1834
      Created wrapper functions for lazy import of ElementTree

  765 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:46:37 -0500
      revision-id: john@arbash-meinel.com-20050627004636-bf432902004a94c5
      Removed all of the test imports of cElementTree

  764 John Arbash Meinel <john@arbash-meinel.com>       Sun 2005-06-26 19:43:59 -0500
      revision-id: john@arbash-meinel.com-20050627004358-d137fbe9570dd71b
      Trying to make bzr startup faster.

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/compression.txt
 
1
Compression
 
2
***********
 
3
 
 
4
At the moment bzr just stores the full text of every file state ever.
 
5
(Files unmodified from one revision are stored only once.)
 
6
 
 
7
This is simple to write, and adequate for even reasonably large trees
 
8
with many versions.  Disk is very cheap.  
 
9
 
 
10
Eventually we might like something more compressed, but this is
 
11
neither an interesting nor urgent problem.  (Not "interesting" in the
 
12
sense that doing it is just a matter of coding; there is no
 
13
theoretical problem or risk.)  
 
14
 
 
15
There are various possibilities:
 
16
 
 
17
* Store history of each file in RCS, relying on RCS to do line-by-line
 
18
  delta compression.  (Does not handle binaries very well.)
 
19
 
 
20
  OpenCMS paper has a horror story about using RCS for file storage.
 
21
 
 
22
* Store full copies of each file in a container with gzip compression,
 
23
  which should fairly efficiently eliminate unchanged areas.  This
 
24
  works on binaries, and gives compression of file text as a side
 
25
  benefit.
 
26
 
 
27
  (Note that ``.zip`` will *not* do for this, because every file is
 
28
  compressed independently.)
 
29
  
 
30
  The OpenCMS paper notes that RCS storage is only 20% more efficient
 
31
  than gzip'd storage of individual file versions.
 
32
 
 
33
* Store history of each file in SCCS; allows quick retrieval of any
 
34
  previous state and may give more efficient storage than RCS.  Allows
 
35
  for divergent branches within a single file.
 
36
 
 
37
* Store xdeltas between consecutive file states.
 
38
 
 
39
* Store xdeltas according to a spanning delta algorithm; this probably
 
40
  requires files are stored with some kind of sequence number so that
 
41
  we can predict related version names.
 
42
 
 
43
* Store in something like XDFS.
 
44
 
 
45
* Any of the above, but with the final storage in some kind of
 
46
  database: psql, sqlite, mysql, whatever is convenient.   
 
47
 
 
48
  It should be something that is safe across system crashes, which
 
49
  rules out tdb at the moment.
 
50
 
 
51
----
 
52
 
 
53
These properties are seen as desirable in darcs and arch:
 
54
 
 
55
* Passive HTTP downloads: without requiring any server-side
 
56
  intelligence, a client can get updates from one version to the next
 
57
  by requesting a set of self-contained files.  
 
58
 
 
59
  The number of files necessary to do this must not be unfeasibly
 
60
  large, and the size of each of those files should be proportionate
 
61
  to the amount of actual change.  In other words the data downloaded
 
62
  should be of comparable size to the actual edits between the trees.
 
63
 
 
64
 
 
65
* Write-once storage: once a file is written to the repository, it is
 
66
  not modified.