You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@ignite.apache.org by vp...@apache.org on 2022/12/28 07:39:52 UTC
[ignite-3] branch main updated: IGNITE-18043 Replaceable deadlock prevention mechanism (#1447)
This is an automated email from the ASF dual-hosted git repository.
vpyatkov pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/ignite-3.git
The following commit(s) were added to refs/heads/main by this push:
new 3ac9af1090 IGNITE-18043 Replaceable deadlock prevention mechanism (#1447)
3ac9af1090 is described below
commit 3ac9af1090976b5588944820caa33a9118b10432
Author: Denis Chudov <mo...@gmail.com>
AuthorDate: Wed Dec 28 09:39:47 2022 +0200
IGNITE-18043 Replaceable deadlock prevention mechanism (#1447)
---
.../java/org/apache/ignite/lang/ErrorGroups.java | 4 +-
.../matchers/CompletableFutureMatcher.java | 64 ++++++++-
.../internal/tx/DeadlockPreventionPolicy.java | 61 ++++++++
.../apache/ignite/internal/tx/LockException.java | 4 +-
.../org/apache/ignite/internal/tx/LockManager.java | 4 +-
.../ignite/internal/tx/impl/HeapLockManager.java | 153 +++++++++++++++------
.../tx/impl/WaitDieDeadlockPreventionPolicy.java | 41 ++++++
...st.java => AbstractDeadlockPreventionTest.java} | 135 ++++++------------
.../internal/tx/AbstractLockManagerTest.java | 4 +-
.../ignite/internal/tx/AbstractLockingTest.java | 122 ++++++++++++++++
.../internal/tx/NoWaitDeadlockPreventionTest.java | 124 +++++++++++++++++
.../internal/tx/NoneDeadlockPreventionTest.java | 63 +++++++++
.../tx/ReversedDeadlockPreventionTest.java | 56 ++++++++
.../internal/tx/TimeoutDeadlockPreventionTest.java | 142 +++++++++++++++++++
.../internal/tx/WaitDieDeadlockPreventionTest.java | 30 ++++
15 files changed, 860 insertions(+), 147 deletions(-)
diff --git a/modules/core/src/main/java/org/apache/ignite/lang/ErrorGroups.java b/modules/core/src/main/java/org/apache/ignite/lang/ErrorGroups.java
index ff2cd3dbfa..61b326c85c 100755
--- a/modules/core/src/main/java/org/apache/ignite/lang/ErrorGroups.java
+++ b/modules/core/src/main/java/org/apache/ignite/lang/ErrorGroups.java
@@ -268,8 +268,8 @@ public class ErrorGroups {
/** Failed to acquire a lock on a key due to a conflict. */
public static final int ACQUIRE_LOCK_ERR = TX_ERR_GROUP.registerErrorCode(5);
- /** Failed to downgrade a lock on a key due to a conflict. */
- public static final int DOWNGRADE_LOCK_ERR = TX_ERR_GROUP.registerErrorCode(6);
+ /** Failed to acquire a lock on a key within a timeout. */
+ public static final int ACQUIRE_LOCK_TIMEOUT_ERR = TX_ERR_GROUP.registerErrorCode(6);
/** Failed to commit a transaction. */
public static final int TX_COMMIT_ERR = TX_ERR_GROUP.registerErrorCode(7);
diff --git a/modules/core/src/testFixtures/java/org/apache/ignite/internal/testframework/matchers/CompletableFutureMatcher.java b/modules/core/src/testFixtures/java/org/apache/ignite/internal/testframework/matchers/CompletableFutureMatcher.java
index ad99ecd1a1..bdbd3df5d9 100644
--- a/modules/core/src/testFixtures/java/org/apache/ignite/internal/testframework/matchers/CompletableFutureMatcher.java
+++ b/modules/core/src/testFixtures/java/org/apache/ignite/internal/testframework/matchers/CompletableFutureMatcher.java
@@ -17,8 +17,11 @@
package org.apache.ignite.internal.testframework.matchers;
+import static org.apache.ignite.internal.testframework.IgniteTestUtils.hasCause;
import static org.hamcrest.Matchers.anything;
import static org.hamcrest.Matchers.equalTo;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+import static org.junit.jupiter.api.Assertions.fail;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;
@@ -27,6 +30,7 @@ import java.util.concurrent.TimeoutException;
import org.hamcrest.Description;
import org.hamcrest.Matcher;
import org.hamcrest.TypeSafeMatcher;
+import org.jetbrains.annotations.Nullable;
/**
* {@link Matcher} that awaits for the given future to complete and then forwards the result to the nested {@code matcher}.
@@ -44,13 +48,19 @@ public class CompletableFutureMatcher<T> extends TypeSafeMatcher<CompletableFutu
/** Time unit for timeout. */
private final TimeUnit timeoutTimeUnit;
+ /**
+ * Class of throwable that should be the cause of fail if the future should fail. If {@code null}, the future should be completed
+ * successfully.
+ */
+ private final Class<? extends Throwable> causeOfFail;
+
/**
* Constructor.
*
* @param matcher Matcher to forward the result of the completable future.
*/
private CompletableFutureMatcher(Matcher<T> matcher) {
- this(matcher, DEFAULT_TIMEOUT_SECONDS, TimeUnit.SECONDS);
+ this(matcher, DEFAULT_TIMEOUT_SECONDS, TimeUnit.SECONDS, null);
}
/**
@@ -59,20 +69,40 @@ public class CompletableFutureMatcher<T> extends TypeSafeMatcher<CompletableFutu
* @param matcher Matcher to forward the result of the completable future.
* @param timeout Timeout.
* @param timeoutTimeUnit {@link TimeUnit} for timeout.
+ * @param causeOfFail If {@code null}, the future should be completed successfully, otherwise it specifies the class of cause
+ * throwable.
*/
- private CompletableFutureMatcher(Matcher<T> matcher, int timeout, TimeUnit timeoutTimeUnit) {
+ private CompletableFutureMatcher(
+ Matcher<T> matcher,
+ int timeout,
+ TimeUnit timeoutTimeUnit,
+ @Nullable Class<? extends Throwable> causeOfFail
+ ) {
this.matcher = matcher;
this.timeout = timeout;
this.timeoutTimeUnit = timeoutTimeUnit;
+ this.causeOfFail = causeOfFail;
}
/** {@inheritDoc} */
@Override
protected boolean matchesSafely(CompletableFuture<? extends T> item) {
try {
- return matcher.matches(item.get(timeout, timeoutTimeUnit));
+ T res = item.get(timeout, timeoutTimeUnit);
+
+ if (causeOfFail != null) {
+ fail("The future was supposed to fail, but it completed successfully.");
+ }
+
+ return matcher.matches(res);
} catch (InterruptedException | ExecutionException | TimeoutException e) {
- throw new AssertionError(e);
+ if (causeOfFail != null) {
+ assertTrue(hasCause(e, causeOfFail, null));
+
+ return true;
+ } else {
+ throw new AssertionError(e);
+ }
}
}
@@ -116,7 +146,31 @@ public class CompletableFutureMatcher<T> extends TypeSafeMatcher<CompletableFutu
* @return matcher.
*/
public static CompletableFutureMatcher<Object> willSucceedIn(int time, TimeUnit timeUnit) {
- return new CompletableFutureMatcher<>(anything(), time, timeUnit);
+ return new CompletableFutureMatcher<>(anything(), time, timeUnit, null);
+ }
+
+ /**
+ * Creates a matcher that matches a future that completes successfully and decently fast.
+ *
+ * @param cause If {@code null}, the future should be completed successfully, otherwise it specifies the class of cause
+ * throwable.
+ * @return matcher.
+ */
+ public static CompletableFutureMatcher<Object> willFailFast(Class<? extends Throwable> cause) {
+ return willFailIn(1, TimeUnit.SECONDS, cause);
+ }
+
+ /**
+ * Creates a matcher that matches a future that completes successfully with any result within the given timeout.
+ *
+ * @param time Timeout.
+ * @param timeUnit Time unit for timeout.
+ * @param cause If {@code null}, the future should be completed successfully, otherwise it specifies the class of cause
+ * throwable.
+ * @return matcher.
+ */
+ public static CompletableFutureMatcher<Object> willFailIn(int time, TimeUnit timeUnit, Class<? extends Throwable> cause) {
+ return new CompletableFutureMatcher<>(anything(), time, timeUnit, cause);
}
/**
diff --git a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/DeadlockPreventionPolicy.java b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/DeadlockPreventionPolicy.java
new file mode 100644
index 0000000000..eaf376860e
--- /dev/null
+++ b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/DeadlockPreventionPolicy.java
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.tx;
+
+import java.util.Comparator;
+import java.util.UUID;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Deadlock prevention policy. Provides comparator for transaction ids, that allows to compare transactions in order to define
+ * which one is allowed to wait and which one should be aborted in case of possible deadlock.
+ * See also {@link org.apache.ignite.internal.tx.impl.HeapLockManager}.
+ */
+public interface DeadlockPreventionPolicy {
+ /**
+ * Comparator for transaction ids that allows to set transaction priority, if deadlock prevention policy requires this priority.
+ * The transaction with higher id has lower priority. If this comparator is {@code null} then behavior of any transaction
+ * in case of conflict depends only on whether this transaction holds a lock or makes a request for lock acquisition.
+ *
+ * @return Transaction id comparator.
+ */
+ @Nullable default Comparator<UUID> txIdComparator() {
+ return null;
+ }
+
+ /**
+ * Timeout (in milliseconds) to wait before aborting a lock attempt that is made by a transaction in case of a conflict
+ * of this transaction with another one on certain key. If transaction priority is applicable (see {@link #txIdComparator()})
+ * then this timeout is applied only for transaction with lower priority. If this method returns {@code 0} this means that
+ * the lock attempt is aborted instantly (timeout is zero). If lesser that {@code 0}, it means that the wait time is infinite.
+ *
+ * @return Timeout, in milliseconds.
+ */
+ default long waitTimeout() {
+ return -1;
+ }
+
+ /**
+ * Whether transaction priority if used for conflict resolution.
+ *
+ * @return Whether priority is used.
+ */
+ default boolean usePriority() {
+ return txIdComparator() != null;
+ }
+}
diff --git a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockException.java b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockException.java
index 701fa8b0b1..e43167b72e 100644
--- a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockException.java
+++ b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockException.java
@@ -28,7 +28,7 @@ public class LockException extends TransactionInternalCheckedException {
*
* @param code Full error code. {@link org.apache.ignite.lang.ErrorGroups.Transactions#RELEASE_LOCK_ERR},
* {@link org.apache.ignite.lang.ErrorGroups.Transactions#ACQUIRE_LOCK_ERR},
- * {@link org.apache.ignite.lang.ErrorGroups.Transactions#DOWNGRADE_LOCK_ERR},
+ * {@link org.apache.ignite.lang.ErrorGroups.Transactions#ACQUIRE_LOCK_TIMEOUT_ERR},
* @param msg The detail message.
*/
public LockException(int code, String msg) {
@@ -41,7 +41,7 @@ public class LockException extends TransactionInternalCheckedException {
* @param traceId Unique identifier of this exception.
* @param code Full error code. {@link org.apache.ignite.lang.ErrorGroups.Transactions#RELEASE_LOCK_ERR},
* {@link org.apache.ignite.lang.ErrorGroups.Transactions#ACQUIRE_LOCK_ERR}
- * {@link org.apache.ignite.lang.ErrorGroups.Transactions#DOWNGRADE_LOCK_ERR},
+ * {@link org.apache.ignite.lang.ErrorGroups.Transactions#ACQUIRE_LOCK_TIMEOUT_ERR},
* @param message Detail message.
* @param cause Optional nested exception (can be {@code null}).
*/
diff --git a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockManager.java b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockManager.java
index 6cb72723b1..6aac334128 100644
--- a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockManager.java
+++ b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/LockManager.java
@@ -38,14 +38,14 @@ public interface LockManager {
public CompletableFuture<Lock> acquire(UUID txId, LockKey lockKey, LockMode lockMode);
/**
- * Attempts to release a lock for the specified {@code lockKey}.
+ * Attempts to release the specified lock.
*
* @param lock Lock to release.
*/
public void release(Lock lock);
/**
- * Release a lock that holds on a specific mode.
+ * Release a lock that is held on the specific mode on the specific key.
*
* @param txId Transaction id.
* @param lockKey The key.
diff --git a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/impl/HeapLockManager.java b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/impl/HeapLockManager.java
index f12444994d..8db16bca76 100644
--- a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/impl/HeapLockManager.java
+++ b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/impl/HeapLockManager.java
@@ -17,11 +17,14 @@
package org.apache.ignite.internal.tx.impl;
+import static java.util.concurrent.CompletableFuture.completedFuture;
import static org.apache.ignite.lang.ErrorGroups.Transactions.ACQUIRE_LOCK_ERR;
+import static org.apache.ignite.lang.ErrorGroups.Transactions.ACQUIRE_LOCK_TIMEOUT_ERR;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
@@ -32,8 +35,11 @@ import java.util.TreeMap;
import java.util.UUID;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.Executor;
+import java.util.concurrent.TimeUnit;
import org.apache.ignite.internal.tostring.IgniteToStringExclude;
import org.apache.ignite.internal.tostring.S;
+import org.apache.ignite.internal.tx.DeadlockPreventionPolicy;
import org.apache.ignite.internal.tx.Lock;
import org.apache.ignite.internal.tx.LockException;
import org.apache.ignite.internal.tx.LockKey;
@@ -47,27 +53,40 @@ import org.jetbrains.annotations.Nullable;
/**
* A {@link LockManager} implementation which stores lock queues in the heap.
*
- * <p>Lock waiters are placed in the queue, ordered from oldest to youngest (highest txId). When
- * a new waiter is placed in the queue, it's validated against current lock owner: if where is an owner with a higher timestamp lock request
- * is denied.
+ * <p>Lock waiters are placed in the queue, ordered according to comparator provided by {@link HeapLockManager#deadlockPreventionPolicy}.
+ * When a new waiter is placed in the queue, it's validated against current lock owner: if there is an owner with a higher transaction id
+ * lock request is denied.
*
- * <p>Read lock can be upgraded to write lock (only available for the oldest read-locked entry of
+ * <p>Read lock can be upgraded to write lock (only available for the lowest read-locked entry of
* the queue).
- *
- * <p>If a younger read lock was upgraded, it will be invalidated if a oldest read-locked entry was upgraded. This corresponds
- * to the following scenario:
- *
- * <p>v1 = get(k, timestamp1) // timestamp1 < timestamp2
- *
- * <p>v2 = get(k, timestamp2)
- *
- * <p>put(k, v1, timestamp2) // Upgrades a younger read-lock to write-lock and waits for acquisition.
- *
- * <p>put(k, v1, timestamp1) // Upgrades an older read-lock. This will invalidate the younger write-lock.
*/
public class HeapLockManager implements LockManager {
private ConcurrentHashMap<LockKey, LockState> locks = new ConcurrentHashMap<>();
+ private final DeadlockPreventionPolicy deadlockPreventionPolicy;
+
+ /** Executor that is used to fail waiters after timeout. */
+ private final Executor delayedExecutor;
+
+ /**
+ * Constructor.
+ */
+ public HeapLockManager() {
+ this(new WaitDieDeadlockPreventionPolicy());
+ }
+
+ /**
+ * Constructor.
+ *
+ * @param deadlockPreventionPolicy Deadlock prevention policy.
+ */
+ public HeapLockManager(DeadlockPreventionPolicy deadlockPreventionPolicy) {
+ this.deadlockPreventionPolicy = deadlockPreventionPolicy;
+ this.delayedExecutor = deadlockPreventionPolicy.waitTimeout() > 0
+ ? CompletableFuture.delayedExecutor(deadlockPreventionPolicy.waitTimeout(), TimeUnit.MILLISECONDS)
+ : null;
+ }
+
@Override
public CompletableFuture<Lock> acquire(UUID txId, LockKey lockKey, LockMode lockMode) {
while (true) {
@@ -131,7 +150,7 @@ public class HeapLockManager implements LockManager {
* @param key The key.
*/
private @NotNull LockState lockState(LockKey key) {
- return locks.computeIfAbsent(key, k -> new LockState());
+ return locks.computeIfAbsent(key, k -> new LockState(deadlockPreventionPolicy, delayedExecutor));
}
/** {@inheritDoc} */
@@ -151,11 +170,25 @@ public class HeapLockManager implements LockManager {
*/
private static class LockState {
/** Waiters. */
- private final TreeMap<UUID, WaiterImpl> waiters = new TreeMap<>();
+ private final TreeMap<UUID, WaiterImpl> waiters;
+
+ private final DeadlockPreventionPolicy deadlockPreventionPolicy;
+
+ /** Delayed executor for waiters timeout callback. */
+ private final Executor delayedExecutor;
/** Marked for removal flag. */
private boolean markedForRemove = false;
+ public LockState(DeadlockPreventionPolicy deadlockPreventionPolicy, Executor delayedExecutor) {
+ Comparator<UUID> txComparator =
+ deadlockPreventionPolicy.txIdComparator() != null ? deadlockPreventionPolicy.txIdComparator() : UUID::compareTo;
+
+ this.waiters = new TreeMap<>(txComparator);
+ this.deadlockPreventionPolicy = deadlockPreventionPolicy;
+ this.delayedExecutor = delayedExecutor;
+ }
+
/**
* Attempts to acquire a lock for the specified {@code key} in specified lock mode.
*
@@ -185,7 +218,7 @@ public class HeapLockManager implements LockManager {
waiter.upgrade(prev);
- return new IgniteBiTuple(CompletableFuture.completedFuture(null), prev.lockMode());
+ return new IgniteBiTuple(completedFuture(null), prev.lockMode());
} else {
waiter.upgrade(prev);
@@ -195,7 +228,11 @@ public class HeapLockManager implements LockManager {
}
if (!isWaiterReadyToNotify(waiter, false)) {
- return new IgniteBiTuple(waiter.fut, waiter.lockMode());
+ if (deadlockPreventionPolicy.waitTimeout() > 0) {
+ setWaiterTimeout(waiter);
+ }
+
+ return new IgniteBiTuple<>(waiter.fut, waiter.lockMode());
}
if (!waiter.locked()) {
@@ -212,7 +249,7 @@ public class HeapLockManager implements LockManager {
}
/**
- * Checks current waiter.
+ * Checks current waiter. It can change the internal state of the waiter.
*
* @param waiter Checked waiter.
* @return True if current waiter ready to notify, false otherwise.
@@ -223,6 +260,12 @@ public class HeapLockManager implements LockManager {
LockMode mode = lockedMode(tmp);
if (mode != null && !mode.isCompatible(waiter.intendedLockMode())) {
+ if (!deadlockPreventionPolicy.usePriority() && deadlockPreventionPolicy.waitTimeout() == 0) {
+ waiter.fail(lockException(waiter.txId(), tmp));
+
+ return true;
+ }
+
return false;
}
}
@@ -234,11 +277,12 @@ public class HeapLockManager implements LockManager {
if (mode != null && !mode.isCompatible(waiter.intendedLockMode())) {
if (skipFail) {
return false;
- } else {
- waiter.fail(new LockException(ACQUIRE_LOCK_ERR, "Failed to acquire a lock due to a conflict [txId=" + waiter.txId()
- + ", waiter=" + tmp + ']'));
+ } else if (deadlockPreventionPolicy.waitTimeout() == 0) {
+ waiter.fail(lockException(waiter.txId(), tmp));
return true;
+ } else {
+ return false;
}
}
}
@@ -248,6 +292,18 @@ public class HeapLockManager implements LockManager {
return true;
}
+ /**
+ * Create lock exception with given parameters.
+ *
+ * @param txId Transaction id.
+ * @param conflictingWaiter Conflicting waiter.
+ * @return Lock exception.
+ */
+ private LockException lockException(UUID txId, WaiterImpl conflictingWaiter) {
+ return new LockException(ACQUIRE_LOCK_ERR, "Failed to acquire a lock due to a conflict [txId="
+ + txId + ", conflictingWaiter=" + conflictingWaiter + ']');
+ }
+
/**
* Attempts to release a lock for the specified {@code key} in exclusive mode.
*
@@ -329,7 +385,11 @@ public class HeapLockManager implements LockManager {
*
* @return List of waiters to notify.
*/
- private ArrayList<WaiterImpl> unlockCompatibleWaiters() {
+ private List<WaiterImpl> unlockCompatibleWaiters() {
+ if (!deadlockPreventionPolicy.usePriority() && deadlockPreventionPolicy.waitTimeout() == 0) {
+ return Collections.emptyList();
+ }
+
ArrayList<WaiterImpl> toNotify = new ArrayList<>();
Set<UUID> toFail = new HashSet<>();
@@ -343,31 +403,47 @@ public class HeapLockManager implements LockManager {
}
}
- for (Map.Entry<UUID, WaiterImpl> entry : waiters.entrySet()) {
- WaiterImpl tmp = entry.getValue();
+ if (deadlockPreventionPolicy.usePriority() && deadlockPreventionPolicy.waitTimeout() >= 0) {
+ for (Map.Entry<UUID, WaiterImpl> entry : waiters.entrySet()) {
+ WaiterImpl tmp = entry.getValue();
- if (tmp.hasLockIntent() && isWaiterReadyToNotify(tmp, false)) {
- assert tmp.hasLockIntent() : "Only failed waiter can be notified here [waiter=" + tmp + ']';
+ if (tmp.hasLockIntent() && isWaiterReadyToNotify(tmp, false)) {
+ assert tmp.hasLockIntent() : "Only failed waiter can be notified here [waiter=" + tmp + ']';
- toNotify.add(tmp);
- toFail.add(tmp.txId());
+ toNotify.add(tmp);
+ toFail.add(tmp.txId());
+ }
}
- }
- for (UUID failTx : toFail) {
- var w = waiters.get(failTx);
+ for (UUID failTx : toFail) {
+ var w = waiters.get(failTx);
- if (w.locked()) {
- w.refuseIntent();
- } else {
- waiters.remove(failTx);
+ if (w.locked()) {
+ w.refuseIntent();
+ } else {
+ waiters.remove(failTx);
+ }
}
-
}
return toNotify;
}
+ /**
+ * Makes the waiter fail after specified timeout (in milliseconds), if intended lock was not acquired within this timeout.
+ *
+ * @param waiter Waiter.
+ */
+ private void setWaiterTimeout(WaiterImpl waiter) {
+ delayedExecutor.execute(() -> {
+ if (!waiter.fut.isDone()) {
+ waiter.fut.completeExceptionally(new LockException(ACQUIRE_LOCK_TIMEOUT_ERR, "Failed to acquire a lock due to "
+ + "timeout [txId=" + waiter.txId() + ", waiter=" + waiter
+ + ", timeout=" + deadlockPreventionPolicy.waitTimeout() + ']'));
+ }
+ });
+ }
+
/**
* Gets a lock mode for this waiter.
*
@@ -412,7 +488,6 @@ public class HeapLockManager implements LockManager {
* A waiter implementation.
*/
private static class WaiterImpl implements Comparable<WaiterImpl>, Waiter {
-
/**
* Holding locks by type.
* TODO: IGNITE-18350 Abandon the collection in favor of BitSet.
diff --git a/modules/transactions/src/main/java/org/apache/ignite/internal/tx/impl/WaitDieDeadlockPreventionPolicy.java b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/impl/WaitDieDeadlockPreventionPolicy.java
new file mode 100644
index 0000000000..6a263bf1dd
--- /dev/null
+++ b/modules/transactions/src/main/java/org/apache/ignite/internal/tx/impl/WaitDieDeadlockPreventionPolicy.java
@@ -0,0 +1,41 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+package org.apache.ignite.internal.tx.impl;
+
+import java.util.Comparator;
+import java.util.UUID;
+import org.apache.ignite.internal.tx.DeadlockPreventionPolicy;
+
+/**
+ * Deadlock prevention policy that, in case of conflict of transactions tx1 and tx2 on the same key, assuming tx1 is holding the lock,
+ * allows tx2 to wait for the lock if tx2 is older than tx1, and aborts tx2 is tx2 is younger than tx1.
+ */
+public class WaitDieDeadlockPreventionPolicy implements DeadlockPreventionPolicy {
+ /** {@inheritDoc} */
+ @Override
+ public Comparator<UUID> txIdComparator() {
+ return UUID::compareTo;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public long waitTimeout() {
+ return 0;
+ }
+}
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/DeadlockPreventionTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractDeadlockPreventionTest.java
similarity index 70%
rename from modules/transactions/src/test/java/org/apache/ignite/internal/tx/DeadlockPreventionTest.java
rename to modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractDeadlockPreventionTest.java
index ca695d99cb..f32ef4e0a6 100644
--- a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/DeadlockPreventionTest.java
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractDeadlockPreventionTest.java
@@ -20,36 +20,29 @@ package org.apache.ignite.internal.tx;
import static org.apache.ignite.internal.testframework.IgniteTestUtils.hasCause;
import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willCompleteSuccessfully;
import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willSucceedFast;
-import static org.apache.ignite.internal.tx.LockMode.S;
-import static org.apache.ignite.internal.tx.LockMode.X;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.jupiter.api.Assertions.assertFalse;
-import static org.junit.jupiter.api.Assertions.assertNotNull;
-import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.fail;
-import java.nio.ByteBuffer;
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-import java.util.UUID;
import java.util.concurrent.CompletableFuture;
-import java.util.concurrent.CompletionException;
import java.util.function.Supplier;
import org.apache.ignite.internal.tx.impl.HeapLockManager;
import org.junit.jupiter.api.Test;
/**
- * Tests for deadlock prevention scenarios.
+ * Abstract class containing some tests for deadlock prevention that check common scenarios for different policies.
*/
-public class DeadlockPreventionTest {
- private LockManager lockManager = new HeapLockManager();
- private Map<UUID, List<CompletableFuture<Lock>>> locks = new HashMap<>();
+public abstract class AbstractDeadlockPreventionTest extends AbstractLockingTest {
+ protected abstract DeadlockPreventionPolicy deadlockPreventionPolicy();
+
+ @Override
+ protected LockManager lockManager() {
+ return new HeapLockManager(deadlockPreventionPolicy());
+ }
@Test
- public void testWaitDie0() {
+ public void testSimpleConflict0() {
var tx1 = beginTx();
var tx2 = beginTx();
@@ -57,11 +50,11 @@ public class DeadlockPreventionTest {
assertThat(xlock(tx1, key1), willCompleteSuccessfully());
- assertThrowsLockException(() -> xlock(tx2, key1));
+ assertFutureFailsOrWaitsForTimeout(() -> xlock(tx2, key1));
}
@Test
- public void testWaitDie1() {
+ public void testSimpleConflict1() {
var tx1 = beginTx();
var tx2 = beginTx();
@@ -77,7 +70,7 @@ public class DeadlockPreventionTest {
}
@Test
- public void testWaitDieSlocks1() {
+ public void testSimpleConflictSlocks1() {
var tx1 = beginTx();
var tx2 = beginTx();
@@ -86,11 +79,11 @@ public class DeadlockPreventionTest {
assertThat(slock(tx1, key1), willSucceedFast());
assertThat(slock(tx2, key1), willSucceedFast());
- assertThrowsLockException(() -> xlock(tx2, key1));
+ assertFutureFailsOrWaitsForTimeout(() -> xlock(tx2, key1));
}
@Test
- public void testWaitDieSlocks2() {
+ public void testSimpleConflictSlocks2() {
var tx1 = beginTx();
var tx2 = beginTx();
@@ -102,11 +95,15 @@ public class DeadlockPreventionTest {
CompletableFuture<?> xlockTx1 = xlock(tx1, key1);
assertFalse(xlockTx1.isDone());
- assertThrowsLockException(() -> xlock(tx2, key1));
+ CompletableFuture<?> xlockTx2 = xlock(tx2, key1);
+
+ assertFutureFailsOrWaitsForTimeout(() -> xlockTx2);
- rollbackTx(tx2);
+ if (xlockTx2.isDone()) {
+ rollbackTx(tx2);
- assertThat(xlockTx1, willSucceedFast());
+ assertThat(xlockTx1, willSucceedFast());
+ }
}
@Test
@@ -127,10 +124,9 @@ public class DeadlockPreventionTest {
commitTx(tx3);
- // TODO correctness
assertThat(futTx1, willSucceedFast());
- assertThrowsLockException(() -> futTx2);
+ assertFutureFailsOrWaitsForTimeout(() -> futTx2);
}
@Test
@@ -161,7 +157,7 @@ public class DeadlockPreventionTest {
assertThat(slock(tx2, k), willSucceedFast());
assertThat(slock(tx1, k), willSucceedFast());
- assertThrowsLockException(() -> xlock(tx2, k));
+ assertFutureFailsOrWaitsForTimeout(() -> xlock(tx2, k));
}
@Test
@@ -209,7 +205,7 @@ public class DeadlockPreventionTest {
commitTx(tx3);
- assertThrowsLockException(() -> futTx2);
+ assertFutureFailsOrWaitsForTimeout(() -> futTx2);
}
@Test
@@ -292,77 +288,26 @@ public class DeadlockPreventionTest {
assertThat(futTx1, willSucceedFast());
}
- private UUID beginTx() {
- return Timestamp.nextVersion().toUuid();
- }
-
- private LockKey key(Object key) {
- ByteBuffer b = ByteBuffer.allocate(Integer.BYTES);
- b.putInt(key.hashCode());
-
- return new LockKey(b);
- }
-
- private CompletableFuture<?> xlock(UUID tx, LockKey key) {
- return acquire(tx, key, X);
- }
-
- private CompletableFuture<?> slock(UUID tx, LockKey key) {
- return acquire(tx, key, S);
- }
-
- private CompletableFuture<?> acquire(UUID tx, LockKey key, LockMode mode) {
- CompletableFuture<Lock> fut = lockManager.acquire(tx, key, mode);
-
- locks.compute(tx, (k, v) -> {
- if (v == null) {
- v = new ArrayList<>();
- }
-
- v.add(fut);
-
- return v;
- });
-
- return fut;
- }
-
- private void commitTx(UUID tx) {
- finishTx(tx);
- }
-
- private void rollbackTx(UUID tx) {
- finishTx(tx);
- }
-
- private void finishTx(UUID tx) {
- List<CompletableFuture<Lock>> txLocks = locks.remove(tx);
- assertNotNull(txLocks);
-
- for (CompletableFuture<Lock> fut : txLocks) {
- assertTrue(fut.isDone());
-
- if (!fut.isCompletedExceptionally()) {
- Lock lock = fut.join();
-
- lockManager.release(lock);
- }
- }
- }
-
- private static void assertCompletedExceptionally(CompletableFuture<?> fut) {
- assertTrue(fut.isDone());
- assertThrows(CompletionException.class, fut::join);
- }
-
- private static void assertThrowsLockException(Supplier<CompletableFuture<?>> s) {
+ /**
+ * This method checks lock future of conflicting transaction provided by supplier, in a way depending on deadlock prevention policy.
+ * If the policy does not allow wait on conflict (wait timeout is equal to {@code 0}) then the future must be failed with
+ * {@link LockException}. Otherwise, it must be not completed. This method is only suitable for checking lock futures of lower priority
+ * transactions, if transaction priority is applicable.
+ *
+ * @param s Supplier of lock future.
+ */
+ protected void assertFutureFailsOrWaitsForTimeout(Supplier<CompletableFuture<?>> s) {
try {
CompletableFuture<?> f = s.get();
- assertTrue(f.isDone());
- f.join();
+ if (deadlockPreventionPolicy().waitTimeout() == 0) {
+ assertTrue(f.isDone());
+ f.join();
- fail();
+ fail();
+ } else {
+ assertFalse(f.isDone());
+ }
} catch (Exception e) {
if (!hasCause(e, LockException.class, null)) {
fail();
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractLockManagerTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractLockManagerTest.java
index b0208498f1..7151370ecc 100644
--- a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractLockManagerTest.java
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractLockManagerTest.java
@@ -63,7 +63,7 @@ public abstract class AbstractLockManagerTest extends IgniteAbstractTest {
protected abstract LockManager newInstance();
@Test
- public void testSingleKeyWrite() throws LockException {
+ public void testSingleKeyWrite() {
UUID txId1 = Timestamp.nextVersion().toUuid();
LockKey key = new LockKey("test");
@@ -727,7 +727,7 @@ public abstract class AbstractLockManagerTest extends IgniteAbstractTest {
for (LockMode lockMode : LockMode.values()) {
lockManager.acquire(txId, key, lockMode);
- lockManager. release(txId, key, lockMode);
+ lockManager.release(txId, key, lockMode);
}
assertTrue(lockManager.locks(txId).hasNext());
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractLockingTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractLockingTest.java
new file mode 100644
index 0000000000..fde11382ce
--- /dev/null
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/AbstractLockingTest.java
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.tx;
+
+import static org.apache.ignite.internal.tx.LockMode.S;
+import static org.apache.ignite.internal.tx.LockMode.X;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.nio.ByteBuffer;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.UUID;
+import java.util.concurrent.CompletableFuture;
+import org.apache.ignite.lang.IgniteBiTuple;
+
+/**
+ * Abstract class making lock manager tests more simple.
+ */
+public abstract class AbstractLockingTest {
+ protected final LockManager lockManager = lockManager();
+ private Map<UUID, Map<IgniteBiTuple<LockKey, LockMode>, CompletableFuture<Lock>>> locks = new HashMap<>();
+
+ protected abstract LockManager lockManager();
+
+ protected UUID beginTx() {
+ return Timestamp.nextVersion().toUuid();
+ }
+
+ protected LockKey key(Object key) {
+ ByteBuffer b = ByteBuffer.allocate(Integer.BYTES);
+ b.putInt(key.hashCode());
+ b.position(0);
+
+ return new LockKey(b);
+ }
+
+ protected CompletableFuture<?> xlock(UUID tx, LockKey key) {
+ return acquire(tx, key, X);
+ }
+
+ protected CompletableFuture<?> slock(UUID tx, LockKey key) {
+ return acquire(tx, key, S);
+ }
+
+ protected CompletableFuture<?> acquire(UUID tx, LockKey key, LockMode mode) {
+ CompletableFuture<Lock> fut = lockManager.acquire(tx, key, mode);
+
+ locks.compute(tx, (k, v) -> {
+ if (v == null) {
+ v = new HashMap<>();
+ }
+
+ assertFalse(v.containsKey(mode));
+
+ v.put(new IgniteBiTuple<>(key, mode), fut);
+
+ return v;
+ });
+
+ return fut;
+ }
+
+ protected void commitTx(UUID tx) {
+ finishTx(tx);
+ }
+
+ protected void rollbackTx(UUID tx) {
+ finishTx(tx);
+ }
+
+ protected void finishTx(UUID tx) {
+ Map<IgniteBiTuple<LockKey, LockMode>, CompletableFuture<Lock>> txLocks = locks.remove(tx);
+ assertNotNull(txLocks);
+
+ for (Map.Entry<IgniteBiTuple<LockKey, LockMode>, CompletableFuture<Lock>> e : txLocks.entrySet()) {
+ CompletableFuture<Lock> fut = e.getValue();
+
+ assertTrue(fut.isDone());
+
+ if (!fut.isCompletedExceptionally()) {
+ Lock lock = fut.join();
+
+ lockManager.release(lock);
+ }
+ }
+ }
+
+ protected void release(UUID tx, LockKey key, LockMode lockMode) {
+ Map<IgniteBiTuple<LockKey, LockMode>, CompletableFuture<Lock>> txLocks = locks.get(tx);
+ assertNotNull(txLocks);
+
+ CompletableFuture<Lock> lockFut = txLocks.remove(new IgniteBiTuple<>(key, lockMode));
+ assertNotNull(lockFut);
+ assertTrue(lockFut.isDone());
+
+ if (!lockFut.isCompletedExceptionally()) {
+ Lock lock = lockFut.join();
+ lockManager.release(lock);
+ }
+
+ if (txLocks.isEmpty()) {
+ locks.remove(tx);
+ }
+ }
+}
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/NoWaitDeadlockPreventionTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/NoWaitDeadlockPreventionTest.java
new file mode 100644
index 0000000000..87944cf244
--- /dev/null
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/NoWaitDeadlockPreventionTest.java
@@ -0,0 +1,124 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.tx;
+
+import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willFailFast;
+import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willSucceedFast;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.util.concurrent.CompletableFuture;
+import org.apache.ignite.internal.tx.impl.HeapLockManager;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test for NO-WAIT deadlock prevention policy, i.e. policy that aborts any transaction that creates a lock request conflicting with
+ * another transaction.
+ */
+public class NoWaitDeadlockPreventionTest extends AbstractLockingTest {
+ private DeadlockPreventionPolicy deadlockPreventionPolicy() {
+ return new DeadlockPreventionPolicy() {
+ @Override
+ public long waitTimeout() {
+ return 0;
+ }
+ };
+ }
+
+ @Override
+ protected LockManager lockManager() {
+ return new HeapLockManager(deadlockPreventionPolicy());
+ }
+
+ @Test
+ public void noWaitFail() {
+ var tx1 = beginTx();
+ var tx2 = beginTx();
+
+ var key = key("test");
+
+ for (LockMode m1 : LockMode.values()) {
+ for (LockMode m2 : LockMode.values()) {
+ assertThat(acquire(tx1, key, m1), willSucceedFast());
+ CompletableFuture<?> tx2Fut = acquire(tx2, key, m2);
+
+ if (m1.isCompatible(m2)) {
+ assertThat(tx2Fut, willSucceedFast());
+ } else {
+ assertTrue(tx2Fut.isCompletedExceptionally());
+ }
+
+ release(tx1, key, m1);
+ release(tx2, key, m2);
+ }
+ }
+ }
+
+ @Test
+ public void noWaitFailReverseOrder() {
+ var tx1 = beginTx();
+ var tx2 = beginTx();
+
+ var key = key("test");
+
+ for (LockMode m2 : LockMode.values()) {
+ for (LockMode m1 : LockMode.values()) {
+ assertThat(acquire(tx2, key, m2), willSucceedFast());
+ CompletableFuture<?> tx1Fut = acquire(tx1, key, m1);
+
+ if (m2.isCompatible(m1)) {
+ assertThat(tx1Fut, willSucceedFast());
+ } else {
+ assertTrue(tx1Fut.isCompletedExceptionally());
+ }
+
+ release(tx2, key, m2);
+ release(tx1, key, m1);
+ }
+ }
+ }
+
+ @Test
+ public void allowNoWaitOnDeadlockOnOne() {
+ var tx0 = beginTx();
+ var tx1 = beginTx();
+
+ var key = key("test0");
+
+ assertThat(slock(tx0, key), willSucceedFast());
+ assertThat(slock(tx1, key), willSucceedFast());
+
+ assertThat(xlock(tx0, key), willFailFast(LockException.class));
+ assertThat(xlock(tx1, key), willFailFast(LockException.class));
+ }
+
+ @Test
+ public void allowNoWaitOnDeadlockOnTwoKeys() {
+ var tx0 = beginTx();
+ var tx1 = beginTx();
+
+ var key0 = key("test0");
+ var key1 = key("test1");
+
+ assertThat(xlock(tx0, key0), willSucceedFast());
+ assertThat(xlock(tx1, key1), willSucceedFast());
+
+ assertThat(xlock(tx0, key1), willFailFast(LockException.class));
+ assertThat(xlock(tx1, key0), willFailFast(LockException.class));
+ }
+}
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/NoneDeadlockPreventionTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/NoneDeadlockPreventionTest.java
new file mode 100644
index 0000000000..9651543986
--- /dev/null
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/NoneDeadlockPreventionTest.java
@@ -0,0 +1,63 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.tx;
+
+import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willSucceedFast;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test for NONE deadlock prevention policy, i.e. policy that doesn't prevent any deadlocks.
+ */
+public class NoneDeadlockPreventionTest extends AbstractDeadlockPreventionTest {
+ @Override
+ protected DeadlockPreventionPolicy deadlockPreventionPolicy() {
+ return new DeadlockPreventionPolicy() { };
+ }
+
+ @Test
+ public void allowDeadlockOnOneKey() {
+ var tx0 = beginTx();
+ var tx1 = beginTx();
+
+ var key = key("test0");
+
+ assertThat(slock(tx0, key), willSucceedFast());
+ assertThat(slock(tx1, key), willSucceedFast());
+
+ assertFalse(xlock(tx0, key).isDone());
+ assertFalse(xlock(tx1, key).isDone());
+ }
+
+ @Test
+ public void allowDeadlockOnTwoKeys() {
+ var tx0 = beginTx();
+ var tx1 = beginTx();
+
+ var key0 = key("test0");
+ var key1 = key("test1");
+
+ assertThat(xlock(tx0, key0), willSucceedFast());
+ assertThat(xlock(tx1, key1), willSucceedFast());
+
+ assertFalse(xlock(tx0, key1).isDone());
+ assertFalse(xlock(tx1, key0).isDone());
+ }
+}
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/ReversedDeadlockPreventionTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/ReversedDeadlockPreventionTest.java
new file mode 100644
index 0000000000..4586501b7d
--- /dev/null
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/ReversedDeadlockPreventionTest.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.tx;
+
+import java.util.Comparator;
+import java.util.UUID;
+import org.jetbrains.annotations.Nullable;
+import org.junit.jupiter.api.BeforeEach;
+
+/**
+ * Test for WOUND-WAIT deadlock prevention policy.
+ */
+public class ReversedDeadlockPreventionTest extends AbstractDeadlockPreventionTest {
+ private long counter;
+
+ @BeforeEach
+ public void before() {
+ counter = 0;
+ }
+
+ @Override
+ protected UUID beginTx() {
+ counter++;
+ return new UUID(0, Long.MAX_VALUE - counter);
+ }
+
+ @Override
+ protected DeadlockPreventionPolicy deadlockPreventionPolicy() {
+ return new DeadlockPreventionPolicy() {
+ @Override
+ public @Nullable Comparator<UUID> txIdComparator() {
+ return Comparator.reverseOrder();
+ }
+
+ @Override
+ public long waitTimeout() {
+ return 0;
+ }
+ };
+ }
+}
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/TimeoutDeadlockPreventionTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/TimeoutDeadlockPreventionTest.java
new file mode 100644
index 0000000000..770493e224
--- /dev/null
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/TimeoutDeadlockPreventionTest.java
@@ -0,0 +1,142 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.tx;
+
+import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willFailFast;
+import static org.apache.ignite.internal.testframework.matchers.CompletableFutureMatcher.willSucceedFast;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+
+import java.util.concurrent.CompletableFuture;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test for NO-WAIT deadlock prevention policy, i.e. policy working in the same way as NO-WAIT but with timeout.
+ */
+public class TimeoutDeadlockPreventionTest extends AbstractDeadlockPreventionTest {
+ @Override
+ protected DeadlockPreventionPolicy deadlockPreventionPolicy() {
+ return new DeadlockPreventionPolicy() {
+ @Override
+ public long waitTimeout() {
+ return 200;
+ }
+ };
+ }
+
+ @Test
+ public void timeoutTest() {
+ var tx1 = beginTx();
+ var tx2 = beginTx();
+
+ var key = key("test");
+
+ assertThat(xlock(tx1, key), willSucceedFast());
+ CompletableFuture<?> tx2Fut = xlock(tx2, key);
+
+ assertFalse(tx2Fut.isDone());
+
+ commitTx(tx1);
+
+ assertThat(tx2Fut, willSucceedFast());
+ }
+
+ @Test
+ public void timeoutTestReverseOrder() {
+ var tx1 = beginTx();
+ var tx2 = beginTx();
+
+ var key = key("test");
+
+ assertThat(xlock(tx2, key), willSucceedFast());
+ CompletableFuture<?> tx2Fut = xlock(tx1, key);
+
+ assertFalse(tx2Fut.isDone());
+
+ commitTx(tx2);
+
+ assertThat(tx2Fut, willSucceedFast());
+ }
+
+ @Test
+ public void timeoutFail() throws InterruptedException {
+ var tx1 = beginTx();
+ var tx2 = beginTx();
+
+ var key = key("test");
+
+ assertThat(xlock(tx1, key), willSucceedFast());
+ CompletableFuture<?> tx2Fut = xlock(tx2, key);
+
+ assertFalse(tx2Fut.isDone());
+
+ Thread.sleep(350);
+
+ commitTx(tx1);
+
+ assertThat(tx2Fut, willFailFast(LockException.class));
+ }
+
+ @Test
+ public void timeoutFailReverseOrder() throws InterruptedException {
+ var tx1 = beginTx();
+ var tx2 = beginTx();
+
+ var key = key("test");
+
+ assertThat(xlock(tx2, key), willSucceedFast());
+ CompletableFuture<?> tx2Fut = xlock(tx1, key);
+
+ assertFalse(tx2Fut.isDone());
+
+ Thread.sleep(350);
+
+ commitTx(tx2);
+
+ assertThat(tx2Fut, willFailFast(LockException.class));
+ }
+
+ @Test
+ public void allowDeadlockOnOneKeyWithTimeout() {
+ var tx0 = beginTx();
+ var tx1 = beginTx();
+
+ var key = key("test0");
+
+ assertThat(slock(tx0, key), willSucceedFast());
+ assertThat(slock(tx1, key), willSucceedFast());
+
+ assertThat(xlock(tx0, key), willFailFast(LockException.class));
+ assertThat(xlock(tx1, key), willFailFast(LockException.class));
+ }
+
+ @Test
+ public void allowDeadlockOnTwoKeysWithTimeout() {
+ var tx0 = beginTx();
+ var tx1 = beginTx();
+
+ var key0 = key("test0");
+ var key1 = key("test1");
+
+ assertThat(xlock(tx0, key0), willSucceedFast());
+ assertThat(xlock(tx1, key1), willSucceedFast());
+
+ assertThat(xlock(tx0, key1), willFailFast(LockException.class));
+ assertThat(xlock(tx1, key0), willFailFast(LockException.class));
+ }
+}
diff --git a/modules/transactions/src/test/java/org/apache/ignite/internal/tx/WaitDieDeadlockPreventionTest.java b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/WaitDieDeadlockPreventionTest.java
new file mode 100644
index 0000000000..273a494554
--- /dev/null
+++ b/modules/transactions/src/test/java/org/apache/ignite/internal/tx/WaitDieDeadlockPreventionTest.java
@@ -0,0 +1,30 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.tx;
+
+import org.apache.ignite.internal.tx.impl.WaitDieDeadlockPreventionPolicy;
+
+/**
+ * Test for {@link WaitDieDeadlockPreventionPolicy}.
+ */
+public class WaitDieDeadlockPreventionTest extends AbstractDeadlockPreventionTest {
+ @Override
+ protected DeadlockPreventionPolicy deadlockPreventionPolicy() {
+ return new WaitDieDeadlockPreventionPolicy();
+ }
+}