bos@108: \chapter{Behind the scenes} jeffpc@56: \label{chap:concepts} jeffpc@56: bos@108: Unlike many revision control systems, the concepts upon which bos@108: Mercurial is built are simple enough that it's easy to understand how bos@108: the software really works. Knowing this certainly isn't necessary, bos@108: but I find it useful to have a ``mental model'' of what's going on. jeffpc@56: bos@109: This understanding gives me confidence that Mercurial has been bos@109: carefully designed to be both \emph{safe} and \emph{efficient}. And bos@111: just as importantly, if it's easy for me to retain a good idea of what bos@111: the software is doing when I perform a revision control task, I'm less bos@111: likely to be surprised by its behaviour. bos@109: bos@112: In this chapter, we'll initially cover the core concepts behind bos@112: Mercurial's design, then continue to discuss some of the interesting bos@112: details of its implementation. bos@112: bos@109: \section{Mercurial's historical record} bos@109: bos@109: \subsection{Tracking the history of a single file} jeffpc@56: bos@108: When Mercurial tracks modifications to a file, it stores the history bos@108: of that file in a metadata object called a \emph{filelog}. Each entry bos@108: in the filelog contains enough information to reconstruct one revision bos@108: of the file that is being tracked. Filelogs are stored as files in bos@108: the \sdirname{.hg/data} directory. A filelog contains two kinds of bos@108: information: revision data, and an index to help Mercurial to find a bos@108: revision efficiently. jeffpc@56: bos@109: A file that is large, or has a lot of history, has its filelog stored bos@109: in separate data (``\texttt{.d}'' suffix) and index (``\texttt{.i}'' bos@109: suffix) files. For small files without much history, the revision bos@109: data and index are combined in a single ``\texttt{.i}'' file. The bos@109: correspondence between a file in the working directory and the filelog bos@109: that tracks its history in the repository is illustrated in bos@109: figure~\ref{fig:concepts:filelog}. jeffpc@56: jeffpc@56: \begin{figure}[ht] bos@108: \centering bos@108: \grafix{filelog} bos@108: \caption{Relationships between files in working directory and bos@108: filelogs in repository} bos@108: \label{fig:concepts:filelog} jeffpc@56: \end{figure} jeffpc@56: bos@109: \subsection{Managing tracked files} bos@109: bos@109: Mercurial uses a structure called a \emph{manifest} to collect bos@109: together information about the files that it tracks. Each entry in bos@109: the manifest contains information about the files present in a single bos@109: changeset. An entry records which files are present in the changeset, bos@109: the revision of each file, and a few other pieces of file metadata. bos@109: bos@109: \subsection{Recording changeset information} bos@109: bos@109: The \emph{changelog} contains information about each changeset. Each bos@109: revision records who committed a change, the changeset comment, other bos@109: pieces of changeset-related information, and the revision of the bos@109: manifest to use. bos@109: bos@109: \subsection{Relationships between revisions} bos@109: bos@109: Within a changelog, a manifest, or a filelog, each revision stores a bos@109: pointer to its immediate parent (or to its two parents, if it's a bos@109: merge revision). As I mentioned above, there are also relationships bos@109: between revisions \emph{across} these structures, and they are bos@109: hierarchical in nature. bos@109: bos@109: For every changeset in a repository, there is exactly one revision bos@109: stored in the changelog. Each revision of the changelog contains a bos@109: pointer to a single revision of the manifest. A revision of the bos@109: manifest stores a pointer to a single revision of each filelog tracked bos@109: when that changeset was created. These relationships are illustrated bos@109: in figure~\ref{fig:concepts:metadata}. bos@109: bos@109: \begin{figure}[ht] bos@109: \centering bos@109: \grafix{metadata} bos@109: \caption{Metadata relationships} bos@109: \label{fig:concepts:metadata} bos@109: \end{figure} bos@109: bos@110: As the illustration shows, there is \emph{not} a ``one to one'' bos@110: relationship between revisions in the changelog, manifest, or filelog. bos@110: If the manifest hasn't changed between two changesets, the changelog bos@110: entries for those changesets will point to the same revision of the bos@110: manifest. If a file that Mercurial tracks hasn't changed between two bos@110: changesets, the entry for that file in the two revisions of the bos@110: manifest will point to the same revision of its filelog. bos@110: bos@110: \section{Safe, efficient storage} bos@109: bos@109: The underpinnings of changelogs, manifests, and filelogs are provided bos@109: by a single structure called the \emph{revlog}. bos@109: bos@109: \subsection{Efficient storage} bos@109: bos@109: The revlog provides efficient storage of revisions using a bos@109: \emph{delta} mechanism. Instead of storing a complete copy of a file bos@109: for each revision, it stores the changes needed to transform an older bos@109: revision into the new revision. For many kinds of file data, these bos@109: deltas are typically a fraction of a percent of the size of a full bos@109: copy of a file. bos@109: bos@109: Some obsolete revision control systems can only work with deltas of bos@109: text files. They must either store binary files as complete snapshots bos@109: or encoded into a text representation, both of which are wasteful bos@109: approaches. Mercurial can efficiently handle deltas of files with bos@109: arbitrary binary contents; it doesn't need to treat text as special. bos@109: bos@109: \subsection{Safe operation} bos@109: bos@109: Mercurial only ever \emph{appends} data to the end of a revlog file. bos@109: It never modifies a section of a file after it has written it. This bos@109: is both more robust and efficient than schemes that need to modify or bos@109: rewrite data. bos@109: bos@109: In addition, Mercurial treats every write as part of a bos@109: \emph{transaction} that can span a number of files. A transaction is bos@109: \emph{atomic}: either the entire transaction succeeds and its effects bos@109: are all visible to readers in one go, or the whole thing is undone. bos@109: This guarantee of atomicity means that if you're running two copies of bos@109: Mercurial, where one is reading data and one is writing it, the reader bos@109: will never see a partially written result that might confuse it. bos@109: bos@109: The fact that Mercurial only appends to files makes it easier to bos@109: provide this transactional guarantee. The easier it is to do stuff bos@109: like this, the more confident you should be that it's done correctly. bos@109: bos@109: \subsection{Fast retrieval} bos@109: bos@109: Mercurial cleverly avoids a pitfall common to all earlier bos@109: revision control systems: the problem of \emph{inefficient retrieval}. bos@109: Most revision control systems store the contents of a revision as an bos@109: incremental series of modifications against a ``snapshot''. To bos@109: reconstruct a specific revision, you must first read the snapshot, and bos@109: then every one of the revisions between the snapshot and your target bos@109: revision. The more history that a file accumulates, the more bos@109: revisions you must read, hence the longer it takes to reconstruct a bos@109: particular revision. bos@109: bos@110: \begin{figure}[ht] bos@110: \centering bos@110: \grafix{snapshot} bos@110: \caption{Snapshot of a revlog, with incremental deltas} bos@110: \label{fig:concepts:snapshot} bos@110: \end{figure} bos@110: bos@109: The innovation that Mercurial applies to this problem is simple but bos@109: effective. Once the cumulative amount of delta information stored bos@109: since the last snapshot exceeds a fixed threshold, it stores a new bos@109: snapshot (compressed, of course), instead of another delta. This bos@109: makes it possible to reconstruct \emph{any} revision of a file bos@110: quickly. This approach works so well that it has since been copied by bos@110: several other revision control systems. bos@110: bos@110: Figure~\ref{fig:concepts:snapshot} illustrates the idea. In an entry bos@110: in a revlog's index file, Mercurial stores the range of entries from bos@110: the data file that it must read to reconstruct a particular revision. bos@109: bos@109: \subsubsection{Aside: the influence of video compression} bos@109: bos@109: If you're familiar with video compression or have ever watched a TV bos@109: feed through a digital cable or satellite service, you may know that bos@109: most video compression schemes store each frame of video as a delta bos@109: against its predecessor frame. In addition, these schemes use bos@109: ``lossy'' compression techniques to increase the compression ratio, so bos@109: visual errors accumulate over the course of a number of inter-frame bos@109: deltas. bos@109: bos@109: Because it's possible for a video stream to ``drop out'' occasionally bos@109: due to signal glitches, and to limit the accumulation of artefacts bos@109: introduced by the lossy compression process, video encoders bos@109: periodically insert a complete frame (called a ``key frame'') into the bos@109: video stream; the next delta is generated against that frame. This bos@109: means that if the video signal gets interrupted, it will resume once bos@109: the next key frame is received. Also, the accumulation of encoding bos@109: errors restarts anew with each key frame. bos@109: bos@112: \subsection{Identification and strong integrity} bos@109: bos@109: Along with delta or snapshot information, a revlog entry contains a bos@109: cryptographic hash of the data that it represents. This makes it bos@109: difficult to forge the contents of a revision, and easy to detect bos@112: accidental corruption. bos@112: bos@112: Hashes provide more than a mere check against corruption; they are bos@112: used as the identifiers for revisions. The changeset identification bos@111: hashes that you see as an end user are from revisions of the bos@112: changelog. Although filelogs and the manifest also use hashes, bos@112: Mercurial only uses these behind the scenes. bos@112: bos@112: Mercurial verifies that hashes are correct when it retrieves file bos@112: revisions and when it pulls changes from another repository. If it bos@112: encounters an integrity problem, it will complain and stop whatever bos@112: it's doing. bos@109: bos@109: In addition to the effect it has on retrieval efficiency, Mercurial's bos@109: use of periodic snapshots makes it more robust against partial data bos@109: corruption. If a revlog becomes partly corrupted due to a hardware bos@109: error or system bug, it's often possible to reconstruct some or most bos@109: revisions from the uncorrupted sections of the revlog, both before and bos@109: after the corrupted section. This would not be possible with a bos@109: delta-only storage model. bos@109: bos@110: \section{The working directory} bos@110: bos@110: Mercurial's good ideas are not confined to the repository; it also bos@110: needs to manage the working directory. The \emph{dirstate} contains bos@110: Mercurial's knowledge of the working directory. This details which bos@110: revision(s) the working directory is updated to, and all files that bos@110: Mercurial is tracking in the working directory. bos@110: bos@110: Because Mercurial doesn't force you to tell it when you're modifying a bos@110: file, it uses the dirstate to store some extra information so it can bos@110: determine efficiently whether you have modified a file. For each file bos@110: in the working directory, it stores the time that it last modified the bos@110: file itself, and the size of the file at that time. bos@110: bos@110: When Mercurial is checking the states of files in the working bos@110: directory, it first checks a file's modification time. If that has bos@110: not changed, the file must not have been modified. If the file's size bos@110: has changed, the file must have been modified. If the modification bos@110: time has changed, but the size has not, only then does Mercurial need bos@110: to read the actual contents of the file to see if they've changed. bos@110: Storing these few extra pieces of information dramatically reduces the bos@110: amount of data that Mercurial needs to read, which yields large bos@110: performance improvements compared to other revision control systems. bos@110: bos@112: \section{Revision history, branching, bos@112: and merging} bos@112: bos@112: Every entry in a Mercurial revlog knows the identity of its immediate bos@112: ancestor revision, usually referred to as its \emph{parent}. In fact, bos@112: a revision contains room for not one parent, but two. Mercurial uses bos@112: a special hash, called the ``null ID'', to represent the idea ``there bos@112: is no parent here''. This hash is simply a string of zeroes. bos@112: bos@112: In figure~\ref{fig:concepts:revlog}, you can see an example of the bos@112: conceptual structure of a revlog. Filelogs, manifests, and changelogs bos@112: all have this same structure; they differ only in the kind of data bos@112: stored in each delta or snapshot. bos@112: bos@112: The first revision in a revlog (at the bottom of the image) has the bos@112: null ID in both of its parent slots. For a ``normal'' revision, its bos@112: first parent slot contains the ID of its parent revision, and its bos@112: second contains the null ID, indicating that the revision has only one bos@112: real parent. Any two revisions that have the same parent ID are bos@112: branches. A revision that represents a merge between branches has two bos@112: normal revision IDs in its parent slots. bos@112: bos@112: \begin{figure}[ht] bos@112: \centering bos@112: \grafix{revlog} bos@112: \caption{} bos@112: \label{fig:concepts:revlog} bos@112: \end{figure} bos@112: bos@110: \section{Other interesting design features} bos@110: bos@110: In the sections above, I've tried to highlight some of the most bos@110: important aspects of Mercurial's design, to illustrate that it pays bos@110: careful attention to reliability and performance. However, the bos@110: attention to detail doesn't stop there. There are a number of other bos@110: aspects of Mercurial's construction that I personally find bos@110: interesting. I'll detail a few of them here, separate from the ``big bos@110: ticket'' items above, so that if you're interested, you can gain a bos@110: better idea of the amount of thinking that goes into a well-designed bos@110: system. bos@110: bos@110: \subsection{Clever compression} bos@110: bos@110: When appropriate, Mercurial will store both snapshots and deltas in bos@110: compressed form. It does this by always \emph{trying to} compress a bos@110: snapshot or delta, but only storing the compressed version if it's bos@110: smaller than the uncompressed version. bos@110: bos@110: This means that Mercurial does ``the right thing'' when storing a file bos@110: whose native form is compressed, such as a \texttt{zip} archive or a bos@110: JPEG image. When these types of files are compressed a second time, bos@110: the resulting file is usually bigger than the once-compressed form, bos@110: and so Mercurial will store the plain \texttt{zip} or JPEG. bos@110: bos@110: Deltas between revisions of a compressed file are usually larger than bos@110: snapshots of the file, and Mercurial again does ``the right thing'' in bos@110: these cases. It finds that such a delta exceeds the threshold at bos@110: which it should store a complete snapshot of the file, so it stores bos@110: the snapshot, again saving space compared to a naive delta-only bos@110: approach. bos@110: bos@110: \subsubsection{Network recompression} bos@110: bos@110: When storing revisions on disk, Mercurial uses the ``deflate'' bos@110: compression algorithm (the same one used by the popular \texttt{zip} bos@110: archive format), which balances good speed with a respectable bos@110: compression ratio. However, when transmitting revision data over a bos@110: network connection, Mercurial uncompresses the compressed revision bos@110: data. bos@110: bos@110: If the connection is over HTTP, Mercurial recompresses the entire bos@110: stream of data using a compression algorithm that gives a etter bos@110: compression ratio (the Burrows-Wheeler algorithm from the widely used bos@110: \texttt{bzip2} compression package). This combination of algorithm bos@110: and compression of the entire stream (instead of a revision at a time) bos@110: substantially reduces the number of bytes to be transferred, yielding bos@110: better network performance over almost all kinds of network. bos@110: bos@110: (If the connection is over \command{ssh}, Mercurial \emph{doesn't} bos@110: recompress the stream, because \command{ssh} can already do this bos@110: itself.) bos@110: bos@109: \subsection{Read/write ordering and atomicity} bos@109: bos@109: Appending to files isn't the whole story when it comes to guaranteeing bos@109: that a reader won't see a partial write. If you recall bos@109: figure~\ref{fig:concepts:metadata}, revisions in the changelog point to bos@109: revisions in the manifest, and revisions in the manifest point to bos@109: revisions in filelogs. This hierarchy is deliberate. bos@109: bos@109: A writer starts a transaction by writing filelog and manifest data, bos@109: and doesn't write any changelog data until those are finished. A bos@109: reader starts by reading changelog data, then manifest data, followed bos@109: by filelog data. bos@109: bos@109: Since the writer has always finished writing filelog and manifest data bos@109: before it writes to the changelog, a reader will never read a pointer bos@109: to a partially written manifest revision from the changelog, and it will bos@109: never read a pointer to a partially written filelog revision from the bos@109: manifest. bos@109: bos@109: \subsection{Concurrent access} bos@109: bos@109: The read/write ordering and atomicity guarantees mean that Mercurial bos@109: never needs to \emph{lock} a repository when it's reading data, even bos@109: if the repository is being written to while the read is occurring. bos@109: This has a big effect on scalability; you can have an arbitrary number bos@109: of Mercurial processes safely reading data from a repository safely bos@109: all at once, no matter whether it's being written to or not. bos@109: bos@109: The lockless nature of reading means that if you're sharing a bos@109: repository on a multi-user system, you don't need to grant other local bos@109: users permission to \emph{write} to your repository in order for them bos@109: to be able to clone it or pull changes from it; they only need bos@109: \emph{read} permission. (This is \emph{not} a common feature among bos@109: revision control systems, so don't take it for granted! Most require bos@109: readers to be able to lock a repository to access it safely, and this bos@109: requires write permission on at least one directory, which of course bos@109: makes for all kinds of nasty and annoying security and administrative bos@109: problems.) bos@109: bos@110: Mercurial uses locks to ensure that only one process can write to a bos@110: repository at a time (the locking mechanism is safe even over bos@110: filesystems that are notoriously hostile to locking, such as NFS). If bos@110: a repository is locked, a writer will wait for a while to retry if the bos@110: repository becomes unlocked, but if the repository remains locked for bos@110: too long, the process attempting to write will time out after a while. bos@110: This means that your daily automated scripts won't get stuck forever bos@110: and pile up if a system crashes unnoticed, for example. (Yes, the bos@110: timeout is configurable, from zero to infinity.) bos@110: bos@110: \subsubsection{Safe dirstate access} bos@110: bos@110: As with revision data, Mercurial doesn't take a lock to read the bos@110: dirstate file; it does acquire a lock to write it. To avoid the bos@110: possibility of reading a partially written copy of the dirstate file, bos@110: Mercurial writes to a file with a unique name in the same directory as bos@110: the dirstate file, then renames the temporary file atomically to bos@110: \filename{dirstate}. The file named \filename{dirstate} is thus bos@110: guaranteed to be complete, not partially written. bos@109: bos@111: \subsection{Avoiding seeks} bos@111: bos@111: Critical to Mercurial's performance is the avoidance of seeks of the bos@111: disk head, since any seek is far more expensive than even a bos@111: comparatively large read operation. bos@111: bos@111: This is why, for example, the dirstate is stored in a single file. If bos@111: there were a dirstate file per directory that Mercurial tracked, the bos@111: disk would seek once per directory. Instead, Mercurial reads the bos@111: entire single dirstate file in one step. bos@111: bos@111: Mercurial also uses a ``copy on write'' scheme when cloning a bos@111: repository on local storage. Instead of copying every revlog file bos@111: from the old repository into the new repository, it makes a ``hard bos@111: link'', which is a shorthand way to say ``these two names point to the bos@111: same file''. When Mercurial is about to write to one of a revlog's bos@111: files, it checks to see if the number of names pointing at the file is bos@111: greater than one. If it is, more than one repository is using the bos@111: file, so Mercurial makes a new copy of the file that is private to bos@111: this repository. bos@111: bos@111: A few revision control developers have pointed out that this idea of bos@111: making a complete private copy of a file is not very efficient in its bos@111: use of storage. While this is true, storage is cheap, and this method bos@111: gives the highest performance while deferring most book-keeping to the bos@111: operating system. An alternative scheme would most likely reduce bos@111: performance and increase the complexity of the software, each of which bos@111: is much more important to the ``feel'' of day-to-day use. bos@109: jeffpc@56: %%% Local Variables: jeffpc@56: %%% mode: latex jeffpc@56: %%% TeX-master: "00book" jeffpc@56: %%% End: