hgbook
view en/concepts.tex @ 109:1b67dc96f27a
Snapshot of concepts chapter.
| author | Bryan O'Sullivan <bos@serpentine.com> |
|---|---|
| date | Fri Nov 10 12:42:00 2006 -0800 (2006-11-10) |
| parents | e0b961975c5e |
| children | 75c076c7a374 |
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 Note that there is not a ``one to one'' relationship between revisions
81 in these different metadata files. If the manifest hasn't changed
82 between two changesets, their changelog entries will point to the same
83 revision of the manifest. If a file that Mercurial tracks hasn't
84 changed between two changesets, the entry for that file in the two
85 revisions of the manifest will point to the same revision of its
86 filelog.
88 \section{An efficient, unified, safe storage mechanism}
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 The innovation that Mercurial applies to this problem is simple but
140 effective. Once the cumulative amount of delta information stored
141 since the last snapshot exceeds a fixed threshold, it stores a new
142 snapshot (compressed, of course), instead of another delta. This
143 makes it possible to reconstruct \emph{any} revision of a file
144 quickly. This approach works so well that it has subsequently been
145 copied by several other revision control systems.
147 \subsubsection{Aside: the influence of video compression}
149 If you're familiar with video compression or have ever watched a TV
150 feed through a digital cable or satellite service, you may know that
151 most video compression schemes store each frame of video as a delta
152 against its predecessor frame. In addition, these schemes use
153 ``lossy'' compression techniques to increase the compression ratio, so
154 visual errors accumulate over the course of a number of inter-frame
155 deltas.
157 Because it's possible for a video stream to ``drop out'' occasionally
158 due to signal glitches, and to limit the accumulation of artefacts
159 introduced by the lossy compression process, video encoders
160 periodically insert a complete frame (called a ``key frame'') into the
161 video stream; the next delta is generated against that frame. This
162 means that if the video signal gets interrupted, it will resume once
163 the next key frame is received. Also, the accumulation of encoding
164 errors restarts anew with each key frame.
166 \subsection{Clever compression}
168 When appropriate, Mercurial will store both snapshots and deltas in
169 compressed form. It does this by always \emph{trying to} compress a
170 snapshot or delta, but only storing the compressed version if it's
171 smaller than the uncompressed version.
173 This means that Mercurial does ``the right thing'' when storing a file
174 whose native form is compressed, such as a \texttt{zip} archive or a
175 JPEG image. When these types of files are compressed a second time,
176 the resulting file is usually bigger than the once-compressed form,
177 and so Mercurial will store the plain \texttt{zip} or JPEG.
179 Deltas between revisions of a compressed file are usually larger than
180 snapshots of the file, and Mercurial again does ``the right thing'' in
181 these cases. It finds that such a delta exceeds the threshold at
182 which it should store a complete snapshot of the file, so it stores
183 the snapshot, again saving space compared to a naive delta-only
184 approach.
186 \subsection{Strong integrity}
188 Along with delta or snapshot information, a revlog entry contains a
189 cryptographic hash of the data that it represents. This makes it
190 difficult to forge the contents of a revision, and easy to detect
191 accidental corruption.
193 Mercurial checks these hashes when retrieving file revisions and when
194 pulling changes from a repository. If it encounters an integrity
195 problem, it will complain and stop whatever it's doing.
197 In addition to the effect it has on retrieval efficiency, Mercurial's
198 use of periodic snapshots makes it more robust against partial data
199 corruption. If a revlog becomes partly corrupted due to a hardware
200 error or system bug, it's often possible to reconstruct some or most
201 revisions from the uncorrupted sections of the revlog, both before and
202 after the corrupted section. This would not be possible with a
203 delta-only storage model.
205 \subsection{Read/write ordering and atomicity}
207 Appending to files isn't the whole story when it comes to guaranteeing
208 that a reader won't see a partial write. If you recall
209 figure~\ref{fig:concepts:metadata}, revisions in the changelog point to
210 revisions in the manifest, and revisions in the manifest point to
211 revisions in filelogs. This hierarchy is deliberate.
213 A writer starts a transaction by writing filelog and manifest data,
214 and doesn't write any changelog data until those are finished. A
215 reader starts by reading changelog data, then manifest data, followed
216 by filelog data.
218 Since the writer has always finished writing filelog and manifest data
219 before it writes to the changelog, a reader will never read a pointer
220 to a partially written manifest revision from the changelog, and it will
221 never read a pointer to a partially written filelog revision from the
222 manifest.
224 \subsection{Concurrent access}
226 The read/write ordering and atomicity guarantees mean that Mercurial
227 never needs to \emph{lock} a repository when it's reading data, even
228 if the repository is being written to while the read is occurring.
229 This has a big effect on scalability; you can have an arbitrary number
230 of Mercurial processes safely reading data from a repository safely
231 all at once, no matter whether it's being written to or not.
233 The lockless nature of reading means that if you're sharing a
234 repository on a multi-user system, you don't need to grant other local
235 users permission to \emph{write} to your repository in order for them
236 to be able to clone it or pull changes from it; they only need
237 \emph{read} permission. (This is \emph{not} a common feature among
238 revision control systems, so don't take it for granted! Most require
239 readers to be able to lock a repository to access it safely, and this
240 requires write permission on at least one directory, which of course
241 makes for all kinds of nasty and annoying security and administrative
242 problems.)
244 Mercurial uses a locking mechanism to ensure that only one process can
245 write to a repository at a time. This locking mechanism is safe even
246 over filesystems that are notoriously unsafe for locking, such as NFS.
247 If a repository is locked, a writer will wait for a while to retry if
248 the repository becomes unlocked, but if the repository remains locked
249 for too long, the process attempting to write will time out after a
250 while. This means that your daily automated scripts won't get stuck
251 forever and pile up if a system crashes unnoticed, for example. (Yes,
252 the timeout is configurable, from zero to infinity.)
256 %%% Local Variables:
257 %%% mode: latex
258 %%% TeX-master: "00book"
259 %%% End: