Mailing-List: contact derby-dev-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: <derby-dev@db.apache.org>
Message-ID: <682444187.1227502304439.JavaMail.jira@brutus>
Date: Sun, 23 Nov 2008 20:51:44 -0800 (PST)
From: "Jeff Stuckman (JIRA)" <jira@apache.org>
To: derby-dev@db.apache.org
Subject: [jira] Commented: (DERBY-2991) Index split deadlock
In-Reply-To: <16734720.1186114252905.JavaMail.jira@brutus>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Jeff Stuckman commented on DERBY-2991:
--------------------------------------

I'm also affected by this issue, and I'd like to note that a concurrent select and update can cause the undesired behavior, not just a concurrent select and insert.

Summary:
Even using READ_COMMITTED, a single non-updatable SELECT and a single UPDATE statement can deadlock against each other when an index includes the updated column.

My test case uses the following table and index:
CREATE TABLE urls (urlid INTEGER NOT NULL PRIMARY KEY, url VARCHAR(2048) NOT NULL UNIQUE, site INTEGER, expectation INTEGER, jobflag CHAR DEFAULT 'N'); CREATE INDEX findurlbysiteandjob ON urls(site,jobflag);

My test case creates two threads and executes the following statements until they deadlock against each other:
UPDATE urls SET jobflag=? WHERE urlid=?	
SELECT urlid,url,expectation FROM urls WHERE site=?

The test eventually deadlocks with the following transaction and lock table
contents:
XID     TYPE  MODE TABLENAME LOCKNAME  STATE TABLETYPE  LOCKCOUNT  INDEXNAME
2217109 ROW   S    URLS      (13,1)    GRANT T          1 FINDURLBYSITEANDJOB
2217114 ROW   X    URLS      (13,1)    WAIT  T          0 FINDURLBYSITEANDJOB
2217113 ROW   S    URLS      (15,1)    GRANT T          1 FINDURLBYSITEANDJOB
2217113 ROW   X    URLS      (3,132)   GRANT T          3          null
2217109 ROW   S    URLS      (3,132)   WAIT  T          0          null
2217109 TABLE IS   URLS      Tablelock GRANT T          2          null
2217113 TABLE IX   URLS      Tablelock GRANT T          4          null
2217114 TABLE IX   URLS      Tablelock GRANT T          1          null
2217113 ROW   S    URLS      (6,1)     GRANT T          1 SQL081111021116970

XID     GLOBAL_XID  USERNAME TYPE                 STATUS  FIRST_INSTANT SQL_TEXT
2217115 null        APP      UserTransaction      IDLE    null select * from SYSCS_DIAG.TRANSACTION_TABLE
2217114 null        APP      InternalTransaction  ACTIVE  null UPDATE urls SET jobflag=? WHERE urlid=?
2217113 null        APP      UserTransaction      ACTIVE  (526,52925) UPDATE urls SET jobflag=? WHERE urlid=?
2069160 null        null     SystemTransaction    IDLE    null          null
2217109 null        APP      UserTransaction      ACTIVE  null


1. The SELECT statement begins to execute and the cursor is stepping through the result set. The results are derived from index FINDURLBYSITEANDJOB as expected.
2. The UPDATE statement begins to execute. The row to be updated is the row immediately after the SELECT statement's cursor. The row is locked and updated.
3. The UPDATE statement must modify the index structure (tree rebalancing or similar?). It must lock the row that the SELECT statement's cursor is currently occupying. It cannot do this, so the transaction waits.
4. The SELECT statement is ready to advance the cursor. However, it cannot advance the cursor because the UPDATE statement has locked the next row. The transaction waits and we have a deadlock.

Apparently, the only way to avoid this deadlock is to LOCK TABLE before updating.

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