Deaklock on HaeinsaComplexTest::testSerializability

[dev-rkoshlyak]

Thread 1 and thread 2 has same commit timestamp.
thread 1 do prewrite primary, thread 2 do abort immediately after that for primary.
Then thread 1 & 2 wait for expiration and all start over again.

For now, I making HaeinsaTransactions::hasSameCommitTimestamp to return false all the time.
I am not sure weather this bug has only deadlock implication or data integrity implication as well. But I think it is unsafe to assume that 2 transactions are the same if they have same commit timestamp.

[eincs]

In conclusion, there is no data integrity problem and producing vary mount of conflict is natural in HaeinsaComplexTest.testSerializability. (I assume that your deadlock means massive mount of conflict with "this row is unstable and not expired yet" message)

Here is the reason why tx2 can't abort tx1's primary row:

Current State:

• Let's assume tx1 is running on thread1 and tx2 is on thread2
• Commit timestamp of tx1 and tx2 is same. (It's vary rare case but it can happen)
• Participating rows of tx1 and tx2 are same. (See: HaeinsaComplexTest.testSerializability)
• Primary and secondary row of tx1 and tx2 are same. (Rows are sorted with HashComparator)
• tx1 succeed to prewrite primary row, and tx2 is about to try prewrite primary row.

Prove:

• Step1: tx2 fails to prewrite primary row. (HaeinsaTable.java#L594)
  It's because the row is already prewritten by tx1.
• Step2: tx2 try recover transaction state immediately. (HaeinsaTable.java#L599)
• Step3: Since primaryRowTx.getCurrent().getState() is STABLE, so it never aborts tx1. (HaeinsaTransaction.java#L454)
  Note that primaryRowTx.getCurrent() is instance of row lock that tx2 read when put method invoked.
  (HaeinsaTable.java#L374, HaeinsaTable.java#L409)

Furthermore, conflict rate of HaeinsaComplexTest.testSerializability does that changes whether I changes HaeinsaTransactions::hasSameCommitTimestamp to return false all the time.

Why so many conflicts in HaeinsaComplexTest.testSerializability?

There are two kind of concurrency control strategy: OCC(Optimistic concurrency control) and PCC(Pessimistic concurrency control). PCC is general strategy for RDBMS, but Haeinsa chooses OCC. In my knowledge, most of transaction implementation of NoSQL chooses OOC too.
See: https://github.com/VCNC/haeinsa/wiki/How-it-Works

Unlike to PCC, OCC do not waits for other concurrent transactions to be completed. It proceed transaction and then check conflicts with other concurrent transaction on commit. So, high conflict rate is inevitable when many of conccurent trasactions acceessing same row. This is also described on wiki too.

Haeinsa is designed for low-conflict environment. If many transactions concurrently access to same row, performance of Haeinsa can be degraded.

See: https://github.com/VCNC/haeinsa/wiki/How-to-Use#important-information

No problem with checking same row with commit timestamp only?

Yes, there is no problem.

Haeinsa uses "HaeinsaTransactions::hasSameCommitTimestamp" to determine proceed or not self-recovery. This self-recovery occurs when transaction fails to prewrite secondary row. (HaeinsaTable.java#L539, HaeinsaTable.java#L600)

In HaeinsaTransaction::recover, value of primaryRowTx.getCurrent().getState() can be one of ABORTED, PREWRITTEN, COMMITTED and STABLE.

In STABLE case, this means that the transaciton did not succeed prewrite primary row at all. That's why HaeinsaTransaction::recover those nothing. In other cases, it implies that prewrite primary row succeed. If commit timestamp of primary row equals to current transaction, it means that lock column of primary row did not changed, and we can proceed self-recovery. Note that if transaction expires, other transaction can proceed recovery and change lock column of primary row. (HaeinsaTable.java#L405) In this case, commit timestamp can't equals.

So, in case of HaeinsaTable.java#L539 and HaeinsaTable.java#L600, it can be considered as same transaction if the commit timestamp is equals. I will do refactoring on the code to describe it clearly.

[eincs]

If there are any other questions, and If you think I'm misunderstanding your situation, please write comment on this issue. Otherwise, I'll close this issue in few days.

[dev-rkoshlyak]

I agree that there are no problems in production. It just i can not run unit test. I am not sure why you can pass test, may be because you using other version of hbase, which is slower and that's why it produce different commit timestamps for you.

[saadmufti]

I just created an issue before I had checked this, I am trying with HBase 1.2 and running into the same issue of testSerializiability never finishing, it is not a deadlock but not making enough progress as too many transaction failures. In my case the threads eventually throw out of memory exception. Maybe it is the unit test that needs to be updated for faster newer versions of HBase? Any shared experiences or hints would be great. Thanks.