[Zope-dev] RE: [ZODB-Dev] [ATT] BTrees conflict resolution leads to indexinconsistencies

[Tim Peters]

[Dieter Maurer]
> Zope indexes use code like this to remove document ids from document
> lists:
>
> 	 def removeForwardIndexEntry(self, entry, documentId):
> 	     indexRow = self._index[entry]
> 	     indexRow.remove(documentId)
> 	     if not indexRow:
> 	         del self._index[entry]
>
> If a concurrent transaction adds a document id to the same "indexRow",
> then this document id can be lost because it is inserted into a document
> list discarded by the other transaction.
>
> Under normal conditions, a "ConflictError" would result because two
> transactions modify the same object (the document list). However, the
> BTrees conflict resolution prevents the "ConflictError" and allows the
> loss.

This must have been a horror to track down -- thank you for the effort!

> The result is an index inconsistency: the forward index ("_index") entry
> and the backward one ("_unindex") not longer correspond. Further
> operations lead to "unable to remove documentId from document list"
> exceptions.
>
>
> I suggest to tighten BTrees conflict resolution not to allow concurrent
> insertions when a bucket was emptied.

Yup, this is a nasty one.  We actually had tests ensuring that this _didn't_
raise ConflictError, but in the context of buckets on their own (used as
objects in their own right).  It's not a problem there (conflict resolution
produces a bucket containing (just) the added item).  A problem only arises
when buckets are used as low-level building blocks in BTrees (the bucket is
resolved correctly, but nothing can link the bucket back into the BTree then
-- or can even be made aware of the necessity for doing so).  For obscure
reasons, a problem also requires that the original BTree have at least three
buckets, and that the key inserted not equal any of the keys deleted.

I have a tentative fix checked in on a branch, which is to punt (not try to
resolve the conflict) if the currently committed bucket state is empty, or
the bucket state being committed is empty.

I need to do more testing; a fix will land in ZODBs 3.2.7, 3.3.1, and 3.4.
I'm sure the bug afflicts the 3.1 line too, but 3.1.5 was the final release
in that line.

It's possible that conflict resolution will be disabled entirely by default
in a future release, but not before machinery is added to make resolution
pluggable.