[HIVE-15077] Acid LockManager is unfair

• Type: Bug
• Status: Closed
• Priority: Blocker
• Resolution: Fixed
• Affects Version/s: 2.3.0
• Fix Version/s: 3.0.0
• Component/s: Transactions
• Assignee: Eugene Koifman
• Reporter: Eugene Koifman
• Created: 26/Oct/16 20:37
• Updated: 01/Oct/19 22:07
• Resolved: 23/Feb/18 21:35

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.

Issue Links

• is broken by: HIVE-10242 ACID: insert overwrite prevents create table command
• relates to: HIVE-10483 insert overwrite partition deadlocks on itself with DbTxnManager