hgbook
view en/concepts.tex @ 111:34b8b7a15ea1
More material.
| author | Bryan O'Sullivan <bos@serpentine.com> |
|---|---|
| date | Fri Nov 10 15:32:33 2006 -0800 (2006-11-10) |
| parents | 75c076c7a374 |
| children | 2fcead053b7a |
line source
1 \chapter{Behind the scenes}
2 \label{chap:concepts}
4 Unlike many revision control systems, the concepts upon which
5 Mercurial is built are simple enough that it's easy to understand how
6 the software really works. Knowing this certainly isn't necessary,
7 but I find it useful to have a ``mental model'' of what's going on.
9 This understanding gives me confidence that Mercurial has been
10 carefully designed to be both \emph{safe} and \emph{efficient}. And
11 just as importantly, if it's easy for me to retain a good idea of what
12 the software is doing when I perform a revision control task, I'm less
13 likely to be surprised by its behaviour.
15 \section{Mercurial's historical record}
17 \subsection{Tracking the history of a single file}
19 When Mercurial tracks modifications to a file, it stores the history
20 of that file in a metadata object called a \emph{filelog}. Each entry
21 in the filelog contains enough information to reconstruct one revision
22 of the file that is being tracked. Filelogs are stored as files in
23 the \sdirname{.hg/data} directory. A filelog contains two kinds of
24 information: revision data, and an index to help Mercurial to find a
25 revision efficiently.
27 A file that is large, or has a lot of history, has its filelog stored
28 in separate data (``\texttt{.d}'' suffix) and index (``\texttt{.i}''
29 suffix) files. For small files without much history, the revision
30 data and index are combined in a single ``\texttt{.i}'' file. The
31 correspondence between a file in the working directory and the filelog
32 that tracks its history in the repository is illustrated in
33 figure~\ref{fig:concepts:filelog}.
35 \begin{figure}[ht]
36 \centering
37 \grafix{filelog}
38 \caption{Relationships between files in working directory and
39 filelogs in repository}
40 \label{fig:concepts:filelog}
41 \end{figure}
43 \subsection{Managing tracked files}
45 Mercurial uses a structure called a \emph{manifest} to collect
46 together information about the files that it tracks. Each entry in
47 the manifest contains information about the files present in a single
48 changeset. An entry records which files are present in the changeset,
49 the revision of each file, and a few other pieces of file metadata.
51 \subsection{Recording changeset information}
53 The \emph{changelog} contains information about each changeset. Each
54 revision records who committed a change, the changeset comment, other
55 pieces of changeset-related information, and the revision of the
56 manifest to use.
58 \subsection{Relationships between revisions}
60 Within a changelog, a manifest, or a filelog, each revision stores a
61 pointer to its immediate parent (or to its two parents, if it's a
62 merge revision). As I mentioned above, there are also relationships
63 between revisions \emph{across} these structures, and they are
64 hierarchical in nature.
66 For every changeset in a repository, there is exactly one revision
67 stored in the changelog. Each revision of the changelog contains a
68 pointer to a single revision of the manifest. A revision of the
69 manifest stores a pointer to a single revision of each filelog tracked
70 when that changeset was created. These relationships are illustrated
71 in figure~\ref{fig:concepts:metadata}.
73 \begin{figure}[ht]
74 \centering
75 \grafix{metadata}
76 \caption{Metadata relationships}
77 \label{fig:concepts:metadata}
78 \end{figure}
80 As the illustration shows, there is \emph{not} a ``one to one''
81 relationship between revisions in the changelog, manifest, or filelog.
82 If the manifest hasn't changed between two changesets, the changelog
83 entries for those changesets will point to the same revision of the
84 manifest. If a file that Mercurial tracks hasn't changed between two
85 changesets, the entry for that file in the two revisions of the
86 manifest will point to the same revision of its filelog.
88 \section{Safe, efficient storage}
90 The underpinnings of changelogs, manifests, and filelogs are provided
91 by a single structure called the \emph{revlog}.
93 \subsection{Efficient storage}
95 The revlog provides efficient storage of revisions using a
96 \emph{delta} mechanism. Instead of storing a complete copy of a file
97 for each revision, it stores the changes needed to transform an older
98 revision into the new revision. For many kinds of file data, these
99 deltas are typically a fraction of a percent of the size of a full
100 copy of a file.
102 Some obsolete revision control systems can only work with deltas of
103 text files. They must either store binary files as complete snapshots
104 or encoded into a text representation, both of which are wasteful
105 approaches. Mercurial can efficiently handle deltas of files with
106 arbitrary binary contents; it doesn't need to treat text as special.
108 \subsection{Safe operation}
110 Mercurial only ever \emph{appends} data to the end of a revlog file.
111 It never modifies a section of a file after it has written it. This
112 is both more robust and efficient than schemes that need to modify or
113 rewrite data.
115 In addition, Mercurial treats every write as part of a
116 \emph{transaction} that can span a number of files. A transaction is
117 \emph{atomic}: either the entire transaction succeeds and its effects
118 are all visible to readers in one go, or the whole thing is undone.
119 This guarantee of atomicity means that if you're running two copies of
120 Mercurial, where one is reading data and one is writing it, the reader
121 will never see a partially written result that might confuse it.
123 The fact that Mercurial only appends to files makes it easier to
124 provide this transactional guarantee. The easier it is to do stuff
125 like this, the more confident you should be that it's done correctly.
127 \subsection{Fast retrieval}
129 Mercurial cleverly avoids a pitfall common to all earlier
130 revision control systems: the problem of \emph{inefficient retrieval}.
131 Most revision control systems store the contents of a revision as an
132 incremental series of modifications against a ``snapshot''. To
133 reconstruct a specific revision, you must first read the snapshot, and
134 then every one of the revisions between the snapshot and your target
135 revision. The more history that a file accumulates, the more
136 revisions you must read, hence the longer it takes to reconstruct a
137 particular revision.
139 \begin{figure}[ht]
140 \centering
141 \grafix{snapshot}
142 \caption{Snapshot of a revlog, with incremental deltas}
143 \label{fig:concepts:snapshot}
144 \end{figure}
146 The innovation that Mercurial applies to this problem is simple but
147 effective. Once the cumulative amount of delta information stored
148 since the last snapshot exceeds a fixed threshold, it stores a new
149 snapshot (compressed, of course), instead of another delta. This
150 makes it possible to reconstruct \emph{any} revision of a file
151 quickly. This approach works so well that it has since been copied by
152 several other revision control systems.
154 Figure~\ref{fig:concepts:snapshot} illustrates the idea. In an entry
155 in a revlog's index file, Mercurial stores the range of entries from
156 the data file that it must read to reconstruct a particular revision.
158 \subsubsection{Aside: the influence of video compression}
160 If you're familiar with video compression or have ever watched a TV
161 feed through a digital cable or satellite service, you may know that
162 most video compression schemes store each frame of video as a delta
163 against its predecessor frame. In addition, these schemes use
164 ``lossy'' compression techniques to increase the compression ratio, so
165 visual errors accumulate over the course of a number of inter-frame
166 deltas.
168 Because it's possible for a video stream to ``drop out'' occasionally
169 due to signal glitches, and to limit the accumulation of artefacts
170 introduced by the lossy compression process, video encoders
171 periodically insert a complete frame (called a ``key frame'') into the
172 video stream; the next delta is generated against that frame. This
173 means that if the video signal gets interrupted, it will resume once
174 the next key frame is received. Also, the accumulation of encoding
175 errors restarts anew with each key frame.
177 \subsection{Strong integrity}
179 Along with delta or snapshot information, a revlog entry contains a
180 cryptographic hash of the data that it represents. This makes it
181 difficult to forge the contents of a revision, and easy to detect
182 accidental corruption. The hash that Mercurial uses is SHA-1, which
183 is 160 bits long. Although all revision data is hashed, the changeset
184 hashes that you see as an end user are from revisions of the
185 changelog. Manifest and file hashes are only used behind the scenes.
187 Mercurial checks these hashes when retrieving file revisions and when
188 pulling changes from a repository. If it encounters an integrity
189 problem, it will complain and stop whatever it's doing.
191 In addition to the effect it has on retrieval efficiency, Mercurial's
192 use of periodic snapshots makes it more robust against partial data
193 corruption. If a revlog becomes partly corrupted due to a hardware
194 error or system bug, it's often possible to reconstruct some or most
195 revisions from the uncorrupted sections of the revlog, both before and
196 after the corrupted section. This would not be possible with a
197 delta-only storage model.
199 \section{The working directory}
201 Mercurial's good ideas are not confined to the repository; it also
202 needs to manage the working directory. The \emph{dirstate} contains
203 Mercurial's knowledge of the working directory. This details which
204 revision(s) the working directory is updated to, and all files that
205 Mercurial is tracking in the working directory.
207 Because Mercurial doesn't force you to tell it when you're modifying a
208 file, it uses the dirstate to store some extra information so it can
209 determine efficiently whether you have modified a file. For each file
210 in the working directory, it stores the time that it last modified the
211 file itself, and the size of the file at that time.
213 When Mercurial is checking the states of files in the working
214 directory, it first checks a file's modification time. If that has
215 not changed, the file must not have been modified. If the file's size
216 has changed, the file must have been modified. If the modification
217 time has changed, but the size has not, only then does Mercurial need
218 to read the actual contents of the file to see if they've changed.
219 Storing these few extra pieces of information dramatically reduces the
220 amount of data that Mercurial needs to read, which yields large
221 performance improvements compared to other revision control systems.
223 \section{Other interesting design features}
225 In the sections above, I've tried to highlight some of the most
226 important aspects of Mercurial's design, to illustrate that it pays
227 careful attention to reliability and performance. However, the
228 attention to detail doesn't stop there. There are a number of other
229 aspects of Mercurial's construction that I personally find
230 interesting. I'll detail a few of them here, separate from the ``big
231 ticket'' items above, so that if you're interested, you can gain a
232 better idea of the amount of thinking that goes into a well-designed
233 system.
235 \subsection{Clever compression}
237 When appropriate, Mercurial will store both snapshots and deltas in
238 compressed form. It does this by always \emph{trying to} compress a
239 snapshot or delta, but only storing the compressed version if it's
240 smaller than the uncompressed version.
242 This means that Mercurial does ``the right thing'' when storing a file
243 whose native form is compressed, such as a \texttt{zip} archive or a
244 JPEG image. When these types of files are compressed a second time,
245 the resulting file is usually bigger than the once-compressed form,
246 and so Mercurial will store the plain \texttt{zip} or JPEG.
248 Deltas between revisions of a compressed file are usually larger than
249 snapshots of the file, and Mercurial again does ``the right thing'' in
250 these cases. It finds that such a delta exceeds the threshold at
251 which it should store a complete snapshot of the file, so it stores
252 the snapshot, again saving space compared to a naive delta-only
253 approach.
255 \subsubsection{Network recompression}
257 When storing revisions on disk, Mercurial uses the ``deflate''
258 compression algorithm (the same one used by the popular \texttt{zip}
259 archive format), which balances good speed with a respectable
260 compression ratio. However, when transmitting revision data over a
261 network connection, Mercurial uncompresses the compressed revision
262 data.
264 If the connection is over HTTP, Mercurial recompresses the entire
265 stream of data using a compression algorithm that gives a etter
266 compression ratio (the Burrows-Wheeler algorithm from the widely used
267 \texttt{bzip2} compression package). This combination of algorithm
268 and compression of the entire stream (instead of a revision at a time)
269 substantially reduces the number of bytes to be transferred, yielding
270 better network performance over almost all kinds of network.
272 (If the connection is over \command{ssh}, Mercurial \emph{doesn't}
273 recompress the stream, because \command{ssh} can already do this
274 itself.)
276 \subsection{Read/write ordering and atomicity}
278 Appending to files isn't the whole story when it comes to guaranteeing
279 that a reader won't see a partial write. If you recall
280 figure~\ref{fig:concepts:metadata}, revisions in the changelog point to
281 revisions in the manifest, and revisions in the manifest point to
282 revisions in filelogs. This hierarchy is deliberate.
284 A writer starts a transaction by writing filelog and manifest data,
285 and doesn't write any changelog data until those are finished. A
286 reader starts by reading changelog data, then manifest data, followed
287 by filelog data.
289 Since the writer has always finished writing filelog and manifest data
290 before it writes to the changelog, a reader will never read a pointer
291 to a partially written manifest revision from the changelog, and it will
292 never read a pointer to a partially written filelog revision from the
293 manifest.
295 \subsection{Concurrent access}
297 The read/write ordering and atomicity guarantees mean that Mercurial
298 never needs to \emph{lock} a repository when it's reading data, even
299 if the repository is being written to while the read is occurring.
300 This has a big effect on scalability; you can have an arbitrary number
301 of Mercurial processes safely reading data from a repository safely
302 all at once, no matter whether it's being written to or not.
304 The lockless nature of reading means that if you're sharing a
305 repository on a multi-user system, you don't need to grant other local
306 users permission to \emph{write} to your repository in order for them
307 to be able to clone it or pull changes from it; they only need
308 \emph{read} permission. (This is \emph{not} a common feature among
309 revision control systems, so don't take it for granted! Most require
310 readers to be able to lock a repository to access it safely, and this
311 requires write permission on at least one directory, which of course
312 makes for all kinds of nasty and annoying security and administrative
313 problems.)
315 Mercurial uses locks to ensure that only one process can write to a
316 repository at a time (the locking mechanism is safe even over
317 filesystems that are notoriously hostile to locking, such as NFS). If
318 a repository is locked, a writer will wait for a while to retry if the
319 repository becomes unlocked, but if the repository remains locked for
320 too long, the process attempting to write will time out after a while.
321 This means that your daily automated scripts won't get stuck forever
322 and pile up if a system crashes unnoticed, for example. (Yes, the
323 timeout is configurable, from zero to infinity.)
325 \subsubsection{Safe dirstate access}
327 As with revision data, Mercurial doesn't take a lock to read the
328 dirstate file; it does acquire a lock to write it. To avoid the
329 possibility of reading a partially written copy of the dirstate file,
330 Mercurial writes to a file with a unique name in the same directory as
331 the dirstate file, then renames the temporary file atomically to
332 \filename{dirstate}. The file named \filename{dirstate} is thus
333 guaranteed to be complete, not partially written.
335 \subsection{Avoiding seeks}
337 Critical to Mercurial's performance is the avoidance of seeks of the
338 disk head, since any seek is far more expensive than even a
339 comparatively large read operation.
341 This is why, for example, the dirstate is stored in a single file. If
342 there were a dirstate file per directory that Mercurial tracked, the
343 disk would seek once per directory. Instead, Mercurial reads the
344 entire single dirstate file in one step.
346 Mercurial also uses a ``copy on write'' scheme when cloning a
347 repository on local storage. Instead of copying every revlog file
348 from the old repository into the new repository, it makes a ``hard
349 link'', which is a shorthand way to say ``these two names point to the
350 same file''. When Mercurial is about to write to one of a revlog's
351 files, it checks to see if the number of names pointing at the file is
352 greater than one. If it is, more than one repository is using the
353 file, so Mercurial makes a new copy of the file that is private to
354 this repository.
356 A few revision control developers have pointed out that this idea of
357 making a complete private copy of a file is not very efficient in its
358 use of storage. While this is true, storage is cheap, and this method
359 gives the highest performance while deferring most book-keeping to the
360 operating system. An alternative scheme would most likely reduce
361 performance and increase the complexity of the software, each of which
362 is much more important to the ``feel'' of day-to-day use.
364 %%% Local Variables:
365 %%% mode: latex
366 %%% TeX-master: "00book"
367 %%% End: