[ZODB-Dev] BTree set question

[Tim Peters]

[John Belmonte]
> I want to make sure I have things straight-- if the same item is added
> or removed from a BTree set in separate transactions, will the
> conflict be resolved automatically?  For an example, say both
> transaction-A and transaction-B add the number 5 to an IITreeSet.  I
> think and hope this will cause a write conflict.

It should, so let us know when it doesn't <wink>.

The rules for BTree-based conflict resolution aren't written down anywhere.
What I know came from reverse-engineering the C code.

If two transactions modify the same *interior* BTree node, that's always a
write conflict (these are really B+ trees:  all data lives in the bucket
(leaf) nodes, and interior nodes can change only when buckets split or
vanish).

If a transcation splits or empties a bucket, and another transaction makes
any modification to that bucket, that's also always a write conflict.

Else we're left with two transactions modifying the same bucket without
splitting or emptying it.  After an obscene amount of time staring at the
code, I added this comment right before MergeTemplate.c's excruciating (>
200 delicate lines) bucket_merge() function; I *believe* it's correct in all
respects, but wouldn't bet my life on it (your life is a different story
<wink>):  (s1 is the bucket state at the time the current transaction began,
s2 is the currently committed bucket state, and s3 is the state the current
transaction is trying to commit):

"""
It's hard to explain "the rules" for bucket_merge, in large part because
any automatic conflict-resolution scheme is going to be incorrect for
some endcases of *some* app.  The scheme here is pretty conservative,
and should be OK for most apps.  It's easier to explain what the code
allows than what it forbids:

Leaving things alone:  it's OK if both s2 and s3 leave a piece of s1
alone (don't delete the key, and don't change the value).

Key deletion:  a transaction (s2 or s3) can delete a key (from s1), but
only if the other transaction (of s2 and s3) doesn't delete the same key.
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.

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
<key, value> pair.

Mapping value modification:  s2 or s3 can modify the value associated
with a key in s1, provided the other transaction doesn't make a
modification of the same key to a different value.  It's OK if s2 and s3
both give the same new value to the key (XXX while it's hard to be
precise about why, this doesn't seem consistent with that it's *not* OK
for both to add a new key mapping to the same value).
"""