Jiamin Huang <notifications@github.com> writes:

This branch introduces a new scheduling algorithm (Variance-Aware-Transaction-Scheduling, VATS) for the record lock manager of InnoDB and XtraDB. Instead of using First-Come-First-Served (FCFS), the newly introduced algorithm uses an Eldest-Transaction-First (ETF) heuristic, which prefers older transactions over new ones.

It could be interesting to extend this to also understand commit order for in-order parallel replication. For in-order parallel replication, the commit order of transactions is fixed from the start. Suppose transactions Tm and Tn are both requesting the same record lock, and that Tm goes before Tn. If Tn gets the lock, it will be immediately killed since Tm must be allowed to go first. But there is no guarantee that Tm will be the older transaction. So prefering Tm over Tn here based on the commit order can potentially avoid some transaction rollback/retry. The function thd_deadlock_victim_preference() seems appropriate for overriding the age-of-transaction preference. If this function returns a prefered deadlock victim, give the lock to the other transaction. If not, the VATS algorithm can be applied. Especially in aggressive parallel replication, there can be a lot of conflicting transactions (one user reported 20% of transactions conflicting, while still getting good speedup from parallel replication). So it might be a worthwhile thing to do. - Kristian.