You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@couchdb.apache.org by Jens Alfke <je...@couchbase.com> on 2013/08/31 20:02:43 UTC

Which revisions does _revs_limit prune?

The only description I can find about revs_limit is "the maximum number of document revisions that will be tracked by CouchDB, even after compaction has occurred." Nothing I've been able to find online says which revisions are thrown out to reach this limit — it could be the oldest ones, or the ones most deeply buried, for example.

I’m guessing it’s most likely the oldest [earliest added] revisions, but it’s not always clear what those are. For example, if a document with a big rev tree gets replicated into this database, all of its revisions are the same age as far as the local db is concerned, because they all got added in the same PUT operation.

Anyone know for sure?

—Jens

Re: Which revisions does _revs_limit prune?

Posted by Jason Smith <jh...@apache.org>.
I think this will not add much to the conversation. But I wrote up my
investigation of how couch figures out revision lengths when reading
documents.

https://gist.github.com/jhs/1577159

@Noah, this is the sort of thing I put into Gist instead of the Wiki due to
all the wiki paper cuts.


On Sun, Sep 1, 2013 at 9:27 AM, Jens Alfke <je...@couchbase.com> wrote:

>
> On Aug 31, 2013, at 2:20 PM, Paul Davis <pa...@gmail.com>
> wrote:
>
> > 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.
>
> Oh — I hadn’t realized that from Dale’s description. And I just got
> through implementing it [in the Couchbase Sync Gateway] as an actual number
> of revisions. Should be easy enough to change, though.
>
> —Jens

Re: Which revisions does _revs_limit prune?

Posted by Jens Alfke <je...@couchbase.com>.
On Aug 31, 2013, at 2:20 PM, Paul Davis <pa...@gmail.com> wrote:

> 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.

Oh — I hadn’t realized that from Dale’s description. And I just got through implementing it [in the Couchbase Sync Gateway] as an actual number of revisions. Should be easy enough to change, though.

—Jens

Re: Which revisions does _revs_limit prune?

Posted by Paul Davis <pa...@gmail.com>.
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 <je...@couchbase.com> wrote:

>
> On Aug 31, 2013, at 11:13 AM, Dale Harvey <da...@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

Re: Which revisions does _revs_limit prune?

Posted by Jens Alfke <je...@couchbase.com>.
On Aug 31, 2013, at 11:13 AM, Dale Harvey <da...@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

Re: Which revisions does _revs_limit prune?

Posted by Dale Harvey <da...@arandomurl.com>.
* stem the tree by turning the ...


On 31 August 2013 19:13, Dale Harvey <da...@arandomurl.com> wrote:

> So the way I implemented this in PouchDB gives Paul Davis's advice, is to
> stem the trees but 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
>
> I worked off a refactor branch of couch that never got merged, but from a
> glance it looks like this is how it is done in
> https://github.com/apache/couchdb/blob/master/src/couchdb/couch_key_tree.erl
>
> 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
>
>
>
> On 31 August 2013 19:05, Robert Newson <rn...@apache.org> wrote:
>
>> The best I can find right now is from couch_key_tree where the
>> truncation occurs;
>>
>> %% What makes this a bit more complicated is that there is a limit to the
>> %% number of revisions kept, specified in couch_db.hrl (default is 1000).
>> When
>> %% this limit is exceeded only the last 1000 are kept. This comes in to
>> play
>> %% when branches are merged. The comparison has to begin at the same
>> place in
>> %% the branches. A revision id is of the form N-XXXXXXX where N is the
>> current
>> %% revision. So each path will have a start number, calculated in
>> %% couch_doc:to_path using the formula N - length(RevIds) + 1 So, .eg. if
>> a doc
>> %% was edit 1003 times this start number would be 4, indicating that 3
>> %% revisions were truncated.
>> %%
>> %% This comes into play in @see merge_at/3 which recursively walks down
>> one
>> %% tree or the other until they begin at the same revision.
>>
>>
>> On 31 August 2013 19:02, Jens Alfke <je...@couchbase.com> wrote:
>> > The only description I can find about revs_limit is "the maximum number
>> of document revisions that will be tracked by CouchDB, even after
>> compaction has occurred." Nothing I've been able to find online says which
>> revisions are thrown out to reach this limit — it could be the oldest ones,
>> or the ones most deeply buried, for example.
>> >
>> > I’m guessing it’s most likely the oldest [earliest added] revisions,
>> but it’s not always clear what those are. For example, if a document with a
>> big rev tree gets replicated into this database, all of its revisions are
>> the same age as far as the local db is concerned, because they all got
>> added in the same PUT operation.
>> >
>> > Anyone know for sure?
>> >
>> > —Jens
>>
>
>

Re: Which revisions does _revs_limit prune?

Posted by Dale Harvey <da...@arandomurl.com>.
So the way I implemented this in PouchDB gives Paul Davis's advice, is to
stem the trees but 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

I worked off a refactor branch of couch that never got merged, but from a
glance it looks like this is how it is done in
https://github.com/apache/couchdb/blob/master/src/couchdb/couch_key_tree.erl

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



On 31 August 2013 19:05, Robert Newson <rn...@apache.org> wrote:

> The best I can find right now is from couch_key_tree where the
> truncation occurs;
>
> %% What makes this a bit more complicated is that there is a limit to the
> %% number of revisions kept, specified in couch_db.hrl (default is 1000).
> When
> %% this limit is exceeded only the last 1000 are kept. This comes in to
> play
> %% when branches are merged. The comparison has to begin at the same place
> in
> %% the branches. A revision id is of the form N-XXXXXXX where N is the
> current
> %% revision. So each path will have a start number, calculated in
> %% couch_doc:to_path using the formula N - length(RevIds) + 1 So, .eg. if
> a doc
> %% was edit 1003 times this start number would be 4, indicating that 3
> %% revisions were truncated.
> %%
> %% This comes into play in @see merge_at/3 which recursively walks down one
> %% tree or the other until they begin at the same revision.
>
>
> On 31 August 2013 19:02, Jens Alfke <je...@couchbase.com> wrote:
> > The only description I can find about revs_limit is "the maximum number
> of document revisions that will be tracked by CouchDB, even after
> compaction has occurred." Nothing I've been able to find online says which
> revisions are thrown out to reach this limit — it could be the oldest ones,
> or the ones most deeply buried, for example.
> >
> > I’m guessing it’s most likely the oldest [earliest added] revisions, but
> it’s not always clear what those are. For example, if a document with a big
> rev tree gets replicated into this database, all of its revisions are the
> same age as far as the local db is concerned, because they all got added in
> the same PUT operation.
> >
> > Anyone know for sure?
> >
> > —Jens
>

Re: Which revisions does _revs_limit prune?

Posted by Robert Newson <rn...@apache.org>.
and "age" of a revision is its depth, not how recently it was
transferred in a PUT operaiton.

B.

On 31 August 2013 19:05, Robert Newson <rn...@apache.org> wrote:
> The best I can find right now is from couch_key_tree where the
> truncation occurs;
>
> %% What makes this a bit more complicated is that there is a limit to the
> %% number of revisions kept, specified in couch_db.hrl (default is 1000). When
> %% this limit is exceeded only the last 1000 are kept. This comes in to play
> %% when branches are merged. The comparison has to begin at the same place in
> %% the branches. A revision id is of the form N-XXXXXXX where N is the current
> %% revision. So each path will have a start number, calculated in
> %% couch_doc:to_path using the formula N - length(RevIds) + 1 So, .eg. if a doc
> %% was edit 1003 times this start number would be 4, indicating that 3
> %% revisions were truncated.
> %%
> %% This comes into play in @see merge_at/3 which recursively walks down one
> %% tree or the other until they begin at the same revision.
>
>
> On 31 August 2013 19:02, Jens Alfke <je...@couchbase.com> wrote:
>> The only description I can find about revs_limit is "the maximum number of document revisions that will be tracked by CouchDB, even after compaction has occurred." Nothing I've been able to find online says which revisions are thrown out to reach this limit — it could be the oldest ones, or the ones most deeply buried, for example.
>>
>> I’m guessing it’s most likely the oldest [earliest added] revisions, but it’s not always clear what those are. For example, if a document with a big rev tree gets replicated into this database, all of its revisions are the same age as far as the local db is concerned, because they all got added in the same PUT operation.
>>
>> Anyone know for sure?
>>
>> —Jens

Re: Which revisions does _revs_limit prune?

Posted by Robert Newson <rn...@apache.org>.
The best I can find right now is from couch_key_tree where the
truncation occurs;

%% What makes this a bit more complicated is that there is a limit to the
%% number of revisions kept, specified in couch_db.hrl (default is 1000). When
%% this limit is exceeded only the last 1000 are kept. This comes in to play
%% when branches are merged. The comparison has to begin at the same place in
%% the branches. A revision id is of the form N-XXXXXXX where N is the current
%% revision. So each path will have a start number, calculated in
%% couch_doc:to_path using the formula N - length(RevIds) + 1 So, .eg. if a doc
%% was edit 1003 times this start number would be 4, indicating that 3
%% revisions were truncated.
%%
%% This comes into play in @see merge_at/3 which recursively walks down one
%% tree or the other until they begin at the same revision.


On 31 August 2013 19:02, Jens Alfke <je...@couchbase.com> wrote:
> The only description I can find about revs_limit is "the maximum number of document revisions that will be tracked by CouchDB, even after compaction has occurred." Nothing I've been able to find online says which revisions are thrown out to reach this limit — it could be the oldest ones, or the ones most deeply buried, for example.
>
> I’m guessing it’s most likely the oldest [earliest added] revisions, but it’s not always clear what those are. For example, if a document with a big rev tree gets replicated into this database, all of its revisions are the same age as far as the local db is concerned, because they all got added in the same PUT operation.
>
> Anyone know for sure?
>
> —Jens