Mercurial stores lots of its data in append-only, intended-to-be-immutable data structures called revlogs. Each revlog is backed by a file on the filesystem. The main component of a revlog is a revision. When a new revision arrives, its content is compared against the previous revision in the file and a zlib-compressed delta/diff is generated. If the delta is smaller than the entry itself, the delta is appended to the revlog. If the compressed delta itself or the stream of deltas that must be applied to recreate the original text is larger than the source text, the compressed full content is appended to the revlog. In other words, Mercurial tries to maintain a balance between file size/growth rate and read times in terms of both I/O and CPU.

The changelog is a revlog that holds information about every changeset/commit in the repository. The manifest is a revlog that holds details about which files are present in every changeset. There exist a separate revlog for each file/path ever present in the repository. These are called filelogs.

When you commit a change touching a single file, Mercurial will append a revision to the changelog describing the commit, a revision to the manifest describing the set of files active in that specific commit, and a new revision to a filelog.

You can poke around your repository's revlogs by running some debug commands. For example:

# Show high-level information about the manifest revlog
$ hg debugrevlog -m

# Show details about each entry in the manifest revlog (this
# actually reads data from an index to the data revlog - pretend
# there aren't index files for now)
$ hg debugindex -m

# Dump the content of a single entry in the changelog.
$ hg debugdata -c 2

I'm generally a big fan of append-only data structures because I love the beneficial caching properties and linear I/O performance. Mercurial and the revlog can take advantage of these properties for some performance wins under key scenarios, especially server operation (pushing commits doesn't necessarily invalidate cached revlog entries, allowing the page cache to service many reads).

Edge cases and deficiencies

As with any system trying to solve a complex problem, the revlog storage format doesn't always work as well as intended.

Let's start by taking by looking at how revlogs do delta storage. I said earlier that revlogs try to store a compressed delta against the previous entry. Well, that previous entry is the previous physical revision in the file/revlog, not the parent revision. You see, entries/revisions in revlogs have a numeric index (0, 1, 2, 3, ...), a SHA-1 hash of their content, and a link to the logical parent of the entry. e.g. say you have two commits in your repo, one made after the other:

0:8ba995b74e18
1:9b2a99adc05e

The revlog has entries at indexes 0 and 1. They are also accessible by their hash/node values of 8ba995b74e18 and 9b2a99adc05e. The parent of 1 is 0. The entry for 0 is the full, compressed content of 0. The entry for 1 is likely a compressed delta from 0 to 1. As we commit, we keep appending new entries. These exist as compressed deltas until the sizes of 0..n is greater than n by itself. At that time, a compressed version of n is stored.

This model works great for linear histories, as changes from n to n+1 are usually small. Mercurial can store a very small delta for each entry. The world is good.

This model works great when entries in revlogs are small. By having small entries (and small changes), the number of deltas required to eclipse the size of a single entry remains small, in effect keeping the length of a delta chain in check. Limiting the length of delta chains is good because it keeps the cost of looking up a single revision's content low. If you have a delta chain of 1000, for example, Mercurial will need to read 1000 revlog entries and apply 1000 deltas to obtain the original value. That can get expensive computationally. Since reads are linear, I/O should remain in check. But you do need to scan a lot of bytes to read in all the deltas and you need to perform a lot of the same computations (such as zlib decompression).

Let's talk a little about where the revlog starts to break down.

First, there's the issue of multiple, interleaved branches in the revlog. Say we have a repository with many branches/heads. We alternate committing between all the heads. This can play havoc with the default revlog delta compression. Since revlogs compress against the previous physical entry in the revlog, if there is lots of alternating between branches and the contents of those branches diverges significantly, the deltas can grow quite large and full revisions will be stored with higher frequency. This means more storage space and more CPU tasked with resolving deltas (since deltas are larger). Although, CPU is kept in check since delta chains tend to be smaller since full revisions are stored with higher frequency.

Second, we have an issue with delta chain explosion of large entries with small turnover. If your base content is large and it isn't changing that much, it will take hundreds or even thousands of revisions before the sum of the delta sizes outgrows that of an entry. This means delta chains can be very long and Mercurial will have to spend a lot of CPU to resolve a single entry.

Third, revlogs are using zlib for compression. As many benchmarks have shown, zlib isn't the fastest or most efficient compression algorithm in the world. It's likely justified as a reasonable default. But alternatives exist. The choice of zlib has implications, especially when other factors (such as excessively long delta chains) come into play.

Let's talk about mitigation strategies.

True parent deltas

While I wasn't around for the original design decisions of revlogs, I'm guessing they were strongly influenced by the fact that sequential I/O on magnetic disks is much, much faster than random I/O. With SSDs and flash storage growing in popularity - a medium that offers random I/O commonly over 100 MB/s - this buys us the luxury of asking do revlogs need to be optimized for sequential I/O and how can revlogs change to take advantage of fast random I/O.

One of the ways revlogs can adapt to fast random I/O is to store the delta against the logical parent, not the physical. The delta chain will thus skip revisions in the revlog. e.g. the chain could be 1, 2, 5, 6, 10, not n, n+1, n+2, .... This would keep deltas small and would reduce the overall size of the revlog. Although, it would likely increase the length of delta chains, especially when dealing with non-linear histories.

It turns out Mercurial has a setting that enables this - format.generaldelta. To create a repository with this enabled, run:

$ hg --config format.generaldelta=true init path/to/repo

The revlogs in that repository with now have deltas computed against the logical parent!

To verify you are using general delta, look for generaldelta in the .hg/requires file. If it isn't there, you probably don't have generaldelta enabled. Please note that cloning a generaldelta repo won't necessarily give your repo generaldelta. You need to have the custom config option set on the client or the client will likely use the defaults.

On repositories with lots of interleaved heads, this can make a huge difference. As a pathalogical example, Mozilla's Try repository (where people push heads to trigger test/automation runs) has over 22,000 heads. The on-disk size of the repository is 3117 MB with the standard settings and 2139 MB with generaldelta! The bulk of this difference comes from the manifest revlog, which is 954 MB smaller with generaldelta.

Alternate compression format

Mercurial uses zlib for revlog compression by default. This is a safe choice. It's relatively fast and yields relatively good compression.

Since Mercurial is highly extensible, it's possible to plug in a custom compression format for revlogs. Facebook's lz4revlog extension will use lz4 for compression. lz4 is faster than zlib, but compression isn't as good. Repositories with lz4 are commonly ~1.5x larger. But CPU bound tasks can be significantly faster.

In theory, any compression format can be used. However, it's not trivially selectable in Mercurial (yet), so someone will need to provide an extension that implements your desired compression format.

Alternate storage backends

In theory, Mercurial revlogs can be backed by anything. This is the extensibility of Mercurial at work. There's just a Mercurial extension sitting between using SQL, S3, Cassandra, or any other storage backend for revlogs.

It's also possible to write custom revlog implementations that change the file layout for interesting scaling possibilities. For example, modern filesystems like ZFS and btrfs support block-level deduplication and transparent compression. If you had block-aligned revlog entries with deduplication enabled, servers could in theory only store each revision at most once. Another idea is to let the filesystem handle the compression. This would cause compression to occur in kernel space (rather than inside Python userspace). This may have beneficial performance properties. It may not. It may depend on the repository. These would be interesting experiments to conduct!

Caveat with alternate revlog implementations

Before you go experimenting with alternative revlog implementations, be forewarned that wall time performance for push and pull operations may suffer!

Currently, Mercurial isn't as smart as it could be when it comes to transferring bundles of changeset data between repositories. Let me explain.

When Mercurial transfers changeset data between repositories, it often uses an encoding format called a bundle. A bundle is effectively a custom archive format for revlog data. If you've ever used hg bundle or hg unbundle to transfer repository data, you've explicitly interacted with bundles. But what's lesser known is that the hg push and hg pull operations also transfer bundles. The only major difference is that they are created on the fly and their existence is hidden from view.

In theory, bundles can be encoded a number of different ways. The most common tunable is the compression format. Over the wire, bundles are zlib (or even uncompressed). If you run hg bundle, you'll likely produce a bzip2 bundle. (This is why hg unbundle can be slower than hg clone - the CPU time spent for bzip2 is much greater than for zlib.) But a problem with bundles as they exist today is that the format is rather static when it comes to what's transferred over the wire. Unless you've mucked about with settings, the client and server will send a zlib-compressed bundle using the physical revlog order. In other words, the bundle format is the Mercurial defaults.

If Mercurial were completely dumb, transferring bundles would involve 1) determining the full text of a revlog entry 2) compressing that entry into a bundle 3) sending that data to a peer 4) decompressing that entry 5) appending that entry to the appropriate revlog (which involves recompression). Fortunately, Mercurial is a bit smarter than that: Mercurial can detect when compressed bits in a bundle will match what is on disk and will avoid the unncessary compression operations.

Anyway, the current bundle transfer mechanism falls apart when there is a mismatch between client and server configurations or even when the server or client is using non-defaults. You can think of this as a revlog impedance mismatch. Essentially, when the client and server are operating with different or uncommon types of revlogs, Mercurial tends to default to the lowest common denominator, or zlib deltas against the physical parent. If, for example, a client wants to use generaldelta with a server employing defaults, the client will have to convert the server's deltas into generaldelta deltas. This requires a non-trivial amount of CPU and pull operations become slower. I believe the opposite is also true: generaldelta clients will emit generaldelta bundles, causing the server to recompute the deltas.

When it comes to custom revlog formats today, essentially nobody wins.

The good news is this will be fixed. There is an effort to improve the bundle format and wire protocols to make matters better. A little protocol negotiation can go a long way to make the situation a lot better. That said, there is still the underlying problem that some clients may want settings that differ from the server's. e.g. clients with SSDs likely want generaldelta because they don't need sequential I/O and SSD space is more expensive, so the smaller repository sizes achieved with generaldelta are appreciated. But a server operator may not want to force generaldelta on all clients because it would make clients on mechanical hard drives slower! The point is revlog impedance mismatch will occur and someone needs to spend the CPU cycles to rectify the matter. I suspect this will be pushed to clients since distributed CPU load is easier to deal with than centralized on the server. But, I wouldn't be surprised if Mercurial allowed server operators to configure the behavior. It's a hard problem. Time will tell.

In the mean time, just know that if you experiment with custom revlog settings, push and pull operations will likely be slower. You may not notice this on day-to-day operations. But on things like initial clone, you could experience a massive slow-down.

Here's some timings with mozilla-central with a Mercurial 1.9 server and client on the same SSD-backed multi-core machine:

• clone default settings - 4:25
• clone --uncompressed - 0:49
• clone from generaldelta - 14:11
• clone from generaldelta to generaldelta - 16:49
• clone from generaldelta --uncompressed - 0:50
• pull 2250 changesets, default from default - 6.7s
• pull 2250 changesets, default from generaldelta - 17.9s
• pull 2250 changesets, generaldelta from default - 28.5s
• pull 2250 changesets, generaldelta from generaldelta - 20.0s

As you can see, anything involving compression and generaldelta is much slower. Once bundle format 2 is fully implemented, I expect the situation to improve. Until then, know that you'll get a ~2.5-4x slowdown from using generaldelta. You'll have to measure other revlog formats for their impact.

In conclusion, Mercurial's revlog file format is an interesting and tunable data structure. It works pretty well for most repositories. But if you are the 1%, you might want to spend some time to investigate changing its default configuration.