Shulou(Shulou.com)06/01 Report--

Original address:

Https://mysqlserverteam.com/contention-aware-transaction-scheduling-arriving-in-innodb-to-boost-performance/

Translator Shen Gang

| | transaction scheduling |

At present, most database systems control concurrency by locking. But for many database vendors, there is a problem:

When multiple transactions need to acquire the same lock at the same time, which transaction should acquire the lock first?

Almost all databases, including previous versions of MySQL, solve this problem through the FIFO mechanism. Simply put, the FIFO mechanism assigns a lock to the transaction that first requests the lock (that is, the transaction is at the head of the waiting queue unless they are not compatible with the lock assigned by the current lock). Because this mechanism is relatively simple to implement, many database vendors schedule transactions through the strategy of FIFO, without considering other scheduling strategies.

A research group at the University of Michigan recently suggested that there is huge room for performance improvement behind this problem. Professor Mozafari and his students proved that different lock allocation strategies and transaction scheduling strategies have a great impact on database performance. They propose an algorithm called Contention-Aware Transaction Scheduling (CATS). Compared with the previous FIFO strategy, this algorithm can significantly reduce database latency and improve throughput.

The official team of Oracle MySQL worked closely with Professor Mozafari and his students to make MySQL the first database to adopt this new technology. After MySQL 8.0.3, CATS policy is the default scheduling algorithm for InnoDB, which means that MySQL users can feel a significant performance improvement, especially in the case of persistent high pressure load.

| | CATS mechanism principle |

CATS algorithm is based on a very simple point of view: not all transactions are equal, not all objects are equal. When a transaction already holds locks for multiple objects, when the transaction requests a new lock, the transaction should be assigned first. On the other hand, unlocking such transactions helps to unlock more transactions. Because the priority of the transaction is assigned to the lock, it can end the transaction more quickly and release the lock of the other acquired object. In this way, the database can get higher throughput and lower latency.

There is a metaphorical example: if both a taxi driver and a bus driver are waiting for coffee, making coffee for bus drivers first (even if bus drivers arrive later than taxi drivers) may allow more people to arrive at their destination as soon as possible. Because there are more passengers on the bus than in the taxi. This may seem unfair to taxi drivers, but this strategy can make the whole system run faster, which is good for everyone in the system.

Of course, we are now solving the problem of locks, not the problem of traffic drivers. Let's use a simple example to illustrate how the CATS mechanism works in a database. We know that under different transaction isolation levels, when a transaction reads or updates data, it needs to acquire the lock of the corresponding data. When the lock required by a transaction is already held by another transaction, the transaction waits until the other transaction releases the lock. When a transaction already holds a part of the object lock, it may be blocked while acquiring the locks of other objects. at this time, a deadlock detection mechanism is needed to detect that there is no lock waiting loop in the current database to prevent deadlock. Take a look at the following picture:

Transaction contention

In this scenario, the FIFO strategy is simple and only needs to consider which transaction first requests a lock on the O1 object. But the CATS algorithm handles this situation more intelligently: the CATS algorithm calculates the number of transactions blocked directly and indirectly by each transaction, and then allocates the locks of the O1 object to transactions that block more transactions. In this scenario, the T1 transaction blocks four transactions and the T2 transaction blocks three transactions. So according to the CATS algorithm, the lock of the O1 object is assigned to the T1 transaction. In this way, more transactions can be released, which will help to improve the overall performance of the system.

For shared locks (S locks), the CATS algorithm allocates as many shared locks as possible. There are differences between FIFO and CATS algorithms in this respect. FIFO allocates shared locks in the order of queues, and stops allocating when there is already an exclusive lock (X lock) on the allocated object. In CATS, the number of transactions blocked is sorted in reverse order, and then locks are allocated in this order.

| | performance improvement brought about by CATS mechanism |

Oracle's Dimitri Kravtchuk tests the new algorithm through Sysbench's OLTP script. The results show that in the case of concurrency, the performance of CATS algorithm is significantly better than that of FIFO algorithm in terms of TPS, average delay, 95% delay and so on. Interestingly, even without concurrency, the performance of the CATS algorithm is the same as that of the FIFO algorithm. That's because when there is no concurrency, there are no transactions to be scheduled, so there is no performance difference. In other words, there is no loss to replace the FIFO algorithm with the CATS algorithm, but there is a great performance improvement when the database is busy.

CATS vs. FIFO in TPS, mean latency and 95th percentile (up to 5.05x improvement)

| | conclusion |

MySQL is the first database in the world to use this state-of-the-art CATS transaction scheduling algorithm. This algorithm solves the problem of sharp decline in database performance under high pressure, which is the main goal that MySQL 8.0 wants to achieve.

The CATS algorithm is designed for cases where transaction concurrency exceeds 32. This value has no parameter configuration and is set empirically.

| | translator's introduction |

Shen Gang Walk Science and Technology Database Technical expert

Familiar with MySQL database operation mechanism, rich experience in database and replication architecture troubleshooting, performance tuning, database backup recovery and migration.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.