« back to all changes in this revision
Viewing changes to doc/developers/container-format.txt
- browse files at revision 2499.4.3
- compare with another revision
- compare with revision 334
- download diff
- download tarball
- view history from revision 2499.4.3
- Committer: Andrew Bennetts
- Date: 2007-06-07 06:41:53 UTC
- mto: This revision was merged to the branch mainline in revision 2519.
- Revision ID: andrew.bennetts@canonical.com-20070607064153-z6sap26og3pbxxrl
Updates in response to feedback on mailing list and in person.
- files modified:
- Makefile
added
removed
doc/developers/container-format.txt
5
5
Status
6
6
======
7
7
8
:Date: 2007-06-01
8
:Date: 2007-06-07
9
9
10
10
This document describes the proposed container format for streaming and
11
11
storing collections of data in Bazaar. Initially this will be used for
14
14
than just that use case.
15
15
16
16
In particular, this document currently focuses almost exclusively on the
17
streaming case, and not the on-disk storage case.
17
streaming case, and not the on-disk storage case. It also does not
18
discuss the APIs used to manipulate containers and their records.
19
18
20
19
21
.. contents::
20
22
21
Specification
22
=============
23
24
This describes just a basic layer for storing simple series of "records".
25
This layer has no intrinsic understanding of the contents of those
26
records.
27
28
The format is:
29
30
* a **container lead-in**, "``bzr pack format 1\n``",
31
* followed by one or more **records**.
32
33
A record is:
34
35
* a 3 byte **kind marker**.
36
* 0 or more bytes of record content, depending on the record type.
37
38
Record types
39
------------
40
41
End Marker
42
~~~~~~~~~~
43
44
An **End Marker** record:
45
46
* has a kind marker of "``EM\n``",
47
* no content bytes.
48
49
End Marker records signal the end of a container.
50
51
Full Text
52
~~~~~~~~~
53
54
A **Full Text** record:
55
56
* has a kind marker of "``FT\n``",
57
* followed by one or more optional **name headers**:
58
"``name:`` *name*\ ``\n``", e.g.::
59
60
name: revision:pqm@pqm.ubuntu.com-20070531210833-8ptk86ocu822hjd5
61
62
* followed by a mandatory **content length header**:
63
"``length:`` *number*\ ``\n``", where *number* is in decimal, e.g::
64
65
length: 1234
66
67
* followed by an **end of headers** byte: "``\n``",
68
* followed by some **bytes**, exactly as many as specified by the length
69
prefix header.
70
71
So a Full Text record looks a bit like an RFC 822-formatted message.
72
e.g.::
73
74
FT
75
name: example-record
76
length: 5
77
78
abcde
79
80
81
Names
82
-----
83
84
Names should be UTF-8 encoded strings, with no whitespace. Names should
85
be unique within a single container, but no guarantee of uniqueness
86
outside of the container is made by this layer.
87
88
89
Characteristics
90
===============
91
92
Some key aspects of this format are discussed in this section.
93
94
No length-prefixing of entire container
95
---------------------------------------
96
97
The overall container is not length prefixed. Instead there is an end
98
marker so that readers can determine when they have read the entire
99
container. This also does not conflict with the goal of allowing
100
single-pass writing.
101
102
Structured as a self-contained series of records
103
------------------------------------------------
104
105
The container contains a series of *records*. Each record is
106
self-delimiting. Record markers are lightweight. The overhead in terms
107
of bytes and processing for records in this container vs. the raw contents
108
of those records is minimal.
109
110
Addressing records
111
------------------
112
113
There is a requirement that each object can be given an arbitrary name.
114
Some revision control systems address all content by the SHA-1 digest of
115
that content, but this scheme is unsatisfactory for Bazaar's revision
116
objects. We can still allow addressing by SHA-1 digest for those content
117
types where it makes sense.
118
119
Some proposed object names:
120
121
* to name a revision: "``revision:``\ *revision-id*". e.g.,
122
`revision:pqm@pqm.ubuntu.com-20070531210833-8ptk86ocu822hjd5`.
123
* to name an inventory delta: "``inventory.delta:``\ *revision-id*". e.g.,
124
`inventory.delta:pqm@pqm.ubuntu.com-20070531210833-8ptk86ocu822hjd5`.
125
126
It seems likely that we may want to have multiple names for an object.
127
This format allows that (by allowing multiple ``name`` headers in a Full
128
Text record).
129
130
Although records are in principle addressable by name, this specification
131
alone doesn't provide for efficient access to a particular record given
132
its name. It is intended that seperate indexes will be maintained to
133
provide this.
23
24
Motivation
25
==========
26
27
To create a low-level file format which is suitable for solving the smart
28
server latency problem and whose layout and requirements are extendable in
29
future versions of Bazaar, and with no requirements that the smart server
30
does not have today.
31
32
33
Terminology
34
===========
35
36
A **container** is a streamable file that contains a series of
37
**records**. Records may have **names**, and consist of bytes.
134
38
135
39
136
40
Use Cases
181
85
182
86
Specifically, we'd like to have this format in Bazaar 0.18.
183
87
184
185
88
Examples of possible record content
186
===================================
89
-----------------------------------
187
90
188
* full texts
91
* full texts of file versions
189
92
* deltas of full texts
190
93
* revisions
191
94
* inventories
195
98
* annotation cache
196
99
197
100
101
Characteristics
102
===============
103
104
Some key aspects of the described format are discussed in this section.
105
106
No length-prefixing of entire container
107
---------------------------------------
108
109
The overall container is not length prefixed. Instead there is an end
110
marker so that readers can determine when they have read the entire
111
container. This also does not conflict with the goal of allowing
112
single-pass writing.
113
114
Structured as a self-contained series of records
115
------------------------------------------------
116
117
The container contains a series of *records*. Each record is
118
self-delimiting. Record markers are lightweight. The overhead in terms
119
of bytes and processing for records in this container vs. the raw contents
120
of those records is minimal.
121
122
Addressing records
123
------------------
124
125
There is a requirement that each object can be given an arbitrary name.
126
Some revision control systems address all content by the SHA-1 digest of
127
that content, but this scheme is unsatisfactory for Bazaar's revision
128
objects. We can still allow addressing by SHA-1 digest for those content
129
types where it makes sense.
130
131
Some proposed object names:
132
133
* to name a revision: "``revision:``\ *revision-id*". e.g.,
134
`revision:pqm@pqm.ubuntu.com-20070531210833-8ptk86ocu822hjd5`.
135
* to name an inventory delta: "``inventory.delta:``\ *revision-id*". e.g.,
136
`inventory.delta:pqm@pqm.ubuntu.com-20070531210833-8ptk86ocu822hjd5`.
137
138
It seems likely that we may want to have multiple names for an object.
139
This format allows that (by allowing multiple ``name`` headers in a Bytes
140
record).
141
142
Although records are in principle addressable by name, this specification
143
alone doesn't provide for efficient access to a particular record given
144
its name. It is intended that seperate indexes will be maintained to
145
provide this.
146
147
It is acceptable to have records with no explicit name, if the expected
148
use of them does not require them. For example:
149
150
* a record's content could be self-describing in the context of a
151
particular container, or
152
* a record could be accessed via an index based on SHA-1, or
153
* when streaming, the first record could be treated specially.
154
155
Reasonably cheap for small records
156
----------------------------------
157
158
The overhead for storing fairly short records (tens of bytes, rather than
159
thousands or millions) is minimal. The minimum overhead is 3 bytes plus
160
the length of the decimal representation of the *length* value (for a
161
record with no name).
162
163
164
Specification
165
=============
166
167
This describes just a basic layer for storing simple series of "records".
168
This layer has no intrinsic understanding of the contents of those
169
records.
170
171
The format is:
172
173
* a **container lead-in**, "``bzr pack format 1\n``",
174
* followed by one or more **records**.
175
176
A record is:
177
178
* a 1 byte **kind marker**.
179
* 0 or more bytes of record content, depending on the record type.
180
181
Record types
182
------------
183
184
End Marker
185
~~~~~~~~~~
186
187
An **End Marker** record:
188
189
* has a kind marker of "``E``",
190
* no content bytes.
191
192
End Marker records signal the end of a container.
193
194
Bytes
195
~~~~~
196
197
A **Bytes** record:
198
199
* has a kind marker of "``B``",
200
* followed by a mandatory **content length** [1]_:
201
"*number*\ ``\n``", where *number* is in decimal, e.g::
202
203
1234
204
205
* followed by zero or more optional **names**:
206
"*name*\ ``\n``", e.g.::
207
208
revision:pqm@pqm.ubuntu.com-20070531210833-8ptk86ocu822hjd5
209
210
* followed by an **end of headers** byte: "``\n``",
211
* followed by some **bytes**, exactly as many as specified by the length
212
prefix header.
213
214
So a Bytes record is a series of lines encoding the length and names (if
215
any) followed by a body.
216
217
For example, this is a possible Bytes record (including the kind marker)::
218
219
B26
220
example-name1
221
example-name2
222
223
abcdefghijklmnopqrstuvwxyz
224
225
226
Names
227
-----
228
229
Names should be UTF-8 encoded strings, with no whitespace. Names should
230
be unique within a single container, but no guarantee of uniqueness
231
outside of the container is made by this layer. Names need to be at least
232
one character long.
233
234
235
.. [1] This requires that the writer of a record knows the full length of
236
the record up front, which typically means it will need to buffer an
237
entire record in memory. For the first version of this format this is
238
considered to be acceptable.
239
198
240
..
199
241
vim: ft=rst tw=74 ai
200
242
Loggerhead is a web-based interface for Breezy
Version: 2.0.1