~bzr-pqm/bzr/bzr.dev

Incremental push/pull
=====================

This use case covers pulling in or pushing out some number of revisions which
is typically a small fraction of the number already present in the target
repository. Pushing and pulling are defined as branch level operations for ease
of interaction with VCS systems that have no repository abstraction (such as
bzr-svn or GNU Arch) but within bzrlib's core they are currently the
responsibility of the Repository object.

Functional Requirements
-----------------------

A push or pull operation must:
 * Copy all the data to reconstruct the selected revisions in the target
   branch. This is the goal of push and pull after all.
 * Reject corrupt data. As bzr has no innate mechanism for discarding corrupted
   data, corrupted data should not be incorporated accidentally.

Factors which should add work for push/pull
-------------------------------------------

 * Baseline overhead: The time to connect to both branches.
 * Actual new data in the revisions being pulled (drives the amount of data to
   move around, includes the commit messages etc)
 * Number of revisions in the two repositories (scaling affects the
   determination of what revisions to move around).

Push/pull overview
------------------

1. New data is identified in the source repository.
2. That data is read from the source repository.
3. The same data is verified and written to the target repository in such a
   manner that its not visible to readers until its ready for use.

New data identification
~~~~~~~~~~~~~~~~~~~~~~~

We have a single top level data object: revisions. Everything else is
subordinate to revisions, so determining the revisions to propagate should be
all thats needed. This depends on revisions with partial data - such as those
with no signature - being flagged in some efficient manner.

We could do this in two manners: determine revisions to sync and signatures to sync in two passes, or change the 'value' of a revision implicitly when the signature is different. E.g. by using merkle hash trees with the signature data a separate component the signatures will naturally be identified to sync.

We want to only exchange data proportional to the number of new revisions and
signatures in the system though. One way to achieve this for revisions is to
walk the graph out from the desired tips until the surface area intersection is
found. For signatures a set difference seems to be needed as there is no DAG of signatures: the presence of one has no implications on the presence of another, so a full pass over the set of signatures would be required to confirm no new signatures are needed (let alone replaced signatures).

IFF we can determine 'new revisions' and 'new signatures' without full graph access then we can scale acceptable for push and pull.

Ghosts are revisions which are not present in a particular repository. Filling ghosts refers to removing ghosts in the target repository when the ghost is present in the source repository. Filling ghosts can be either an explicit or implicit action. The common case is no ghosts.

Set synchronisation approaches
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A set synchronisation approach is one which synchronises two sets without
regard for innate structure. This can be very efficient but requires adding a
new node to be processed with every commit. Caching of the results of the
various set based syncs I've seen is possible but because the data structures
look different depending on the tip revision being synced up to the cache needs
to be very complex. I recommend not using such an approach for the common case
pull because of the failure to scale. We can use such an approach for
synchronisation of new signatures and ghosts, which should be an explicit
option in both cases.

DAG synchronisation approaches
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

A DAG based approach to synchronistion is one that uses the DAG structure to
determine the difference in present nodes. It can as a result operate from the
tip of the DAG backwards. A dag based approach should allow incremental access
to data and not require a full-graph scan for incremental operations.

File level scaling
^^^^^^^^^^^^^^^^^^

We should read roughly as much of the revision level graph as is needed from
each repository to determine the node difference.  If requested we should
perform a detailed scan to pick up ghost revisions and revisions which have had
signatures added. This should not be the default as it requires full history
access in both cases.

Expected file IO and access pattern:

 * Common case: repo with many branches of one project, to the same.

   1. Source and Target branch tips read.
   2. Find the tip of each branch in their repo (will require reading some of
      the revision graph but is typically near the end of the graph).
   3. Read and parse increasing amounts of the revision graph until one is
      found to be a subset of the other, or a complete list of revisions to be
      transmitted is created.

 * Uncommon cases: 
   
   1. Repositories with many projects or branches which are very old may
      require reading a lot of unrelated graph data.

   1. Initial push/pull scenarios should not require reading an entire graph.


API scaling
^^^^^^^^^^^

 1. Get branch tips.
 2. Determine one sided graph difference. To avoid obtaining a full graph over
    the wire this needs to be done without reference to the full graph, and
    with some logarthmic scaling algorithm. There are several already available
    for this. 

With ghost and new-signature detection:

 * File IO access pattern will read the entire graph on the 'target' side - if
   no ghosts are present then stop, otherwise seek the new revisions on the
   source side with the regular algorithm and also explicitly search for the
   ghost points from the target; plus a set difference search is needed on
   signatures.

 * Semantic level can probably be tuned, but as its also complex I suggest
   deferring analysis for optimal behaviour of this use case.


Data reading
~~~~~~~~~~~~

When transferring information about a revision the graph of data for the
revision is walked: revision -> inventory, revision -> matching signature,
inventory -> file ids:revision pairs.

File level scaling
^^^^^^^^^^^^^^^^^^

As we're reading already committed data, as long as nothing is mutating data on
disk reading should be race free. We will:

 - read each revision object
 - read the matching inventory delta
 - attempt to read a signature object
 - parse the inventory delta
 - read the fileid:revisionid compressed chunk for each line in the inventory
   delta

Theres no point validating that the data read is valid, as transmission through to the client writing the data might invalidate it; we need to validate before we write.

API scaling
^^^^^^^^^^^

Given that we have established the revisions needed, a single API call should
suffice to obtain all data; the API should present the data in such an order
that it can be validated as it arrives and thus not require large scale
buffering on disk. Specifically each item of data should be validatable (e.g.
for some file data we want the fileid:revisionid:validationhash + content).


Data Verification and writing
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

New data written to a repository should be completed intact when it is made
visible. This suggests that either all the data for a revision must be made
atomically visible (e.g. by renaming a single file) or the leaf nodes of the
reference graph must become visible first.

Data is referred to via the following graph:
revision -> revision
revision -> signature
revision -> inventory
inventory -> fileid:revisionid
fileid:revisionid -> fileid:revisionid

Data is verifiable via a different ordering:
signature -> revision -> inventory -> fileid:revisionid texts.

We dont gpg verify each revision today; this analysis only speaks to hash
verification of contents.

To validate a revision we need to validate the data it refers to. But to
validate the contents of a revision we need the new texts in the inventory for
the revision - to check a fileid:revisionid we need to know the expected sha1
of the full text and thus also need to read the delta chain to construct the
text as we accept it to determine if its valid. Providing separate validators
for the chosen representation would address this.
e.g: For an inventory entry FILEID:REVISIONID we store the validator of the
full text :SHA1:. If we also stored the validator of the chosen disk
representation (:DELTASHA1:) we could validate the transmitted representation
without expanding the delta in the common case. If that failed we could expand
the delta chain and try against the full text validator, and finally fail. As
different delta generators might generate different deltas, :DELTASHA1: should
not become part of the revision validator, only the inventory disk encoding. In
a related manner a transmission format that allowed cheap validation of content
without applying locally stored deltas would be advantageous because no local
reads would be incurred to validate new content. For instance, always sending a
full text for any file, possibly with a delta-chain when transmitting multiple
revisionids of the file, would allow this. (git pack-files have this property).

Overview summary
^^^^^^^^^^^^^^^^

A single-file local format would allow safe atomic addition of data while
allowing optimisal transmission order of data. Failing this the validation of
data should be tuned to not require reading local texts during data addition
even in the presence of delta chains. We should have transmission-validators
separate from content validators that allow validation of the delta-transmitted
form of objects.

File level scaling
^^^^^^^^^^^^^^^^^^

* Every new file text requires transmission and local serialisation.
* Every commit requires transmission and storage of a revision, signature and inventory.

Thus 4000 commits to a 50000 path tree of 10 files on averages requires (with
knits) between 26 writes (2*(3+10)) and 80006 (2*(4000*10 + 3)) writes. In all
cases there are 4000 * 13 distinct objects to record.

Grouping data by fileid, content and metadata, gives the figures above.
Data grouping:

* File per full identifier (fileid:revisionid:meta|content): 104000
* Delta-chain per object: object id count * constant overhead per object id 
  (26 -> 80006)
* Collation/pack file: 1

Performance for these depends heavily on implementation:
 - Using full ids we could name by validator or by id, giving best performance
   that depends on either receiving data in validator order or in id order.
 - using delta-chain per object we get least seek overhead and syscall overhead
   if we recieve in topological order within the object id, and object ids in
   lexical order.
 - Using a collation/pack file we can stream it into place and validate as we go,
   giving near ideal performance.

API scaling
^^^^^^^^^^^

The api for writing new data recieved over the network will need to be geared
to the transmission and local storage method. What we need is for the
transmission method to reasonably closely match the desired write ordering
locally. This suggests that once we decide on the best local storage means we
should design the api.


take N commits from A to B, if B is local then merge changes into the tree.
copy ebough data to recreate snapshots
avoid ending up wth corrupt/bad data

Notes from London
-----------------

 #. setup

   look at graph of revisions for ~N comits to deretmine eligibility for 
   if preserve mainline is on, check LH only

    identify objects to send that are not on the client repo
      - revision - may be proportional to the graph
      - inventory - proportional to work
      - texts     - proportional to work
      - signatures - ???

 #. data transmission

  * send data proportional to the new information
  * validate the data:

   #. validate the sha1 of the full text of each transmitted text.
   #. validate the sha1:name mapping in each newly referenced inventory item.
   #. validate the sha1 of the XML of each inventory against the revision.
      **this is proportional to tree size and must be fixed**

 #. write the data to the local repo.
    The API should output the file texts needed by the merge as by product of the transmission

 #. tree application

Combine the output from the transmission step with additional 'new work data' for anything already in the local repository that is new in this tree.
should write new files and stat existing files proportional to the count of the new work and the size of the full texts.