[ZODB-Dev] BTree set question

[John Belmonte]

Tim Peters wrote:
> 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).
> """

Thanks very much, I'm glad I asked.  While the merge rules are as I 
hoped in the case of a set, I'm alarmed by the mapping value 
modification rule.  It's *not* conservative, and inconsistent (as you 
point out) with key insertion/deletion-- I consider it a bug.

Regards,
-John


-- 
http:// if  ile.org/