How Arch Works

Gnu Arch

• Front Page
• On-line tutorial
• Mailing List
• Download
• Bug Tracker
• Gnu Project Page
• Community Wiki
• The supermirror

Support Services
(coming soon...)

• Per Incident
• Subscription
• Deployment Services
• Custom Development

Products
(coming soon...)

• Deluxe Distributions
• Documentation
• Schwag

Alternative/Regional Providers
(coming soon...)

This page contains a brief dissection of Arch -- a high-level description of how Arch works. The intention is to give technically savvy readers deeper insight into Arch by helping them to develop some intuitions about how Arch is implemented.

There are two parts and, depending on your interests, you might want to skip the first. These are:

• Performance Principles
• A Layered Architecture

Performance Principles

Before examining the details of the Arch implementation directly, it will be helpful to name a few performance principles that shape the overall design:

Minimize Server-side Computation

Arch allows multiple users to access a single archive over a network. Consequently, although it also supports serverless, local operation, Arch must support a client-server mode of operation.

We wish Arch to scale in number of concurrent users accessing an archive as far as possible. For example, if a popular project commits an important bug-fix, there may be thousands or tens of thousands of users who want to update their local sources after that commit.

Consequently, the design of Arch aims to

minimize server-side computation and i/o bandwidth consumption

The primary strategy for doing so is to

maximize the client-side share of unavoidable computation

Disk Space is Cheap

Most revision control systems in widespread use today were conceived or designed at least a decade and in some cases two decades ago. Even some contemporary designs follow design patterns that were established that long ago.

Systems designed with that older perspective place a very high premium on disk space. Although they work hard to be fast, nevertheless they are apt to make trade-offs that consume I/O bandwidth and CPU cycles in favor of consuming disk space. Even worse, these trade-offs often add to the implementation complexity of these systems.

These days, such trade-offs are already somewhat anachronistic and, within just a few years, such trade-offs will be completely absurd. Multiple gigabyte disks can be had for under $200USD and, before long, we'll have terabyte disks in such price ranges. Storage at those scales is more than ample for revision control purposes.

The lesson?

disk space is very cheap If the storage costs of an extravagant configuration of Arch work out to a few 10s of dollars per programmer, per year, our disk space usage is not excessive.

I/O Bandwidth is Expensive

Unfortunately, there is for the forseeable future still a sharp constraint about just how much disk space we can touch for a given arch operation: I/O bandwidth remains expensive, especially relative to disk capacity.

I/O Bandwidth costs are imposed at more than one layer. On-device cache space limits, seek times, transfer times, OS cache space limits, and CPU cache space limits, and main-memory speeds all constrain the utility of passing lots of data back and forth to disk.

I/O bandwidth is very expensive

Networks are Slow

A fast, local network connection can easily have lower latency and higher bandwidth than a local disk. Nevertheless, the expected case for most Arch operations over a network is that they pass over the Internet or a comparable network. Minimizing roundtrips and the quantity of data transfered is critical.

for Arch: network bandwidth is more expensive than disk bandwidth and each network roundtrip may as well be a punch in the face

A Layered Architecture

Tree Inventories

The lowest level concept in Arch is that of a tree inventory.

A tree inventory is a listing of all of the files and directories in a tree, with two fields per file or directory. These fields are:

1. a physical name -- the location of a file relative to the root of the source tree. For example: ./src/include/foo.h
2. an inventory id -- an identifier naming the file. This identifier remains constant even if the physical name of the file changes.

In other words, if a file is renamed, its physical name changes, but its inventory id remains the same. This allows Arch to recognize that a file has been renamed by comparing two versions of the physical name for a given inventory id. Here is a fragment of a directory listing showing physical names and inventory ids:

   physical name:               inventory id:

   links/Makefile.in            i_x9034AKLJn3
   links/make-links.sh.in       i_lk3n8908nNx
   links/remove-links.sh.in     i_lk3nn90lkjs
    

How are inventory ids associated with files? How does arch know what the inventory id of a given file is? Three mechanisms are provided:

1. inventory ids can be stored within a file For example, an id can be stored in a comment in a C source file. This mechanism is in some sense the most convenient, but is only suitable for text files, and only for text files that can tolerate such comments.
2. inventory ids can be stored in separate files The inventory id for a file foo can be stored in ./.arch-ids/foo.id. Special commands must be used to rename such a file (so that the .id file is renamed at the same time) but this mechanism can be used with any type of file.
3. inventory ids can be omitted Users can choose to not assign an id to a given file in which case its physical name serves double-duty as its inventory id. Arch can not recognize when such a file is renamed (since the inventory id will change in the process) but for some situtations, this is an acceptable trade-off for the convenience of not having to set-up ids.

Changesets

Traditional diff is most familiar as a way to show the differences between two versions of a single file. Given a command line option, diff can be recursively applied to all of the same-named files within a tree.

Traditional patch is familiar as a way to take the output of diff, a description of changes made to a file, and apply those changes to some different file.

The next layer of Arch takes diff and patch one step further by taking advantage of inventory ids. The arch commands mkpatch/dopatch (aka make-changeset/apply-changeset) produce and apply a whole-tree diff-like account of differences, taking into account renames, adds, and deletes. Additionally, these arch commands handle symbolic links, binary files, and file permissions.

For example, as we'll see below, when you commit a set of changes, that operation records the mkpatch output of your modified tree compared to the unmodified version you "checked out" from an archive.

Namespace and Archive

The combination of mkpatch/dopatch and inventory ids allows for a kind of "by hand" approach to revision control in the diff/patch style. Programmers could cooperate by exchanging and applying changesets created by mkpatch much as they can cooperate by creating and exchanging patch sets made by diff.

The next layer of arch, the namespace and archive layer, essentially just automates that by hand process. It provides a mechanism for naming (with globally unique, human-readable names) the changesets programmers create, and a mechanism for publishing changesets and retrieving published changesets.

Global Revision Names

The arch namespace is organized around the concept of a development line -- a sequence of revisions ordinarilly beginning with a complete tree called a base revision and proceding with a number of successive changeset revisions, each defined relative to its predecessort by a changeset.

For example, a programmer might initially import the source for an implementation of tar creating a base revision named:

	tar--mainline--1.0--base-0

After fixing a bug, the programmer can commit the changeset describing the bugfix. The changeset and the tree resulting from applying it are known as:

	tar--mainline--1.0--patch-1

Additional work and more commits would yield:

	tar--mainline--1.0--patch-1
	tar--mainline--1.0--patch-2
	tar--mainline--1.0--patch-3
        ... etc.

This development line is situated within a particular arch archive which itself has a name. Prefixing the archive name to a revision name yields a globally unique name for the revision:

	lord@emf.net--gnu-archive-2004/tar--mainline--1.0--patch-3

Tags are named in the same way and function comparably to base revisions. For example, instead of importing a new source tree to create

	tar--mainline--1.0--base-0

	tar--mainline--1.0--base-0 => tar--experimental--1.0--patch-4

Archive Storage

The most basic role of an arch archive, therefore, is to store base revisions, commit revisions, and tag revisions in a way that (1) associates them with their name; (2) allows programmers to query and retrieve revisions and the changesets and other data associated with them.

Internally to arch, the storage mechanism is isolated from the rest of the implementation by an abstraction barrier. Entirely new storage managers are easy to install.

In practice, only a very simple storage manager is used and experience has shown this stone-simple approach to work well. In particular, archives are stored as ordinary files: imported base revisions are stored as a compressed tar file of the entire source tree; changeset revisions created by commit are stored as a compressed tar file containing just the changeset; tag revisions are stored as a small text file containing the name of the tagged revision.

The stone-simple approach has some enourmous advantages and is one are where the performance principles enumerated above come into play. Some example advantages:

• A server is merely a generic file server The only capability needed for an arch server is the ability to create new files and directories and retrieve existing ones. Consequently, an unmodified FTP, SFTP, or WebDAV server is, already, an arch archive server. Nearly no computation takes place server-side and a given server can easily support very large numbers of concurrent connections.
• Network traffic is minimized Imports and commits ship to the server compressed tar files of just the essential data of the transition. Subsequent retrievals simply read that data back. As a result, basic operations require few round-trips and minimal bandwidth.
• Replication is easy New files are added to archives with every commit, tag, or import transaction, but old files are never removed or modified. Consequently, it is trivial to replicate and incrementally update read-only mirrors of any archive. Arch has a built-in facility for this and programs such as rsync can be configured to do the job more efficiently.

Archive Caching, Revision Libraries and Other Speedups

The archive storage layer has many advantages but it also creates a performance problem that needs to be solved:

Simple Archive Formats Can be Slow

Consider how, given just the archive storage mechanism described above, a particular revision can be retrieved. Let's suppose that we want to get a copy of the tree for:

	tar--mainline--1.0--patch-4
    

Absent any other mechanism, we would build that tree with the following steps:

1. retrieve the base revision -- fetch the compressed tar file of the base-0 revision from an archive and unpack it.
2. retrieve and apply the first changeset -- fetch the compressed tar file of the changeset for patch-1, unpack it, and apply the changeset to the base-0 tree. Now we have a patch-1 tree.
3. retrieve and apply successive changesets -- continue applying changesets until we lllreach the desired revision (patch-4).

That's conceptually simple, and it's a direct consequence of our choice of "dumb server" storage management, but it is problematic. For example, suppose that instead of wanting the patch-4 revision we wanted the patch-140 revision. Instead of having to apply four changesets to the base revision, we'd have to apply 140 -- which would be prohibitively expensive.

Worse, in the case of wanting the patch-140 revision, we may find ourselves violating some of our performance principles. After all, even compressed, those 140 changesets that we'll fetch from the server may turn out to be larger than just a complete copy of the patch-140 tree would be. By not having the server compute that complete tree, we may be trading network costs for server costs.

Arch solves these problems with three mechanisms: archive cached revisions, archive mirrors, and client-side revision libraries.

Archive Cached Revisions

One way to reduce the amount of changeset application and network bandwidth associated with building a revision is to apply our performance principle that disk space is very cheap.

Specifically, we augment the archive format to permit (user-directed) caching of pre-built revisions, stored as compressed tar files. Continuing the earlier example, a user may have asked that the revision patch-130 be cached. That means that in addition to containing a compressed tar file of the changeset that describes how patch-130 differs from patch-129 the archive will contain a compressed tar-file of a pre-built copy of patch-130.

Now, if a user asks for a copy of the patch-140 tree, rather than starting at base-0 then fetching and applying 140 changesets, arch will fetch the full-tree copy of patch-130 then fetch and apply only 10 changesets to produce a patch-140 tree.

In keeping with our goals of client-side computation and dumb servers, when an archive cached revision is created it is constructed on some client, bundled as a tar file, and stored on the server.

Which revisions should be archive cached? One rational, approximately time-and-bandwidth optimal policy would be to space cached revisions such that the sum of the sizes of changesets between any two cached revisions is about the same as the size as the tar file containing the cached revision. Spacing them further apart would lead to a situation where sometimes the total size of changesets fetched to build a revision exceeds what could have been fetched with denser caching. Spacing them closer together will cause arch to sometimes fetch a cached revision when it would have been faster to fetch several changesets instead. Note that applying this policy approximately doubles the size of an archive -- which is quite accessible since archives are relatively compact to begin with and, after all, disk space is very cheap.

Other caching policies make good sense in some situations, though. Therefore, we leave it to users to explicitly cache revisions -- a process that can trivially be automated to implement whatever policy a user chooses.

Archive Mirrors

A second technique for saving on network costs is to use archive mirrors. Arch contains a facility for constructing and incrementally updating local, read-only copies of remote archives. When such a mirror is used, each changeset or base revision from the remote archive is fetched exactly once and, thereafter, access to it is entirely local. In our example, this would still (by default) mean applying 140 changesets -- but at least those changesets would reside on a local disk.

Archive caching and archive mirroring interact in a favorable way. Although mirrors are generally read-only, users may archive-cache a revision in a mirror. For example, one reasonable set-up is to publish a heavily read archive on the Internet, but archive-cache nothing there. Instead, encourage users to mirror from that public archive rather than use it directly, and to archive-cache according to their needs in their local copies.

Revision Libraries

The final technique for speeding up arch operations is entirely a client-side optimization. As with archive mirrors and archive caching, it trades-off disk space for speed.

The technique provides for something called a revisision library. A revision library is a read-only collection of pre-built whole-tree copies of revisions, stored more or less as ordinary trees.

A special feature of revision libraries is that unmodified files are shared between revisions via hard-links. For example, suppose that a revision library contains patch-139 and we wish to add patch-140 to the library. The addition happens in two steps: First, a hard-linked copy of patch-139 is created. All of the files in this copy are shared with the original patch-139 -- they are the hard-links to the two files. Second, the changeset defining patch-140 is applied to the hard-linked copy. The changeset application process "breaks hard-links" for files it modifies. Thus, the end result is a patch-140 tree in which files that are unmodified since patch-139 are shared with the patch-139 tree via hard-links, and modified files are private to the patch-140 tree.

This is a reasonably space-efficient way to store many, many revisions in space which is a fraction of the sum of their individual sizes.

The revision library mechanism is designed to be configurable as a cache or memo. Revisions can be automatically added to a library, on demand, or they can be explicitly added. It is a trivial matter for users to implement a "pruning" policy to discard revisions that are no longer needed.

When a revision library is present, many arch operations become very, very fast. For example, suppose again that we want a patch-140 tree and that initially the revision library contains patch-139. Arch (suitably configured) will proceed by adding patch-140 to the library (by creating a hard-linked copy of 139 and applying one changeset to it) and then recursively copying the resulting tree from the library to the user's work area. If the library already contains patch-140, then only the recursive copy is necessary.

Often the tools that a user uses to work on their checked-out trees are well-behaved with respect to hard-links. Emacs and vi, for example, do not modify the files you edit --- they write fresh copies of those files containing your modifications and thus they break hard-links to those files.

Arch can take advantage of the hard-link-safety of common tools. When checking-out a tree, you can ask arch to not recursively copy the tree form a revision library but, instead, to make your working copy by hard-linking to the revision library. This turns out to be a blindingly fast way to check out a tree. (And, arch contains integrity checking features for revision libraries. Should your tools fail to be hard-link-safe after all, arch will notice and protect you from any resulting revision library corruption.)

Speedups Summarized

The basic archive storage model of arch is simple, space-efficient, and often but not always network- and time-efficient. In some cases, however, without additional mechanisms, it would lead to gross network- and time-inefficiencies.

We eliminate those gross inefficiences with three mechanisms, archive caching, archive mirroring, and revision libraries, which have in common that that they trade disk-space and client-side computation for better performance overall. A pleasant property of this approach is that it requires _no_ server-side computation and thus, excellent speeds can be achieved without sacrificing the scalability or arch in the slightest.

Patch Logs and Merging

We've seen so far how arch allows users to commit import, changeset, and tag revisions. We've seen that these are assigned globally unique names and examined how they are stored in archives. We've seen how revisions are retrieved from archives and looked at some of the speed-up mechanisms that exist to make retrieval fast.

Now we turn to the question of merging. Suppose, for example, that two users are each working on their own development line of a single project. Naturally, they may want to share work: each user will want to combine his changes with changes made by the other. How does arch handle this?

To understand the answer, we must first understand patch logs and then we can turn to history sensitive merging.

Patch Logs

Whenever a user creates any new revision he must provide a short description of the revision. The description, formatted similarly to an email message, contains a header that provides a brief summary of the revision, and a body that can contain details.

Arch maintains a special directory, called {arch} in the top level of each project tree. This directory contains the patch log entries that pertain to the tree.

For example, when a tree is first imported, the user writes a patch log entry and that is stored in a file under {arch}, indexed by the name of the revision created by the import. The tar bundle containing the imported tree contains that patch log file.

Similarly, when a user commits or tags a revision, the patch log entry for that new revision is treated like a newly added file -- it appears in the associated changeset.

This implies, for one thing, that a given revision contains patch log files for its ancestors in its development line. The tree for patch-140 contains patch log files for base-0, patch-1, .... through patch-140 itself.

When patch log files are added to a revision, arch adds additional, automatically computed headers. For example, one header names all newly added files in the revision. Another header reports what files have been deleted.

Conveniently, patch log files can be processed and summarized to produce a conventional ChangeLog file. In fact, arch has facilities to do so automatically.

History Sensitive Merging

Consider, then, what happens if a user wants to add to his tree the changes assocated with a revision made in a different development line. For example, suppose that I have checked out a copy of

	tar--mainline--1.0--patch-140

	tar--bugfixes--1.0--patch-2

Arch can accomplish this quite easily simply by fetching the changeset for the bugfix and applying it to my patch-140 tree. That changeset treats the patch log entry for the bugfix revision as a newly added file. Therefore, after applying the changeset, my (now modified) tree for

	tar--mainline--1.0--patch-140

	tar--bugfixes--1.0--patch-2

That's handy in and of itself. For example, if I don't remember whether the bug-fix changes have been applied to my tree, I can use arch to query the patch log files and look for a record of it having been applied.

It's also handy for smart merging. For example, in my mainline tree, I can ask arch:

	% tla whats-missing tla--bugfixes--1.0

	patch-1
        patch-3
        patch-4

Using the summary lines from log messages, arch can report:

	% tla --summary whats-missing tla--bugfixes--1.0
	patch-1
        	fix the help message
        patch-3
		fix buffer overflow (bug #238)
        patch-4
		correct exit status  (bug #14)

and a command such as:

	% tla whats-missing tla--bugfixes--1.0 | tla replay --list -

Merging isn't limited to just the changesets created by commit. Indeed, arch can compute the differences between any two revisions and apply those to my tree as a form of merging. Intelligently deciding which two revisions to compare is a tricky problem with no one solution -- arch provides a variety of solutions, most of which examine patch-logs to help with the decision process. This general mechanism is the basis for specific history-sensitive merge commands such as star-merge.

And the Rest is Easy

The above summarizes the essense of what could be dubbed core arch. Although many details have been omitted or glossed over, hopefully you now have some intuition about how arch works.

Many commands are built on top of the basic facilities outlined above. In all cases, they boil down to simple combinations of the above ideas: changeset computation and application, building revisions based on archive and revision library data, and so forth.