Uploaded image for project: 'Hive'
  1. Hive
  2. HIVE-15077

Acid LockManager is unfair

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Blocker
    • Resolution: Fixed
    • Affects Version/s: 2.3.0
    • Fix Version/s: 3.0.0
    • Component/s: Transactions
    • Labels:
      None

      Description

      HIVE-10242 made the acid LM unfair.

      In TxnHandler.checkLock(), suppose we are trying to acquire SR5 (the number is extLockId).

      Then
      LockInfo[] locks = lockSet.toArray(new LockInfo[lockSet.size()]);

      may look like this (all explicitly listed locks are in Waiting state)

      {...., SR5 SW3 X4}

      So the algorithm will find SR5 in the list and start looking backwards (to the left).
      According to IDs, SR5 should wait for X4 to be granted but X4 won't even be examined and so SR5 may be granted.

      Theoretically, this could cause starvation.

      The query that generates the list already has
      query.append(" and hl_lock_ext_id <= ").append(extLockId);

      but it should use "<" rather than "<=" to exclude the locks being checked from "locks" list which will make the algorithm look at all locks "in front" of a given lock.

      Here is an example (add to TestDbTxnManager2)

        @Test
        public void testFairness2() throws Exception {
          dropTable(new String[]{"T7"});
          CommandProcessorResponse cpr = driver.run("create table if not exists T7 (a int) partitioned by (p int) stored as orc TBLPROPERTIES ('transactional'='true')");
          checkCmdOnDriver(cpr);
          checkCmdOnDriver(driver.run("insert into T7 partition(p) values(1,1),(1,2)"));//create 2 partitions
          cpr = driver.compileAndRespond("select a from T7 ");
          checkCmdOnDriver(cpr);
          txnMgr.acquireLocks(driver.getPlan(), ctx, "Fifer");//gets S lock on T7
          HiveTxnManager txnMgr2 = TxnManagerFactory.getTxnManagerFactory().getTxnManager(conf);
          swapTxnManager(txnMgr2);
          cpr = driver.compileAndRespond("alter table T7 drop partition (p=1)");
          checkCmdOnDriver(cpr);
          //tries to get X lock on T7.p=1 and gets Waiting state
          LockState lockState = ((DbTxnManager) txnMgr2).acquireLocks(driver.getPlan(), ctx, "Fiddler", false);
          List<ShowLocksResponseElement> locks = getLocks();
          Assert.assertEquals("Unexpected lock count", 4, locks.size());
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", null, locks);
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", "p=1", locks);
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", "p=2", locks);
          checkLock(LockType.EXCLUSIVE, LockState.WAITING, "default", "T7", "p=1", locks);
      
          HiveTxnManager txnMgr3 = TxnManagerFactory.getTxnManagerFactory().getTxnManager(conf);
          swapTxnManager(txnMgr3);
          //this should block behind the X lock on  T7.p=1
          cpr = driver.compileAndRespond("select a from T7");
          checkCmdOnDriver(cpr);
          txnMgr3.acquireLocks(driver.getPlan(), ctx, "Fifer");//gets S lock on T6
          locks = getLocks();
          Assert.assertEquals("Unexpected lock count", 7, locks.size());
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", null, locks);
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", "p=1", locks);
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", "p=2", locks);
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", null, locks);
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", "p=1", locks);
          checkLock(LockType.SHARED_READ, LockState.ACQUIRED, "default", "T7", "p=2", locks);
          checkLock(LockType.EXCLUSIVE, LockState.WAITING, "default", "T7", "p=1", locks);
      
        }
      

      The 2nd locks = getLocks(); output shows that all locks for the 2nd select * from T7 are all acquired while they should block behind the X lock to be fair.

        Attachments

        1. HIVE-15077.02.patch
          14 kB
          Eugene Koifman

          Issue Links

            Activity

              People

              • Assignee:
                ekoifman Eugene Koifman
                Reporter:
                ekoifman Eugene Koifman
              • Votes:
                0 Vote for this issue
                Watchers:
                4 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: