← Back to branch summary

~bzr/ubuntu/lucid/bzr/beta-ppa

« back to all changes in this revision

Viewing changes to doc/developers/repository.txt

  • Committer: Martin Pool
  • Date: 2010-07-02 07:29:40 UTC
  • mfrom: (129.1.7 packaging-karmic)
  • Revision ID: mbp@sourcefrog.net-20100702072940-hpzq5elg8wjve8rh
http://bugs.debian.org/452024
http://bugs.debian.org/464688
http://bugs.debian.org/523595
http://bugs.debian.org/526233
http://bugs.debian.org/537708
http://bugs.debian.org/555336
http://bugs.debian.org/555343
https://launchpad.net/bugs/249452
https://launchpad.net/bugs/385074
* PPA rebuild.
* PPA rebuild for Karmic.
* PPA rebuild for Jaunty.
* PPA rebuild for Hardy.
* From postinst, actually remove the example bash completion scripts.
  (LP: #249452)
* New upstream release.
* New upstream release.
* New upstream release.
* Revert change to Build-depends: Dapper does not have python-central.
  Should be python-support..
* Target ppa..
* Target ppa..
* Target ppa..
* Target ppa..
* New upstream release.
* Switch to dpkg-source 3.0 (quilt) format.
* Bump standards version to 3.8.4.
* Remove embedded copy of python-configobj. Closes: #555336
* Remove embedded copy of python-elementtree. Closes: #555343
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* debian/control: Fix obsolete-relation-form-in-source
  lintian warning. 
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split out docs into bzr-doc package.
* New upstream release.
* Added John Francesco Ferlito to Uploaders.
* Fix install path to quick-reference guide
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again, again.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to path changes.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Bump standards version to 3.8.3.
* Remove unused patch system.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix copy and paste tab error in .install file
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
 + Fixes compatibility with Python 2.4. Closes: #537708
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream version.
* Bump standards version to 3.8.2.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add python-pyrex to build-deps to ensure C extensions are always build.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix API compatibility version. (Closes: #526233)
* New upstream release.
  + Fixes default format for upgrade command. (Closes: #464688)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add missing dependency on zlib development library. (Closes:
  #523595)
* Add zlib build-depends.
* Add zlib build-depends.
* Add zlib build-depends.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Move to section vcs.
* Bump standards version to 3.8.1.
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Recommend ca-certificates. (Closes: #452024)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Update watch file. bazaar now uses launchpad to host its sources.
* Remove patch for inventory root revision copy, applied upstream.
* New upstream release.
* New upstream release.
* New upstream release
* Force removal of files installed in error to /etc/bash_completion.d/
  (LP: #249452)
* New upstream release.
* New upstream release
* New upstream release.
* Bump standards version.
* Include patch for inventory root revision copy, required for bzr-svn.
* New upstream release.
* Remove unused lintian overrides.
* Correct the package version not to be native.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Final 1.5 release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add myself as a co-maintainer.
* Add a Dm-Upload-Allowed: yes header.
* New upstream bugfix release.
* New upstream release.
* Final 1.3 release.
* New upstream release.
* First release candidate of the upcoming 1.3 release.
* Rebuild to fix the problem caused by a build with a broken python-central.
* New upstream release.
* Rebuild for dapper PPA.
* Apply Lamont's patches to fix build-dependencies on dapper.
  (See: https://bugs.launchpad.net/bzr/+bug/189915)

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/developers/repository.txt
 
1
============
 
2
Repositories
 
3
============
 
4
 
 
5
Status
 
6
======
 
7
 
 
8
:Date: 2007-07-08
 
9
 
 
10
This document describes the services repositories offer and need to offer
 
11
within bzrlib.
 
12
 
 
13
 
 
14
.. contents::
 
15
 
 
16
 
 
17
Motivation
 
18
==========
 
19
 
 
20
To provide clarity to API and performance tradeoff decisions by
 
21
centralising the requirements placed upon repositories.
 
22
 
 
23
 
 
24
Terminology
 
25
===========
 
26
 
 
27
A **repository** is a store of historical data for bzr.
 
28
 
 
29
 
 
30
Command Requirements
 
31
====================
 
32
 
 
33
==================  ====================
 
34
Command             Needed services
 
35
==================  ====================
 
36
Add                 None
 
37
Annotate            Annotated file texts, revision details
 
38
Branch              Fetch, Revision parents, Inventory contents, All file texts
 
39
Bundle              Maximally compact diffs (file and inventory), Revision graph
 
40
                    difference, Revision texts.
 
41
Commit              Insert new texts, insert new inventory via delta, insert
 
42
                    revision, insert signature
 
43
Fetching            Revision graph difference, ghost identification, stream data
 
44
                    introduced by a set of revisions in some cheap form, insert
 
45
                    data from a stream, validate data during insertion.
 
46
Garbage Collection  Exclusive lock the repository preventing readers.
 
47
Revert              Delta from working tree to historical tree, and then
 
48
                    arbitrary file access to obtain the texts of differing
 
49
                    files.
 
50
Uncommit            Revision graph access.
 
51
Status              Revision graph access, revision text access, file
 
52
                    fingerprint information, inventory differencing.
 
53
Diff                As status but also file text access.
 
54
Merge               As diff but needs up to twice as many file texts -
 
55
                    base and other for each changed file. Also an initial
 
56
                    fetch is needed.
 
57
Log                 Revision graph (entire at the moment) access,
 
58
                    sometimes status between adjacent revisions. Log of a
 
59
                    file needs per-file-graph. Dominator caching or
 
60
                    similar tools may be needed to prevent entire graph
 
61
                    access.
 
62
Missing             Revision graph access, and revision texts to show
 
63
                    output.
 
64
Update              As for merge, but twice.
 
65
==================  ====================
 
66
 
 
67
Data access patterns
 
68
====================
 
69
 
 
70
Ideally we can make our data access for commands such as branch to
 
71
dovetail well with the native storage in the repository, in the common
 
72
case. Doing this may require choosing the behaviour of some commands to
 
73
allow us to have a smaller range of access patterns which we can optimise
 
74
more heavily. Alternatively if each command is very predicable in its
 
75
data access pattern we may be able to hint to the low level layers which
 
76
pattern is needed on a per command basis to get efficient behaviour.
 
77
 
 
78
===================  ===================================================
 
79
Command              Data access pattern
 
80
===================  ===================================================
 
81
Annotate-cached      Find text name in an inventory, Recreate one text,
 
82
                     recreate annotation regions
 
83
Annotate-on demand   Find file id from name, then breadth-first pre-order
 
84
                     traversal of versions-of-the-file until the annotation
 
85
                     is complete.
 
86
Branch               Fetch, possibly taking a copy of any file present in a
 
87
                     nominated revision when it is validated during fetch.
 
88
Bundle               Revision-graph as for fetch; then inventories for
 
89
                     selected revision_ids to determine file texts, then
 
90
                     mp-parent deltas for all determined file texts.
 
91
Commit               Something like basis-inventories read to determine
 
92
                     per-file graphs, insertion of new texts (which may
 
93
                     be delta compressed), generation of annotation
 
94
                     regions if the repository is configured to do so,
 
95
                     finalisation of the inventory pointing at all the new
 
96
                     texts and finally a revision and possibly signature.
 
97
Fetching             Revision-graph searching to find the graph difference.
 
98
                     Scan the inventory data introduced during the selected
 
99
                     revisions, and grab the on disk data for the found
 
100
                     file texts, annotation region data, per-file-graph
 
101
                     data, piling all this into a stream.
 
102
Garbage Collection   Basically a mass fetch of all the revisions which
 
103
                     branches point at, then a bait and switch with the old
 
104
                     repository thus removing unreferenced data.
 
105
Revert               Revision graph access for the revision being reverted
 
106
                     to, inventory extraction of that revision,
 
107
                     dirblock-order file text extract for files that were
 
108
                     different.
 
109
Uncommit             Revision graph access to synthesise pending-merges
 
110
                     linear access down left-hand-side, with is_ancestor
 
111
                     checks between all the found non-left-hand-side
 
112
                     parents.
 
113
Status               Lookup the revisions added by pending merges and their
 
114
                     commit messages. Then an inventory difference between
 
115
                     the trees involved, which may include a working tree.
 
116
                     If there is a working tree involved then the file
 
117
                     fingerprint for cache-misses on files will be needed.
 
118
                     Note that dirstate caches most of this making
 
119
                     repository performance largely irrelevant: but if it
 
120
                     was fast enough dirstate might be able to be simpler/
 
121
Diff                 As status but also file text access for every file
 
122
                     that is different - either one text (working tree
 
123
                     diff) or a diff of two (revision to revision diff).
 
124
Merge                As diff but needs up to twice as many file texts -
 
125
                     base and other for each changed file. Also an initial
 
126
                     fetch is needed. Note that the access pattern is
 
127
                     probably id-based at the moment, but that may be
 
128
                     'fixed' with the iter_changes based merge. Also note
 
129
                     that while the texts from OTHER are the ones accessed,
 
130
                     this is equivalent to the **newest** form of each text
 
131
                     changed from BASE to OTHER. And as the repository
 
132
                     looks at when data is introduced, this should be the
 
133
                     pattern we focus on for merge.
 
134
Log                  Revision graph (entire at the moment) access, log of a
 
135
                     file wants a per-file-graph. Log -v will want
 
136
                     newest-first inventory deltas between revisions.
 
137
Missing              Revision graph access, breadth-first pre-order.
 
138
Update               As for merge, but twice.
 
139
===================  ===================================================
 
140
 
 
141
Patterns used
 
142
-------------
 
143
 
 
144
Note that these are able to be changed by changing what we store. For
 
145
instance if the repository satisfies mpdiff requests, then bundle can be
 
146
defined in terms of mpdiff lookups rather than file text lookups
 
147
appropriate to create mpdiffs. If the repository satisfies full text
 
148
requests only, then you need the topological access to build up the
 
149
desired mpdiffs.
 
150
 
 
151
=========================================== =========
 
152
Pattern                                     Commands
 
153
=========================================== =========
 
154
Single file text                            annotate, diff
 
155
Files present in one revision               branch
 
156
Newest form of files altered by revisions   merge, update?
 
157
Topological access to file versions/deltas  annotate-uncached
 
158
Stream all data required to recreate revs   branch (lightweight)
 
159
Stream file texts in topological order      bundle
 
160
Write full versions of files, inv, rev, sig commit
 
161
Write deltas of files, inv for one tree     commit
 
162
Stream all data introduced by revs          fetch
 
163
Regenerate/combine deltas of many trees     fetch, pack
 
164
Reconstruct all texts and validate trees    check, fetch
 
165
Revision graph walk                         fetch, pack, uncommit,
 
166
                                            annotate-uncached,
 
167
                                            merge, log, missing
 
168
Top down access multiple invs concurrently  status, diff, merge?, update?
 
169
Concurrent access to N file texts           diff, merge
 
170
Iteration of inventory deltas               log -v, fetch?
 
171
=========================================== =========
 
172
 
 
173
Facilities to scale well
 
174
========================
 
175
 
 
176
Indices
 
177
-------
 
178
 
 
179
We want < linear access to all data in the repository. This suggests
 
180
everything is indexed to some degree.
 
181
 
 
182
Often we know the kind of data we are accessing; which allows us to
 
183
partition our indices if that will help (e.g. by reducing the total index
 
184
size for queries that only care about the revision graph).
 
185
 
 
186
Indices that support our data access patterns will usually display
 
187
increased locality of reference, reducing the impact of a large indices
 
188
without needing careful page size management or other tricks.
 
189
 
 
190
We need repository wide indices. For the current repositories this is
 
191
achieved by dividing the keyspace (revisions, signatures, inventories,
 
192
per-fileid) and then having an append only index within each keyspace.
 
193
For pack based repositories we will want some means to query the index of
 
194
each component pack, presumably as a single logical index.
 
195
 
 
196
It would be nice if indexing was made cleanly separate from storage. So
 
197
that suggests indices don't know the meaning of the lookup; indices which
 
198
offer particular ordering, or graph walking facilities will clearly need
 
199
that information, but perhaps they don't need to know the semantics ?
 
200
 
 
201
Index size
 
202
~~~~~~~~~~
 
203
 
 
204
Smaller indexes are good. We could go with one big index, or a different
 
205
index for different operation styles. As multiple indices will occupy more
 
206
space in total we should consider carefully about adding indices.
 
207
 
 
208
Index ordering
 
209
~~~~~~~~~~~~~~
 
210
 
 
211
Looking at the data access patterns some operations such as graph walking
 
212
can clearly be made more efficient by offering direct iteration rather
 
213
than repeated reentry into the index - so having indices that support
 
214
iteration in such a style would be useful eventually.
 
215
 
 
216
Changing our current indexes
 
217
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
218
 
 
219
We can consider introducing cleaner indices in advance of a full pack
 
220
based repository.
 
221
 
 
222
There are many possibilities for this, but I've chosen one that seems ok
 
223
to me for illustration.
 
224
 
 
225
A key element is to consider when indices are updated. I think that the
 
226
update style proposed for pack based repositories - write once, then when
 
227
we group data again rewrite a new single index - is sufficent.
 
228
 
 
229
Replace .kndx
 
230
^^^^^^^^^^^^^
 
231
 
 
232
We could discard the per-knit .kndx by writing a new index at the end of
 
233
every bzr transaction indexing the new data introduced by the bzr
 
234
operation. e.g. at the end of fetch. This can be based on the new
 
235
``GraphIndex`` index type.
 
236
 
 
237
Encoding a knit entry into a ``GraphIndex`` can be done as follows:
 
238
 
 
239
* Change the key to include a prefix of the knit name, to allow filtering
 
240
  out of data from different knits.
 
241
* Encode the parents from the knit as the zeroth node reference list.
 
242
* If the knit hunk was delta compressed encode the node it was delta
 
243
  compressed against as the 1st node reference list (otherwise the 1st
 
244
  node reference list will be empty to indicate no compression parents).
 
245
* For the value encode similarly to the current knit format the byte
 
246
  offset for the data record in the knit, the byte length for the data
 
247
  record in the knit and the no-end-of-line flag.
 
248
 
 
249
Its important to note that knit repositories cannot be regenerated by
 
250
scanning .knits, so a mapped index is still irreplaceable and must be
 
251
transmitted on push/pull.
 
252
 
 
253
A potential improvement exists by specialising this further to not record
 
254
data that is not needed - e.g. an index of revisions does not need to
 
255
support a pointer to a parent compressed text as revisions.knit is not
 
256
delta-compressed ever. Likewise signatures do not need the parent pointers
 
257
at all as there is no 'signature graph'.
 
258
 
 
259
Data
 
260
----
 
261
 
 
262
Moving to pack based repositories
 
263
---------------------------------
 
264
 
 
265
We have a number of challenges to solve.
 
266
 
 
267
Naming of files
 
268
~~~~~~~~~~~~~~~
 
269
 
 
270
As long as the file name is unique it does not really matter. It might be
 
271
interesting to have it be deterministic based on content, but there are no
 
272
specific problems we have solved by doing that, and doing so would require
 
273
hashing the full file. OTOH hashing the full file is a cheap way to detect
 
274
bit-errors in transfer (such as windows corruption). Non-reused file names
 
275
are required for data integrity, as clients having read an index will
 
276
readv at arbitrary times later.
 
277
 
 
278
Discovery of files
 
279
~~~~~~~~~~~~~~~~~~
 
280
 
 
281
With non-listable transports how should the collection of pack/index files
 
282
be found ? Initially record a list of all the pack/index files from
 
283
write actions. (Require writable transports to be listable). We can then
 
284
use a heuristic to statically combine pack/index files later.
 
285
 
 
286
Housing files
 
287
~~~~~~~~~~~~~
 
288
 
 
289
Combining indices on demand
 
290
~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
291
 
 
292
Merging data on push
 
293
~~~~~~~~~~~~~~~~~~~~
 
294
 
 
295
A trivial implementation would be to make a pack which has just the data
 
296
needed for the push, then send that. More sophisticated things would be
 
297
streaming single-pass creation, and also using this as an opportunity to
 
298
increase the packedness of the local repo.
 
299
 
 
300
Choosing compression/delta support
 
301
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
302
 
 
303
Caching and writeing of data
 
304
============================
 
305
 
 
306
Repositories try to provide a consistent view of the data within them
 
307
within a 'lock context'.
 
308
 
 
309
Locks
 
310
-----
 
311
 
 
312
Locks come in two flavours - read locks and write locks. Read locks allow
 
313
data to be read from the repository. Write locks allow data to be read and
 
314
signal that you intend to write data at some point. The actual writing of
 
315
data must take place within a Write Group.
 
316
 
 
317
Write locks provide a cache of repository data during the period of the
 
318
write lock, and allow write_groups to be acquired. For some repositories
 
319
the presence of a write lock is exclusive to a single client, for others
 
320
which are lock free or use server side locks (e.g.  svn), the write lock
 
321
simply provides the cache context.
 
322
 
 
323
Write Groups
 
324
------------
 
325
 
 
326
Write groups are the only allowed means for inserting data into a
 
327
repository.  These are created by ``start_write_group``, and concluded by
 
328
either ``commit_write_group`` or ``abort_write_group``.  A write lock must
 
329
be held on the repository for the entire duration.  At most one write
 
330
group can be active on a repository at a time.
 
331
 
 
332
Write groups signal to the repository the window during which data is
 
333
actively being inserted. Several write groups could be committed during a
 
334
single lock.
 
335
 
 
336
There is no guarantee that data inserted during a write group will be
 
337
invisible in the repository if the write group is not committed.
 
338
Specifically repositories without atomic insertion facilities will be
 
339
writing data as it is inserted within the write group, and may not be able
 
340
to revert that data - e.g. in the event of a dropped SFTP connection in a
 
341
knit repository, inserted file data will be visible in the repository. Some
 
342
repositories have an atomic insertion facility, and for those
 
343
all-or-nothing will apply.
 
344
 
 
345
The precise meaning of a write group is format specific. For instance a
 
346
knit based repository treats the write group methods as dummy calls,
 
347
simply meeting the api that clients will use. A pack based repository will
 
348
open a new pack container at the start of a write group, and rename it
 
349
into place at commit time.
 
350
 
 
351
 
 
352
..
 
353
   vim: ft=rst tw=74 ai
 
354