Derby
  1. Derby
  2. DERBY-3961

Deadlock detection fails for InternalTransaction

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Duplicate
    • Affects Version/s: 10.4.2.0
    • Fix Version/s: 10.5.2.0
    • Component/s: Store
    • Labels:
      None
    • Environment:
      Windows Vista

      Description

      It is easy to cause a deadlock which is not detected by the deadlock detection algorithm. The transactions fail due to a lock timeout , possibly because a transaction of type InternalTransaction is part of the cycle.

      Resolving issue DERBY-2991 will make it more difficult to cause such deadlocks, but it will still be possible.

      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 SELECT urlid,url,expectation FROM urls WHERE site=?

      Here is what I think is happening:
      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 perform index maintenance (tree rebalancing or similar?). This apparently causes an InternalTransaction to be created. It then 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.
      The result: Transaction 2217113 waits for the "nested transaction" 2217114 to complete. 2217114 waits for 2217109 to release its lock. 2217109 waits for 2217113 to release its lock. We have a cycle and a deadlock. The transactions time out with "A lock could not be obtained within the time requested", apparently because the dependency between transactions 2217113 and 2217114 is not detected.

        Issue Links

          Activity

          Hide
          Jeff Stuckman added a comment -

          I am the original reporter and I believe that this issue has been resolved with the fix for DERBY-2991.

          From what you say, it appears that the comprehensive changes made to the index split case in DERBY-2991 have eliminated all cases where this behavior is manifested.

          In a perfect world, the lock manager would be updated to recognize deadlocks where the internal transaction and the parent transaction are on the same thread. This would have made it easier to debug DERBY-2991, and will possibly make it easier to recognize and debug future issues. However, it appears that there are currently no known cases that would benefit from such a change.

          Show
          Jeff Stuckman added a comment - I am the original reporter and I believe that this issue has been resolved with the fix for DERBY-2991 . From what you say, it appears that the comprehensive changes made to the index split case in DERBY-2991 have eliminated all cases where this behavior is manifested. In a perfect world, the lock manager would be updated to recognize deadlocks where the internal transaction and the parent transaction are on the same thread. This would have made it easier to debug DERBY-2991 , and will possibly make it easier to recognize and debug future issues. However, it appears that there are currently no known cases that would benefit from such a change.
          Hide
          Mike Matrigali added a comment -

          I can't be sure without a test case - just made an informed guess,
          but the description and the lock table looked like a duplicat to me.
          Obviously the best case would be for the original reporter to either submit his test case or to run his test
          case against 10.5. If it still breaks, please do reopen this issue.

          o DERBY-2991 will result in a lock timeout vs. a deadlock, in the btree split case. This is because the lock
          manager does not recognize that the internal transaction for the split and the parent transaction are the
          same thread and thus should be treated as the same waiter for purpose of deadlock detection. So what
          happens is that no deadlock is detected where there is one, so the threads hang around until they reach
          lock timeout.

          o All row locks of the form (N, 1) will no longer be requested in 10.5 after the fix for DERBY-2991, so if one sees
          a missed deadlock in versions previous to 10.5 where these are part of the deadlock cycle they should be
          fixed by DERBY-2991.

          Show
          Mike Matrigali added a comment - I can't be sure without a test case - just made an informed guess, but the description and the lock table looked like a duplicat to me. Obviously the best case would be for the original reporter to either submit his test case or to run his test case against 10.5. If it still breaks, please do reopen this issue. o DERBY-2991 will result in a lock timeout vs. a deadlock, in the btree split case. This is because the lock manager does not recognize that the internal transaction for the split and the parent transaction are the same thread and thus should be treated as the same waiter for purpose of deadlock detection. So what happens is that no deadlock is detected where there is one, so the threads hang around until they reach lock timeout. o All row locks of the form (N, 1) will no longer be requested in 10.5 after the fix for DERBY-2991 , so if one sees a missed deadlock in versions previous to 10.5 where these are part of the deadlock cycle they should be fixed by DERBY-2991 .
          Hide
          Kristian Waagan added a comment -

          It is not immediately clear to me that this report is a duplicate. Has this been investigated?
          Is it correct that these transactions time out instead of being detected as a deadlock?
          Too bad we don't have a reproduction...

          Show
          Kristian Waagan added a comment - It is not immediately clear to me that this report is a duplicate. Has this been investigated? Is it correct that these transactions time out instead of being detected as a deadlock? Too bad we don't have a reproduction...

            People

            • Assignee:
              Unassigned
              Reporter:
              Jeff Stuckman
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development