9:30 a.m.
In the past, parent nodes were not (write) locked when child nodes
were added or removed.
With PL, we simply got a read lock on a parent and edited the child
map. This allowed for phantom reads (and TBH wasn't really R_R either).
With OL, we didn't increment parent versioning when children were
added or removed, but attempted to merge child maps.
For both of the above, we introduced a LockParentForChildInsertRemove
system-wide config property (which defaulted to false). If true, a WL
was acquired on parents (PL) or parent versioning was incremented and
validated (OL) when adding/removing children.
Now with MVCC - since there are no read locks - we have a problem.
Consider:
1. Tx begns.
2. Tx reads /a (no locks)
3. Tx removes /a/b (locks /a/b)
4. Tx counts children of /a (will still see that /a/b is in /a's
child map).
he approaches I have considered are:
1. Removing /a/b from /a's child map.
This will provide a consistent view to the tx removing /a/b but will
mean that other txs will also see /a/b disappear when counting /a's
children, but not when querying the cache for /a/b! Worse, rollbacks
would mean re-adding /a/b to /a's child map, providing weird views on
other readers (/a/b disappears for a while, then reappears)
2. Make a copy of /a for the tx to work off, when removing /a/b.
This is the same as having LockParentForChildInsertRemove semantics.
Copy the parent as well and work off it, but to prevent problems with
concurrent child removes and adds, we'd have to lock the parent.
My vote is for approach 2. In fact, LockParentForChildInsertRemove
would always need to be enabled when using MVCC. Perhaps this should
be a deprecated property that just supports additional consistency for
OL and PL, and be removed when OL/PL eventually get removed?
Thoughts?
--
Manik Surtani
Lead, JBoss Cache
manik(a)jboss.org
3:21 p.m.
Manik Surtani wrote:
Now with MVCC - since there are no read locks - we have a problem.
Consider:
1. Tx begns.
2. Tx reads /a (no locks)
3. Tx removes /a/b (locks /a/b)
4. Tx counts children of /a (will still see that /a/b is in /a's child
map).
he approaches I have considered are:
1. Removing /a/b from /a's child map.
This will provide a consistent view to the tx removing /a/b but will
mean that other txs will also see /a/b disappear when counting /a's
children, but not when querying the cache for /a/b! Worse, rollbacks
would mean re-adding /a/b to /a's child map, providing weird views on
other readers (/a/b disappears for a while, then reappears)
2. Make a copy of /a for the tx to work off, when removing /a/b. This
is the same as having LockParentForChildInsertRemove semantics.
Copy the parent as well and work off it, but to prevent problems with
concurrent child removes and adds, we'd have to lock the parent.
My vote is for approach 2. In fact, LockParentForChildInsertRemove
would always need to be enabled when using MVCC. Perhaps this should be
a deprecated property that just supports additional consistency for OL
and PL, and be removed when OL/PL eventually get removed?
Thoughts?
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.
--
Jason T. Greene
JBoss, a division of Red Hat
3:03 a.m.
On 3 Jul 2008, at 21:21, Jason T. Greene wrote:
Manik Surtani wrote:
> Now with MVCC - since there are no read locks - we have a problem.
> Consider:
> 1. Tx begns.
> 2. Tx reads /a (no locks)
> 3. Tx removes /a/b (locks /a/b)
> 4. Tx counts children of /a (will still see that /a/b is in /a's
> child map).
> he approaches I have considered are:
> 1. Removing /a/b from /a's child map.
> This will provide a consistent view to the tx removing /a/b but
> will mean that other txs will also see /a/b disappear when
> counting /a's children, but not when querying the cache for /a/b!
> Worse, rollbacks would mean re-adding /a/b to /a's child map,
> providing weird views on other readers (/a/b disappears for a
> while, then reappears)
> 2. Make a copy of /a for the tx to work off, when removing /a/b.
> This is the same as having LockParentForChildInsertRemove semantics.
> Copy the parent as well and work off it, but to prevent problems
> with concurrent child removes and adds, we'd have to lock the parent.
> My vote is for approach 2. In fact, LockParentForChildInsertRemove
> would always need to be enabled when using MVCC. Perhaps this
> should be a deprecated property that just supports additional
> consistency for OL and PL, and be removed when OL/PL eventually get
> removed?
> Thoughts?
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.
I guess that approach can still be taken. Just that then it
introduces the potential for phantom reads (nodes appearing in the
child set of a parent), but by that stage lockParent can be a cfg
option to prevent that.
Will investigate further.
Cheers,
--
Manik Surtani
Lead, JBoss Cache
manik(a)jboss.org
3:43 a.m.
Manik Surtani wrote:
On 3 Jul 2008, at 21:21, Jason T. Greene wrote:
> Manik Surtani wrote:
>
>> Now with MVCC - since there are no read locks - we have a problem.
>> Consider:
>> 1. Tx begns.
>> 2. Tx reads /a (no locks)
>> 3. Tx removes /a/b (locks /a/b)
>> 4. Tx counts children of /a (will still see that /a/b is in /a's
>> child map).
>> he approaches I have considered are:
>> 1. Removing /a/b from /a's child map.
>> This will provide a consistent view to the tx removing /a/b but will
>> mean that other txs will also see /a/b disappear when counting /a's
>> children, but not when querying the cache for /a/b! Worse, rollbacks
>> would mean re-adding /a/b to /a's child map, providing weird views on
>> other readers (/a/b disappears for a while, then reappears)
>> 2. Make a copy of /a for the tx to work off, when removing /a/b.
>> This is the same as having LockParentForChildInsertRemove semantics.
>> Copy the parent as well and work off it, but to prevent problems with
>> concurrent child removes and adds, we'd have to lock the parent.
>> My vote is for approach 2. In fact, LockParentForChildInsertRemove
>> would always need to be enabled when using MVCC. Perhaps this should
>> be a deprecated property that just supports additional consistency
>> for OL and PL, and be removed when OL/PL eventually get removed?
>> Thoughts?
>
> 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.
I guess that approach can still be taken. Just that then it introduces
the potential for phantom reads (nodes appearing in the child set of a
parent), but by that stage lockParent can be a cfg option to prevent that.
Right, but phantoms are still allowed by RR, and locking the parent can
significantly reduce performance. As an example, in POJO Cache, a list
is mapped as a root node, and its child elements are child nodes.
Locking the parent effectively serializes concurrent list adds. This is
especially a problem if the TX is not short-lived. Now it could be
possible to change the POJO Cache list impl to use hash branches in the
fqn to stripe the parent locking (this is what the internal area
currently does), however, this is stll less optimal than having no
parent locking.
I think the real desire for locking the parent is for doing certain
atomic operations, like those on ConcurrentMap. However we could provide
a special API for such things, and in it's absence the user can still do
a cooperative lock on the parent with an update.
--
Jason T. Greene
JBoss, a division of Red Hat
4:08 a.m.
On 4 Jul 2008, at 09:43, Jason T. Greene wrote:
Manik Surtani wrote:
> On 3 Jul 2008, at 21:21, Jason T. Greene wrote:
>> Manik Surtani wrote:
>>
>>> Now with MVCC - since there are no read locks - we have a
>>> problem. Consider:
>>> 1. Tx begns.
>>> 2. Tx reads /a (no locks)
>>> 3. Tx removes /a/b (locks /a/b)
>>> 4. Tx counts children of /a (will still see that /a/b is in /a's
>>> child map).
>>> he approaches I have considered are:
>>> 1. Removing /a/b from /a's child map.
>>> This will provide a consistent view to the tx removing /a/b but
>>> will mean that other txs will also see /a/b disappear when
>>> counting /a's children, but not when querying the cache for /a/
>>> b! Worse, rollbacks would mean re-adding /a/b to /a's child map,
>>> providing weird views on other readers (/a/b disappears for a
>>> while, then reappears)
>>> 2. Make a copy of /a for the tx to work off, when removing /a/
>>> b. This is the same as having LockParentForChildInsertRemove
>>> semantics.
>>> Copy the parent as well and work off it, but to prevent problems
>>> with concurrent child removes and adds, we'd have to lock the
>>> parent.
>>> My vote is for approach 2. In fact,
>>> LockParentForChildInsertRemove would always need to be enabled
>>> when using MVCC. Perhaps this should be a deprecated property
>>> that just supports additional consistency for OL and PL, and be
>>> removed when OL/PL eventually get removed?
>>> Thoughts?
>>
>> 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.
> I guess that approach can still be taken. Just that then it
> introduces the potential for phantom reads (nodes appearing in the
> child set of a parent), but by that stage lockParent can be a cfg
> option to prevent that.
Right, but phantoms are still allowed by RR, and locking the parent
can significantly reduce performance. As an example, in POJO Cache,
a list is mapped as a root node, and its child elements are child
nodes. Locking the parent effectively serializes concurrent list
adds. This is especially a problem if the TX is not short-lived. Now
it could be possible to change the POJO Cache list impl to use hash
branches in the fqn to stripe the parent locking (this is what the
internal area currently does), however, this is stll less optimal
than having no parent locking.
Yeah I agree though, from a perf perspective, locking parents for
inserting and removing children sucks.
I think the real desire for locking the parent is for doing certain
atomic operations, like those on ConcurrentMap. However we could
provide a special API for such things, and in it's absence the user
can still do a cooperative lock on the parent with an update.
Not really - we only have atomic ops on the data level and not on the
structural level. E.g., Node.putIfAbsent(), etc. only operate on the
node's data map. There is no Node.addChildIfAbsent() or anything of
the sort - yet. :-)
Cheers,
--
Manik Surtani
Lead, JBoss Cache
manik(a)jboss.org
7:35 a.m.
On 3 Jul 2008, at 21:21, Jason T. Greene wrote:
Manik Surtani wrote:
> Now with MVCC - since there are no read locks - we have a problem.
> Consider:
> 1. Tx begns.
> 2. Tx reads /a (no locks)
> 3. Tx removes /a/b (locks /a/b)
> 4. Tx counts children of /a (will still see that /a/b is in /a's
> child map).
> he approaches I have considered are:
> 1. Removing /a/b from /a's child map.
> This will provide a consistent view to the tx removing /a/b but
> will mean that other txs will also see /a/b disappear when
> counting /a's children, but not when querying the cache for /a/b!
> Worse, rollbacks would mean re-adding /a/b to /a's child map,
> providing weird views on other readers (/a/b disappears for a
> while, then reappears)
> 2. Make a copy of /a for the tx to work off, when removing /a/b.
> This is the same as having LockParentForChildInsertRemove semantics.
> Copy the parent as well and work off it, but to prevent problems
> with concurrent child removes and adds, we'd have to lock the parent.
> My vote is for approach 2. In fact, LockParentForChildInsertRemove
> would always need to be enabled when using MVCC. Perhaps this
> should be a deprecated property that just supports additional
> consistency for OL and PL, and be removed when OL/PL eventually get
> removed?
> Thoughts?
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.
There is one more consequence of not locking parents for adding
children though. The way things work as per current designs, we have:
1. T1 reads /a/b - no locks needed.
2. T1 writes to /a/b/c - /a/b/c is locked.
2.1. /a/b/c is copied (call this copy /a/b/c'), version updated.
2.2. Versions checked for write skew.
3. T1 commits.
3.1. /a/b/c is replaced with /a/b/c' in /a/b's child map.
3.2. Lock on /a/b/c is released.
So that works, except that there can be a race where updates can be
lost. Consider:
1. T1 reads /a/b - no locks needed.
2. T1 writes to /a/b/c - /a/b/c is locked.
2.1. /a/b/c is copied (call this copy /a/b/c'), version updated.
2.2. Versions checked for write skew.
3. T2 writes to /a/b - /a/b is locked.
3.1. /a/b is copied to /a/b' and version is updated.
3.2. Write skew chk
4. T1 commits.
4.1. /a/b/c is replaced with /a/b/c' in /a/b's child map.
4.2. Lock on /a/b/c is released.
5. T2 commits.
5.1. /a/b is replaced with /a/b' in /a's child map.
5.2. Lock on /a/b is released.
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).
I'd vote for the 2nd approach above.
Any other thoughts around this?
Cheers,
--
Manik Surtani
Lead, JBoss Cache
manik(a)jboss.org
12:55 p.m.
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:
- 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.
--
Jason T. Greene
JBoss, a division of Red Hat
5:49 a.m.
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(a)jboss.org
5982
days inactive
5987
days old
jbosscache-dev@lists.jboss.org
7 comments
2 participants
participants (2)
-
Jason T. Greene -
Manik Surtani