Mailing-List: contact user-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@couchdb.apache.org
Received-SPF: pass (nike.apache.org: domain of randall.leeds@gmail.com
 designates 209.85.161.52 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :cc:content-type:content-transfer-encoding;
        b=JgRxKgVR8Br+fNfGmZVBQ8vVOupD3j1dgexZwu0d+C5QdVkIQqN1ExbW8ndTZaSfoI
         SrVDoZ+Nlj5z35FBzJe15XgzPRnhFzL85vt/Bo5PHadS0W+ZCyX80H//yDJU757OCJ9X
         1R4EzSc2h3An4aAt4GfVcgnWoq83FuwDY684g=
MIME-Version: 1.0
In-Reply-To: <AANLkTimHg5TYMQVKOCrRZCZQGYFAG2ynf8=ytzngfNCQ@mail.gmail.com>
References: <AANLkTik57VFC_tg3EaHcO1og+QuC2-e5-fmQ8xusob=i@mail.gmail.com>
	<A0818322-21AF-4923-AA37-388B0FA09E94@dionne-associates.com>
	<AANLkTimNCCSBbqu7TocD17kX3FYTqrkjMEMsoX2JG9zS@mail.gmail.com>
	<AANLkTikXE484zmrC2GwyQmXyrKBN_Pg7nz2KZLt7vSzX@mail.gmail.com>
	<AANLkTikThzLbj7eBYE93c+fUAnOO1+gO8Fgz9xgyWmvu@mail.gmail.com>
	<AANLkTimHg5TYMQVKOCrRZCZQGYFAG2ynf8=ytzngfNCQ@mail.gmail.com>
Date: Wed, 16 Feb 2011 11:24:33 -0800
Message-ID: <AANLkTiny5jUe3EpcqCgyDSQHw=TCqgjE7ViqU2PW=SXn@mail.gmail.com>
Subject: Re: interested in learning about replication algorithm
From: Randall Leeds <randall.leeds@gmail.com>
To: user@couchdb.apache.org
Cc: Aaron Boxer <boxerab@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

The algorithm at a high level goes like this:

Get some changes
Check them for revisions that are missing from the target
Pull/Push the missing revisions
Repeat

These functions map to the public API in an obvious way:
/_changes
/_missing_revs
/_all_docs or /_bulk_docs

For any production-ready replicator you'll probably want to checkpoint
your progress.
CouchDB stores checkpoints in documents prefixed with "_local/".
Docs named this way don't replicate, don't show up in views, etc.
Good for internal metadata stuff like this.

Stable checkpointing requires that, up to a certain sequence, all
updates must be flushed to disk on both sides.
Currently this is accomplished with a separate POST to /_ensure_full_commit=
.
Couch also honors a header on document update requests called
X-Couch-Full-Commit.

Almost all the replicator code is contained in couch_rep* or couch_replicat=
or*.
The latter is the new replicator code by Filipe, which may have some
dependency on the old code (I'm not sure).

That should be enough to get you started.

-Randall

On Tue, Feb 15, 2011 at 18:51, Aaron Boxer <boxerab@gmail.com> wrote:
> Thanks, guys! I guess I need to dig into the actual code.
>
> I would like to implement a similar algorithm in C, for another project
> I am working on.
>
>
>
> On Tue, Feb 15, 2011 at 5:48 PM, Robert Newson <robert.newson@gmail.com> =
wrote:
>> It's worth mentioning that, like git, the hash also includes the
>> previous contents (and, hence, is dependent on all previous updates),
>>
>> Only identical sequences of updates will yield the same _rev.
>>
>> B.
>>
>> On 15 February 2011 22:37, Randall Leeds <randall.leeds@gmail.com> wrote=
:
>>> On Tue, Feb 15, 2011 at 07:30, Aaron Boxer <boxerab@gmail.com> wrote:
>>>> Interesting. Thanks!
>>>>
>>>> How do version ids get generated? =C2=A0How do the different nodes
>>>> avoid version id collision; i.e. two nodes updating a document with th=
e
>>>> same version id?
>>>
>>> The revision id contains both a monotonically increasing number
>>> revision number and a hash of the document contents. The hash breaks
>>> ties (storing the conflict, not resolving it, but deterministically
>>> choosing a privileged version to report as the "newest").
>>>
>>> In this manner, should two nodes perform the same update the revision
>>> is said to exist in both places already and replication will note this
>>> and not copy the document again.
>>>
>>> -Randall
>>>
>>
>