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 Wed, 12 Nov 2008 14:05:44 GMT

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

Knut Anders Hatlen commented on DERBY-2991:

We already have code to save the position by key and reposition using
the saved key (methods savePosition() and reposition() in
BTreeScan). Currently, we only save the key on transaction borders so
that we can reposition a holdable cursor after a commit. This is
needed because transactions release all their locks on commit, scan
locks included.

I think it should be possible to use the same logic to save the
position within a transaction. The current position of an index scan
is stored in a BTreeRowPosition object, either as a Page/RecordId pair
which requires a scan protection lock, or as a key value. Every time
the access layer is reentered, reposition() is called which either
just reacquires the latch on the page (if there's a scan lock) or
repositions from the root of the B-tree (if there's no scan lock).

So I think that if we find a way to ensure that we always save the
position by key when we're about to release the latch on a leaf page
(either because we cannot obtain a lock immediately, or because we're
leaving the access layer), the repositioning code should work more or
less as it is.

I'm hoping that saving the key each time we release the latch doesn't
have a too heavy impact on single-threaded performance. For short
keys, it should be relatively cheap, and the cost of saving the key
may be outweighed by what we save by not having to maintain the scan
protection lock.

With the optimizations suggested for the repositioning in earlier
comments, I believe that the repositioning will not be more expensive
than today in the common case where the page hasn't been split.

I'd welcome any comments and suggestions on how to implement this.

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