[jira] Commented: (DERBY-2991) Index split deadlock

["Knut Anders Hatlen (JIRA)" <ji...@apache.org>]

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

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

I'm hoping to find some time to investigate this issue.

So far, only one suggestion for how we can fix this has come up. The
basic idea is that we don't set the scan lock to protect the scan
position, and instead we reposition the scan if we need to wait for a
lock and therefore have released the latch on the index leaf.

Most of the discussion has been about how we can avoid the
repositioning when it's not needed, and I think we have a reasonably
good understanding of how we can do that by having a (non-persistent)
field in the page objects that give us a version number after which it
is guaranteed that no row has moved off the page.

Earlier in the discussion we have said that this field should have a
special value to tell that it's uninitialized when the page is faulted
in to the page cache. After some more thinking, I now believe it would
be more reasonable to initialize it to the current version of the
page. Otherwise, the field would be uninitialized for most of the
cached pages, and it wouldn't help us avoiding repositioning most of
the time.

What hasn't been discussed yet, is how we can do the repositioning
when we don't have the scan lock. Øystein mentioned that the scan
could copy the key when it needs to wait for a lock, and use the key
to reposition itself in the B-tree. I think that sounds like a good
approach, but there are some things that are not quite clear to me:

1) Would copying the key work for non-unique indexes as well? I guess
so since the non-unique indexes seem to append the RecordId to the
key.

2) How stable are the RecordIds? Can they be changed by other
operations than compress table?

3) If the isolation level is READ_COMMITTED or higher, the open scans
would have an intentional read lock on the table, so even without the
scan locks compress table shouldn't be able to change the RecordIds
while a scan is waiting for a lock (the intentional read lock should
block compress table when it attempts to write lock the table). But
would this work in READ_UNCOMMITTED? Or rather, does it work correctly
in READ_UNCOMMITTED today? READ_UNCOMMITTED doesn't set shared locks,
so I would assume that it doesn't set any shared scan locks either.

Comments and suggestions would be appreciated. I'll do some more
digging and report back with my findings.

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