[jbosscache-dev] Locking parents for insertion and removal with MVCC

[Manik Surtani]

On 4 Jul 2008, at 18:55, Jason T. Greene wrote:

> Manik Surtani wrote:
>> On 3 Jul 2008, at 21:21, Jason T. Greene wrote:
>>> Manik Surtani wrote:
>>>
>>> Why not treat a delete like a modify (as I think it has been done  
>>> in the past)? When a node is deleted, it is locked, and either a  
>>> sentinel or just an fqn is stored in the TX context that issued  
>>> the delete. Then the parent still conains the original node,  
>>> allowing concurrent readers, while the calling tx knows to filter  
>>> deleted nodes from child operations.
>> Wasn't as simple - phantoms are problematic since we have no read  
>> locks.  Let me explain: Node /a/b exists.  T1 starts, adds child /a/ 
>> b/c.  T2 reads /a/b.  Gets child count for /a/b.  Sees 1  
>> (phantom).  Then tries to do a get() on /a/b/c and sees this as  
>> well - since this is added to the parent and the parent is not  
>> locked for writing (i.e., copied).
>> I have worked around this by only attaching new children to their  
>> parents at commit time.  This completely gets rid of phantoms, but  
>> introduces a problem where when retrieving children newly added in  
>> a tx by accessing it's parent, you won't see the new children.  So  
>> I've updated GetChildrenNamesCommand to retrieve the child list,  
>> and then correct it based on children added and removed in the  
>> current scope before returning.  This works well, save for the  
>> overhead of checking and correcting the child list with respect to  
>> anything added or removed in the current scope.
>
> Cool! Phantoms are still going to be possible with RR, since they  
> will show up after the inserting tx has committed but before the  
> reading tx has committed. This is fine though IMO. More comments  
> below:

Ah yes, of course.  What I saw was not really phantoms, but reading  
uncommitted adds which is a big no-no anyway.  :-)

> - snip -
>
>> In the above sequence, changes made to /a/b/c are lost in step 5.1  
>> since changes to /a/b/c are made in /a/b/c' which is attached to /a/ 
>> b and /a/b is replaced with /a/b'.
>> Now this can be solved by either:
>> 1.  Acquiring parent lock at *commit* time.
>> Simpler to implement and more secure, but involves more locking,  
>> even if for a short while.
>> 2.  Merge child maps during commit (steps 4.1 and 5.1) between the  
>> copied node and the original node.
>> E.g., in 5.1., merge child maps between /a/b and /a/b' before  
>> swapping refs on /a.  Slightly more complex to implement (may need  
>> to track whether children have been modified on each copied node).
>
> If you are already maintaining the local tx add/removes, why does a  
> copied node need a copy of the child map? Couldn't it just be a  
> shallow reference copy? The map is already concurrent.

Yes, it should just be a shallow ref.  Wasn't thinking.  :-)  I had an  
intermediate problem with child ref leaks which was the result of some  
legacy code directly modifying the child map, but this is implemented  
properly now and the child map copy is no longer needed.  The shallow  
ref does greatly simplify things.

Cheers,
--
Manik Surtani
Lead, JBoss Cache
manik at jboss.org