db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "John H. Embretsen (JIRA)" <j...@apache.org>
Subject [jira] Commented: (DERBY-2991) Index split deadlock
Date Fri, 03 Aug 2007 12:35:53 GMT

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

John H. Embretsen commented on DERBY-2991:

This is an interesting case which reminds me (but is different from) a deadlock issue I encountered
in a long-running test not so long ago. I was not able to reproduce the deadlock, but we suspect
that there may be a bug in the code that creates the deadlock message about the lock cycles,
see DERBY-2877 for details.

This test (InsertSelectDeadlock.java) is interesting because you get a lock timeout message
rather than a deadlock message (even if you add a deadlockTimeout property with a lower value
than the waitTimeout property - I've tried), although in practice this is a deadlock. 

Also, even if derby.language.logStatementText is set to true (I edited the test class to do
that), you don't get any more information about the offending statement which (presumably)
holds an exclusive lock on the index root (1,1).

Here's the relevant information extracted from the derby.log Bogdan attached:

*** The following row is the victim ***
279       |ROW          |S   |0        |(1,7)   |WAIT |NULL               |
*** The above row is the victim ***
269       |ROW          |X   |1        |(1,7)   |GRANT|NULL               |
282       |ROW          |X   |0        |(1,1)   |WAIT |SQL070802115706620 |
279       |ROW          |S   |1        |(1,1)   |GRANT|SQL070802115706620 |

(I excluded things like tabletype (always T) and tablename (always TRACK_EVENT)).

The transactions above are probably:

XID 279: select * from TRACK_EVENT where ID > ?
XID 269: insert into TRACK_EVENT values (?,?,?,?,?,?,?,?,?,?,?,?,?,?)
XID 282: [index btree split?]

We are assuming (based on the stack traces) that XID 269 has spawned another transaction,
XID 282, which is trying to modify the index, but is not allowed to because XID 279 is already
holding an S (Shared) lock on it. I guess derby does not recognize this as a deadlock because
the index-modifying transaction has a completely different transaction number. So, in systems
that don't have deadlockTrace enabled, deadlocks may be camouflaged as lock wait timeouts.

I was kind of hoping that this comment would help so that more people could understand these
issues, hence increasing the chances of getting them fixed (or, at the least, improving related
documentation). I'm sorry for not being able to work out a solution or provide answers to
Bogdan's questions at this point, but I'm hoping someone else will be assisting soon.

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