Mailing-List: contact user-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@couchdb.apache.org
Received-SPF: pass (athena.apache.org: domain of jchris@gmail.com designates
 209.85.160.56 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=mime-version:sender:in-reply-to:references:date
         :x-google-sender-auth:message-id:subject:from:to:content-type;
        b=uIhrnQCBq5zu3JjMBu/XSm6/kndyFigF22CPIBiD5emcaVZGXFAKg3t0idDLQPzs1Z
         iG+x9FlM/HO32WUvS9989go9uPebFAUL+wjVMXC8J3uQJKXoJt0Jq77WDwj7s0qzqg9A
         9BTisTn0ZhearzFrxl/5xvdh8euPu4rrTHGH4=
MIME-Version: 1.0
Sender: jchris@gmail.com
In-Reply-To: <20091209093128.GA7729@uk.tiscali.com>
References: <e282921e0912071427t11b2f4ccqadaae404c5c780f5@mail.gmail.com>
	 <20091209093128.GA7729@uk.tiscali.com>
Date: Thu, 10 Dec 2009 09:34:18 -0800
Message-ID: <e282921e0912100934w6db4ceadk8363baeefbdee4aa@mail.gmail.com>
Subject: Re: Reducible checksum?
From: Chris Anderson <jchris@apache.org>
To: user@couchdb.apache.org, Chris Anderson <jchris@apache.org>
Content-Type: text/plain; charset=ISO-8859-1

On Wed, Dec 9, 2009 at 1:31 AM, Brian Candler <B.Candler@pobox.com> wrote:
> On Mon, Dec 07, 2009 at 02:27:18PM -0800, Chris Anderson wrote:
>> If there's a generic way to do this, and it
>> is cheap enough, it could be generalized to handle view etags. Your
>> row count + max timestamp trick seems sensible to me, but obviously is
>> not generalizable.
>>
>> Presumably you could avoid hashing the keys and values by leaning on
>> the document._rev. However, that just pushes the problem back a step.
>
> Aha. These days the _rev includes a cryptographic checksum of the document
> contents, correct?
>
> In that case I think all we need is a simple sum, modulo 2^128, of the _rev
> hashes. This is commutative and associative, and very cheap. (An XOR has the
> problem that if the same document is emitted an even number of times, it
> vanishes).
>
> Now, we know that the set of (k,v) pair(s) emitted for any particular doc
> can't change unless you modify the design doc. So we could simply add this
> sum to a hash of the design doc as a final step, to get the etag. You'd also
> have to include the view params in the final hash (e.g. startkey, endkey,
> skip) because it's possible that the same set of docs could appear under
> different parts of the key space, emitting different keys and/or values, and
> you'd want different etags for those.
>
> This leaves one question: I know the view index already contains
> {{key,_id},value}, but does it include _rev? If not, would the extra storage
> overhead be acceptable?

There have been request for _rev in the view rows in the past but
we've always responded with the recommendation to just emit the rev as
part of your value.

If we were to use a solution like this for the view etags we'd want to
hard-code it, but for now you should be able to prototype your
approach with the current API.

>
> The alternative I can see is to take a hash of each {{key,_id},value} and to
> sum those hashes. The trouble is this is more expensive computation-wise,
> especially if the value is large (e.g. when you emit the whole document).
>
> Cheers,
>
> Brian.
>


-- 
Chris Anderson
http://jchrisa.net
http://couch.io