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 |
|
|
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