hgbook
view en/concepts.tex @ 110:75c076c7a374
More concepts stuff.
| author | Bryan O'Sullivan <bos@serpentine.com> |
|---|---|
| date | Fri Nov 10 15:09:49 2006 -0800 (2006-11-10) |
| parents | 1b67dc96f27a |
| children | 34b8b7a15ea1 |
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 I have a good idea what the software is doing
12 when I perform a revision control task, I'm less likely to be
13 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.
184 Mercurial checks these hashes when retrieving file revisions and when
185 pulling changes from a repository. If it encounters an integrity
186 problem, it will complain and stop whatever it's doing.
188 In addition to the effect it has on retrieval efficiency, Mercurial's
189 use of periodic snapshots makes it more robust against partial data
190 corruption. If a revlog becomes partly corrupted due to a hardware
191 error or system bug, it's often possible to reconstruct some or most
192 revisions from the uncorrupted sections of the revlog, both before and
193 after the corrupted section. This would not be possible with a
194 delta-only storage model.
196 \section{The working directory}
198 Mercurial's good ideas are not confined to the repository; it also
199 needs to manage the working directory. The \emph{dirstate} contains
200 Mercurial's knowledge of the working directory. This details which
201 revision(s) the working directory is updated to, and all files that
202 Mercurial is tracking in the working directory.
204 Because Mercurial doesn't force you to tell it when you're modifying a
205 file, it uses the dirstate to store some extra information so it can
206 determine efficiently whether you have modified a file. For each file
207 in the working directory, it stores the time that it last modified the
208 file itself, and the size of the file at that time.
210 When Mercurial is checking the states of files in the working
211 directory, it first checks a file's modification time. If that has
212 not changed, the file must not have been modified. If the file's size
213 has changed, the file must have been modified. If the modification
214 time has changed, but the size has not, only then does Mercurial need
215 to read the actual contents of the file to see if they've changed.
216 Storing these few extra pieces of information dramatically reduces the
217 amount of data that Mercurial needs to read, which yields large
218 performance improvements compared to other revision control systems.
220 \section{Other interesting design features}
222 In the sections above, I've tried to highlight some of the most
223 important aspects of Mercurial's design, to illustrate that it pays
224 careful attention to reliability and performance. However, the
225 attention to detail doesn't stop there. There are a number of other
226 aspects of Mercurial's construction that I personally find
227 interesting. I'll detail a few of them here, separate from the ``big
228 ticket'' items above, so that if you're interested, you can gain a
229 better idea of the amount of thinking that goes into a well-designed
230 system.
232 \subsection{Clever compression}
234 When appropriate, Mercurial will store both snapshots and deltas in
235 compressed form. It does this by always \emph{trying to} compress a
236 snapshot or delta, but only storing the compressed version if it's
237 smaller than the uncompressed version.
239 This means that Mercurial does ``the right thing'' when storing a file
240 whose native form is compressed, such as a \texttt{zip} archive or a
241 JPEG image. When these types of files are compressed a second time,
242 the resulting file is usually bigger than the once-compressed form,
243 and so Mercurial will store the plain \texttt{zip} or JPEG.
245 Deltas between revisions of a compressed file are usually larger than
246 snapshots of the file, and Mercurial again does ``the right thing'' in
247 these cases. It finds that such a delta exceeds the threshold at
248 which it should store a complete snapshot of the file, so it stores
249 the snapshot, again saving space compared to a naive delta-only
250 approach.
252 \subsubsection{Network recompression}
254 When storing revisions on disk, Mercurial uses the ``deflate''
255 compression algorithm (the same one used by the popular \texttt{zip}
256 archive format), which balances good speed with a respectable
257 compression ratio. However, when transmitting revision data over a
258 network connection, Mercurial uncompresses the compressed revision
259 data.
261 If the connection is over HTTP, Mercurial recompresses the entire
262 stream of data using a compression algorithm that gives a etter
263 compression ratio (the Burrows-Wheeler algorithm from the widely used
264 \texttt{bzip2} compression package). This combination of algorithm
265 and compression of the entire stream (instead of a revision at a time)
266 substantially reduces the number of bytes to be transferred, yielding
267 better network performance over almost all kinds of network.
269 (If the connection is over \command{ssh}, Mercurial \emph{doesn't}
270 recompress the stream, because \command{ssh} can already do this
271 itself.)
273 \subsection{Read/write ordering and atomicity}
275 Appending to files isn't the whole story when it comes to guaranteeing
276 that a reader won't see a partial write. If you recall
277 figure~\ref{fig:concepts:metadata}, revisions in the changelog point to
278 revisions in the manifest, and revisions in the manifest point to
279 revisions in filelogs. This hierarchy is deliberate.
281 A writer starts a transaction by writing filelog and manifest data,
282 and doesn't write any changelog data until those are finished. A
283 reader starts by reading changelog data, then manifest data, followed
284 by filelog data.
286 Since the writer has always finished writing filelog and manifest data
287 before it writes to the changelog, a reader will never read a pointer
288 to a partially written manifest revision from the changelog, and it will
289 never read a pointer to a partially written filelog revision from the
290 manifest.
292 \subsection{Concurrent access}
294 The read/write ordering and atomicity guarantees mean that Mercurial
295 never needs to \emph{lock} a repository when it's reading data, even
296 if the repository is being written to while the read is occurring.
297 This has a big effect on scalability; you can have an arbitrary number
298 of Mercurial processes safely reading data from a repository safely
299 all at once, no matter whether it's being written to or not.
301 The lockless nature of reading means that if you're sharing a
302 repository on a multi-user system, you don't need to grant other local
303 users permission to \emph{write} to your repository in order for them
304 to be able to clone it or pull changes from it; they only need
305 \emph{read} permission. (This is \emph{not} a common feature among
306 revision control systems, so don't take it for granted! Most require
307 readers to be able to lock a repository to access it safely, and this
308 requires write permission on at least one directory, which of course
309 makes for all kinds of nasty and annoying security and administrative
310 problems.)
312 Mercurial uses locks to ensure that only one process can write to a
313 repository at a time (the locking mechanism is safe even over
314 filesystems that are notoriously hostile to locking, such as NFS). If
315 a repository is locked, a writer will wait for a while to retry if the
316 repository becomes unlocked, but if the repository remains locked for
317 too long, the process attempting to write will time out after a while.
318 This means that your daily automated scripts won't get stuck forever
319 and pile up if a system crashes unnoticed, for example. (Yes, the
320 timeout is configurable, from zero to infinity.)
322 \subsubsection{Safe dirstate access}
324 As with revision data, Mercurial doesn't take a lock to read the
325 dirstate file; it does acquire a lock to write it. To avoid the
326 possibility of reading a partially written copy of the dirstate file,
327 Mercurial writes to a file with a unique name in the same directory as
328 the dirstate file, then renames the temporary file atomically to
329 \filename{dirstate}. The file named \filename{dirstate} is thus
330 guaranteed to be complete, not partially written.
334 %%% Local Variables:
335 %%% mode: latex
336 %%% TeX-master: "00book"
337 %%% End: