db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Øystein Grøvlen (JIRA) <j...@apache.org>
Subject [jira] Commented: (DERBY-2991) Index split deadlock
Date Fri, 16 Nov 2007 04:53:43 GMT

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

Øystein Grøvlen commented on DERBY-2991:

See the analysis made by Knut Anders above (17/Aug/07).  This is a deadlock between an index
scan that has shared locked a special row of the page to avoid that the row it is waiting
for is moved to another page.  When another transaction needs to split the page, it creates
a deadlock since the splitter needs this special lock in order to perform the split.  Hence,
I think all isolation levels except READ UNCOMMITTED will have this problem.   (Since for
all other isolation levels the scanner will have to wait for the exclusive lock of the inserter).

As Knut Anders say, this deadlock could be avoided if the scanner did not lock this special
row, but instead had some way to detect that the row has moved, and then renavigate from the
root in such cases.  I would think something similar happens during rollback where an index
 row may have moved due to page splits between do and undo.  Maybe something similar could
be done here.  I think there are parts to this:

  1. When a scan needs to wait for a lock, instead of locking this special row, it copies
the key of the row so that when it has acquired the lock it is waiting for, it can restart
the scan using this key.  

  2. In order to detect when a renavigation is needed, the page needs to have some kind of
state id that indicates whether a renavigation may be needed.  That is, should some row move
off the page or in other ways have their address change, the state id will be incremented.
 This way the scanner, by copying the current state id before it is suspended, can detect
whether the page has changed.  (One need to consider whether this state id is something that
needs to be persisted on the page or whether it can just reside in memory.  It depends on
whether it may occur that the page is no longer in the page cache when the scan resumes.)


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