[
https://issues.apache.org/jira/browse/IGNITE-16175?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Alexey Scherbakov updated IGNITE-16175:
---------------------------------------
Description:
h3. The actual definitions of deadlock prevention schemes look as the follows:
h3. Wait-Die Scheme
In this scheme, if a transaction requests to lock a resource (data item), which
is already held with a conflicting lock by another transaction, then one of the
two possibilities may occur −
* If TS(T{~}i{~}) < TS(T{~}j{~}) − that is T{~}i{~}, which is requesting a
conflicting lock, is older than T{~}j{~} − then T{~}i{~} is allowed to wait
until the data-item is available.
* If TS(T{~}i{~}) > TS(t{~}j{~}) − that is T{~}i{~} is younger than T{~}j{~} −
then T{~}i{~} dies. T{~}i{~} is restarted later with a random delay but with
the same timestamp.
This scheme allows the older transaction to wait but kills the younger one.
h3. Wound-Wait Scheme
In this scheme, if a transaction requests to lock a resource (data item), which
is already held with conflicting lock by some another transaction, one of the
two possibilities may occur −
* If TS(T{~}i{~}) < TS(T{~}j{~}), then T{~}i{~} forces T{~}j{~} to be rolled
back − that is T{~}i{~} wounds T{~}j{~}. T{~}j{~} is restarted later with a
random delay but with the same timestamp.
* If TS(T{~}i{~}) > TS(T{~}j{~}), then T{~}i{~} is forced to wait until the
resource is available.
This scheme, allows the younger transaction to wait; but when an older
transaction requests an item held by a younger one, the older transaction
forces the younger one to abort and release the item.
In both the cases, the transaction that enters the system at a later stage is
aborted.
*It seems current implementation doesn't exactly follow any of one.*
Currently a younger transaction can kill older transaction.
Transactions must be restarted with the same timestamp to reduce abort rate.
This test must pass in wound-wait mode:
{code:java}
public void testWoundWait() {
accounts.recordView().upsert(makeValue(1, 100.));
InternalTransaction tx = (InternalTransaction)
igniteTransactions.begin();
InternalTransaction tx2 = (InternalTransaction)
igniteTransactions.begin();
var table = accounts.recordView().withTransaction(tx); // Older tx
var table2 = accounts.recordView().withTransaction(tx2); // Younger tx
assertTrue(tx.timestamp().compareTo(tx2.timestamp()) < 0);
table2.upsert(makeValue(1, 200));
table.get(makeKey(1));
assertThrows(Exception.class, () -> tx2.commit(), "Younger tx must be
aborted");
}
{code}
It's also interesting to investigate other prevention modes, like NO_WAIT,
which claims to be most performant mode [1]
[1] http://www.vldb.org/pvldb/vol8/p209-yu.pdf
was:
h3. The actual definitions of deadlock prevention schemes look as the follows:
h3. Wait-Die Scheme
In this scheme, if a transaction requests to lock a resource (data item), which
is already held with a conflicting lock by another transaction, then one of the
two possibilities may occur −
* If TS(T{~}i{~}) < TS(T{~}j{~}) − that is T{~}i{~}, which is requesting a
conflicting lock, is older than T{~}j{~} − then T{~}i{~} is allowed to wait
until the data-item is available.
* If TS(T{~}i{~}) > TS(t{~}j{~}) − that is T{~}i{~} is younger than T{~}j{~} −
then T{~}i{~} dies. T{~}i{~} is restarted later with a random delay but with
the same timestamp.
This scheme allows the older transaction to wait but kills the younger one.
h3. Wound-Wait Scheme
In this scheme, if a transaction requests to lock a resource (data item), which
is already held with conflicting lock by some another transaction, one of the
two possibilities may occur −
* If TS(T{~}i{~}) < TS(T{~}j{~}), then T{~}i{~} forces T{~}j{~} to be rolled
back − that is T{~}i{~} wounds T{~}j{~}. T{~}j{~} is restarted later with a
random delay but with the same timestamp.
* If TS(T{~}i{~}) > TS(T{~}j{~}), then T{~}i{~} is forced to wait until the
resource is available.
This scheme, allows the younger transaction to wait; but when an older
transaction requests an item held by a younger one, the older transaction
forces the younger one to abort and release the item.
In both the cases, the transaction that enters the system at a later stage is
aborted.
*It seems current implementation doesn't exactly follow any of one.*
Currently a younger transaction can kill older transaction.
Transactions must be restarted with the same timestamp to reduce abort rate.
This test must pass in wound-wait mode:
{code:java}
public void testWoundWait() {
accounts.recordView().upsert(makeValue(1, 100.));
InternalTransaction tx = (InternalTransaction)
igniteTransactions.begin();
InternalTransaction tx2 = (InternalTransaction)
igniteTransactions.begin();
var table = accounts.recordView().withTransaction(tx); // Older tx
var table2 = accounts.recordView().withTransaction(tx2); // Younger tx
assertTrue(tx.timestamp().compareTo(tx2.timestamp()) < 0);
table2.upsert(makeValue(1, 200));
table.get(makeKey(1));
assertThrows(Exception.class, () -> tx2.commit(), "Younger tx must be
aborted");
}
{code}
> Deadlock prevention implementation doesn't exactly follows the definition
> -------------------------------------------------------------------------
>
> Key: IGNITE-16175
> URL: https://issues.apache.org/jira/browse/IGNITE-16175
> Project: Ignite
> Issue Type: Improvement
> Reporter: Alexey Scherbakov
> Priority: Major
> Labels: ignite-3
>
> h3. The actual definitions of deadlock prevention schemes look as the follows:
> h3. Wait-Die Scheme
> In this scheme, if a transaction requests to lock a resource (data item),
> which is already held with a conflicting lock by another transaction, then
> one of the two possibilities may occur −
> * If TS(T{~}i{~}) < TS(T{~}j{~}) − that is T{~}i{~}, which is requesting a
> conflicting lock, is older than T{~}j{~} − then T{~}i{~} is allowed to wait
> until the data-item is available.
> * If TS(T{~}i{~}) > TS(t{~}j{~}) − that is T{~}i{~} is younger than T{~}j{~}
> − then T{~}i{~} dies. T{~}i{~} is restarted later with a random delay but
> with the same timestamp.
> This scheme allows the older transaction to wait but kills the younger one.
> h3. Wound-Wait Scheme
> In this scheme, if a transaction requests to lock a resource (data item),
> which is already held with conflicting lock by some another transaction, one
> of the two possibilities may occur −
> * If TS(T{~}i{~}) < TS(T{~}j{~}), then T{~}i{~} forces T{~}j{~} to be rolled
> back − that is T{~}i{~} wounds T{~}j{~}. T{~}j{~} is restarted later with a
> random delay but with the same timestamp.
> * If TS(T{~}i{~}) > TS(T{~}j{~}), then T{~}i{~} is forced to wait until the
> resource is available.
> This scheme, allows the younger transaction to wait; but when an older
> transaction requests an item held by a younger one, the older transaction
> forces the younger one to abort and release the item.
> In both the cases, the transaction that enters the system at a later stage is
> aborted.
> *It seems current implementation doesn't exactly follow any of one.*
> Currently a younger transaction can kill older transaction.
> Transactions must be restarted with the same timestamp to reduce abort rate.
> This test must pass in wound-wait mode:
> {code:java}
> public void testWoundWait() {
> accounts.recordView().upsert(makeValue(1, 100.));
> InternalTransaction tx = (InternalTransaction)
> igniteTransactions.begin();
> InternalTransaction tx2 = (InternalTransaction)
> igniteTransactions.begin();
> var table = accounts.recordView().withTransaction(tx); // Older tx
> var table2 = accounts.recordView().withTransaction(tx2); // Younger tx
> assertTrue(tx.timestamp().compareTo(tx2.timestamp()) < 0);
> table2.upsert(makeValue(1, 200));
> table.get(makeKey(1));
> assertThrows(Exception.class, () -> tx2.commit(), "Younger tx must be
> aborted");
> }
> {code}
>
> It's also interesting to investigate other prevention modes, like NO_WAIT,
> which claims to be most performant mode [1]
> [1] http://www.vldb.org/pvldb/vol8/p209-yu.pdf
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
