It seems to be these two statements that conflict with one another; these
statements were group-committed on the master, so will be attempted by slave
to run in parallel:

UPDATE  `table10_innodb_int_autoinc` AS X SET `col_char_12_key` = 'j' WHERE X . `col_int_key` IN ( 223 , 4 , 113 , 1674772480 , 242679808 ) ORDER BY `col_char_12`,`col_char_12_key`,`col_int`,`col_int_key`,`pk` LIMIT 5;

UPDATE  `table10_innodb_int_autoinc` AS X SET `col_char_12_key` = 4113170432  ORDER BY `col_char_12`,`col_char_12_key`,`col_int`,`col_int_key`,`pk` LIMIT 7;

Here is the content of the table after replaying the binlogs up to this point:

The problem is probably caused by different execution plan on slave compared
to on master.

The first update can apparently use two different execution plans. One that
uses the `col_int_key` index to check the IN ( ... ) predicate, and one that
does not.

When using the index, the first UPDATE does not conflict with the second,
since no rows in the index match any of the values in the IN ( ... ) list.

However, when the index is not used, there is conflict with the second UPDATE,
as a table scan must be used.

This can be seen by adding IGNORE INDEX (col_int_key) to the first UPDATE; in
this case running the second update first blocks the first update:

--connect (s3,127.0.0.1,root,,test,$SLAVE_MYPORT,)

BEGIN;

UPDATE  `table10_innodb_int_autoinc` AS X SET `col_char_12_key` = 4113170432  ORDER BY `col_char_12`,`col_char_12_key`,`col_int`,`col_int_key`,`pk` LIMIT 7;

--connect (s1,127.0.0.1,root,,test,$SLAVE_MYPORT,)

BEGIN;

UPDATE  `table10_innodb_int_autoinc` AS X ignore index (col_int_key) SET `col_char_12_key` = 'j' WHERE X . `col_int_key` IN ( 223 , 4 , 113 , 1674772480 , 242679808 ) ORDER BY `col_char_12`,`col_char_12_key`,`col_int`,`col_int_key`,`pk` LIMIT 5;

# This UPDATE hangs here and eventually gets a lock wait timeout.

Unfortunately, this is a very serious issue, and I am not sure how it could be
solved. It is a fundamental assumption of parallel replication that if two
statements ran without lock conflicts on the master, then they will also be
able to run without lock conflicts on the slave. Without this, it is not safe
to enforce the same commit order on the slave, as it may cause deadlocks, as
seen in this example.

I am not sure that this requires using unsafe statements to trigger (like the
LIMIT in this case), I will try to investigate this further.

For a side note, these UPDATEs are probably not real unsafe statements, they look more like those that are currently marked unsafe because it is easier to do so. They have ORDER BY clauses which include, among other fields, pk, so the LIMIT should be deterministic and hence safe.
There are open upstream bugs about it, e.g. #62537 and #71105

Hi Kristian,

May I propose a solution to this problem (that I think might be useful also for a different scenario).
1) Record relay log position for when starting a set of parallel transactions
2) process transactions given parallelism
3) IF a lock wait time-out occurs, restart this set with parallelism set to 1.
4a) IF it fails even then too (with parallelism = 1) stop slave, report to user etc
4b) IF it works like this, reset parallelism to original value

Add counters so that DBA can see if this is a frequently occurring scenario.

(one can also imagine have more heuristics for how to handle the parallelism assuming
if there is a solid framework for retires exists)

—

An other scenario where a framework like above would be useful is to allow for
optimistic slave concurrency. I.e in certain scenarios guess that transactions can
be processed in parallel (still committing in order), and dynamically adjust parallelism down to 1
if this guess turns out to be wrong.

Way of guessing could be

• if transactions are created by different connections on master
  (would need to record this in binlog)
• if transactions use different databases
  etc etc...

What do you think ?

/Jonas

Hi Jonas,

> May I propose a solution to this problem (that I think might be useful also for a different scenario).
> 1) Record relay log position for when starting a set of parallel transactions
> 2) process transactions given parallelism
> 3) IF a lock wait time-out occurs, restart this set with parallelism set to 1.
> 4a) IF it fails even then too (with parallelism = 1) stop slave, report to user etc
> 4b) IF it works like this, reset parallelism to original value

The main problem is the need for a timeout. This timeout needs to be small
enough that it doesn't cause too much slave delay, yet large enough that it
doesn't cause spurious failure due to transactions taking too long without any
deadlocks.

However, we could actually detect the deadlock immediately without
timeouts. Whenever in InnoDB we are about to the transaction T1 wait for a
lock owned by T2, we can check if T1 needs to commit before T2 - if so,
instead of letting T1 wait, we will fail and rollback T2 with a deadlock
error. We then proceed to re-try T2 as you describe.

I think this is an interesting solution worth pursuing. I believe this is also
more or less what Galera does.

> An other scenario where a framework like above would be useful is to allow for
> optimistic slave concurrency. I.e in certain scenarios guess that transactions can
> be processed in parallel (still committing in order), and dynamically adjust parallelism down to 1
> if this guess turns out to be wrong.
>
> Way of guessing could be
>
> if transactions are created by different connections on master
> (would need to record this in binlog)
> if transactions use different databases
> etc etc...

Yes, I agree. Since we already know the desired commit order, we can just
start them in parallel and immediately detect if there is any conflict, seen
by a later transaction owning a row or gap lock needed by an earlier
transaction. In case of conflict, we can roll back the later transaction and
re-try it. As long as rollbacks are sufficiently infrequent, this should be a
win...

It is an interesting idea for sure. Maybe the time to try it out is getting
nearer.

- Kristian.

So here is how I think this bug should be fixed:

1. First, MDEV-5262 should be fixed, so that transactions that fail during
parallel replication due to deadlock or other temporary error can be re-tried
and eventually succeed.

2. Second, when InnoDB is about to let transaction T1 wait for a lock owned by
transaction T2, it should invoke a callback into the upper layer. This
callback will return a status code about what to do - either let T1 wait; roll
back T2 with deadlock error and let T1 proceed; or roll back T1 with deadlock
error. For parallel replication, we will then check if T1 comes before T2 in
commit order (same Relay_log_info and domain_id, and sub_id of T1 smaller than
T2); if so we ask to roll back T2 so that T1 can proceed and T2 can be
re-tried.

This should solve this and other similar deadlocks due to the enforced commit
order. Later, we can also use this to implement more opportunistic search for
possible parallelims, as suggested by Jonas.

Temporary re-assigned to Serg for review

Pushed to 10.0.13.