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 paul.joseph.davis@gmail.com
 designates 209.85.210.180 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:from:date:message-id:subject:to
         :content-type;
        b=TvUtxtJwrwkp52VfbYi3C7sGLDDzTa0gezvnnBN5pyrwxeTq1xrQ8exri7CfOD6hXg
         umzQZaoWb1agg8RofXjLkKA++lcF9bWHMU5snTIT5kqzPb1HEdg2nqnNUFS4GuApUSFQ
         fuPp2bdPGZIJFv7TOLi0Nf2XNqss6M98nYrwI=
MIME-Version: 1.0
In-Reply-To: <AANLkTinQL_njEBuMqD+4av76SukMfe4+_9R1ziw87RB_@mail.gmail.com>
References: <AANLkTimDsDLhagZtzWz=q=VYR_5JbLL1HNjcAwr91h6t@mail.gmail.com>
 <AANLkTin=jQrfHMxgbTUb3x=jF_WV-6-WZDJ6OB1TguF8@mail.gmail.com>
 <D6B95099-C6B8-4C94-BF74-8CA967A52C48@dionne-associates.com>
 <AANLkTin_xvhOvb0-f5p1Qv8MFarhAeG+RHjuvLZV=uNZ@mail.gmail.com>
 <AANLkTimat8pa7BCGLyx2Xm5j-p9dVB-=fk0zLBqaiQ_O@mail.gmail.com>
 <AANLkTimKt6unuXY6B5mde+xmC7mqN1-QVV+wRKZ5acGA@mail.gmail.com>
 <AANLkTim=GZpW1UW_RAzPdPxNwKLoRJZtVPhThz2rf8pM@mail.gmail.com>
 <AANLkTinQL_njEBuMqD+4av76SukMfe4+_9R1ziw87RB_@mail.gmail.com>
From: Paul Davis <paul.joseph.davis@gmail.com>
Date: Sat, 18 Dec 2010 20:27:29 -0500
Message-ID: <AANLkTimfv=g8tMgjd=FFuPay-vB=_hg4W8qGA3b_iTBt@mail.gmail.com>
Subject: Re: How fast do CouchDB propagate changes to other nodes?
To: user@couchdb.apache.org
Content-Type: text/plain; charset=ISO-8859-1

On Sat, Dec 18, 2010 at 8:23 PM, Randall Leeds <randall.leeds@gmail.com> wrote:
> On Sat, Dec 18, 2010 at 16:41, Paul Davis <paul.joseph.davis@gmail.com> wrote:
>> Right, I probably jumped a couple steps there:
>>
>> The unique datums we have to work with here are the _id/_rev pairs.
>> Theoretically (if we ignore rev_stemming) the ordering with which
>> these come to us is roughly unimportant.
>>
>> So the issue with our history (append only) is that there's no real
>> way to order it such that we can efficiently seek through it to see
>> what we have in common (that I can think of). Ie, replication still
>> needs a way to say "I only need to send these bits". Right now its the
>> src/dst/seq triple that lets us zip through only new edits.
>>
>> Well, theoretically, we could keep a merkle tree of all edits we've
>> ever seen and go that way, but that'd require keeping a history of
>> every edit ever seen which could never be removed.
>>
>> Granted this is just quick thinking. I could definitely be missing
>> something clever.
>>
>
> We're on the same page. I don't have anything clever yet either.
> The only other thing that's crossed my mind is some way to exchange
> information about checkpoints each participant has with a third party.
> You'd have to somehow verify that the checkpoint being presented to
> you is actually one created by the third party, which involves trust
> or verification. I like the verification route because I'd still love
> to decouple the endpoint from its hostname, the idea that I was
> stabbing quite horribly at when I prematurely proposed a couple
> patches to give databases uuids. But back to the point, something like
> "you got a bunch of edits since last we spoke, but I got these edits
> from this other endpoint, are they the same ones?" Even then, I'm not
> sure how this works without the merkle.
>

Your last bit there was exactly my idea about the bloom filter. Just
populate the filter with hashes of the uniquely identifying bits of an
edit and then send the filter around.