11:18 a.m.
Manik Surtani wrote:
Ok, this seems to work, making things a lot more 'correct'.
But
before I roll this into an official release and start making changes
en-masse, porting this to 1.4.x and 2.0.0, I'd like to step back and
think about whether this is what we really want. Here is what I've
effectively done with 1.3.0.SP4, all related to pessimistic locking only:
a) Added a mechanism for not removing nodes when remove() is called,
and instead storing them in a map which can be referenced by
concurrent threads and locks attempted. (Mutated version of Brian's
original fix to JBCACHE-871)
b) When locking nodes in PLI.lock(), added a mechanism to obtain a WL
on a node if the next node after it needs to be created or removed.
(JBCACHE-875)
c) Modified PLI.lock() to start with Fqn.ROOT rather than Fqn.get(0),
which applies the same cache-wide locking behaviour to the root as
well. Prior to this, the root never was locked for anything.
The implications of these, for the sake of accuracy and correctness,
are possibly:
1) Performance impact on inspecting nodes in b) to decide on whether
WLs are needed
2) Memory impact on maintaining a map of removed nodes in a)
- Can't we simply mark a node as REMOVED (special attribute in that
node's hashmap), so we don't need an additional list ?
- What happens if you remove an entire subtree (2000 nodes) in a TX ? Is
the current list a list of Fqns, or a copy of the nodes ?
3) Reduced concurrency due to overall stronger locks in b)
4) Much reduced concurrency because of the locking in c)
Can we resume the discussion initiated by Brian Dueck some time ago, to
provide the concept of 'multiple roots' ? We could create N buckets, and
the hashcode of the first elements of an FQN selects the bucket
(subtree) into which the FQN will go. The N buckets are NEVER removed,
but they are not visible to the user. Therefore, if we have to lock the
root, we never actually lock "/", but e.g. bucket #24.
5) Potential of more deadlocks/timeouts because of 3) and 4) above.
Of the above, 5) manifests itself in a few unit tests that have now
started to fail (TxCacheLoaderTest, some state transfer tests, etc.).
Simple example, taken from one of the failing tests, leads to a deadlock:
1: mgr.begin();
2: Transaction tx=mgr.getTransaction();
3: cache1.put("/one/two/three", "key1", "val1");
4: assertNull(cache2.get("/one/two/three", "key1"));
5: tx.commit();
Line 3 obtains a WL on "/" on cache1, for GTX 1
Line 4 obtains a WL on "/" on cache2, for GTX 2
Line 5, on replication, tries to get a WL on "/" on cache2, for GTX 1
Both GTXs relate to the same TX since they are in the same thread.
Boom, deadlock.
One thing here though, in my opinion, another bug in the original PLI:
When doing a get on a node that doesn't exist, intermediate nodes are
created. E.g., cache2.get("/one/two/three", "key1") actually ends up
creating /one/two/three first, and after the JBCACHE-875 fix, /, /one
and /one/two will be WL'd for a get() on a nonexistent node!!
Shouldn't the loop just be short-circuited such that at any point, if
the next node does not exist and the lock_type requested is READ, just
return a null? Saves us a whole bunch of unnecessary WL's ...
Absolutely, this is a bug ! We should never create nodes for GET or
REMOVE !!
--
Bela Ban
Lead JGroups / JBoss Clustering team
JBoss - a division of Red Hat
11:43 a.m.
New subject: Fundamental problem with pessimistic locking
On 27 Nov 2006, at 17:18, Bela Ban wrote:
Manik Surtani wrote:
> Ok, this seems to work, making things a lot more 'correct'. But
> before I roll this into an official release and start making
> changes en-masse, porting this to 1.4.x and 2.0.0, I'd like to
> step back and think about whether this is what we really want.
> Here is what I've effectively done with 1.3.0.SP4, all related to
> pessimistic locking only:
>
> a) Added a mechanism for not removing nodes when remove() is
> called, and instead storing them in a map which can be referenced
> by concurrent threads and locks attempted. (Mutated version of
> Brian's original fix to JBCACHE-871)
> b) When locking nodes in PLI.lock(), added a mechanism to obtain
> a WL on a node if the next node after it needs to be created or
> removed. (JBCACHE-875)
> c) Modified PLI.lock() to start with Fqn.ROOT rather than Fqn.get
> (0), which applies the same cache-wide locking behaviour to the
> root as well. Prior to this, the root never was locked for anything.
> The implications of these, for the sake of accuracy and
> correctness, are possibly:
>
> 1) Performance impact on inspecting nodes in b) to decide on
> whether WLs are needed
> 2) Memory impact on maintaining a map of removed nodes in a)
- Can't we simply mark a node as REMOVED (special attribute in that
node's hashmap), so we don't need an additional list ?
This was the (seemingly) simpler solution at the time, although I may
move away from this. Marking a node as removed will involve clean-up
code for nodes marked as such either on transaction completion or (in
the non-tx case) as the call returns, probably as a part of the PLI.
And I'd use a (transient) boolean member variable rather than a
special attribute though; somehow cleaner.
- What happens if you remove an entire subtree (2000 nodes) in a
TX ? Is the current list a list of Fqns, or a copy of the nodes ?
Child nodes are added to this map as well, as they will be removed
and their locks lost in the same way. The Map is keyed on Fqn, and
the actual Node is the value so all locks, etc. are not lost.
> 3) Reduced concurrency due to overall stronger locks in b)
> 4) Much reduced concurrency because of the locking in c)
Can we resume the discussion initiated by Brian Dueck some time
ago, to provide the concept of 'multiple roots' ? We could create N
buckets, and the hashcode of the first elements of an FQN selects
the bucket (subtree) into which the FQN will go. The N buckets are
NEVER removed, but they are not visible to the user. Therefore, if
we have to lock the root, we never actually lock "/", but e.g.
bucket #24.
Yes, this is something to revisit but not for a patch on 1.3.0 or
even a micro version (1.4.1). Similar in some ways to the hashing I
was suggesting the Hibernate guys use to improve concurrency, except
that we could do it implicitly.
> <SNIP>
>
> One thing here though, in my opinion, another bug in the original
> PLI:
>
> When doing a get on a node that doesn't exist, intermediate nodes
> are created. E.g., cache2.get("/one/two/three", "key1") actually
> ends up creating /one/two/three first, and after the JBCACHE-875
> fix, /, /one and /one/two will be WL'd for a get() on a
> nonexistent node!! Shouldn't the loop just be short-circuited
> such that at any point, if the next node does not exist and the
> lock_type requested is READ, just return a null? Saves us a whole
> bunch of unnecessary WL's ...
Absolutely, this is a bug ! We should never create nodes for GET or
REMOVE !!
http://jira.jboss.com/jira/browse/JBCACHE-881
6656
days inactive
6656
days old
jbosscache-dev@lists.jboss.org
1 comments
2 participants
participants (2)
-
Bela Ban -
Manik Surtani