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] Updated: (DERBY-2991) Index split deadlock
Date Tue, 16 Dec 2008 14:58:45 GMT

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

Knut Anders Hatlen updated DERBY-2991:

    Attachment: d2991-preview-1d.stat

Attaching a new preview patch (1d) that implements the optimization
which prevents the expensive repositioning when no rows have been
moved off the page. I haven't done any serious testing of the
correctness in all scenarios, I'm just posting it so that we can get
more information about the performance impact of saving the position.

As an initial test, I reran the index-join test that I mentioned
earlier and that showed a significant decrease in performance with the
preview-1c patch. With the preview-1d patch, I'm not able to see any
decrease (the numbers are actually slightly better with the 1d patch
than with trunk, though I'm not sure whether it's significant). Below
are the results for 1, 2, 4, 8 and 16 concurrent threads for the 1d
patch (rows prefixed with 'd2991') and trunk (rows prefixed with
'trunk'). The AVG_TPS column shows the number of transactions per
second, all configurations were run 30 times (each test run had 30 sec
warmup and 45 sec steady state) and the AVG_TPS column shows the
average from the 30 runs.

JAR       |THREADS    |AVG_TPS               
d2991     |1          |136.3599695946353     
trunk     |1          |136.0475449900022     
d2991     |2          |265.9779264453826     
trunk     |2          |262.8875064800415     
d2991     |4          |262.95638006368955    
trunk     |4          |255.46471154558247    
d2991     |8          |256.97232845038025    
trunk     |8          |252.92527586462265    
d2991     |16         |256.84847624018147    
trunk     |16         |254.06894019626188    

I will see if I can write some more specific tests that test the other
possible worst-case scenarios suggested in earlier comments.

What the patch does, is that it saves the version of the page in the
BTreeRowPosition object before it saves the page, and each time rows
can be moved off the page (in operations that previously acquired an
exclusive scan lock) this is flagged in the in-memory representation
of the page. BTreeScan.reposition() will first match the version in
BTreeRowPosition with the flagged version number on the page, and will
only reposition by key if the page has been flagged after the position
was saved. Pages are automatically flagged with the current version
when they are fetched into the cache, so we'll always reposition by
key if the page has been evicted from the cache after we saved the

The patch also makes savePosition() reuse the DataValueDescriptor
object in which the key is stored, so that it's only allocated once
per scan.

Currently, the patch does not handle the case where the page has
disappeared when we reposition (only happens with holdable cursors
after a commit followed by truncate table, I think) or the case where
the leaf page has turned into a branch page while we waited. These
problems led to four failures in derbyall and four failures in

> 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: d2991-preview-1a.diff, d2991-preview-1a.stat, d2991-preview-1b.diff,
d2991-preview-1b.stat, d2991-preview-1c.diff, d2991-preview-1c.stat, d2991-preview-1d.diff,
d2991-preview-1d.stat, 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