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] Commented: (DERBY-2991) Index split deadlock
Date Tue, 02 Dec 2008 16:12:46 GMT

    [ https://issues.apache.org/jira/browse/DERBY-2991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12652417#action_12652417

Knut Anders Hatlen commented on DERBY-2991:

I agree that the overhead would be acceptable if it had (almost) only
affected those situations where a deadlock could occur, but now
there's an overhead in other situations as well.

A B-tree scan may release the latch on the current leaf page in the
following situations:

1) When a lock cannot be obtained without waiting

2) When no more rows should be returned by the scan (current key >
stop key)

3) After a bulk fetch (where a bulk contains from 1 row to 16 rows)

4) When the end of the current leaf has been reached and the next leaf
has been latched

With the latest patch, we save the current position by key in (1) and
(3). In (2) it's not needed because the scan is complete and no
repositioning will ever be attempted. In (4) it's not needed since
we're now successfully positioned on the first row on the next page.

The only situation in which a deadlock can occur, is (1), but we
currently always reposition by renavigating the B-tree after having
saved the position by key, so the overhead is also seen in
(3). Unfortunately, almost any query that reads more than 16 rows from
an index will be hit by this.

I'm planning to update the experimental patch with the discussed
optimization so that we don't need to renavigate the B-tree when
repositioning in the common case. If that's successful, we can revisit
whether the patch should be split and reviewed/committed in smaller
pieces. If we have a proof of concept in place that shows that the
performance issues are solvable, it might be acceptable to commit a
partial solution that causes performance regressions for some
operations for a shorter period of time (a week or so) before we
commit the final patch.

> 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