db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Knut Anders Hatlen (JIRA)" <j...@apache.org>
Subject [jira] Updated: (DERBY-2991) Index split deadlock
Date Fri, 28 Nov 2008 10:45:44 GMT

     [ https://issues.apache.org/jira/browse/DERBY-2991?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel

Knut Anders Hatlen updated DERBY-2991:

    Attachment: d2991-preview-1c.stat

Here's a new update (preview-1c).

In this patch, I have removed the locking of the scan protection
handle completely. This also led to the removal of some debug code
used to simulate wait and/or deadlock when locking the scan, and
therefore the test cases in T_b2i that expected this debug code to
run also had to be removed.

I ran some simple performance tests to get an impression of how the
performance is affected (used o.a.derbyTesting.perf.clients.Runner).

For single-record selects on primary key (-load sr_select) the
throughput was increased by 5-10%. I suppose this improvement is seen
because we no longer spend any time on obtaining and releasing the
scan locks. And since there's no saving of position or repositioning
happening with this load, no extra overhead is introduced.

For 1000x10000 index joins (-load index_join) the throughput was down
15% (single-threaded) to 45% (multi-threaded). These operations
release the latch on the leaf frequently (once every 16 rows in the
index scans), which would mean that a costly renavigation in the
B-tree would happen very often. Additionally, the renavigation would
increase the contention on the root node of the B-tree, which is
probably why the performance drop is greater in the multi-threaded

Since some operations may see a significant performance drop, I think
the previously discussed optimization to prevent unnecessary
renavigation needs to be implemented before we can consider the patch
ready for commit.

The patch is starting to get big, but I'm not sure how to split it up
in smaller increments without temporarily degrading the performance of
the trunk. The patch currently removes a lot more code than it adds,
though, so the size of the patch doesn't tell the whole truth. The
inserted/deleted ratio is about 1/7, as seen by

$ svn diff | diffstat | tail -1
 27 files changed, 196 insertions(+), 1410 deletions(-)

I'll be away next week and will probably not have much time to work on
this issue, but I will read my mail and try to answer questions.

> Index split deadlock
> --------------------
>                 Key: DERBY-2991
>                 URL: https://issues.apache.org/jira/browse/DERBY-2991
>             Project: Derby
>          Issue Type: Bug
>          Components: Store
>    Affects Versions:,
>         Environment: Windows XP, Java 6
>            Reporter: Bogdan Calmac
>            Assignee: Knut Anders Hatlen
>         Attachments: d2991-preview-1a.diff, d2991-preview-1a.stat, d2991-preview-1b.diff,
d2991-preview-1b.stat, d2991-preview-1c.diff, d2991-preview-1c.stat, derby.log, InsertSelectDeadlock.java,
Repro2991.java, stacktraces_during_deadlock.txt
> After doing dome research on the mailing list, it appears that the index split deadlock
is a known behaviour, so I will start by describing the theoretical problem first and then
follow with the details of my test case.
> If you have concurrent select and insert transactions on the same table, the observed
locking behaviour is as follows:
>  - the select transaction acquires an S lock on the root block of the index and then
waits for an S lock on some uncommitted row of the insert transaction
>  - the insert transaction acquires X locks on the inserted records and if it needs to
do an index split creates a sub-transaction that tries to acquire an X lock on the root block
of the index
> In summary: INDEX LOCK followed by ROW LOCK + ROW LOCK followed by INDEX LOCK = deadlock
> In the case of my project this is an important issue (lack of concurrency after being
forced to use table level locking) and I would like to contribute to the project and fix this
issue (if possible). I was wondering if someone that knows the code can give me a few pointers
on the implications of this issue:
>  - Is this a limitation of the top-down algorithm used?
>  - Would fixing it require to use a bottom up algorithm for better concurrency (which
is certainly non trivial)?
>  - Trying to break the circular locking above, I would first question why does the select
transaction need to acquire (and hold) a lock on the root block of the index. Would it be
possible to ensure the consistency of the select without locking the index?
> -----
> The attached test (InsertSelectDeadlock.java) tries to simulate a typical data collection
application, it consists of: 
>  - an insert thread that inserts records in batch 
>  - a select thread that 'processes' the records inserted by the other thread: 'select
* from table where id > ?' 
> The derby log provides detail about the deadlock trace and stacktraces_during_deadlock.txt
shows that the inser thread is doing an index split.
> The test was run on and with identical behaviour.
> Thanks,
> Bogdan Calmac.

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message