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
