annotate notes.txt @ 190:3dd5ce2fddb6

merge: short-circuit search for merge into empty repo

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

merge: short-circuit search for merge into empty repo

We should have 3 cases for merge:

- - we have no changesets
- - we have less than half the changesets
- - we have more than half the changesets

For no changesets, we can immediately tell that we need everything.
This happens when we initially branch from a remote repo, so we simply shortcircuit the search and grab everything from the root

When we're actually tracking a project, we should generally have most
of the changesets, so the current search algorithm should minimize
searching.

It should rarely occur that upstreams gets far ahead of us, in which
case, we suffer a longer search.

manifest hash: eabd55841b03225176ea72b985aad36431a438a9
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)

iD8DBQFCmfajywK+sNU5EO8RAuyKAKCf7Nw6XSK5HEzbrZae7Q06e3dk4wCgjbK6
YUTEfkpPP1h3mNHIHRKz+aI=
=eGMq
-----END PGP SIGNATURE-----

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.

Graph resolving:

Mercurial does branching by copying (or COWing) a repository and thus
keeps everything nice and linear within a repository. However, when a
merge of repositories (a "pull") is done, we may often have two head
revisions in a given graph. To keep things simple, Mercurial forces
the head revisions to be merged.

It first finds the closest common ancestor of the two heads. If one is
a child of the other, it becomes the new head. Otherwise, we call out
to a user-specified 3-way merge tool.

Merging files, manifests, and changesets:

We begin by comparing changeset DAGs, pulling all nodes we don't have
in our DAG from the other repository. As we do so, we collect a list
of changed files to merge.

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

After we've merged files, we merge the manifest log DAG and resolve
additions and deletions. Then we are ready to resolve the changeset
DAG - if our merge required any changes (the new head is not a
decendent of our tip), we must create a new changeset describing all
of the changes needed to merge it into the tip.

Merge performance:

The I/O operations for performing a merge are O(changed files), not
O(total changes) and in many cases, we needn't even unpack the deltas
to add them to our repository (though this optimization isn't
necessary).

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.

Remote access:

Mercurial currently supports pulling from "serverless" repositories.
Simply making the repo directory accessibly via the web and pointing
hg at it can accomplish a pull. This is relatively bandwidth efficient
but no effort has been spent on pipelining, so it won't work
especially well over LAN yet.

It's also quite amenable to rsync, if you don't mind keeping an intact
copy of the master around locally.

Also note the append-only and ordering properties of the commit
guarantee that readers will always see a repository in a consistent
state and no special locking is necessary. As there is generally only
one writer to an hg repository, there is in fact no exclusion
implemented yet. 


Some comparisons to git:

Most notably, Mercurial uses delta compression and repositories
created with it will grow much more slowly over time. This also allows
it to be much more bandwidth efficient. I expect repos sizes and sync
speeds to be similar to or better than BK, given the use of binary diffs.

Mercurial is roughly the same performance as git in some areas and is
faster in others as it keeps around more metadata. One example is
listing and retrieving past versions of a file, which it can do
without reading all the changesets. This metadata will also allow it
to perform better merges as described above.