annotate notes.txt @ 1696:4a3d4843a1bc

Merge with Peter van Dijk

Some notes about Mercurial's design

Revlogs:

The fundamental storage type in Mercurial is a "revlog". A revlog is
the set of all revisions to a file. Each revision is either stored
compressed in its entirety or as a compressed binary delta against the
previous version. The decision of when to store a full version is made
based on how much data would be needed to reconstruct the file. This
lets us ensure that we never need to read huge amounts of data to
reconstruct a file, regardless of how many revisions of it we store.

In fact, we should always be able to do it with a single read,
provided we know when and where to read. This is where the index comes
in. Each revlog has an index containing a special hash (nodeid) of the
text, hashes for its parents, and where and how much of the revlog
data we need to read to reconstruct it. Thus, with one read of the
index and one read of the data, we can reconstruct any version in time
proportional to the file size.

Similarly, revlogs and their indices are append-only. This means that
adding a new version is also O(1) seeks.

Generally revlogs are used to represent revisions of files, but they
also are used to represent manifests and changesets.

Manifests:

A manifest is simply a list of all files in a given revision of a
project along with the nodeids of the corresponding file revisions. So
grabbing a given version of the project means simply looking up its
manifest and reconstruction all the file revisions pointed to by it.

Changesets:

A changeset is a list of all files changed in a check-in along with a
change description and some metadata like user and date. It also
contains a nodeid to the relevent revision of the manifest. Changesets
and manifests are one-to-one, but contain different data for
convenience.

Nodeids:

Nodeids are unique ids that are used to represent the contents of a
file AND its position in the project history. That is, if you change a
file and then change it back, the result will have a different nodeid
because it has different history. This is accomplished by including
the parents of a given revision's nodeids with the revision's text
when calculating the hash.

Graph merging:

Nodeids are implemented as they are to simplify merging. Merging a
pair of directed acyclic graphs (aka "the family tree" of the file
history) requires some method of determining if nodes in different
graphs correspond. Simply comparing the contents of the node (by
comparing text of given revisions or their hashes) can get confused by
identical revisions in the tree.

The nodeid approach makes it trivial - the hash uniquely describes a
revision's contents and its graph position relative to the root, so
merge is simply checking whether each nodeid in graph A is in the hash
table of graph B. If not, we pull them in, adding them sequentially to
the revlog.

Branching and merging:

Everything in Mercurial is potentially a branch and every user
effectively works in their own branch. When you do a checkout,
Mercurial remembers what the parent changeset was and uses it for the
next check in.

To do a merge of branches in Mercurial, you check out the heads of the
two branches into the same working directory which causes a merge to
be performed, and then check in the result once you're happy with it.
The resulting checkin will have two parents.

It decides when a merge is necessary by first determining if there are
any uncommitted changes in the working directory. This effectively
makes the working directory a branch off the checked in version it's
based on. Then it also determines if the working directory is a direct
ancestor or descendent of the second version we're attempting to
checkout. If neither is true, we simply replace the working directory
version with the new version. Otherwise we perform a merge between the
two versions.

Merging files and manifests:

We begin by comparing two versions manifests and deciding which files
need to be added, deleted, and merged.

Then for each file, we perform a graph merge and resolve as above.
It's important to merge files using per-file DAGs rather than just
changeset level DAGs as this diagram illustrates:

M   M1   M2

AB
 |`-------v     M2 clones M
aB       AB     file A is change in mainline
 |`---v  AB'    file B is changed in M2
 |   aB / |     M1 clones M
 |   ab/  |     M1 changes B
 |   ab'  |     M1 merges from M2, changes to B conflict
 |    |  A'B'   M2 changes A
  `---+--.|
      |  a'B'   M2 merges from mainline, changes to A conflict
      `--.|
         ???    depending on which ancestor we choose, we will have
	        to redo A hand-merge, B hand-merge, or both
                but if we look at the files independently, everything
		is fine

The result is a merged version in the working directory, waiting for
check-in.

Rollback:

When performing a commit or a merge, we order things so that the
changeset entry gets added last. We keep a transaction log of the name
of each file touched and its length prior to the transaction. On
abort, we simply truncate each file to its prior length. This is one
of the nice properties of the append-only structure of the revlogs.
We can also reuse this journal for "undo".

Merging between repositories:

One of the key features of Mercurial is the ability to merge between
independent repositories in a decentralized fashion. Each repository
can act as a read-only server or a client. Clients operating by
pulling all branches that it hasn't seen from the server and adding
them into its graph. This is done in two steps: searching for new
"roots" and pulling a "changegroup"

Searching for new "roots" begins by finding all new heads and
searching backwards from those heads to the first unknown nodes in
their respective branches. These nodes are the 'roots' that are used
to calculate the 'changegroup': the set of all changesets starting at
those roots. Mercurial takes pains to make this search efficient in
both bandwidth and round-trips.

Once the roots are found, the changegroup can be transferred as a
single streaming transfer. This is organized as an ordered set of
deltas for changesets, manifests, and files. Large chunks of deltas
can be directly added to the repository without unpacking so it's
fairly fast.