You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-dev@db.apache.org by Knut Anders Hatlen <Kn...@Sun.COM> on 2006/11/17 16:25:13 UTC
Releasing latches when waiting for locks. When and why?
Hi,
I have come across some use of locks and latches which I don't
understand. One of the lockObject() methods in the lock manager
(SinglePool.lockObject(Object, Lockable, Object, int, Latch)) takes a
Latch parameter. When this method is used, the specified latch will be
released if the lock cannot be obtained immediately, and that page
will be re-latched when the lock has been obtained.
Does anyone know what this method is used for? I have tried to find a
code path to it from the JDBC methods, but I have not found such a
path yet. Actually, I even modified the method so that it threw an
exception each time it was called, and ran derbyall and the JUnit
tests. Only some of the storeunit tests failed, but they invoke the
methods of StoredPage and friends directly, so they don't really
count.
So, when none of the tests that use our public interface use this kind
of locking, when and for what purpose is it used?
Thanks,
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Dyre.Tjeldvoll@Sun.COM writes:
> Anders Morken <an...@stud.ntnu.no> writes:
>
>> We've taken some long hard looks at the lock manager, and we're
>> convinced that there's a lot of potential for improvement in Derby lock
>> management. Not that there's anything wrong with the approach taken in
>> the current implementation - correctness first, optimization later. =)
>>
>> One of the things that we've observed is that on a single-row update
>> transaction, a shared lock is obtained on a row in the B-tree container
>> just before an exclusive lock is obtained on a row in the data
>> container. Off the top of my head I can't remember if why figured out
>> exactly why. =)
>>
>>> Having said that it would be interesting if someone had time to
>>> implement a higher performance latch implementation and plug it in
>>> and see how much it helps. It would decrease the total time spent
>>> in lock manager.
>
> I think Knut Anders has been playing with that idea, so if you're not
> doing it yourself I'm sure he (we) would love to hear about any ideas
> you may have.
Well, my ideas are pretty vague at the moment. The ideas I have played
with so far (see also DERBY-1704) are:
1) Split the hash table in LockSet into multiple hash tables to
reduce the monitor contention. This would reduce monitor
contention for both locking and latching, but wouldn't make any
of them cheaper in the single-client case.
2) Eliminating the hash table in SinglePool by having a direct
pointer from a compatibility space to its locks. This would
reduce monitor contention and CPU usage for locking, but not for
latching.
To reduce the cost of latching, we would at least need to move the
latches out of the lock table (LockSet). One way could be to change
the interface and separate between lockable and latchable objects. As
it is now, both lockable and latchable objects implement the Lockable
interface, and the LockFactory interface says that two Lockables
represent the same lockable object if their equals() methods return
true. This is fine for row locking, but for latching it is unnecessary
overhead because the objects that are latched have no equals() method
and therefore must be the exact same object. If we instead had a
Latchable interface which were simpler than the Lockable, and which
required reference equality in order to represent the same latchable
object, I think we could get closer to the "just set a flag on the
page" idea.
>> We've actually considered doing that for fun, but as our goal right now
>> is to produce a big honkin' report, not fix anything, we haven't. Still,
>> it would probably give a quite significant benefit.
>
> Reports are a fact of life :)
>
>> Using a Java profiler on a reasonably modern X86 system we've found that
>> while acquiring a Derby lock takes about 60-70 microseconds and a latch
>> costs 50-60 microseconds in the non-contended (single thread) cases,
>> acquiring and releasing a ReentrantLock available in Java 1.5 and up
>> costs about 1,5 microseconds. A latch could in theory be about as cheap
>> as a ReentrantLock, and on Java 1.5 and up it would make sense to base
>> Latches on ReentrantLocks.
>
> Interesting observation! But unfortunately not available for Derby for a long
> time :(
If the interface of the lock manager is changed to be more in line
with the new concurrency utilities, we could have different lock
managers for JDK < 1.5 and JDK >= 1.5, and let the 1.5 lock manager
(or at least the latching) just be a thin wrapper around
ReentrantLock. Don't know if that is feasible.
>> However, just separating the latch data structures from the lock data
>> structures could give significant scalability benefits, as right now the
>> latches and locks are all stored in the same hash tables, causing
>> significant monitor contention in multithreaded cases.
>
> Absolutely. In the multi-core world it is essential to keep the amount
> of shared data at an absolute minimum
>
>> I dunno if our report would be of any interest to you guys, but it's not
>> finished yet, and I'm not sure if it appropriate to post it just yet.
>> Still, it's interesting stuff we're digging up, and it's interesting to
>> see how you guys investigate this. =)
>
> I'd love to read it, and I expect others in the Derby community would
> too.
Indeed! It sounds like you have some very interesting numbers, and I'm
looking forward to reading your report!
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Dy...@Sun.COM.
Anders Morken <an...@stud.ntnu.no> writes:
> We've taken some long hard looks at the lock manager, and we're
> convinced that there's a lot of potential for improvement in Derby lock
> management. Not that there's anything wrong with the approach taken in
> the current implementation - correctness first, optimization later. =)
>
> One of the things that we've observed is that on a single-row update
> transaction, a shared lock is obtained on a row in the B-tree container
> just before an exclusive lock is obtained on a row in the data
> container. Off the top of my head I can't remember if why figured out
> exactly why. =)
>
>> Having said that it would be interesting if someone had time to
>> implement a higher performance latch implementation and plug it in
>> and see how much it helps. It would decrease the total time spent
>> in lock manager.
I think Knut Anders has been playing with that idea, so if you're not
doing it yourself I'm sure he (we) would love to hear about any ideas
you may have.
> We've actually considered doing that for fun, but as our goal right now
> is to produce a big honkin' report, not fix anything, we haven't. Still,
> it would probably give a quite significant benefit.
Reports are a fact of life :)
> Using a Java profiler on a reasonably modern X86 system we've found that
> while acquiring a Derby lock takes about 60-70 microseconds and a latch
> costs 50-60 microseconds in the non-contended (single thread) cases,
> acquiring and releasing a ReentrantLock available in Java 1.5 and up
> costs about 1,5 microseconds. A latch could in theory be about as cheap
> as a ReentrantLock, and on Java 1.5 and up it would make sense to base
> Latches on ReentrantLocks.
Interesting observation! But unfortunately not available for Derby for a long
time :(
> However, just separating the latch data structures from the lock data
> structures could give significant scalability benefits, as right now the
> latches and locks are all stored in the same hash tables, causing
> significant monitor contention in multithreaded cases.
Absolutely. In the multi-core world it is essential to keep the amount
of shared data at an absolute minimum
> I dunno if our report would be of any interest to you guys, but it's not
> finished yet, and I'm not sure if it appropriate to post it just yet.
> Still, it's interesting stuff we're digging up, and it's interesting to
> see how you guys investigate this. =)
I'd love to read it, and I expect others in the Derby community would
too.
--
dt
Re: Releasing latches when waiting for locks. When and why?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Mike Matrigali <mi...@sbcglobal.net> writes:
> Anders Morken wrote:
>> Mike Matrigali:
[...]
>>> Having said that it would be interesting if someone had time to
>>> implement a higher performance latch implementation and plug it in
>>>and see how much it helps. It would decrease the total time spent
>>>in lock manager.
>>
>> We've actually considered doing that for fun, but as our goal right now
>> is to produce a big honkin' report, not fix anything, we haven't. Still,
>> it would probably give a quite significant benefit.
>>
>> Using a Java profiler on a reasonably modern X86 system we've found that
>> while acquiring a Derby lock takes about 60-70 microseconds and a latch
>> costs 50-60 microseconds in the non-contended (single thread) cases,
>> acquiring and releasing a ReentrantLock available in Java 1.5 and up
>> costs about 1,5 microseconds. A latch could in theory be about as cheap
>> as a ReentrantLock, and on Java 1.5 and up it would make sense to base
>> Latches on ReentrantLocks.
>
> Do you have something to compare these numbers to. Maybe compared to
> the overall cost of Derby inserting a single row (not comitting), on
> the same machine. Basically would be interested in what is the current
> locking overhead in cpu cost per some standard statement/xact. I think
> when I looked at this awhile back locking/latching together was
> somewhere around 5% of
> a TPC/B like xact. Given that, making locking 0 would only give a 5%
> improvement, so never was that motivated to look at latching. But
> maybe other parts of the system/JVM have raised the ratio.
I did one experiment where I short-circuited all the methods in
SinglePool (had to keep some of the callback logic in order to keep
StoredPage happy) and ran some tests with read-only load using the
test client attached to DERBY-1961. With one client, I saw 20%
increase in throughput. Also, the CPU numbers Kristian posted at
http://wiki.apache.org/db-derby/Derby1961ResourceUsage2 indicate that
the lock manager has considerably more overhead than 5% for some types
of load. Note that his numbers include the network server cost, so for
embedded Derby the relative numbers would probably be even higher.
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Dy...@Sun.COM.
Anders Morken <an...@stud.ntnu.no> writes:
> The major benefit of reworking the lock manager is scalability - right
> now it's pretty much single threaded, which is fine for a lot of the
> scenarios Derby was written to perform in. However, for "benchmark
> compliance" in a world of multicore desktops and servers, it may be
> beneficial to work on Derby's scalability.
For those who might not be convinced about this I suggest running the
test client (select or join) from DERBY-1961
with all data in memory on a multi-cpu/multi-core machine using
1 and 2 clients. "Something" is serializing the load, (and introducing
a penalty in the process). And so far everything points to the lock
manager.
I just ran this experiment on a 2-CPU AMD Opteron
The average of 3 100 sec runs using 1 client was
23423.783 TPS
The average of 3 100 sec runs using 2 clients was
20282.193 TPS
That is -13.411 %. Not only does it not scale, it scales negatively.
>
> To maintain Derby's small footprint while expanding it to handle bigger
> iron is one of the challenges here, and we don't want Derby to become
> big fat O-hm-cle, do we? =)
True, but multi-cpu/multi-core is spreading to smaller devices, as well. It
used to be a server-room thing, but now you find it in desktops and
even laptops. The segment where you can afford to ignore this
(even with a microscopic footprint) is quickly disappearing.
--
dt
Re: Releasing latches when waiting for locks. When and why?
Posted by Anders Morken <an...@stud.ntnu.no>.
Mike Matrigali:
> by single row update do you mean (obviously not exact syntax):
> update x = y where key = z
This one, yeah. ~100-byte rows, INTEGER primary keys, we update the
filler only. UPDATE thetable SET filler = <foo> WHERE key = <random number>;
> In the cursor case derby maintains an "internal" lock on the btree page
> so that it can optimize scanning. This lock allows the scan to maintain
> it's position without extra overhead on each next on the page.
We haven't considered the impact of cursors, maybe we should take a look
at that. Thanks for the tip. =)
> Do you have something to compare these numbers to. Maybe compared to
> the overall cost of Derby inserting a single row (not comitting), on the
> same machine. Basically would be interested in what is the current
> locking overhead in cpu cost per some standard statement/xact. I think
> when I looked at this awhile back locking/latching together was
> somewhere around 5% of
> a TPC/B like xact. Given that, making locking 0 would only give a 5%
> improvement, so never was that motivated to look at latching. But
> maybe other parts of the system/JVM have raised the ratio.
Knut Anders Hatlen has gathered a lot of interesting figures in
http://wiki.apache.org/db-derby/Derby1961ResourceUsage2 - well worth a
look and a bit of pondering. =)
The major benefit of reworking the lock manager is scalability - right
now it's pretty much single threaded, which is fine for a lot of the
scenarios Derby was written to perform in. However, for "benchmark
compliance" in a world of multicore desktops and servers, it may be
beneficial to work on Derby's scalability.
To maintain Derby's small footprint while expanding it to handle bigger
iron is one of the challenges here, and we don't want Derby to become
big fat O-hm-cle, do we? =)
> What java profiler do you use? Do you like it for working on Derby?
NetBeans' profiler, freely available from http://www.netbeans.org/ as an
add-on to the (also freely available) IDE.
> >I dunno if our report would be of any interest to you guys, but it's not
> >finished yet, and I'm not sure if it appropriate to post it just yet.
> I would be very interested in seeing the report.
At least we'll have to work a bit more on it before presenting it even
as a draft. But Knut Anders has measured many of the same things we've
measured and reported the juicy bits on the list and in the Wiki, so
you're not missing out on terribly much. =)
--
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?
Posted by Mike Matrigali <mi...@sbcglobal.net>.
Anders Morken wrote:
> Mike Matrigali:
>
>>Knut Anders Hatlen wrote:
>>
>>>Thanks Bryan, that could be the case. I have done some more
>>>investigation and it seems like the method is only called when a
>>>B-tree container is opened with a lock policy. It also seems like the
>>>B-tree containers always are opened with a null/NoLocking lock policy
>>>(regardless of isolation level) and therefore the method is never
>>>called.
>>
>>Derby uses data only locking, so it doesn't get locks on rows in the
>>btree. Instead it gets locks on the rows that the rows in the btree
>>point at.
>
>
> Well, this is exactly the stuff we (me and my partner in crime, Per
> Ottar, who lurks on this list but hasn't posted anything yet, afaik =)
> are investigating as part of our autumn project.
>
> We've taken some long hard looks at the lock manager, and we're
> convinced that there's a lot of potential for improvement in Derby lock
> management. Not that there's anything wrong with the approach taken in
> the current implementation - correctness first, optimization later. =)
>
> One of the things that we've observed is that on a single-row update
> transaction, a shared lock is obtained on a row in the B-tree container
> just before an exclusive lock is obtained on a row in the data
> container. Off the top of my head I can't remember if why figured out
> exactly why. =)
by single row update do you mean (obviously not exact syntax):
update x = y where key = z
or
update where current of in a cursor?
In the cursor case derby maintains an "internal" lock on the btree page
so that it can optimize scanning. This lock allows the scan to maintain
it's position without extra overhead on each next on the page.
>
>
>>Having said that it would be interesting if someone had time to
>>implement a higher performance latch implementation and plug it in
>>and see how much it helps. It would decrease the total time spent
>>in lock manager.
>
>
> We've actually considered doing that for fun, but as our goal right now
> is to produce a big honkin' report, not fix anything, we haven't. Still,
> it would probably give a quite significant benefit.
>
> Using a Java profiler on a reasonably modern X86 system we've found that
> while acquiring a Derby lock takes about 60-70 microseconds and a latch
> costs 50-60 microseconds in the non-contended (single thread) cases,
> acquiring and releasing a ReentrantLock available in Java 1.5 and up
> costs about 1,5 microseconds. A latch could in theory be about as cheap
> as a ReentrantLock, and on Java 1.5 and up it would make sense to base
> Latches on ReentrantLocks.
Do you have something to compare these numbers to. Maybe compared to
the overall cost of Derby inserting a single row (not comitting), on the
same machine. Basically would be interested in what is the current
locking overhead in cpu cost per some standard statement/xact. I think
when I looked at this awhile back locking/latching together was
somewhere around 5% of
a TPC/B like xact. Given that, making locking 0 would only give a 5%
improvement, so never was that motivated to look at latching. But
maybe other parts of the system/JVM have raised the ratio.
What java profiler do you use? Do you like it for working on Derby?
>
> However, just separating the latch data structures from the lock data
> structures could give significant scalability benefits, as right now the
> latches and locks are all stored in the same hash tables, causing
> significant monitor contention in multithreaded cases.
>
> I dunno if our report would be of any interest to you guys, but it's not
> finished yet, and I'm not sure if it appropriate to post it just yet.
I would be very interested in seeing the report.
> Still, it's interesting stuff we're digging up, and it's interesting to
> see how you guys investigate this. =)
>
Re: Releasing latches when waiting for locks. When and why?
Posted by Anders Morken <an...@stud.ntnu.no>.
Mike Matrigali:
> Knut Anders Hatlen wrote:
> >
> >Thanks Bryan, that could be the case. I have done some more
> >investigation and it seems like the method is only called when a
> >B-tree container is opened with a lock policy. It also seems like the
> >B-tree containers always are opened with a null/NoLocking lock policy
> >(regardless of isolation level) and therefore the method is never
> >called.
> Derby uses data only locking, so it doesn't get locks on rows in the
> btree. Instead it gets locks on the rows that the rows in the btree
> point at.
Well, this is exactly the stuff we (me and my partner in crime, Per
Ottar, who lurks on this list but hasn't posted anything yet, afaik =)
are investigating as part of our autumn project.
We've taken some long hard looks at the lock manager, and we're
convinced that there's a lot of potential for improvement in Derby lock
management. Not that there's anything wrong with the approach taken in
the current implementation - correctness first, optimization later. =)
One of the things that we've observed is that on a single-row update
transaction, a shared lock is obtained on a row in the B-tree container
just before an exclusive lock is obtained on a row in the data
container. Off the top of my head I can't remember if why figured out
exactly why. =)
> Having said that it would be interesting if someone had time to
> implement a higher performance latch implementation and plug it in
> and see how much it helps. It would decrease the total time spent
> in lock manager.
We've actually considered doing that for fun, but as our goal right now
is to produce a big honkin' report, not fix anything, we haven't. Still,
it would probably give a quite significant benefit.
Using a Java profiler on a reasonably modern X86 system we've found that
while acquiring a Derby lock takes about 60-70 microseconds and a latch
costs 50-60 microseconds in the non-contended (single thread) cases,
acquiring and releasing a ReentrantLock available in Java 1.5 and up
costs about 1,5 microseconds. A latch could in theory be about as cheap
as a ReentrantLock, and on Java 1.5 and up it would make sense to base
Latches on ReentrantLocks.
However, just separating the latch data structures from the lock data
structures could give significant scalability benefits, as right now the
latches and locks are all stored in the same hash tables, causing
significant monitor contention in multithreaded cases.
I dunno if our report would be of any interest to you guys, but it's not
finished yet, and I'm not sure if it appropriate to post it just yet.
Still, it's interesting stuff we're digging up, and it's interesting to
see how you guys investigate this. =)
--
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?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Olav Sandstaa <Ol...@Sun.COM> writes:
> Knut Anders Hatlen wrote:
[...]
> This is impressive, and much higher than what I would have expected by
> just moving the latching out of the lock manager.
>
>> I would guess that the improvement is mainly caused by
>>
>> a) Less contention on the lock table since the latches no longer
>> were stored in the lock table.
>>
>> b) Less context switches because the fair queue in the lock manager
>> wasn't used, allowing clients to process more transactions before
>> they needed to give the CPU to another thread.
>>
>
> In addition I also would guess there is a third positive contribution
> to the increased performance by this patch:
>
> c) less CPU spent in the lock manager, particularly due to reduced
> use of hash tables.
Yes, I believe this is true. I guess this is the main reason for the
increase in the one-client case (3-4%). In the test, each transaction
latches four pages (three index pages and one data page), so the patch
removes at least 8 hash accesses per transaction.
>> I hadn't thought about b) before, but I think it sounds reasonable
>> that using a fair wait queue for latches would slow things down
>> considerably if there is a contention point like the root node of a
>> B-tree. I also think it sounds reasonable that the latching doesn't
>> use a fair queue, since the latches are held for such a short time
>> that starvation is not likely to be a problem.
>>
>
> I agree that b) is likely a major contributor to the performance
> improvement you see. Would this also be the case if you run in
> client-server mode? In client-server mode you would anyway get a
> context switch for each operation Derby do since the worker thread
> would block on network IO. Have you tried the same test to see what
> performance improvement you get when running in client-server mode
> with this patch?
I have run the same test in client/server mode, and the resulting
graph is attached. As you suggested, the improvement was not as big as
in embedded mode, but there's still more than 50% increase in the
throughput for 30 concurrent clients.
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Olav Sandstaa <Ol...@Sun.COM>.
Knut Anders Hatlen wrote:
> To see the effect of this change, I tested the patch on a dual-CPU
> machine with the test client from DERBY-1961 running single-record
> select operations. Derby was running in embedded mode, and the entire
> database was in the page cache. The results for 1 to 100 concurrent
> clients compared to the code in trunk are shown in the attached graph
> (latch.png).
>
> For one client, there was not much gained, but for two clients, the
> throughput increased 20% compared to trunk. For three clients, the
> increase was 40%, and it was 145% for 30 clients. This was a lot more
> than I expected! I also ran a TPC-B like test with 20 clients and saw
> a 17% increase in throughput (disk write cache was enabled).
>
This is impressive, and much higher than what I would have expected by
just moving the latching out of the lock manager.
> I would guess that the improvement is mainly caused by
>
> a) Less contention on the lock table since the latches no longer
> were stored in the lock table.
>
> b) Less context switches because the fair queue in the lock manager
> wasn't used, allowing clients to process more transactions before
> they needed to give the CPU to another thread.
>
In addition I also would guess there is a third positive contribution to
the increased performance by this patch:
c) less CPU spent in the lock manager, particularly due to reduced use
of hash tables.
> I hadn't thought about b) before, but I think it sounds reasonable
> that using a fair wait queue for latches would slow things down
> considerably if there is a contention point like the root node of a
> B-tree. I also think it sounds reasonable that the latching doesn't
> use a fair queue, since the latches are held for such a short time
> that starvation is not likely to be a problem.
>
I agree that b) is likely a major contributor to the performance
improvement you see. Would this also be the case if you run in
client-server mode? In client-server mode you would anyway get a context
switch for each operation Derby do since the worker thread would block
on network IO. Have you tried the same test to see what performance
improvement you get when running in client-server mode with this patch?
Olav
Re: Releasing latches when waiting for locks. When and why?
Posted by 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?
Posted by 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?
Posted by 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
Re: Releasing latches when waiting for locks. When and why?
Posted by 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?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Suresh Thalamati <su...@gmail.com> writes:
> If we are removing Latching out of LockManager for perfromance
> reasons, my preference also would be to handle at the page level,
> instead of having yet another indirection.
>
> As Mike mentioned , it would be nice to have a VTI that will show the
> latches in the system.
It should be doable to write a VTI which scans the page cache and
shows which pages are latched and by whom they are latched. With that
approach it would probably be difficult to ensure that we get a
consistent view since the latches may change while we're scanning the
cache. But perhaps that's good enough for debugging purposes?
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Suresh Thalamati <su...@gmail.com>.
Mike Matrigali wrote:
>
>
> Daniel John Debrunner wrote:
>
>> Knut Anders Hatlen wrote:
>>
>>> Mike Matrigali <mi...@sbcglobal.net> writes:
>>>
< snip .?
>>
>> I'm not so sure. If it's simpler to keep page latching at the page
>> level, then it would be better to remove the added complexity from the
>> lock manager. What's the current state of IDEs/debuggers tracking down
>> java synchronization deadlocks? Seems a better place to solve the
>> problem.
>
> And also does it help track down a deadlock that is half java
> synchonization and half derby lock wait?
>
I doubt IDES/Debuggers will helps if a user really hits a LATCH/LOCK
or a LATCH/LATCH deadlock. Most of the time I would think they are not
easily reproducible cases; All that user going to tell is DERBY is
acting weird/frozen.
Recent jvms (jdk142 onwards) do tell if there is dead-lock on the
monitor on a stack dump. I hope the stacks will give us some clues,
if the dead locks involves onlt latches or locks also.
If it is embedded , say in APP server I wonder how easy to get a
stack dump or how big it is going to be!
If some one is wondering , does these deadlocks really happen, I
found one : http://issues.apache.org/jira/browse/DERBY-1189
(but Mike seems to have got luckey with the repro)
Lock : LATCH, T1, Page(35,Container(0, 1728))
Waiting XID : {385920, BaseContainerHandle:(Container(0, 1728))} ,
APP, CALL S
YSCS_UTIL.SYSCS_INPLACE_COMPRESS_TABLE('APP', 'T1', 1, 1, 1)
Granted XID : {385920, BaseContainerHandle:(Container(0, 1728))}
. The selected victim is XID : 385920.
If we are removing Latching out of LockManager for perfromance
reasons, my preference also would be to handle at the page level,
instead of having yet another indirection.
As Mike mentioned , it would be nice to have a VTI that will show the
latches in the system.
Thanks
-suresh
Re: Releasing latches when waiting for locks. When and why?
Posted by Mike Matrigali <mi...@sbcglobal.net>.
Daniel John Debrunner wrote:
> 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'm not so sure. If it's simpler to keep page latching at the page
> level, then it would be better to remove the added complexity from the
> lock manager. What's the current state of IDEs/debuggers tracking down
> java synchronization deadlocks? Seems a better place to solve the problem.
And also does it help track down a deadlock that is half java
synchonization and half derby lock wait?
>
> Dan.
>
>
>
Re: Releasing latches when waiting for locks. When and why?
Posted by Daniel John Debrunner <dj...@apache.org>.
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'm not so sure. If it's simpler to keep page latching at the page
level, then it would be better to remove the added complexity from the
lock manager. What's the current state of IDEs/debuggers tracking down
java synchronization deadlocks? Seems a better place to solve the problem.
Dan.
Re: Releasing latches when waiting for locks. When and why?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
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.
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Mike Matrigali <mi...@sbcglobal.net>.
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.
Dyre.Tjeldvoll@Sun.COM wrote:
> Knut Anders Hatlen <Kn...@Sun.COM> writes:
>
>
>>Daniel John Debrunner <dj...@apache.org> writes:
>>
>>
>>>Knut Anders Hatlen wrote:
>>>
>>>>Mike Matrigali <mi...@sbcglobal.net> writes:
>>>>
>>>>
>>>>>Having said that it would be interesting if someone had time to
>>>>>implement a higher performance latch implementation and plug it in
>>>>>and see how much it helps. It would decrease the total time spent
>>>>>in lock manager.
>>>>
>>>>Ok, a new experiment: I removed the calls to LockFactory.latchObject()
>>>>and LockFactory.unlatch() in BasePage. Instead, I let BasePage check
>>>>manually whether it was latched and use wait/notifyAll if it was. The
>>>>patch (which is very simple) is attached.
>>>>
>>>
>>>The original decision to use the lock manager for the latches was to
>>>enable easier debugging of deadlocks during the early development of
>>>the store code. A local latch implementation, like Knut Anders made,
>>>does make a lot of sense, but does leave derby open to undetectable
>>>deadlocks. Given the performance gains it probably is worth the risk,
>>>especially since I don't think we've seen a problem with latch
>>>ordering for many years.
>>
>>Thanks to you all for your input! I have logged DERBY-2107 and will
>>start working on a local latch implementation along the lines of the
>>patch I sent out.
>
>
> Being able to detect/debug deadlocks would be very convenient. Isn't it
> possible to write code for this that can be enabled if one
> suspects a deadlock, but has no or minimal performance impact when disabled?
>
Re: Releasing latches when waiting for locks. When and why?
Posted by Dy...@Sun.COM.
Knut Anders Hatlen <Kn...@Sun.COM> writes:
> Daniel John Debrunner <dj...@apache.org> writes:
>
>> Knut Anders Hatlen wrote:
>>> Mike Matrigali <mi...@sbcglobal.net> writes:
>>>
>>>> Having said that it would be interesting if someone had time to
>>>> implement a higher performance latch implementation and plug it in
>>>> and see how much it helps. It would decrease the total time spent
>>>> in lock manager.
>>>
>>> Ok, a new experiment: I removed the calls to LockFactory.latchObject()
>>> and LockFactory.unlatch() in BasePage. Instead, I let BasePage check
>>> manually whether it was latched and use wait/notifyAll if it was. The
>>> patch (which is very simple) is attached.
>>>
>>
>> The original decision to use the lock manager for the latches was to
>> enable easier debugging of deadlocks during the early development of
>> the store code. A local latch implementation, like Knut Anders made,
>> does make a lot of sense, but does leave derby open to undetectable
>> deadlocks. Given the performance gains it probably is worth the risk,
>> especially since I don't think we've seen a problem with latch
>> ordering for many years.
>
> Thanks to you all for your input! I have logged DERBY-2107 and will
> start working on a local latch implementation along the lines of the
> patch I sent out.
Being able to detect/debug deadlocks would be very convenient. Isn't it
possible to write code for this that can be enabled if one
suspects a deadlock, but has no or minimal performance impact when disabled?
--
dt
Re: Releasing latches when waiting for locks. When and why?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Daniel John Debrunner <dj...@apache.org> writes:
> Knut Anders Hatlen wrote:
>> Mike Matrigali <mi...@sbcglobal.net> writes:
>>
>>> Having said that it would be interesting if someone had time to
>>> implement a higher performance latch implementation and plug it in
>>> and see how much it helps. It would decrease the total time spent
>>> in lock manager.
>>
>> Ok, a new experiment: I removed the calls to LockFactory.latchObject()
>> and LockFactory.unlatch() in BasePage. Instead, I let BasePage check
>> manually whether it was latched and use wait/notifyAll if it was. The
>> patch (which is very simple) is attached.
>>
>
> The original decision to use the lock manager for the latches was to
> enable easier debugging of deadlocks during the early development of
> the store code. A local latch implementation, like Knut Anders made,
> does make a lot of sense, but does leave derby open to undetectable
> deadlocks. Given the performance gains it probably is worth the risk,
> especially since I don't think we've seen a problem with latch
> ordering for many years.
Thanks to you all for your input! I have logged DERBY-2107 and will
start working on a local latch implementation along the lines of the
patch I sent out.
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Daniel John Debrunner <dj...@apache.org>.
Knut Anders Hatlen wrote:
> Mike Matrigali <mi...@sbcglobal.net> writes:
>
>> Having said that it would be interesting if someone had time to
>> implement a higher performance latch implementation and plug it in
>> and see how much it helps. It would decrease the total time spent
>> in lock manager.
>
> Ok, a new experiment: I removed the calls to LockFactory.latchObject()
> and LockFactory.unlatch() in BasePage. Instead, I let BasePage check
> manually whether it was latched and use wait/notifyAll if it was. The
> patch (which is very simple) is attached.
>
The original decision to use the lock manager for the latches was to
enable easier debugging of deadlocks during the early development of the
store code. A local latch implementation, like Knut Anders made, does
make a lot of sense, but does leave derby open to undetectable
deadlocks. Given the performance gains it probably is worth the risk,
especially since I don't think we've seen a problem with latch ordering
for many years.
Dan.
Re: Releasing latches when waiting for locks. When and why?
Posted by Dy...@Sun.COM.
Knut Anders Hatlen <Kn...@Sun.COM> writes:
> For one client, there was not much gained, but for two clients, the
> throughput increased 20% compared to trunk. For three clients, the
> increase was 40%, and it was 145% for 30 clients. This was a lot more
> than I expected! I also ran a TPC-B like test with 20 clients and saw
> a 17% increase in throughput (disk write cache was enabled).
Wow!! :)
>
> I would guess that the improvement is mainly caused by
>
> a) Less contention on the lock table since the latches no longer
> were stored in the lock table.
>
> b) Less context switches because the fair queue in the lock manager
> wasn't used, allowing clients to process more transactions before
> they needed to give the CPU to another thread.
>
> I hadn't thought about b) before, but I think it sounds reasonable
> that using a fair wait queue for latches would slow things down
> considerably if there is a contention point like the root node of a
> B-tree. I also think it sounds reasonable that the latching doesn't
> use a fair queue, since the latches are held for such a short time
> that starvation is not likely to be a problem.
>From your patch it seems like moving latching out of the lock manager
makes the code _more_ readable AND faster. Seems like a win-win
situation :)
--
dt
Re: Releasing latches when waiting for locks. When and why?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Mike Matrigali <mi...@sbcglobal.net> writes:
> Having said that it would be interesting if someone had time to
> implement a higher performance latch implementation and plug it in
> and see how much it helps. It would decrease the total time spent
> in lock manager.
Ok, a new experiment: I removed the calls to LockFactory.latchObject()
and LockFactory.unlatch() in BasePage. Instead, I let BasePage check
manually whether it was latched and use wait/notifyAll if it was. The
patch (which is very simple) is attached.
To see the effect of this change, I tested the patch on a dual-CPU
machine with the test client from DERBY-1961 running single-record
select operations. Derby was running in embedded mode, and the entire
database was in the page cache. The results for 1 to 100 concurrent
clients compared to the code in trunk are shown in the attached graph
(latch.png).
For one client, there was not much gained, but for two clients, the
throughput increased 20% compared to trunk. For three clients, the
increase was 40%, and it was 145% for 30 clients. This was a lot more
than I expected! I also ran a TPC-B like test with 20 clients and saw
a 17% increase in throughput (disk write cache was enabled).
I would guess that the improvement is mainly caused by
a) Less contention on the lock table since the latches no longer
were stored in the lock table.
b) Less context switches because the fair queue in the lock manager
wasn't used, allowing clients to process more transactions before
they needed to give the CPU to another thread.
I hadn't thought about b) before, but I think it sounds reasonable
that using a fair wait queue for latches would slow things down
considerably if there is a contention point like the root node of a
B-tree. I also think it sounds reasonable that the latching doesn't
use a fair queue, since the latches are held for such a short time
that starvation is not likely to be a problem.
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Mike Matrigali <mi...@sbcglobal.net>.
Knut Anders Hatlen wrote:
>
> Thanks Bryan, that could be the case. I have done some more
> investigation and it seems like the method is only called when a
> B-tree container is opened with a lock policy. It also seems like the
> B-tree containers always are opened with a null/NoLocking lock policy
> (regardless of isolation level) and therefore the method is never
> called.
Derby uses data only locking, so it doesn't get locks on rows in the
btree. Instead it gets locks on the rows that the rows in the btree
point at.
>
> However, I made an interesting discovery in
> B2IRowLocking3.lockRowOnPage(). It uses the following procedure for
> locking a row while holding a latch:
>
> 1) Try to lock the row with timeout == NOWAIT.
> 2) If the lock couldn't be obtained without waiting, manually
> release the latch and try to lock the row with a normal timeout.
>
> I don't see why this couldn't be done similarly in the few cases that
> maybe some time in the future will need that functionality. Perhaps we
> could change those calls and reduce some of the complexity of the lock
> manager? I generally prefer to optimize for the most common and/or
> least complex cases, and let the more complex cases pay the cost of
> extra complexity themselves. If the more complex cases are only for
> possible future use, I think that point is even more valid.
>
> Also, I'm not sure that using the lock manager for latching is optimal
> in the first place. The description of Derby's B-tree implementation
> [1], says that the implementation is similar to ARIES/IM [2].
> According to the ARIES/IM report,
>
> "Acquiring a latch is cheaper than acquiring a lock (in the
> no-conflict case, 10s of instructions versus 100s of instructions),
> because the latch control information is always in virtual memory in
> a fixed place, and direct addressability to the latch information is
> possible given the latch name. Since each transaction holds at most
> 2 or 3 latches simultaneously (...), the latch request blocks can be
> permanently allocated to each transaction and initialized with
> transaction ID, etc. right at the start of that transaction. On the
> other hand, storage for individual locks may have to be acquired,
> formatted, and released dynamically, and more instructions need to
> be executed to acquire and release locks."
The decision to uses the lockmanager in derby was definitely not a
performance decision. It was a decsion to reuse existing code, and
leave the optimization to later. Along the way quite a few
optimizations were added to improve the latch path through the
lockmanger. I have to also say that from the supportability/ease of
development it has been
nice to have latches and locks in the same space so that latch/lock
deadlocks/waits (which are usually bugs) are automatically caught and
diagnosed using existing lock manager tools/error reporting. Another
factor was that we wanted to continue to have 100% pure java
implementation so we didn't have the access to the standard test/set
instructions other implementation might have. But I am sure one
could get pretty close.
Having said that it would be interesting if someone had time to
implement a higher performance latch implementation and plug it in
and see how much it helps. It would decrease the total time spent
in lock manager.
>
> In Derby, latching is cheaper than locking, but not nearly as cheap as
> the ARIES/IM report suggests. I have done some measurements and come
> to the conclusion that setting one latch is about half the cost of
> setting one lock. The reason why latching is so expensive in Derby, is
> that it basically uses the same code as the locking, and therefore
> gets some of the extra overhead caused by the locks' dynamic nature. I
> think it would be a great improvement if latching of pages didn't have
> to go through the lock table and instead just set a flag on the page
> object.
>
> Footnotes:
> [1] http://db.apache.org/derby/papers/btree_package.html
>
> [2] http://www.almaden.ibm.com/u/mohan/RJ6846.pdf
>
Re: Releasing latches when waiting for locks. When and why?
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Bryan Pendleton <bp...@amberpoint.com> writes:
>> When this method is used, the specified latch will be
>> released if the lock cannot be obtained immediately, and that page
>> will be re-latched when the lock has been obtained.
>
> I'm just guessing here ...
>
> I think that there are some fairly advanced Btree traversal algorithms,
> in particular situations in which you are reading backward through a
> Btree which may be undergoing concurrent structural modifications by
> others, in which a primitive operation like the one you describe is crucial.
>
> So perhaps this method was included in the Store in preparation for some
> access method techniques which haven't yet been implemented?
Thanks Bryan, that could be the case. I have done some more
investigation and it seems like the method is only called when a
B-tree container is opened with a lock policy. It also seems like the
B-tree containers always are opened with a null/NoLocking lock policy
(regardless of isolation level) and therefore the method is never
called.
However, I made an interesting discovery in
B2IRowLocking3.lockRowOnPage(). It uses the following procedure for
locking a row while holding a latch:
1) Try to lock the row with timeout == NOWAIT.
2) If the lock couldn't be obtained without waiting, manually
release the latch and try to lock the row with a normal timeout.
I don't see why this couldn't be done similarly in the few cases that
maybe some time in the future will need that functionality. Perhaps we
could change those calls and reduce some of the complexity of the lock
manager? I generally prefer to optimize for the most common and/or
least complex cases, and let the more complex cases pay the cost of
extra complexity themselves. If the more complex cases are only for
possible future use, I think that point is even more valid.
Also, I'm not sure that using the lock manager for latching is optimal
in the first place. The description of Derby's B-tree implementation
[1], says that the implementation is similar to ARIES/IM [2].
According to the ARIES/IM report,
"Acquiring a latch is cheaper than acquiring a lock (in the
no-conflict case, 10s of instructions versus 100s of instructions),
because the latch control information is always in virtual memory in
a fixed place, and direct addressability to the latch information is
possible given the latch name. Since each transaction holds at most
2 or 3 latches simultaneously (...), the latch request blocks can be
permanently allocated to each transaction and initialized with
transaction ID, etc. right at the start of that transaction. On the
other hand, storage for individual locks may have to be acquired,
formatted, and released dynamically, and more instructions need to
be executed to acquire and release locks."
In Derby, latching is cheaper than locking, but not nearly as cheap as
the ARIES/IM report suggests. I have done some measurements and come
to the conclusion that setting one latch is about half the cost of
setting one lock. The reason why latching is so expensive in Derby, is
that it basically uses the same code as the locking, and therefore
gets some of the extra overhead caused by the locks' dynamic nature. I
think it would be a great improvement if latching of pages didn't have
to go through the lock table and instead just set a flag on the page
object.
Footnotes:
[1] http://db.apache.org/derby/papers/btree_package.html
[2] http://www.almaden.ibm.com/u/mohan/RJ6846.pdf
--
Knut Anders
Re: Releasing latches when waiting for locks. When and why?
Posted by Mike Matrigali <mi...@sbcglobal.net>.
Bryan is right. This is exactly the kind of access that Btree's need,
and why the interface was there in the first place. My dim memory is
that for some reason it didn't work right for btree's so btree's
hand coded it - but now I don't remember the details.
Bryan Pendleton wrote:
>> When this method is used, the specified latch will be
>> released if the lock cannot be obtained immediately, and that page
>> will be re-latched when the lock has been obtained.
>
>
> I'm just guessing here ...
>
> I think that there are some fairly advanced Btree traversal algorithms,
> in particular situations in which you are reading backward through a
> Btree which may be undergoing concurrent structural modifications by
> others, in which a primitive operation like the one you describe is
> crucial.
>
> So perhaps this method was included in the Store in preparation for some
> access method techniques which haven't yet been implemented?
>
> thanks,
>
> bryan
>
>
>
>
Re: Releasing latches when waiting for locks. When and why?
Posted by Bryan Pendleton <bp...@amberpoint.com>.
> When this method is used, the specified latch will be
> released if the lock cannot be obtained immediately, and that page
> will be re-latched when the lock has been obtained.
I'm just guessing here ...
I think that there are some fairly advanced Btree traversal algorithms,
in particular situations in which you are reading backward through a
Btree which may be undergoing concurrent structural modifications by
others, in which a primitive operation like the one you describe is crucial.
So perhaps this method was included in the Store in preparation for some
access method techniques which haven't yet been implemented?
thanks,
bryan