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 <[email protected]> wrote: > > On Aug 31, 2013, at 11:13 AM, Dale Harvey <[email protected]> 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
