couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Paul Davis <paul.joseph.da...@gmail.com>
Subject Re: Which revisions does _revs_limit prune?
Date Sat, 31 Aug 2013 21:20:23 GMT
Dale Harvey's summary is exactly right in the description of how it works
currently. And he's exactly right that the algorithm in no way protects
against documents that are heavily conflicted. We've been pondering a fix
for this at Cloudant for some time now because we've had cases of documents
so conflicted that they basically prevent the database from accepting
writes (think hundreds of conflicts). Given that its only the depth that's
limited this can lead us to hundreds of thousands of revisions that the key
tree has to work over. Not a good recipe for awesomeness.

So the thing to point out is the documentation that Jens found is lying.
revs_limit is the depth limit, it doesn't limit the total number of
revisions.


On Sat, Aug 31, 2013 at 2:47 PM, Jens Alfke <jens@couchbase.com> wrote:

>
> 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
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message