Mercurial_ The Definitive Guide - Bryan O'Sullivan [26]
Figure 4-2. Metadata relationships
As the illustration shows, there is not a “one to one” relationship between revisions in the changelog, manifest, or filelog. If a file that Mercurial tracks hasn’t changed between two changesets, the entry for that file in the two revisions of the manifest will point to the same revision of its filelog.[3]
* * *
[3] It is possible (though unusual) for the manifest to remain the same between two changesets, in which case the changelog entries for those changesets will point to the same revision of the manifest.
Safe, Efficient Storage
The underpinnings of changelogs, manifests, and filelogs are provided by a single structure called the revlog.
Efficient Storage
The revlog provides efficient storage of revisions using a delta mechanism. Instead of storing a complete copy of a file for each revision, it stores the changes needed to transform an older revision into the new revision. For many kinds of file data, these deltas are typically a fraction of a percent of the size of a full copy of a file.
Some obsolete revision control systems can only work with deltas of text files. They must either store binary files as complete snapshots or encoded into a text representation, both of which are wasteful approaches. Mercurial can efficiently handle deltas of files with arbitrary binary contents; it doesn’t need to treat text as special.
Safe Operation
Mercurial only ever appends data to the end of a revlog file. It never modifies a section of a file after it has written it. This is both more robust and more efficient than schemes that need to modify or rewrite data.
In addition, Mercurial treats every write as part of a transaction that can span a number of files. A transaction is atomic: either the entire transaction succeeds and all its effects are visible to readers in one go, or the whole thing is undone. This guarantee of atomicity means that if you’re running two copies of Mercurial, where one is reading data and one is writing it, the reader will never see a partially written result that might cause confusion.
The fact that Mercurial only appends to files makes it easier to provide this transactional guarantee. The easier it is to do stuff like this, the more confident you should be that it’s done correctly.
Fast Retrieval
Mercurial cleverly avoids a pitfall common to all earlier revision control systems: the problem of inefficient retrieval. Most revision control systems store the contents of a revision as an incremental series of modifications against a “snapshot.” (Some base the snapshot on the oldest revision, others on the newest.) To reconstruct a specific revision, you must first read the snapshot, and then every one of the revisions between the snapshot and your target revision. The more history that a file accumulates, the more revisions you must read, and hence the longer it takes to reconstruct a particular revision.
Figure 4-3. Snapshot of a revlog, with incremental deltas
The innovation that Mercurial applies to this problem is simple but effective. Once the cumulative amount of delta information stored since the last snapshot exceeds a fixed threshold, it stores a new snapshot (compressed, of course) instead of another delta. This makes it possible to reconstruct any revision of a file quickly. This approach works so well that it has since been copied by several other revision control systems.
Figure 4-3 illustrates the idea. In an entry in a revlog’s index file, Mercurial stores the range of entries from the data file that it must read to reconstruct a particular revision.
* * *
Aside: the influence of video compression
If you’re familiar with video compression or have ever watched a TV feed through a digital cable or satellite service, you may know that most video compression schemes store each frame of video as a delta against its predecessor frame.
Mercurial borrows this idea to make it possible