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 b.candler@pobox.com
 designates 208.72.237.25 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=date:from:to
	:subject:message-id:mime-version:content-type; q=dns; s=sasl; b=
	djlQTuKCsfhOAAga3A61QccFk5tNlkyaNyzjGcKpIhYP/yXk9N+gKvp16zip93b7
	CryA0K/95ii+lclQDO6jdVRuqxks8P82Jo8863KAZMd0fRSx/tGGAhx7lYgxwSBe
	7bElo+23fku1i3btpQJpvwQ1aFyCxGgjxZzYmQCSzIw=
Date: Mon, 7 Dec 2009 10:34:53 +0000
From: Brian Candler <B.Candler@pobox.com>
To: user@couchdb.apache.org
Subject: Reducible checksum?
Message-ID: <20091207103453.GB5146@uk.tiscali.com>
Mail-Followup-To: user@couchdb.apache.org
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.5.17+20080114 (2008-01-14)

I am thinking about storing some derived data which is associated with key
ranges of a view. (Example: an image which provides a graphical summary of a
key range).

I would like to determine when it's time to regenerate an image, that is,
when the underlying view has changed within that range.

One thought I had was if I could make a reduce function which was some sort
of checksum of the key/value pairs. Then I could just do a reduce query
across the key range, and see if the reduce value has changed. It would be
like an etag for the range.

Unfortunately, I can't just do something simple like an md5sum across the
range, because couchdb implements a tree of reduces and re-reduces, and may
decide to restructure this tree. I'd like a checksum which is invariant
across all possible reduce trees for the same data.

Something simple would be to XOR all the keys and values together, but
sometimes this would not detect changes which happen to XOR to the same
data.

Perhaps I should md5 each (key,value) pair, and then XOR all those together
in the reduce function.

Since my docs have updated timestamps, maybe I should just take the max() of
the updated timestamp for each doc, together with a count of the docs (so as
to be able to detect deletions)

I just wondered if anyone had already made an elegant solution for this? Or
some completely different way of determining whether a view has changed
between a given startkey and endkey?

Thanks,

Brian.