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 Fri, 17 Aug 2007 12:40:30 GMT

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

Knut Anders Hatlen commented on DERBY-2991:
-------------------------------------------

> - 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.

B-tree scans lock the leaf node on which they are currently positioned
(in your case the root node is probably also a leaf node) so that they
don't have to reposition if they lose the latch on the page. The scan
always releases the latch on the B-tree leaf if it has to wait for a
row lock. The latch is released in order to prevent deadlocks. Since
the page is not latched while the scan waits for the row lock, the row
might have moved to another page in the index and therefore the scan
would have to start a new search to reposition on the row. The shared
lock on the B-tree leaf ensures that the row is not moved off the
current page so that the repositioning isn't needed. Since the lock on
the leaf node is shared, it allows more concurrency than if the
(exclusive) latch were kept. But since the lock on the leaf is more or
less like a shared latch, there's still a possibility for deadlocks if
the B-tree needs to be restructured (like the split deadlock you're
seeing).

> Would it be possible to ensure the consistency of the select without
> locking the index?

I think so, if the select transaction had a way to reposition the scan
after it got the row lock it was waiting for. The current code just
checks the leaf page again to find the row, since it knows it can't
have moved to another page. If there weren't a lock on the index page,
the scan would need to detect that the row had moved and start a new
search from the root node.

I don't know enough about this area of the code to say whether or not
it is doable, or how much work it is. Hopefully, someone more
knowledgeable will chime in with more details.

> Index split deadlock
> --------------------
>
>                 Key: DERBY-2991
>                 URL: https://issues.apache.org/jira/browse/DERBY-2991
>             Project: Derby
>          Issue Type: Bug
>          Components: Store
>    Affects Versions: 10.2.2.0
>         Environment: Windows XP, Java 6
>            Reporter: Bogdan Calmac
>         Attachments: derby.log, InsertSelectDeadlock.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 10.2.2.0 and 10.3.1.4 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.


Mime
View raw message