hgbook

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