← Back to team overview

maria-developers team mailing list archive

Re: [MariaDB/server] Add new scheduling algorithm for reducing tail latencies (#245)


Jiamin Huang <notifications@xxxxxxxxxx> 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

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.