couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jens Alfke <j...@couchbase.com>
Subject Re: Which revisions does _revs_limit prune?
Date Sat, 31 Aug 2013 19:47:33 GMT

On Aug 31, 2013, at 11:13 AM, Dale Harvey <dale@arandomurl.com> wrote:

> So the way I implemented this in PouchDB gives Paul Davis's advice, is to
> stem the trees by turning the revision tree into a set of revision lists,
> listing all the individual paths from head to root, then stemming each list
> to the rev limit, then merging them back into a single tree

Makes sense. The algorithm I’m working on is (I think) equivalent: start at each leaf and
walk toward the root, labeling each node with consecutive depths (so leaf=0, its parent=1,
…) but never overwriting a depth with a larger one. Then sort the nodes by depth, and remove
the deepest ones.

> I keep meaning to write a test to reproduce this, but I am fairly certain
> this has the problem with a document that is generating a lot of conflicts
> (by being deleted and recreated continuously), can dos CouchDB as shallow
> branches never get pruned, but I may possibly be missing something

Yeah, any situation where there’s periodically a conflict (more often than every N generations)
will prevent pruning, because every revision will be within distance N of a leaf. I’m not
sure how to deal with this. It seems like deletions should be treated less like full leaves;
maybe they’re not allowed to shorten a path to a root. Hm.

—Jens
Mime
View raw message