[
https://issues.apache.org/jira/browse/IGNITE-18091?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17634256#comment-17634256
]
Denis Chudov edited comment on IGNITE-18091 at 11/15/22 9:44 AM:
-----------------------------------------------------------------
*Correct* means that the behavior matches the expectations.
||N||Scenario||Ignite 3||MVP||Expected||
|1|*testWaitDie0* \\ var tx1 = beginTx(); \\ var tx2 = beginTx(); \\ \\ var
key1 = key("test"); \\ \\ xlock(tx2, key1).join(); \\ \\ CompletableFuture<?>
xlockFutTx1 = xlock(tx1, key1); \\ assertFalse(xlockFutTx1.isDone()); \\
commitTx(tx2); \\ xlockFutTx1.join();|Tx2 waits on attempt to acquire
x-lock.\\*Note:* works correctly with reverse transaction order.|correct|X-lock
for tx2 fails, as tx2 younger than tx1 and is not allowed to wait for tx1, it
should DIE instead.|
|2|*testWaitDie1* \\ \\ var tx1 = beginTx(); \\ var tx2 = beginTx(); \\ \\
var key1 = key("test"); \\ \\ xlock(tx2, key1).join(); \\ \\
CompletableFuture<?> xlockFutTx1 = xlock(tx1, key1); \\
assertFalse(xlockFutTx1.isDone()); \\ \\ commitTx(tx2); \\
xlockFutTx1.join();|Tx1 fails on attempt of acquiring the x-lock \\ \\ Note:
works correctly with reverse transaction order.|correct|tx2 successfully
acquires x-lock. \\ tx1 waits on attempt of acquiring x-lock. \\ After tx2 is
committed, the future for tx1 is completed without exception. \\ |
|3|*testWaitDieSlocks0* \\ \\ var tx1 = beginTx(); \\ var tx2 = beginTx(); \\
\\ var key1 = key("test"); \\ \\ slock(tx1, key1).join(); \\ slock(tx2,
key1).join(); \\ \\ CompletableFuture<?> xlockTx1 = xlock(tx1, key1); \\
assertFalse(xlockTx1.isDone()); \\ \\ commitTx(tx2); \\
xlockTx1.join();|X-lock for tx1 returns future that is completed exceptionally
with LockException \\ \\ Note: works correctly with reverse transaction
order.|correct|Tx1 waits for tx2 to commit, then x-lock for tx1 is acquired.|
|4|*testWaitDieSlocks1* \\ \\ var tx1 = beginTx(); \\ var tx2 = beginTx(); \\
\\ var key1 = key("test"); \\ \\ slock(tx1, key1).join(); \\ slock(tx2,
key1).join(); \\ \\ assertThrowsException(() -> xlock(tx2, key1));|Tx2 waits
on attempt to acquire x-lock. \\ \\ Note: works correctly with reverse
transaction order.|correct|Tx2 should fail on attempt to acquire x-lock, as tx1
is holding s-lock and tx2 can’t wait for tx1.|
|5|*testWaitDieSlocks2* \\ \\ var tx1 = beginTx(); \\ var tx2 = beginTx(); \\
\\ var key1 = key("test"); \\ \\ slock(tx1, key1).join(); \\ slock(tx2,
key1).join(); \\ \\ CompletableFuture<?> xlockTx1 = xlock(tx1, key1); \\
assertFalse(xlockTx1.isDone()); \\ \\ assertThrowsException(() -> xlock(tx2,
key1)); \\ \\ rollbackTx(tx2); \\ \\ xlockTx1.join();|Tx2 waits on attempt to
acquire x-lock.|correct|Tx1 should wait after attempt to acquire x-lock, as tx2
is holding s-lock. \\ Tx2 should fail on attempt to acquire x-lock, as tx1 is
holding s-lock and tx2 can’t wait for tx1. \\ Then tx2 rolls back, and tx1
successfully acquires x-lock. \\ \\ |
|6|*testNonFair* \\ \\ var tx1 = beginTx(); \\ var tx2 = beginTx(); \\ var tx3
= beginTx(); \\ \\ var k = key("test"); \\ \\ slock(tx3, k).join(); \\ \\
CompletableFuture<?> futTx2 = xlock(tx2, k); \\ assertFalse(futTx2.isDone());
\\ \\ CompletableFuture<?> futTx1 = xlock(tx1, k); \\
assertFalse(futTx1.isDone()); \\ \\ commitTx(tx3); \\ \\ futTx2.join(); \\
\\ assertFalse(futTx1.isDone()); \\ \\ commitTx(tx2); \\ \\
futTx1.join();|Tx2 waits on attempt to acquire x-lock. \\ \\ Note: works
correctly with reverse transaction order.|correct|Tx1 and tx2 wait for tx3 to
commit in order to acquire x-lock. After tx3 is committed, tx2 as more young
acquires x-lock first, and tx1 continues to wait. After tx2 is committed, tx1
acquires x-lock. So conflict between waiting transactions is resolved in an
order allowing all transactions to succeed.|
|7|*testReenterWithConflict* \\ \\ var tx1 = beginTx(); \\ var tx2 =
beginTx(); \\ \\ var k = key("test"); \\ \\ slock(tx2, k).join(); \\
slock(tx1, k).join(); \\ \\ CompletableFuture<?> futTx1 = xlock(tx1, k); \\
assertFalse(futTx1.isDone()); \\ \\ commitTx(tx2); \\ \\ futTx1.join();|Tx1
waits on attempt to acquire x-lock. \\ \\ Note: works correctly with reverse
transaction order.|correct|Tx1 should wait for tx1 to commit in order to
upgrade s-lock to x-lock.|
|8|*testReenterWithConflictAndAbort* \\ \\ var tx1 = beginTx(); \\ var tx2 =
beginTx(); \\ \\ var k = key("test"); \\ \\ slock(tx2, k).join(); \\
slock(tx1, k).join(); \\ \\ assertThrowsException(() -> xlock(tx2, k));|Tx2
waits for tx1 \\ \\ Note: works correctly with reverse transaction
order.|correct|Tx2 is not allowed to wait for tx1 to commit.|
|9|*testReenterAllowed* \\ \\ var tx1 = beginTx(); \\ \\ var k = key("test");
\\ \\ slock(tx1, k).join(); \\ xlock(tx1, k).join();|correct|correct|Reenter
allowed|
|10|*testNonFairConflictWithAlreadyWaiting* \\ \\ var tx1 = beginTx(); \\ var
tx2 = beginTx(); \\ var tx3 = beginTx(); \\ \\ var k = key("test"); \\ \\
slock(tx2, k).join(); \\ \\ CompletableFuture<?> futTx1 = xlock(tx1, k); \\
assertFalse(futTx1.isDone()); \\ \\ slock(tx3, k).join(); \\ \\
assertFalse(futTx1.isDone());|Tx1 fails on attempt to acquire x-lock. \\ \\
Note: works correctly with reverse transaction order.|correct|In non-fair lock
waiting order, tx3 is allowed to acquire s-lock that is compatible with s-lock
that is held by tx2, in spite of tx1 that started to wait for x-lock before.
Tx1 continues to wait.|
|11|*testNonFairConflictWithAlreadyWaitingWithAbort* \\ \\ var tx1 =
beginTx(); \\ var tx2 = beginTx(); \\ var tx3 = beginTx(); \\ \\ var k =
key("test"); \\ \\ slock(tx3, k).join(); \\ \\ CompletableFuture<?> futTx2 =
xlock(tx2, k); \\ assertFalse(futTx2.isDone()); \\ \\ slock(tx1, k).join(); \\
\\ commitTx(tx3); \\ \\ assertThrowsException(() -> futTx2);|Tx1 fails on
attempt to acquire x-lock.|Future for tx2 doesn’t complete neither
exceptionally nor normally.|Tx2 waits for x-lock, as it is older than tx3 that
is holding s-lock. But after that, tx1 also acquires s-lock, and succeeds
because of non-fair lock waiting order. After that, tx3 is committed. Now tx2
waits only for tx1, but according to waitDie deadlock prevention policy, it is
not allowed to do that, the future for tx2 should complete exceptionally.|
|12|*testNonFairTakeFirstCompatible* \\ \\ var tx1 = beginTx(); \\ var tx2 =
beginTx(); \\ var tx3 = beginTx(); \\ var tx4 = beginTx(); \\ \\ var k =
key("test"); \\ \\ slock(tx4, k).join(); \\ \\ CompletableFuture<?> futTx2 =
xlock(tx2, k); \\ assertFalse(futTx2.isDone()); \\ \\ slock(tx1, k).join(); \\
slock(tx3, k).join(); \\ \\ assertFalse(futTx2.isDone()); \\ \\
commitTx(tx1); \\ commitTx(tx3); \\ commitTx(tx4); \\ \\ futTx2.join();| \\
Tx2 fails in an attempt to acquire x-lock.| \\ correct| \\ S-locks for tx1 and
tx3 are acquired successfully regardless of order comparing to tx2.|
|13|*testLockOrderAfterRelease* \\ \\ var tx1 = beginTx(); \\ var tx2 =
beginTx(); \\ var tx3 = beginTx(); \\ var tx4 = beginTx(); \\ \\ var k =
key("test"); \\ \\ xlock(tx4, k).join(); \\ \\ CompletableFuture<?> futTx3 =
slock(tx3, k); \\ assertFalse(futTx3.isDone()); \\ \\ CompletableFuture<?>
futTx2 = xlock(tx2, k); \\ assertFalse(futTx2.isDone()); \\ \\
CompletableFuture<?> futTx1 = slock(tx1, k); \\ assertFalse(futTx1.isDone());
\\ \\ commitTx(tx4); \\ \\ futTx3.join(); \\ assertFalse(futTx1.isDone()); \\
assertFalse(futTx2.isDone()); \\ \\ commitTx(tx3); \\ \\ futTx2.join(); \\
\\ commitTx(tx2); \\ \\ futTx1.join(); \\ \\ | \\ Tx3 fails in an attempt to
acquire s-lock.| \\ correct| \\ After x-lock for tx4 is released, only s-lock
for tx3 should be acquired. In spite of the fact that s-lock for tx1 is
compatible, tx1 still should wait because if it acquires lock, tx2 will have to
be aborted, as it isn’t allowed to wait for tx1.|
|14| \\ *testMultipleCompatibleLocksAcquiredAfterIncompatibleReleased* \\ \\
var tx1 = beginTx(); \\ var tx2 = beginTx(); \\ var tx3 = beginTx(); \\ \\ var
k = key("test"); \\ \\ xlock(tx3, k).join(); \\ \\ CompletableFuture<?>
futTx2 = slock(tx2, k); \\ assertFalse(futTx2.isDone()); \\ \\
CompletableFuture<?> futTx1 = slock(tx1, k); \\ assertFalse(futTx1.isDone());
\\ \\ commitTx(tx3); \\ \\ futTx2.join(); \\ futTx1.join(); \\ \\ | \\ Tx2
fails in an attempt to acquire s-lock. \\ \\ Note: works correctly with
reverse transaction order.| \\ Lock for tx1 is not acquired.| \\ After x-lock
for tx3 is released, s-locks for both tx1 and tx2 could be acquired as they are
compatible with each other.|
was (Author: denis chudov):
*Correct* means that the behavior matches the expectations.
||N||Scenario||Ignite 3||MVP||Expected||
|1|*testWaitDie0*
var tx1 = beginTx();
var tx2 = beginTx();
var key1 = key("test");
xlock(tx2, key1).join();
CompletableFuture<?> xlockFutTx1 = xlock(tx1, key1);
assertFalse(xlockFutTx1.isDone());
commitTx(tx2);
xlockFutTx1.join();|Tx2 waits on attempt to acquire x-lock.
*Note:* works correctly with reverse transaction order.|correct|X-lock for tx2
fails, as tx2 younger than tx1 and is not allowed to wait for tx1, it should
DIE instead.|
|2|*testWaitDie1*
var tx1 = beginTx();var tx2 = beginTx();
var key1 = key("test");
xlock(tx2, key1).join();
CompletableFuture<?> xlockFutTx1 = xlock(tx1, key1);
{_}assertFalse{_}(xlockFutTx1.isDone());
commitTx(tx2);
xlockFutTx1.join();|Tx1 fails on attempt of acquiring the x-lock
*Note:* works correctly with reverse transaction order.|correct|tx2
successfully acquires x-lock.
tx1 waits on attempt of acquiring x-lock.
After tx2 is committed, the future for tx1 is completed without exception.|
|3|*testWaitDieSlocks0*
*var tx1 = beginTx();var tx2 = beginTx();
*
*var key1 = key("test");
*
*slock(tx1, key1).join();slock(tx2, key1).join();*
*CompletableFuture<?> xlockTx1 = xlock(tx1, key1);
{_}assertFalse{_}(xlockTx1.isDone());*
*commitTx(tx2);xlockTx1.join();*|X-lock for tx1 returns future that is
completed exceptionally with LockException
*Note:* works correctly with reverse transaction order.|correct|Tx1 waits for
tx2 to commit, then x-lock for tx1 is acquired.|
> Compare deadlock prevention implementations and work out decisions about
> correct behavior in corner cases
> ---------------------------------------------------------------------------------------------------------
>
> Key: IGNITE-18091
> URL: https://issues.apache.org/jira/browse/IGNITE-18091
> Project: Ignite
> Issue Type: Task
> Reporter: Denis Chudov
> Assignee: Denis Chudov
> Priority: Major
> Labels: ignite-3
>
> *Motivation*
> Today we have several possible implementations of deadlock prevention: AI 3
> [1], transactions POC [2], and possible implementation based on concurrency
> control paper [3]. Moreover, we have a multiple granularity lock model [4]
> where some lock modes are compatible, others are not, which allows
> reenterability in some cases, and sharing of locks between transactions. We
> should understand the differences of behavior of each implementation in
> different scenarios, and how it matches with our expectations.
> *Definition of done*
> Table with a set of scenarios and description of behavior, including the
> expected one.
> [1] org.apache.ignite.internal.tx.impl.HeapLockManager
> [2] https://github.com/ascherbakoff/ai3-txn-mvp
> [3] https://dl.acm.org/doi/pdf/10.1145/320251.320260
> [4] https://web.stanford.edu/class/cs245/readings/granularity-of-locks.pdf
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
