Mercurial > hg
comparison mercurial/help/internals/revlogs.txt @ 27631:c18292a6ff54
internals: document revlog format
It seems like a good idea to document the revlog format.
There is a lot more that could be added to this documentation.
But you have to start somewhere.
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Wed, 30 Dec 2015 16:21:57 -0700 |
parents | |
children | b0b9f6b0a777 |
comparison
equal
deleted
inserted
replaced
27630:9358124b4a65 | 27631:c18292a6ff54 |
---|---|
1 Revisions Logs | |
2 ============== | |
3 | |
4 Revision logs - or *revlogs* - are an append only data structure for | |
5 storing discrete entries, or *revisions*. They are the primary storage | |
6 mechanism of repository data. | |
7 | |
8 Revlogs effectively model a directed acyclic graph (DAG). Each node | |
9 has edges to 1 or 2 *parent* nodes. Each node contains metadata and | |
10 the raw value for that node. | |
11 | |
12 Revlogs consist of entries which have metadata and revision data. | |
13 Metadata includes the hash of the revision's content, sizes, and | |
14 links to its *parent* entries. The collective metadata is referred | |
15 to as the *index* and the revision data is the *data*. | |
16 | |
17 Revision data is stored as a series of compressed deltas against previous | |
18 revisions. | |
19 | |
20 Revlogs are written in an append-only fashion. We never need to rewrite | |
21 a file to insert nor do we need to remove data. Rolling back in-progress | |
22 writes can be performed by truncating files. Read locks can be avoided | |
23 using simple techniques. This means that references to other data in | |
24 the same revlog *always* refer to a previous entry. | |
25 | |
26 Revlogs can be modeled as 0-indexed arrays. The first revision is | |
27 revision #0 and the second is revision #1. The revision -1 is typically | |
28 used to mean *does not exist* or *not defined*. | |
29 | |
30 File Format | |
31 ----------- | |
32 | |
33 A revlog begins with a 32-bit big endian integer holding version info | |
34 and feature flags. | |
35 | |
36 This integer is logically divided into 2 16-bit shorts. The least | |
37 significant half of the integer is the format/version short. The other | |
38 short holds feature flags that dictate behavior of the revlog. | |
39 | |
40 Only 1 bit of the format/version short is currently used. Remaining | |
41 bits are reserved for future use. | |
42 | |
43 The following values for the format/version short are defined: | |
44 | |
45 0 | |
46 The original revlog version. | |
47 1 | |
48 RevlogNG (*next generation*). It replaced version 0 when it was | |
49 implemented in 2006. | |
50 | |
51 The feature flags short consists of bit flags. Where 0 is the least | |
52 significant bit, the following bit offsets define flags: | |
53 | |
54 0 | |
55 Store revision data inline. | |
56 1 | |
57 Generaldelta encoding. | |
58 | |
59 2-15 | |
60 Reserved for future use. | |
61 | |
62 The following header values are common: | |
63 | |
64 00 00 00 01 | |
65 RevlogNG | |
66 00 01 00 01 | |
67 RevlogNG + inline | |
68 00 02 00 01 | |
69 RevlogNG + generaldelta | |
70 00 03 00 01 | |
71 RevlogNG + inline + generaldelta | |
72 | |
73 Following the 32-bit header is *index* data. Inlined revision data is possibly | |
74 located between index entries. More on this layout is described below. | |
75 | |
76 RevlogNG Format | |
77 --------------- | |
78 | |
79 RevlogNG (version 1) begins with an index describing the revisions in | |
80 the revlog. If the ``inline`` flag is set, revision data is stored inline, | |
81 or between index entries (as opposed to in a separate container). | |
82 | |
83 Each index entry is 64 bytes. The byte layout of each entry is as | |
84 follows, with byte 0 being the first byte (all data stored as big endian): | |
85 | |
86 0-5 (6 bytes) | |
87 Absolute offset of revision data from beginning of revlog. | |
88 6-7 (2 bytes) | |
89 Bit flags impacting revision behavior. | |
90 8-11 (4 bytes) | |
91 Compressed length of revision data / chunk as stored in revlog. | |
92 12-15 (4 bytes) | |
93 Uncompressed length of revision data / chunk. | |
94 16-19 (4 bytes) | |
95 Base or previous revision this revision's delta was produced against. | |
96 -1 means this revision holds full text (as opposed to a delta). | |
97 For generaldelta repos, this is the previous revision in the delta | |
98 chain. For non-generaldelta repos, this is the base or first | |
99 revision in the delta chain. | |
100 20-23 (4 bytes) | |
101 A revision this revision is *linked* to. This allows a revision in | |
102 one revlog to be forever associated with a revision in another | |
103 revlog. For example, a file's revlog may point to the changelog | |
104 revision that introduced it. | |
105 24-27 (4 bytes) | |
106 Revision of 1st parent. -1 indicates no parent. | |
107 28-31 (4 bytes) | |
108 Revision of 2nd parent. -1 indicates no 2nd parent. | |
109 32-63 (32 bytes) | |
110 Hash of revision's full text. Currently, SHA-1 is used and only | |
111 the first 20 bytes of this field are used. The rest of the bytes | |
112 are ignored and should be stored as \0. | |
113 | |
114 If inline revision data is being stored, the compressed revision data | |
115 (of length from bytes offset 8-11 from the index entry) immediately | |
116 follows the index entry. There is no header on the revision data. There | |
117 is no padding between it and the index entries before and after. | |
118 | |
119 If revision data is not inline, then raw revision data is stored in a | |
120 separate byte container. The offsets from bytes 0-5 and the compressed | |
121 length from bytes 8-11 define how to access this data. | |
122 | |
123 Delta Chains | |
124 ------------ | |
125 | |
126 Revision data is encoded as a chain of *chunks*. Each chain begins with | |
127 the compressed original full text for that revision. Each subsequent | |
128 *chunk* is a *delta* against the previous revision. We therefore call | |
129 these chains of chunks/deltas *delta chains*. | |
130 | |
131 The full text for a revision is reconstructed by loading the original | |
132 full text for the base revision of a *delta chain* and then applying | |
133 *deltas* until the target revision is reconstructed. | |
134 | |
135 *Delta chains* are limited in length so lookup time is bound. They are | |
136 limited to ~2x the length of the revision's data. The linear distance | |
137 between the base chunk and the final chunk is also limited so the | |
138 amount of read I/O to load all chunks in the delta chain is bound. | |
139 | |
140 Deltas and delta chains are either computed against the previous | |
141 revision in the revlog or another revision (almost certainly one of | |
142 the parents of the revision). Historically, deltas were computed against | |
143 the previous revision. The *generaldelta* revlog feature flag (enabled | |
144 by default in Mercurial 3.7) activates the mode where deltas are | |
145 computed against an arbitrary revision (almost certainly a parent revision). | |
146 | |
147 File Storage | |
148 ------------ | |
149 | |
150 Revlogs logically consist of an index (metadata of entries) and | |
151 revision data. This data may be stored together in a single file or in | |
152 separate files. The mechanism used is indicated by the ``inline`` feature | |
153 flag on the revlog. | |
154 | |
155 Mercurial's behavior is to use inline storage until a revlog reaches a | |
156 certain size, at which point it will be converted to non-inline. The | |
157 reason there is a size limit on inline storage is to establish an upper | |
158 bound on how much data must be read to load the index. It would be a waste | |
159 to read tens or hundreds of extra megabytes of data just to access the | |
160 index data. | |
161 | |
162 The actual layout of revlog files on disk is governed by the repository's | |
163 *store format*. Typically, a ``.i`` file represents the index revlog | |
164 (possibly containing inline data) and a ``.d`` file holds the revision data. | |
165 | |
166 Revision Entries | |
167 ---------------- | |
168 | |
169 Revision entries consist of an optional 1 byte header followed by an | |
170 encoding of the revision data. The headers are as follows: | |
171 | |
172 \0 (0x00) | |
173 Revision data is the entirety of the entry, including this header. | |
174 u (0x75) | |
175 Raw revision data follows. | |
176 x (0x78) | |
177 zlib (RFC 1950) data. | |
178 | |
179 The 0x78 value is actually the first byte of the zlib header (CMF byte). | |
180 | |
181 Hash Computation | |
182 ---------------- | |
183 | |
184 The hash of the revision is stored in the index and is used both as a primary | |
185 key and for data integrity verification. | |
186 | |
187 Currently, SHA-1 is the only supported hashing algorithm. To obtain the SHA-1 | |
188 hash of a revision: | |
189 | |
190 1. Hash the parent nodes | |
191 2. Hash the fulltext of the revision | |
192 | |
193 The 20 byte node ids of the parents are fed into the hasher in ascending order. |