Source Code Control Before Merging: RCS, CVS and the Locking Model

The Revision Control System, written by Walter Tichy at Purdue in 1982, stores a file as a chain of deltas in a single archive file with a ,v suffix. CVS, built on top of RCS, added a repository of directories and a network protocol. Together they defined what source control meant for roughly two decades, and the model they established carried an assumption that turned out to be the source of nearly every later problem: that a repository’s job is to store versions, and that combining versions is a separate, optional activity.

Delta chains and why the latest revision was slow

The RCS file format is a small piece of engineering that explains a large amount of downstream behaviour. The archive begins with a header naming the head revision and a description, then a set of administrative records, then the revision tree itself. Each revision is stored as a delta against its parent, encoded as a list of line ranges plus literal text for the changed lines. The delta is textual and line-oriented; the diff algorithm supplies the ranges.

Two choices here matter. The first is that only one full copy of the file exists in the archive, and it is the revision that RCS designates as the tip by default, with the historical revisions stored as reverse deltas. Reconstructing an old revision requires applying deltas backwards along the path from the tip, and reconstructing the tip requires a single read. The design deliberately puts the common case first, which means checkout of the head is fast and retrieval of a revision ten steps back costs ten delta applications, each requiring a seek and a scan of the delta text.

The second is that the entire history of one file is one file in the filesystem. This makes the archive self-contained and trivially copyable, and it makes concurrent access need file locking. RCS provided a lockfile mechanism precisely because the archive is not append-only and a partially applied delta would destroy history. A process that computes a delta against the current tip and writes it must have exclusive access for the whole read-modify-write cycle.

The consequence is the mechanism later systems had to escape. In an RCS archive, the unit of concurrency control is the file, and the granularity cannot be finer because the format has no way to append to a revision tree without knowing the parent’s current state. Every checkin serializes on a POSIX lock of a single inode.

Why the model felt natural

In 1982 the alternative was not version control with merging. It was a shared directory with a convention about whose turn it was to edit a file. RCS replaced an honour system with a lock that the tool enforced, and the tool also answered a question the shared directory could not: what did this file look like three weeks ago. The answer was an exact byte-level reconstruction, not an approximation, and the storage was a single archive rather than a copy per snapshot.

The lock was not perceived as a limitation because it matched the working practice. A file was owned by one person at a time, changes were made deliberately, and the important thing was that a revision once recorded could be recovered. The RCS manual’s framing of the system is about retaining old versions and reconstructing them, with concurrency control present as a safety property rather than a workflow.

CVS splits the repository and inherits the granularity

CVS moved the repository to a server and let many clients check out working copies over the network. Two things changed structurally. First, the repository became a directory tree mirroring the source tree, with each file’s RCS archive in place, so the model scaled from one file to a project. Second, and more consequentially, CVS introduced the possibility of two developers holding separate working copies of the same file simultaneously.

The protocol CVS uses is worth describing because its shape explains the failure mode. A client connects, authenticates, and then sends commands as text lines with a length prefix on file contents. Commands include Modified, Is-modified, Unchanged and UseUnchanged, which are the client telling the server what state its working copy is in, and update, commit and ci for synchronization. The stat-and-update optimization, the UseUnchanged handshake, sends a list of files rather than comparing contents, which means the client’s belief about a file’s modification time is part of the protocol’s correctness. A clock skew between client and server, or a file touched by a build, produces a false classification.

Commit in CVS is per file, not per changeset. Each file is merged and written independently, so an interrupted commit leaves the repository in a state where some files of a logical change are in and others are not. There is no transaction spanning the commit, and no identifier that ties the files together. The convention of writing the same log message to every file was the only thing that made a changeset discoverable afterwards, and reconstructing one required searching the log for the message.

cvs update implements the merge. If a file changed on the server and the working copy is unmodified, the client receives the new revision. If both changed, CVS runs a line-based three-way merge using the common ancestor recorded in the file’s revision history, writes conflict markers into the file, and tells the user. If the working copy is modified and the server’s copy is unchanged, nothing happens. There is no repository-side notion of what a client is working on, so the merge can only be computed at update time, against whatever the server happens to hold at that moment.

The ancestor problem

Three-way merge requires the common ancestor, and CVS derives it from per-file revision numbers: the branch from the revision the client checked out to the current head. This works when the client’s checkout base is a single ancestor. It degrades when the client has already merged once, because the base recorded is still the original checkout revision, not the last merged point. Re-merging then presents changes that were already merged as new, a phenomenon that produces the duplicate-application and spurious-conflict patterns familiar to anyone who worked with long-lived CVS branches.

The deeper issue is that CVS has no representation of a merge as a fact. Merging writes a new revision whose content came from two parents, but the archive stores only one parent, the branch it was committed onto. The merge relationship exists solely in the human memory and in the log message. Any later operation that wants to know what has already been integrated must re-derive it from content, and content-based derivation cannot distinguish a change that was merged from a change that was independently made.

What locking actually protected

CVS offered cvs edit and cvs unedit, which create a lock on the file in the repository. This is the RCS model reintroduced as an option, and it never became the default because it serializes precisely the activity that distributed development exists to parallelize. The documented advice in the CVS book was to merge, not lock, and to merge often to keep conflicts small.

Locking protects a property that merging does not: that the file a developer reads is the file the developer writes. Under merging, this is false by construction. A developer reads revision 1.4, writes a change, and commits against revision 1.6, with 1.5’s changes having appeared underneath. The tool presents the developer’s edit as a diff against the base they saw, and the merge results in a file that no human has read in full. Whether that file is correct is not a question the tool can answer, because correctness depends on what 1.5 changed.

For text files with small, local edits, the probability that a mechanical merge produces something wrong is low enough that the practice is worth it. For generated files, binary assets, and any file where the merge algorithm produces a syntactically valid but semantically wrong result, merging without the base guarantee is unsound. The record of CVS-era problems is dominated by files that should have been locked and were not.

Storage, not concurrency, set the ceiling

The delta-chain format also set a scaling behaviour that CVS inherited and could not fix. Checking out a whole project requires reading one archive per file. For a tree with tens of thousands of files, that is tens of thousands of opens, seeks and delta reconstructions. The cost is proportional to file count, and the constant is dominated by per-file operations rather than by bytes transferred, which is why CVS checkouts feel slow in a way that no amount of network bandwidth fixes.

The opposite design, content-addressed storage with a single pack of compressed objects, was not available in 1982 for reasons of memory and simplicity, and by the time it was affordable the delta-per-file model was embedded in every tool. The lesson is not that Tichy chose badly; the single-archive format was a good fit for a single-user tool on a timesharing system. It is that a storage format’s per-operation cost becomes the system’s ceiling once the format is the integration point for a whole ecosystem. The same structural trap appears in the version-vector growth problem described in Optimistic Concurrency and the Conflict Check That Arrives Too Late: a representation chosen for the single-machine case required coordination once it had to span many.

The lasting structural defect

CVS’s model of a revision as a per-file event, and of a merge as a per-file operation with an implicitly derived ancestor, is the part that later systems had to replace rather than repair. Subversion kept the centralized repository but made commits atomic across files and stored changesets as first-class objects. Distributed systems went further, deriving the merge base from a graph of commits with recorded parents, which is the only way to answer “what has already been merged” without guessing from content.

The intermediate step is instructive because it shows the cost of the wrong unit. A per-file history with one parent per revision cannot express a merge, so every tool built on it re-derives integration state, and every re-derivation is an approximation. The lock and the merge were never the real argument. The real defect was that the data model had no place to put the relationship that developers cared about.

A related boundary, policed by build tools rather than by the language, is covered in Header Files as an Interface Contract and the ODR Landmine. For how the same divergence between written rule and shipped behaviour hardens into a standard, De Jure Standard Versus De Facto Implementation treats the general case.