Re: Releasing latches when waiting for locks. When and why?

[Olav Sandstaa <Ol...@Sun.COM>]

Knut Anders Hatlen wrote:
> Mike Matrigali <mi...@sbcglobal.net> writes:
>
>   
>> One approach would be to continue to support the latching in the
>> lockmanager, but to provide an alternate implementation using the
>> same interfaces (or new interfaces if necessary).  Then make the
>> default module implementation be the new improved one, but if a
>> deadlock is suspected run under the existing lockmanager with
>> all the exising nobs/reporting for deadlock and timeout.
>>     
>
> That's an excellent idea! I think it's possible to do this without
> creating a new module. We could for instance have a property which
> told SinglePool.latchObject() whether or not it should go through the
> lock table. I will investigate how this could be done and possibly
> come up with a new patch for DERBY-2107.
>   

I think you should go for your original approach where you just move the 
latching out of the lock manager and to the page level. In addition to 
the large performance improvement, this is a simple solution where the 
code is easy to understand and maintain. It also gives the opportunity 
to simplify the lock manager interface by being able to remove the latch 
specific methods from SinglePool (which IMHO did not fit well into a 
generic lock manager interface).

I understand that having the latches in the lock manager helped finding 
deadlocks that included latches, but given that this kind of deadlocks 
is due to a programming error and not due to user level deadlocks caused 
by SQL statements it is a high price in terms of performance to include 
all latches in the lock manager. This type of deadlocks is most likely 
to be seen by developers (hopefully) who do changes to the code. A 
simple approach to help discovering the cause of a deadlock would be to 
introduce a timeout when waiting for a latch and print this to the log 
file (I think you suggested that in one of your earlier emails).

Olav

Re: Releasing latches when waiting for locks. When and why?

[Knut Anders Hatlen <Kn...@Sun.COM>]

Anders Morken <an...@stud.ntnu.no> writes:

> While I'm not an expert on the subject matter, I can't help myself but
> chime in and share my thoughts on this... =)
>
> During the course of our project on analyzing Derby's SMP scalability
> properties, we've investigated Derby's locking and latching pretty thoroughly.
>
> We've followed this thread with interest as it's very much related to our
> ongoing work - and moving latches out of the data structure locks are managed
> in is one of the suggestions for improving scalability we have noted in our
> report.
>
> Anyway, one thing I've found while working on Derby is that the separation
> between interfaces and implementations can be a great advantage - adding the
> capability to use Java 1.4's NIO interfaces in RAFContainer was simplified a
> lot when we could just overload a few methods with a 1.4 specific class.
>
> Relating this to BasePage and latching, I believe that an implementation
> restricted to Java 1.3/1.4's concurrency control abilities will be rather
> disadvantaged compared to ReentrantLock and it's friends living in
> java.util.concurrent.locks in Java 1.5+.

Could you please elaborate on this? How are they disadvantaged? Wrt
performance, I would think that there are no disadvantages since
ReentrantLock is built on top of monitors and wait/notify, just like
the latches. It could be that ReentrantLock is easier to use, but I
have my doubts since there are semantic mismatches between latches and
ReentrantLock (for instance, the owner of a latch is a transaction and
the owner of a ReentrantLock is a thread, so nested latches could be a
problem).

> Now, I realise that I may sound like a broken record now - for DERBY-801 I
> jumped on the "new fancy features!" bandwagon, and I'm doing it again now.
>
> However, what I'm trying to convey this time isn't a strong desire to make
> something cool with the latest features - but to leave an avenue open for that
> at a later stage. This will be a bit harder (and probably a lot messier ;) if
> all the latching code is integrated into the BasePage code.

Most of the latching logic is currently in BasePage, and the
DERBY-2107 patch actually removes a lot more code from BasePage than
it adds to it, so I don't think that patch will make it any harder to
use cool features in the future. Since we don't know yet which cool
features we will use in the future, how they will be used, or whether
they will be used at all, I'm afraid that rewriting BasePage to use
some general abstraction could be a lot of extra work on something
that may never be used.

Moving the latching out of the lock manager was a relatively small
change. Since we all like incremental changes, I would say that it's
the first increment, and if someone later wishes to factor out all the
latching code from BasePage, that could be the next increment.

> At the very least I'd suggest factoring out latch functionality (state,
> synchronization, waiting) into a separate class. The LockFactory interface
> could (maybe with some modifications?) still be the factory interface for
> latches, even if they are not necessarily managed and stored in the big lock
> hash table.
>
> Giving the Lock factory responsibility for picking the appropriate latch
> implementation would not only save the BasePage implementation from containing
> a lot of latch logic, but it could also permit us to have, say, an
> implementation like the current one where deadlocks involving latches and
> locks can be debugged together for debugging work, a lightweight pure-java
> exclusive latch for Java 1.4 and possibly a shared/exclusive latch using
> ReentrantReadWriteLocks from Java 1.5.
>
> Now, I'm just mentioning the last one because we've observed significant wait
> times caused by contended latch waits on the root and second-level blocks in a
> B-tree index. Adding shared latching for B-tree traversing code could possibly
> be one way to alleviate this problem. 

But even if we factor out the latching code now, we would still need
to rewrite that code if we some time in the future decide to implement
shared latches. And that would probably be the easy part... ;)

> Of course great care must be taken when working in this part of Derby and more
> thought should go into this before a decision on how to handle this is made,
> as Mike has pointed out it is easy to make a mistake here that causes silent
> corruption and data loss. (Not to mention that different latching
> implementations on different JVMs and debug/non-debug builds could lead to
> some very, uhm, "interesting" Heisenbugs... =)

Yes, I think that's a good argument for not having different latch
implementations depending on build/vm.

> Anyway, I'm a newbie at this, but those are my two cents, and I'm just
> throwing my thoughts out here in the hope that someone finds a use for them.
> To reiterate - my point is that if we keep this architecturally clean, we can
> reap some benefits right away and keep the avenue open for more cool stuff
> later. My ideas for what could be "cool stuff" are not necessarily good ideas.
> =)

Thanks for sharing your thoughts! And please let us know the next time
you get cool ideas, too! :)

-- 
Knut Anders

Re: Releasing latches when waiting for locks. When and why?

[Anders Morken <an...@stud.ntnu.no>]

While I'm not an expert on the subject matter, I can't help myself but
chime in and share my thoughts on this... =)

During the course of our project on analyzing Derby's SMP scalability
properties, we've investigated Derby's locking and latching pretty thoroughly.

We've followed this thread with interest as it's very much related to our
ongoing work - and moving latches out of the data structure locks are managed
in is one of the suggestions for improving scalability we have noted in our
report.

Anyway, one thing I've found while working on Derby is that the separation
between interfaces and implementations can be a great advantage - adding the
capability to use Java 1.4's NIO interfaces in RAFContainer was simplified a
lot when we could just overload a few methods with a 1.4 specific class.

Relating this to BasePage and latching, I believe that an implementation
restricted to Java 1.3/1.4's concurrency control abilities will be rather
disadvantaged compared to ReentrantLock and it's friends living in
java.util.concurrent.locks in Java 1.5+.

Now, I realise that I may sound like a broken record now - for DERBY-801 I
jumped on the "new fancy features!" bandwagon, and I'm doing it again now.

However, what I'm trying to convey this time isn't a strong desire to make
something cool with the latest features - but to leave an avenue open for that
at a later stage. This will be a bit harder (and probably a lot messier ;) if
all the latching code is integrated into the BasePage code.

At the very least I'd suggest factoring out latch functionality (state,
synchronization, waiting) into a separate class. The LockFactory interface
could (maybe with some modifications?) still be the factory interface for
latches, even if they are not necessarily managed and stored in the big lock
hash table.

Giving the Lock factory responsibility for picking the appropriate latch
implementation would not only save the BasePage implementation from containing
a lot of latch logic, but it could also permit us to have, say, an
implementation like the current one where deadlocks involving latches and
locks can be debugged together for debugging work, a lightweight pure-java
exclusive latch for Java 1.4 and possibly a shared/exclusive latch using
ReentrantReadWriteLocks from Java 1.5.

Now, I'm just mentioning the last one because we've observed significant wait
times caused by contended latch waits on the root and second-level blocks in a
B-tree index. Adding shared latching for B-tree traversing code could possibly
be one way to alleviate this problem. 

Of course great care must be taken when working in this part of Derby and more
thought should go into this before a decision on how to handle this is made,
as Mike has pointed out it is easy to make a mistake here that causes silent
corruption and data loss. (Not to mention that different latching
implementations on different JVMs and debug/non-debug builds could lead to
some very, uhm, "interesting" Heisenbugs... =)

Anyway, I'm a newbie at this, but those are my two cents, and I'm just
throwing my thoughts out here in the hope that someone finds a use for them.
To reiterate - my point is that if we keep this architecturally clean, we can
reap some benefits right away and keep the avenue open for more cool stuff
later. My ideas for what could be "cool stuff" are not necessarily good ideas.
=)

Thanks,
-- 
Anders Morken

My opinions may have changed, but not the fact that I am right!

Re: Releasing latches when waiting for locks. When and why?

[Knut Anders Hatlen <Kn...@Sun.COM>]

Olav Sandstaa <Ol...@Sun.COM> writes:

> Knut Anders Hatlen wrote:
>> Mike Matrigali <mi...@sbcglobal.net> writes:
>>
>>   
>>> One approach would be to continue to support the latching in the
>>> lockmanager, but to provide an alternate implementation using the
>>> same interfaces (or new interfaces if necessary).  Then make the
>>> default module implementation be the new improved one, but if a
>>> deadlock is suspected run under the existing lockmanager with
>>> all the exising nobs/reporting for deadlock and timeout.
>>>     
>>
>> That's an excellent idea! I think it's possible to do this without
>> creating a new module. We could for instance have a property which
>> told SinglePool.latchObject() whether or not it should go through the
>> lock table. I will investigate how this could be done and possibly
>> come up with a new patch for DERBY-2107.
>>   
>
> I think you should go for your original approach where you just move
> the latching out of the lock manager and to the page level. In
> addition to the large performance improvement, this is a simple
> solution where the code is easy to understand and maintain. It also
> gives the opportunity to simplify the lock manager interface by being
> able to remove the latch specific methods from SinglePool (which IMHO
> did not fit well into a generic lock manager interface).

I started looking at how this could be achieved, but I didn't find any
clean way to keep the old latching interface for debugging. So I tend
to agree that it would be better to remove the latching from the lock
manager entirely. Much of the old latching logic is implemented in the
Lockable callbacks in BasePage, and having two separate latch
implementations feels a bit awkward and, as you said, could be
difficult to maintain.

> I understand that having the latches in the lock manager helped
> finding deadlocks that included latches, but given that this kind of
> deadlocks is due to a programming error and not due to user level
> deadlocks caused by SQL statements it is a high price in terms of
> performance to include all latches in the lock manager. This type of
> deadlocks is most likely to be seen by developers (hopefully) who do
> changes to the code.

So what you basically say is that deadlocks caused by locks alone are
(most often) caused by problems in the applications, and deadlocks
involving latches are always caused by internal Derby
errors. Therefore, users should never have to debug deadlocks
involving latches. Given that a deadlock is reported as a possible
deadlock involving latches, a developer equipped with a repro should
have enough clues to be able to instrument/trace the code to find the
cause. It sounds like an acceptable cost to me when held against the
performance impact. But then I have never debugged a deadlock in the
B-trees...

> A simple approach to help discovering the cause
> of a deadlock would be to introduce a timeout when waiting for a latch
> and print this to the log file (I think you suggested that in one of
> your earlier emails).

Yes, I am planning to post a followup patch which adds timeout and a
meaningful error message once the first patch goes in. If we decide
not to keep the latch interface, I will also post a patch which cleans
up the lock manager. However, no one has commented on the first patch
yet, and I don't intend to commit it until another pair of eyes has
looked at it.

-- 
Knut Anders