[Zodb-checkins] SVN: ZODB/branches/3.3/ Collector #1734. Critical
bug in BTree conflict resolution.
Tim Peters
tim.one at comcast.net
Thu Mar 24 15:56:00 EST 2005
Log message for revision 29668:
Collector #1734. Critical bug in BTree conflict resolution.
Stop silent data loss in some BTree cases where a transaction adds
a new key to a bucket while a concurrent transaction deletes all
keys from the same bucket.
Still needs porting to ZODB trunk and to 3.2 line.
Changed:
U ZODB/branches/3.3/NEWS.txt
U ZODB/branches/3.3/src/BTrees/MergeTemplate.c
U ZODB/branches/3.3/src/BTrees/tests/testConflict.py
U ZODB/branches/3.3/src/ZODB/POSException.py
-=-
Modified: ZODB/branches/3.3/NEWS.txt
===================================================================
--- ZODB/branches/3.3/NEWS.txt 2005-03-24 15:24:15 UTC (rev 29667)
+++ ZODB/branches/3.3/NEWS.txt 2005-03-24 20:56:00 UTC (rev 29668)
@@ -2,6 +2,21 @@
============================
Release date: DD-MMM-2005
+BTrees
+------
+
+Collector #1734: BTrees conflict resolution leads to index inconsistencies.
+
+Silent data loss could occur due to BTree conflict resolution when one
+transaction T1 added a new key to a BTree containing at least three buckets,
+and a concurrent transaction T2 deleted all keys in the bucket to which the
+new key was added. Conflict resolution then created a bucket containing the
+newly added key, but the bucket remained isolated, disconnected from the
+BTree. In other words, the committed BTree didn't contain the new key added by
+T1. Conflict resolution doesn't have enough information to repair this,
+so ``ConflictError`` is now raised in such cases.
+
+
ZEO
---
Modified: ZODB/branches/3.3/src/BTrees/MergeTemplate.c
===================================================================
--- ZODB/branches/3.3/src/BTrees/MergeTemplate.c 2005-03-24 15:24:15 UTC (rev 29667)
+++ ZODB/branches/3.3/src/BTrees/MergeTemplate.c 2005-03-24 20:56:00 UTC (rev 29668)
@@ -70,7 +70,9 @@
* However, it's not OK for s2 and s3 to, between them, end up deleting all
* the keys. This is a higher-level constraint, due to that the caller of
* bucket_merge() doesn't have enough info to unlink the resulting empty
- * bucket from its BTree correctly.
+ * bucket from its BTree correctly. It's also not OK if s2 or s3 are empty,
+ * because the transaction that emptied the bucket unlinked the bucket from
+ * the tree, and nothing we do here can get it linked back in again.
*
* Key insertion: s2 or s3 can add a new key, provided the other transaction
* doesn't insert the same key. It's not OK even if they insert the same
@@ -91,6 +93,13 @@
SetIteration i1 = {0,0,0}, i2 = {0,0,0}, i3 = {0,0,0};
int cmp12, cmp13, cmp23, mapping, set;
+ /* If either "after" bucket is empty, punt. */
+ if (s2->len == 0 || s3->len == 0)
+ {
+ merge_error(-1, -1, -1, 12);
+ goto err;
+ }
+
if (initSetIteration(&i1, OBJECT(s1), 1) < 0)
goto err;
if (initSetIteration(&i2, OBJECT(s2), 1) < 0)
Modified: ZODB/branches/3.3/src/BTrees/tests/testConflict.py
===================================================================
--- ZODB/branches/3.3/src/BTrees/tests/testConflict.py 2005-03-24 15:24:15 UTC (rev 29667)
+++ ZODB/branches/3.3/src/BTrees/tests/testConflict.py 2005-03-24 20:56:00 UTC (rev 29668)
@@ -177,7 +177,7 @@
test_merge(base, b1, b2, bm, 'merge insert from empty')
- def testMergeEmptyAndFill(self):
+ def testFailMergeEmptyAndFill(self):
base, b1, b2, bm, e1, e2, items = self._setupConflict()
b1.clear()
@@ -185,7 +185,7 @@
b2.update(e2)
bm.update(e2)
- test_merge(base, b1, b2, bm, 'merge insert from empty')
+ test_merge(base, b1, b2, bm, 'merge insert from empty', should_fail=1)
def testMergeEmpty(self):
base, b1, b2, bm, e1, e2, items = self._setupConflict()
@@ -274,7 +274,7 @@
test_merge(base, b1, b2, bm, 'merge insert from empty')
- def testMergeEmptyAndFill(self):
+ def testFailMergeEmptyAndFill(self):
base, b1, b2, bm, e1, e2, items = self._setupConflict()
b1.clear()
@@ -282,7 +282,7 @@
b2.update(e2)
bm.update(e2)
- test_merge(base, b1, b2, bm, 'merge insert from empty')
+ test_merge(base, b1, b2, bm, 'merge insert from empty', should_fail=1)
def testMergeEmpty(self):
base, b1, b2, bm, e1, e2, items = self._setupConflict()
@@ -742,7 +742,91 @@
else:
self.fail("expected ConflictError")
+ def testConflictWithOneEmptyBucket(self):
+ # If one transaction empties a bucket, while another adds an item
+ # to the bucket, all the changes "look resolvable": bucket conflict
+ # resolution returns a bucket containing (only) the item added by
+ # the latter transaction, but changes from the former transaction
+ # removing the bucket are uncontested: the bucket is removed from
+ # the BTree despite that resolution thinks it's non-empty! This
+ # was first reported by Dieter Maurer, to zodb-dev on 22 Mar 2005.
+ b = self.t
+ for i in range(0, 200, 4):
+ b[i] = i
+ # bucket 0 has 15 values: 0, 4 .. 56
+ # bucket 1 has 15 values: 60, 64 .. 116
+ # bucket 2 has 20 values: 120, 124 .. 196
+ state = b.__getstate__()
+ # Looks like: ((bucket0, 60, bucket1, 120, bucket2), firstbucket)
+ # If these fail, the *preconditions* for running the test aren't
+ # satisfied -- the test itself hasn't been run yet.
+ self.assertEqual(len(state), 2)
+ self.assertEqual(len(state[0]), 5)
+ self.assertEqual(state[0][1], 60)
+ self.assertEqual(state[0][3], 120)
+ # Set up database connections to provoke conflict.
+ self.openDB()
+ r1 = self.db.open().root()
+ r1["t"] = self.t
+ transaction.commit()
+
+ r2 = self.db.open(synch=False).root()
+ copy = r2["t"]
+ # Make sure all of copy is loaded.
+ list(copy.values())
+
+ self.assertEqual(self.t._p_serial, copy._p_serial)
+
+ # Now one transaction empties the first bucket, and another adds a
+ # key to the first bucket.
+
+ for k in range(0, 60, 4):
+ del self.t[k]
+ transaction.commit()
+
+ copy[1] = 1
+
+ try:
+ transaction.commit()
+ except ConflictError, detail:
+ self.assert_(str(detail).startswith('database conflict error'))
+ transaction.abort()
+ else:
+ self.fail("expected ConflictError")
+
+ # Same thing, except commit the transactions in the opposite order.
+ b = OOBTree()
+ for i in range(0, 200, 4):
+ b[i] = i
+
+ r1 = self.db.open().root()
+ r1["t"] = b
+ transaction.commit()
+
+ r2 = self.db.open(synch=False).root()
+ copy = r2["t"]
+ # Make sure all of copy is loaded.
+ list(copy.values())
+
+ self.assertEqual(b._p_serial, copy._p_serial)
+
+ # Now one transaction empties the first bucket, and another adds a
+ # key to the first bucket.
+ b[1] = 1
+ transaction.commit()
+
+ for k in range(0, 60, 4):
+ del copy[k]
+ try:
+ transaction.commit()
+ except ConflictError, detail:
+ self.assert_(str(detail).startswith('database conflict error'))
+ transaction.abort()
+ else:
+ self.fail("expected ConflictError")
+
+
def test_suite():
suite = TestSuite()
for k in (TestIOBTrees, TestOOBTrees, TestOIBTrees, TestIIBTrees,
Modified: ZODB/branches/3.3/src/ZODB/POSException.py
===================================================================
--- ZODB/branches/3.3/src/ZODB/POSException.py 2005-03-24 15:24:15 UTC (rev 29667)
+++ ZODB/branches/3.3/src/ZODB/POSException.py 2005-03-24 20:56:00 UTC (rev 29668)
@@ -187,6 +187,9 @@
# 11; conflicting changes in an internal BTree node
'Conflicting changes in an internal BTree node',
+
+ # 12; i2 or i3 was empty
+ 'Empty bucket in a transaction',
]
def __init__(self, p1, p2, p3, reason):
More information about the Zodb-checkins
mailing list