##// END OF EJS Templates
documentation: add `zstd` compression to the internal `revlogs` documentation...
Antoine Cezar -
r45961:684083d1 default
parent child Browse files
Show More
@@ -1,239 +1,241 b''
1 Revision logs - or *revlogs* - are an append only data structure for
1 Revision logs - or *revlogs* - are an append only data structure for
2 storing discrete entries, or *revisions*. They are the primary storage
2 storing discrete entries, or *revisions*. They are the primary storage
3 mechanism of repository data.
3 mechanism of repository data.
4
4
5 Revlogs effectively model a directed acyclic graph (DAG). Each node
5 Revlogs effectively model a directed acyclic graph (DAG). Each node
6 has edges to 1 or 2 *parent* nodes. Each node contains metadata and
6 has edges to 1 or 2 *parent* nodes. Each node contains metadata and
7 the raw value for that node.
7 the raw value for that node.
8
8
9 Revlogs consist of entries which have metadata and revision data.
9 Revlogs consist of entries which have metadata and revision data.
10 Metadata includes the hash of the revision's content, sizes, and
10 Metadata includes the hash of the revision's content, sizes, and
11 links to its *parent* entries. The collective metadata is referred
11 links to its *parent* entries. The collective metadata is referred
12 to as the *index* and the revision data is the *data*.
12 to as the *index* and the revision data is the *data*.
13
13
14 Revision data is stored as a series of compressed deltas against
14 Revision data is stored as a series of compressed deltas against
15 ancestor revisions.
15 ancestor revisions.
16
16
17 Revlogs are written in an append-only fashion. We never need to rewrite
17 Revlogs are written in an append-only fashion. We never need to rewrite
18 a file to insert nor do we need to remove data. Rolling back in-progress
18 a file to insert nor do we need to remove data. Rolling back in-progress
19 writes can be performed by truncating files. Read locks can be avoided
19 writes can be performed by truncating files. Read locks can be avoided
20 using simple techniques. This means that references to other data in
20 using simple techniques. This means that references to other data in
21 the same revlog *always* refer to a previous entry.
21 the same revlog *always* refer to a previous entry.
22
22
23 Revlogs can be modeled as 0-indexed arrays. The first revision is
23 Revlogs can be modeled as 0-indexed arrays. The first revision is
24 revision #0 and the second is revision #1. The revision -1 is typically
24 revision #0 and the second is revision #1. The revision -1 is typically
25 used to mean *does not exist* or *not defined*.
25 used to mean *does not exist* or *not defined*.
26
26
27 File Format
27 File Format
28 ===========
28 ===========
29
29
30 A revlog begins with a 32-bit big endian integer holding version info
30 A revlog begins with a 32-bit big endian integer holding version info
31 and feature flags. This integer overlaps with the first four bytes of
31 and feature flags. This integer overlaps with the first four bytes of
32 the first revision entry.
32 the first revision entry.
33
33
34 This integer is logically divided into 2 16-bit shorts. The least
34 This integer is logically divided into 2 16-bit shorts. The least
35 significant half of the integer is the format/version short. The other
35 significant half of the integer is the format/version short. The other
36 short holds feature flags that dictate behavior of the revlog.
36 short holds feature flags that dictate behavior of the revlog.
37
37
38 The following values for the format/version short are defined:
38 The following values for the format/version short are defined:
39
39
40 0
40 0
41 The original revlog version.
41 The original revlog version.
42 1
42 1
43 RevlogNG (*next generation*). It replaced version 0 when it was
43 RevlogNG (*next generation*). It replaced version 0 when it was
44 implemented in 2006.
44 implemented in 2006.
45 2
45 2
46 In-development version incorporating accumulated knowledge and
46 In-development version incorporating accumulated knowledge and
47 missing features from 10+ years of revlog version 1.
47 missing features from 10+ years of revlog version 1.
48 57005 (0xdead)
48 57005 (0xdead)
49 Reserved for internal testing of new versions. No defined format
49 Reserved for internal testing of new versions. No defined format
50 beyond 32-bit header.
50 beyond 32-bit header.
51
51
52 The feature flags short consists of bit flags. Where 0 is the least
52 The feature flags short consists of bit flags. Where 0 is the least
53 significant bit. The bit flags vary by revlog version.
53 significant bit. The bit flags vary by revlog version.
54
54
55 Version 0 revlogs have no defined flags and the presence of a flag
55 Version 0 revlogs have no defined flags and the presence of a flag
56 is considered an error.
56 is considered an error.
57
57
58 Version 1 revlogs have the following flags at the specified bit offsets:
58 Version 1 revlogs have the following flags at the specified bit offsets:
59
59
60 0
60 0
61 Store revision data inline.
61 Store revision data inline.
62 1
62 1
63 Generaldelta encoding.
63 Generaldelta encoding.
64
64
65 Version 2 revlogs have the following flags at the specified bit offsets:
65 Version 2 revlogs have the following flags at the specified bit offsets:
66
66
67 0
67 0
68 Store revision data inline.
68 Store revision data inline.
69
69
70 The following header values are common:
70 The following header values are common:
71
71
72 00 00 00 01
72 00 00 00 01
73 v1
73 v1
74 00 01 00 01
74 00 01 00 01
75 v1 + inline
75 v1 + inline
76 00 02 00 01
76 00 02 00 01
77 v1 + generaldelta
77 v1 + generaldelta
78 00 03 00 01
78 00 03 00 01
79 v1 + inline + generaldelta
79 v1 + inline + generaldelta
80
80
81 Following the 32-bit header is the remaining 60 bytes of the first index
81 Following the 32-bit header is the remaining 60 bytes of the first index
82 entry. Following that are additional *index* entries. Inlined revision
82 entry. Following that are additional *index* entries. Inlined revision
83 data is possibly located between index entries. More on this inlined
83 data is possibly located between index entries. More on this inlined
84 layout is described below.
84 layout is described below.
85
85
86 Version 1 Format
86 Version 1 Format
87 ================
87 ================
88
88
89 Version 1 (RevlogNG) begins with an index describing the revisions in
89 Version 1 (RevlogNG) begins with an index describing the revisions in
90 the revlog. If the ``inline`` flag is set, revision data is stored inline,
90 the revlog. If the ``inline`` flag is set, revision data is stored inline,
91 or between index entries (as opposed to in a separate container).
91 or between index entries (as opposed to in a separate container).
92
92
93 Each index entry is 64 bytes. The byte layout of each entry is as
93 Each index entry is 64 bytes. The byte layout of each entry is as
94 follows, with byte 0 being the first byte (all data stored as big endian):
94 follows, with byte 0 being the first byte (all data stored as big endian):
95
95
96 0-3 (4 bytes) (rev 0 only)
96 0-3 (4 bytes) (rev 0 only)
97 Revlog header
97 Revlog header
98
98
99 0-5 (6 bytes)
99 0-5 (6 bytes)
100 Absolute offset of revision data from beginning of revlog.
100 Absolute offset of revision data from beginning of revlog.
101
101
102 6-7 (2 bytes)
102 6-7 (2 bytes)
103 Bit flags impacting revision behavior. The following bit offsets define:
103 Bit flags impacting revision behavior. The following bit offsets define:
104
104
105 0: REVIDX_ISCENSORED revision has censor metadata, must be verified.
105 0: REVIDX_ISCENSORED revision has censor metadata, must be verified.
106
106
107 1: REVIDX_ELLIPSIS revision hash does not match its data. Used by
107 1: REVIDX_ELLIPSIS revision hash does not match its data. Used by
108 narrowhg
108 narrowhg
109
109
110 2: REVIDX_EXTSTORED revision data is stored externally.
110 2: REVIDX_EXTSTORED revision data is stored externally.
111
111
112 8-11 (4 bytes)
112 8-11 (4 bytes)
113 Compressed length of revision data / chunk as stored in revlog.
113 Compressed length of revision data / chunk as stored in revlog.
114
114
115 12-15 (4 bytes)
115 12-15 (4 bytes)
116 Uncompressed length of revision data. This is the size of the full
116 Uncompressed length of revision data. This is the size of the full
117 revision data, not the size of the chunk post decompression.
117 revision data, not the size of the chunk post decompression.
118
118
119 16-19 (4 bytes)
119 16-19 (4 bytes)
120 Base or previous revision this revision's delta was produced against.
120 Base or previous revision this revision's delta was produced against.
121 This revision holds full text (as opposed to a delta) if it points to
121 This revision holds full text (as opposed to a delta) if it points to
122 itself. For generaldelta repos, this is the previous revision in the
122 itself. For generaldelta repos, this is the previous revision in the
123 delta chain. For non-generaldelta repos, this is the base or first
123 delta chain. For non-generaldelta repos, this is the base or first
124 revision in the delta chain.
124 revision in the delta chain.
125
125
126 20-23 (4 bytes)
126 20-23 (4 bytes)
127 A revision this revision is *linked* to. This allows a revision in
127 A revision this revision is *linked* to. This allows a revision in
128 one revlog to be forever associated with a revision in another
128 one revlog to be forever associated with a revision in another
129 revlog. For example, a file's revlog may point to the changelog
129 revlog. For example, a file's revlog may point to the changelog
130 revision that introduced it.
130 revision that introduced it.
131
131
132 24-27 (4 bytes)
132 24-27 (4 bytes)
133 Revision of 1st parent. -1 indicates no parent.
133 Revision of 1st parent. -1 indicates no parent.
134
134
135 28-31 (4 bytes)
135 28-31 (4 bytes)
136 Revision of 2nd parent. -1 indicates no 2nd parent.
136 Revision of 2nd parent. -1 indicates no 2nd parent.
137
137
138 32-63 (32 bytes)
138 32-63 (32 bytes)
139 Hash of revision's full text. Currently, SHA-1 is used and only
139 Hash of revision's full text. Currently, SHA-1 is used and only
140 the first 20 bytes of this field are used. The rest of the bytes
140 the first 20 bytes of this field are used. The rest of the bytes
141 are ignored and should be stored as \0.
141 are ignored and should be stored as \0.
142
142
143 If inline revision data is being stored, the compressed revision data
143 If inline revision data is being stored, the compressed revision data
144 (of length from bytes offset 8-11 from the index entry) immediately
144 (of length from bytes offset 8-11 from the index entry) immediately
145 follows the index entry. There is no header on the revision data. There
145 follows the index entry. There is no header on the revision data. There
146 is no padding between it and the index entries before and after.
146 is no padding between it and the index entries before and after.
147
147
148 If revision data is not inline, then raw revision data is stored in a
148 If revision data is not inline, then raw revision data is stored in a
149 separate byte container. The offsets from bytes 0-5 and the compressed
149 separate byte container. The offsets from bytes 0-5 and the compressed
150 length from bytes 8-11 define how to access this data.
150 length from bytes 8-11 define how to access this data.
151
151
152 The 6 byte absolute offset field from the first revlog entry overlaps
152 The 6 byte absolute offset field from the first revlog entry overlaps
153 with the revlog header. That is, the first 6 bytes of the first revlog
153 with the revlog header. That is, the first 6 bytes of the first revlog
154 entry can be split into four bytes containing the header for the revlog
154 entry can be split into four bytes containing the header for the revlog
155 file and an additional two bytes containing the offset for the first
155 file and an additional two bytes containing the offset for the first
156 entry. Since this is the offset from the beginning of the file for the
156 entry. Since this is the offset from the beginning of the file for the
157 first revision entry, the two bytes will always be set to zero.
157 first revision entry, the two bytes will always be set to zero.
158
158
159 Version 2 Format
159 Version 2 Format
160 ================
160 ================
161
161
162 (In development. Format not finalized or stable.)
162 (In development. Format not finalized or stable.)
163
163
164 Version 2 is identical to version 1 with the following differences.
164 Version 2 is identical to version 1 with the following differences.
165
165
166 There is no dedicated *generaldelta* revlog format flag. Instead,
166 There is no dedicated *generaldelta* revlog format flag. Instead,
167 the feature is implied enabled by default.
167 the feature is implied enabled by default.
168
168
169 Delta Chains
169 Delta Chains
170 ============
170 ============
171
171
172 Revision data is encoded as a chain of *chunks*. Each chain begins with
172 Revision data is encoded as a chain of *chunks*. Each chain begins with
173 the compressed original full text for that revision. Each subsequent
173 the compressed original full text for that revision. Each subsequent
174 *chunk* is a *delta* against the previous revision. We therefore call
174 *chunk* is a *delta* against the previous revision. We therefore call
175 these chains of chunks/deltas *delta chains*.
175 these chains of chunks/deltas *delta chains*.
176
176
177 The full text for a revision is reconstructed by loading the original
177 The full text for a revision is reconstructed by loading the original
178 full text for the base revision of a *delta chain* and then applying
178 full text for the base revision of a *delta chain* and then applying
179 *deltas* until the target revision is reconstructed.
179 *deltas* until the target revision is reconstructed.
180
180
181 *Delta chains* are limited in length so lookup time is bound. They are
181 *Delta chains* are limited in length so lookup time is bound. They are
182 limited to ~2x the length of the revision's data. The linear distance
182 limited to ~2x the length of the revision's data. The linear distance
183 between the base chunk and the final chunk is also limited so the
183 between the base chunk and the final chunk is also limited so the
184 amount of read I/O to load all chunks in the delta chain is bound.
184 amount of read I/O to load all chunks in the delta chain is bound.
185
185
186 Deltas and delta chains are either computed against the previous
186 Deltas and delta chains are either computed against the previous
187 revision in the revlog or another revision (almost certainly one of
187 revision in the revlog or another revision (almost certainly one of
188 the parents of the revision). Historically, deltas were computed against
188 the parents of the revision). Historically, deltas were computed against
189 the previous revision. The *generaldelta* revlog feature flag (enabled
189 the previous revision. The *generaldelta* revlog feature flag (enabled
190 by default in Mercurial 3.7) activates the mode where deltas are
190 by default in Mercurial 3.7) activates the mode where deltas are
191 computed against an arbitrary revision (almost certainly a parent revision).
191 computed against an arbitrary revision (almost certainly a parent revision).
192
192
193 File Storage
193 File Storage
194 ============
194 ============
195
195
196 Revlogs logically consist of an index (metadata of entries) and
196 Revlogs logically consist of an index (metadata of entries) and
197 revision data. This data may be stored together in a single file or in
197 revision data. This data may be stored together in a single file or in
198 separate files. The mechanism used is indicated by the ``inline`` feature
198 separate files. The mechanism used is indicated by the ``inline`` feature
199 flag on the revlog.
199 flag on the revlog.
200
200
201 Mercurial's behavior is to use inline storage until a revlog reaches a
201 Mercurial's behavior is to use inline storage until a revlog reaches a
202 certain size, at which point it will be converted to non-inline. The
202 certain size, at which point it will be converted to non-inline. The
203 reason there is a size limit on inline storage is to establish an upper
203 reason there is a size limit on inline storage is to establish an upper
204 bound on how much data must be read to load the index. It would be a waste
204 bound on how much data must be read to load the index. It would be a waste
205 to read tens or hundreds of extra megabytes of data just to access the
205 to read tens or hundreds of extra megabytes of data just to access the
206 index data.
206 index data.
207
207
208 The actual layout of revlog files on disk is governed by the repository's
208 The actual layout of revlog files on disk is governed by the repository's
209 *store format*. Typically, a ``.i`` file represents the index revlog
209 *store format*. Typically, a ``.i`` file represents the index revlog
210 (possibly containing inline data) and a ``.d`` file holds the revision data.
210 (possibly containing inline data) and a ``.d`` file holds the revision data.
211
211
212 Revision Entries
212 Revision Entries
213 ================
213 ================
214
214
215 Revision entries consist of an optional 1 byte header followed by an
215 Revision entries consist of an optional 1 byte header followed by an
216 encoding of the revision data. The headers are as follows:
216 encoding of the revision data. The headers are as follows:
217
217
218 \0 (0x00)
218 \0 (0x00)
219 Revision data is the entirety of the entry, including this header.
219 Revision data is the entirety of the entry, including this header.
220 u (0x75)
220 ( (0x28)
221 Raw revision data follows.
221 zstd https://github.com/facebook/zstd
222 x (0x78)
222 u (0x75)
223 zlib (RFC 1950) data.
223 Raw revision data follows.
224 x (0x78)
225 zlib (RFC 1950) data.
224
226
225 The 0x78 value is actually the first byte of the zlib header (CMF byte).
227 The 0x78 value is actually the first byte of the zlib header (CMF byte).
226
228
227 Hash Computation
229 Hash Computation
228 ================
230 ================
229
231
230 The hash of the revision is stored in the index and is used both as a primary
232 The hash of the revision is stored in the index and is used both as a primary
231 key and for data integrity verification.
233 key and for data integrity verification.
232
234
233 Currently, SHA-1 is the only supported hashing algorithm. To obtain the SHA-1
235 Currently, SHA-1 is the only supported hashing algorithm. To obtain the SHA-1
234 hash of a revision:
236 hash of a revision:
235
237
236 1. Hash the parent nodes
238 1. Hash the parent nodes
237 2. Hash the fulltext of the revision
239 2. Hash the fulltext of the revision
238
240
239 The 20 byte node ids of the parents are fed into the hasher in ascending order.
241 The 20 byte node ids of the parents are fed into the hasher in ascending order.
General Comments 0
You need to be logged in to leave comments. Login now