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 Thu, 26 Feb 2009 13:23:02 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-2a.stat

I'm attaching a new patch (d2991-2a.diff) which has these changes
compared to the preview-1e patch:

- added more comments and removed mentioning of scan lock in (some of
  the) existing comments

- removed the savedLockedPos flag from BTreeRowPosition and moved back
  to the original approach of just using current_rh != null to
  indicate that the row on the current position was locked. This also
  allows cheap repositioning by record id in more cases than before
  because current_rh is not null as often as it was with the
  preview-1e patch

- fixed the bug exposed by testBTreeMaxScan_fetchMaxRowFromBeginning
  in IndexSplitDeadlockTest. The problem was that one of the methods
  was passed the scan_position instance variable as an argument. When
  that method called reopenScan(), the instance variable would be
  replaced, but the local variable would remain the same, and this
  inconsistency triggered an assert in the added code. Solved by
  removing the position from the argument list and instead using the
  instance variable directly

- fixed the bug exposed by
  testBTreeForwardScan_fetchRows_resumeScanAfterCompress. Solved by
  fetching the page with another method that didn't fail if the page
  had disappeared, and reposition from the root of the B-tree if the
  page was removed by SYSCS_COMPRESS_TABLE.

- updated canon for store/updatelocksJDBC30.sql which has been added
  to derbyall recently

I have just realized that there are some more problems that need to be
resolved, but I think they will have just minor effect on the patch,
so I'm posting it anyway to allow others to take a look at it and see
if there are more serious problems with it.

Here's a description of the changes in each file touched by the patch
(excluding the test files which were just updated so that they didn't
expect scan locks in the lock tables, and so that they didn't expect
index split deadlocks):

* impl/store/access/sort/Scan.java

Removed savePosition() method from the interface because the position
is now always saved by key when the scan doesn't hold a latch on the

* impl/store/access/btree/LeafControlRow.java

Removed calls to Scan.saveScanPositions() and
BTreeLockingPolicy.lockScan() before splitting the page, because
positions are always saved by the scan itself now, and because we
don't use scan locks anymore.

Set a hint in the page object after splitting to notify the scans that
they must reposition from the root of the B-tree after a split.

* impl/store/access/btree/BTreeController.java

Don't lock scan before purging committed deletes. Set a hint in the
page object to tell the scans that they must reposition from the root
of the B-tree since the row may not be there anymore.

* impl/store/access/btree/BTreeScan.java

Remove locking/unlocking of scan.

Update savePosition() to allow the position to be saved by record id
and by key at the same time, and make it possible to pass in a partial
or a full key to reduce the number of slots that must be fetched from
the page.

Update reposition() to reposition by record id if possible and by key
if needed. Repositioning by record id (which is cheaper) is possible
if the row is guaranteed to be on the same page as when the position
was saved (that is, no split or purge operation has been performed on
the page after saving the position).

Use savePositionAndReleasePage() when returning from the scan in
delete(), fetch(), doesCurrentPositionQualify() and

* impl/store/access/btree/BTreeMaxScan.java

Remove the BTreeRowPosition argument from fetchMaxRowFromBeginning()
to prevent that it goes out of sync with the instance variable
scan_position when reopenScan() is called. Use the fresh instance
variable instead.

Remove references to the scan protection handle.

* impl/store/access/btree/BTreeRowPosition.java

Add more state (and methods to access the state):

  - parent of the position. That is, which scan owns this
    position. This was needed to allow the position to be saved from
    some methods that didn't know which scan it belonged to. Could
    alternatively be solved by passing the scan as an argument to
    those methods (or actually to those methods and their callers)
    which is probably cleaner, but could be performed in a later

  - version number of the current leaf page when the position was
    saved (used to determine whether full repositioning is needed
    because of split, etc.)

  - template for the key to save (to prevent allocation each time the
    key is saved). When the position is saved by key, this is
    identical to current_positionKey. A separate field was added so
    that we keep the object even when current_positionKey is nulled
    out, but a possibly cleaner solution would be to have just a flag
    telling whether the value in current_positionKey is valid, and
    never reset current_positionKey to null. Could be done in a later

  - fetch descriptor used to fetch the rest of the key in the cases
    where the scan has already fetched parts of the key before saving
    the position

* impl/store/access/btree/BTreePostCommit.java

purgeRowLevelCommittedDeletes() sets a hint in the page object to
force scans to reposition from the root of the B-tree when at least
one row has been purged from the page.

I think the same change should have been made in
purgeCommittedDeletes(). I missed it because the method assumed an
exclusive table lock and therefore didn't need a scan lock. Will
update the patch later.

* impl/store/access/btree/OpenBTree.java

Remove references to the removed saveScanPositions() method and to the
protection record handle.

Make the debug code that simulates release of latches save the
position since that's what happens if the latches really are released
by the production code now.

* impl/store/access/btree/index/B2IRowLockingRR.java
* impl/store/access/btree/index/B2INoLocking.java
* impl/store/access/btree/index/B2IRowLocking1.java
* impl/store/access/btree/index/B2IRowLocking3.java
* impl/store/access/btree/BTreeLockingPolicy.java

Remove request_scan_lock parameter.

Remove code to lock/unlock scan.

Save position of scan if lock cannot be granted immediately.

* impl/store/access/btree/BTreeForwardScan.java

Save position by key each time the scan returns a group of rows. Use
the partial (possibly full) key fetched by the scan to make the save
position operation cheaper.

* impl/store/access/RAMTransaction.java
* impl/store/access/heap/HeapScan.java
* iapi/store/access/conglomerate/ScanManager.java
* iapi/store/access/conglomerate/TransactionManager.java

Remove saveScanPositions()/savePosition() because the position will
already have been saved now since we always save the position when we
release the latch.

* impl/store/access/heap/HeapRowLocation.java

Remove THROWASSERT from and complete implementation of
setFrom(DataValueDescriptor) to allow the RowLocation in the index row
to be copied when we save the position.

* impl/store/raw/data/BasePage.java
* iapi/store/raw/Page.java

Remove reference to protection record handle.

Add code to set the hint that repositioning from the root of the
B-tree is needed.

* iapi/store/raw/RecordHandle.java

Remove constant identifying the record protection handle that we no
longer use.

> 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-2a.diff, d2991-2a.stat, 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, d2991-preview-1e.diff, derby.log, InsertSelectDeadlock.java,
perftest.diff, Repro2991.java, stacktraces_during_deadlock.txt, test-1.diff, test-2.diff,
> 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