preface
If all transactions in the database are executed sequentially, this approach can ensure that transactions are executed without exceptions and errors, but the problem is that serial execution can lead to performance bottlenecks. The concurrent execution of transactions, if not controlled, can cause many problems, including deadlocks, lost updates, and so on. This requires us to make a reasonable trade-off between performance and security, and use the appropriate concurrency control mechanism to ensure the execution of concurrent transactions.
Problems with concurrent transactions
First, let’s take a look at the problems associated with concurrent transactions. Concurrent transactions accessing the same record can be roughly summarized as the following three cases:
- Read-read: concurrent transactions read the same record successively;
- Write – write: that is, concurrent transactions make successive changes to the same record;
- Write-read or read-write: two concurrent transactions read and write the same record.
Read –
Since reading the record does not affect the record in any way, there is no security issue for the same transaction to read the same record concurrently, so this operation is allowed.
Write –
If concurrent transactions are allowed to read the same record and subsequently make changes to that record based on the old value, then the changes made by the previous transaction are overwritten by the changes made by the later transaction, which is a commit override problem.
On the other hand, concurrent transactions make changes to the same record one after another, and one transaction is committed and then another is rolled back. In this case, the committed changes are lost due to rollback, which is the rollback overwrite problem.
Both of these problems cause lost updates, where rollback coverage is called category 1 lost update problem and commit coverage is called Category 2 lost update problem.
Write-read or read-write
This is the most complex and problematic situation.
If one transaction reads a change record that has not yet been committed by another transaction, then there is a dirty read problem;
If we control that a transaction can only read changes made by other committed transactions, then the data read by that transaction will be different before and after the other transaction commits the changes, which means that non-repeatable reads have occurred.
If one transaction queries some records based on some criteria, and then another transaction inserts some records into the table, the original transaction queries again under the same criteria and finds that the results are not the same as the results obtained in the first query, this indicates that phantom reading has occurred.
The isolation level of the transaction
For the problems that may occur in the execution of concurrent transactions mentioned above, their severity is also different. We can order the problems according to their severity:
Lost update > Dirty read > Unrepeatable read > Phantom read
Copy the codeSo if we can tolerate less serious problems, we can get some performance gains. There are four levels of isolation for transactions:
- Read uncommitted (
Read Uncommitted) : Allows reading of uncommitted records, resulting in dirty reads, unrepeatable reads, and phantom reads. - Read Submitted (
Read Committed) : only allow reading has been submitted records, will not happen dirty read, but there will be repeated read, magic read; - Repeatable (
Repeatable Read) : There will be no dirty read and unrepeatable read problems, but there will be magic read problems; butMySQLUtilized under this isolation levelMVCCorClearance lockYou can disable illusory problems; - Serializable (
Serializable) : namely, the transaction is executed sequentially, and the above problems will not occur naturally.
It is important to note that none of the above isolation levels will cause rollback overwrites, but commit overwrites for MySQL, This can happen at Read Uncommitted, Read Committed, and Repeatable Read isolation levels (the standard Repeatable Read isolation level does not allow commit overwrites) and additional locks are required to avoid this problem.
Implementation of isolation levels
The SQL specification defines these four isolation levels, but it does not specify how to implement them, so different databases implement and use them differently. The STANDARD for SQL isolation levels is based on the lock-based implementation, because it is necessary to understand how traditional lock-based isolation levels are implemented.
Implementation of traditional isolation levels
Since traditional isolation levels are implemented based on locks, let’s take a look at locks.
The lock
There are two kinds of traditional locks:
- Shared lock (
Shared Locks) :S lockWhen a transaction reads a record, it first obtains the shared lock of the record. - Exclusive lock (
Exclusive Locks) :X lockWhen a transaction writes to a record, it first acquires the record’s exclusive lock.
It should be noted that if a record is added with a shared lock, other transactions can also obtain the shared lock of the record, but cannot obtain the exclusive lock of the record, that is, S lock is compatible with S lock, and S lock is incompatible with X lock. However, other transactions cannot acquire the shared lock or exclusive lock of a record with exclusive lock, that is, X lock and X lock are incompatible.
In addition, when a transaction reads a record, it needs to acquire the S lock first. However, when a transaction reads a record, it needs to acquire the X lock for that record. Take MySQL as an example, there are two lock read modes:
- Add to record when read
S lock:
SELECT.LOCK IN SHARE MODE;
Copy the codeIf a transaction executes this statement, an S lock is placed on the read record, allowing other transactions to acquire the S lock on the record. If another transaction needs to acquire the record’s X lock, it will need to wait until the current transaction commits to release the S lock.
- Add to record when read
X lock:
SELECT.FOR UPDATE;
Copy the codeIf a transaction executes this statement, an X lock is placed on the read record, so that other transactions that want to remove the S or X lock on the record need to wait until the current transaction commits to release the X lock.
In terms of granularity, locks can be divided into two types:
- Row lock: Only one row of records is locked. Records of other rows are not affected.
- Table lock: Locks the entire table, affecting all operations on the table.
Implement isolation levels based on locks
In the lock-based implementation, the difference between the four isolation levels lies in the locking method:
- Read uncommitted: Read operation without lock, read, read, read, write read parallel; Write operations to add
X lockAnd is not released until the transaction commits. - Reading has been submitted: Read operation plus
S lock, write operation plusX lockAnd is not released until the transaction is committed; Read operations do not block other transaction reads or writes, and write operations block other transaction writes and reads, thus preventing dirty read problems. - Repeatable read: Read operation plus
S lockAnd is not released until the transaction commits, write operation plusX lockAnd is not released until the transaction is committed; Read operations do not block other transaction reads but block other transaction writes. Write operations block other transaction reads and writes, preventing dirty and unrepeatable reads. - serialization: Add both read and write operations
X lockIt is not released until the transaction commits, and the granularity is a table lock, that is, strict serial.
There are a few details worth noting:
- If a lock is acquired and not released until after the transaction commits, the lock is calledLong locks; If the lock is released after the operation is complete, the lock is calledShort lock. For example, read actions added under committed isolation level
S lockShort lock, added by write operationX lockFor the long locks. - For repeatable reads and serialization isolation levels, added by read operations
S lockAnd write operationsX lockAll are long locks, that is, locks acquired by a transaction can not be released until the transaction is committed. This protocol divides lock acquisition and lock release into two different stagesTwo phase lockProtocol (2-phase locking). The two-phase locking protocol states that in the locking phase, a transaction can acquire the lock but cannot release the lock. However, in the unlocking stage, transactions can only release locks, but cannot acquire new locks. Two-phase locking protocol can ensure the serialized execution of transactions and solve the problem of transaction concurrency, but it will greatly increase the probability of deadlock.
Implementation of MySQL isolation level
Different databases have different support for the isolation levels specified in the SQL standard, and while the database engine implements the isolation levels as closely as possible to the standard isolation level specification, there are some differences from what the standard expects.
MySQL (InnoDB) supports four isolation levels, which are somewhat different from the standard isolation levels. For example, MySQL at repeatable read isolation level can prevent phantom read problems, but can also commit overwrite problems.
Compared with the traditional lock-based isolation level implementation, MySQL implements read-write concurrency control through MVCC (Multi-version concurrency control) and write-write concurrency control through two-phase locking. MVCC is a lock-free solution to solve the problem of read-write concurrency and greatly improve the performance of read-write concurrency.
Realization principle of MVCC
Create table book (primary key book_ID, name book_name, stock); Then insert some data into the table:
INSERT INTO book VALUES(1.'Data structure'.100);
INSERT INTO book VALUES(2.'guide to c + +'.100);
INSERT INTO book VALUES(3.'proficient in Java.100);
Copy the codeVersion of the chain
For tables using the InnoDB storage engine, the clustered index record contains two important hidden columns:
- The transaction ID (
DB_TRX_ID) : Whenever a transaction modifies a record in the cluster index, the transaction ID of the current transaction is recordedDB_TRX_IDIn the. - Rollback pointer (
DB_ROLL_PTR) : Each time a transaction modifies a record in the cluster index, the older version of the record is recordedundoLog, passDB_ROLL_PTRThis pointer can be used to retrieve information about older versions of the record.
If multiple changes are made to the record in a transaction, each change generates an undo log, and these undo logs are concatenated in a version chain using the DB_ROLL_PTR pointer. The start point of the version chain is the latest value of the record, and the end point is the initial value at the start of the transaction.
For example, we make the following changes in table book:
BEGIN;
UPDATE book SET stock = 200 WHERE id = 1;
UPDATE book SET stock = 300 WHERE id = 1;
Copy the codeThen the version chain of the record with id=1 is as follows:
ReadView
For transactions using the Read Uncommitted isolation level, only the record of the latest version in the version chain is Read; For transactions with Serializable isolation level, InnoDB uses locking to access records. The Read Committed and Repeatable Read isolation levels require that the Committed transaction changes be Read, meaning that the version cannot be Read if the changes in the version chain are not Committed. So you need to determine which version in the version chain can be Read by the current transaction under Read Committed and Repeatable Read isolation levels. The concept of ReadView was proposed to solve this problem.
A ReadView is a snapshot of a schedule record, in which we can get which of the transactions associated with the current record are committed stable transactions, which are active transactions, and which were started after the snapshot was generated. From this we can judge the latest version records that can be read in the publishing chain according to the visibility comparison algorithm.
Visibility comparison algorithm is a comparison algorithm based on transaction ID. First, we need to know the fact that transaction ids are incrementally allocated. From ReadView we can get the minimum and maximum transaction ids that are active in the system at the time of snapshot creation (the maximum transaction ID is actually the value of the ID that will be assigned to the next transaction in the system), so we have a range of active transaction ids that we can call ACTIVE_TRX_ID_RANGE. In this case, all transactions with transaction IDS smaller than this range are committed stable transactions, all transactions larger than this range are started after snapshot generation, and all transactions within the ACTIVE_TRX_ID_RANGE are committed stable transactions in addition to active transactions.
With the above information, we follow the start node of the version chain to find the latest readable version record:
1. Determine whether the DB_TRX_ID field in the version record is equal to the transaction ID that generated the ReadView. If it is equal, it means that the version of the record was generated in the current transaction and can be read by the current transaction. Otherwise, proceed to Step 2.
2. If the DB_TRX_ID field is smaller than the ACTIVE_TRX_ID_RANGE range, the version record is visible to the current transaction. Otherwise proceed to the next step.
3. If the DB_TRX_ID field is in the ACTIVE_TRX_ID_RANGE and the transaction ID is not active, the version record is visible to the current transaction. If the transaction ID corresponds to an active transaction and is not visible to the current transaction, the next version record in the version chain is read and the above steps are repeated until the version visible to the current transaction is found.
If a version record is visible to the current transaction after the preceding steps, the version record is returned in the query result. Otherwise, read the next version record and proceed with the above steps until the end of the version chain. If no version visible to the current transaction is found after traversing the version chain, the query result is empty.
In MySQL, the difference between Read Committed and Repeatable Read isolation levels is when they generate readViews.
MVCC implements different isolation levels
The ReadView mechanism only works at Read Committed and Repeatable Read isolation levels, so MVCC is only available at those isolation levels. At the Read Committed isolation level, readViews are generated each time data is Read; In Repeatable Read isolation, the ReadView is generated only when the transaction reads data for the first time and is used for all subsequent Read operations.
Let’s take a look at the different behaviors of MVCC at Read Committed and Repeatable Read isolation levels with examples. Let’s continue with the table Book as an example.
Read Committed Isolation level analysis
Let’s assume that at the Read Committed isolation level, a transaction with id 10 is executing:
BEGIN; // Start Transaction 10
UPDATE book SET stock = 200 WHERE id = 2;
UPDATE book SET stock = 300 WHERE id = 2;
Copy the codeAt this point, the transaction has not been committed, and the version chain of the record with ID 2 is shown below:
Then we start a transaction to query the record with id 2:
BEGIN;
SELECT * FROM book WHERE id = 2;
Copy the codeWhen the SELECT statement is executed, a ReadView is generated with ACTIVE_TRX_ID_RANGE as [10, 11] and the current transaction IDcreator_trx_id as 0 (because a separate transaction ID is assigned when a write is performed in a transaction, Otherwise the transaction ID is 0). According to the working principle of ReadView as described earlier, the version we query is recorded as
+----------+-----------+-------+
| book_id | book_name | stock |
+----------+-----------+-------+
2 | |C + + guide100 | |
+----------+-----------+-------+
Copy the codeThen we commit the transaction with transaction ID 10:
BEGIN; // Start Transaction 10
UPDATE book SET stock = 200 WHERE id = 2;
UPDATE book SET stock = 300 WHERE id = 2;
COMMIT;
Copy the codeEnable the execution of another transaction with id 11, but do not commit:
BEGIN; // Start Transaction 11
UPDATE book SET stock = 400 WHERE id = 2;
Copy the codeAt this point, the version chain of the record with ID 2 is shown as the figure below:
Select * from transaction where id = 2;
BEGIN;
SELECT * FROM book WHERE id = 2; Transaction 10 is not committed at this time
SELECT * FROM book WHERE id = 2; // Transaction 10 is committed at this point
Copy the codeWhen the SELECT statement is executed a second time, a ReadView is generated with ACTIVE_TRX_ID_RANGE [11, 12] and the current transaction IDcreator_trx_id is 0. According to the working principle of ReadView, the version we query is recorded as
+----------+-----------+-------+
| book_id | book_name | stock |
+----------+-----------+-------+
2 | |C + + guide300 | |
+----------+-----------+-------+
Copy the codeAs you can see from the above analysis, because a new ReadView is generated each time the query is executed, transactions at the Read Committed isolation level Read data after the Committed transaction changes in the query schedule.
Repeatable Read Isolation level analysis
We repeat the above transaction at Repeatable Read isolation level:
BEGIN; // Start Transaction 20
UPDATE book SET stock = 200 WHERE id = 2;
UPDATE book SET stock = 300 WHERE id = 2;
Copy the codeAt this point, the transaction has not committed, and then we start a transaction to query the record with id 2:
BEGIN;
SELECT * FROM book WHERE id = 2;
Copy the codeWhen the transaction executes the SELECT statement for the first time, a ReadView is generated. The ACTIVE_TRX_ID_RANGE in the ReadView is [10, 11] and the transaction IDcreator_trx_id is 0. According to the working principle of ReadView, the version we query is recorded as
+----------+-----------+-------+
| book_id | book_name | stock |
+----------+-----------+-------+
2 | |C + + guide100 | |
+----------+-----------+-------+
Copy the codeThen we commit the transaction with transaction ID 20:
BEGIN; // Start Transaction 20
UPDATE book SET stock = 200 WHERE id = 2;
UPDATE book SET stock = 300 WHERE id = 2;
COMMIT;
Copy the codeEnable the execution of another transaction with id 21, but do not commit:
BEGIN; // Start Transaction 21
UPDATE book SET stock = 400 WHERE id = 2;
Copy the codeSelect * from transaction where id = 2;
BEGIN;
SELECT * FROM book WHERE id = 2; Transaction 10 is not committed at this time
SELECT * FROM book WHERE id = 2; // Transaction 10 is committed at this point
Copy the codeNo new ReadView is generated when the SELECT statement is executed the second time. The ReadView generated from the first query is still used. So the version record we queried is the same as the first query:
+----------+-----------+-------+
| book_id | book_name | stock |
+----------+-----------+-------+
2 | |C + + guide100 | |
+----------+-----------+-------+
Copy the codeFrom the above analysis, it can be found that the transaction in Repeatable Read isolation level only generates ReadView when executing the query for the first time, and the subsequent query operations in this transaction will use this ReadView. Therefore, the same query is executed for many times in a transaction at this isolation level, and the result is the same. This enables repeatable reading.
Snapshot read and current read
Read the snapshot
At the Read Committed and Repeatable Read isolation levels, ordinary SELECT queries Read a version in the MVCC version chain, which is equivalent to reading a snapshot, hence the name snapshot Read. This type of reading does not lock, so the read operation is non-blocking, so it is also called non-blocking read.
In the standard Repeatable Read isolation level, an S lock is placed on the Read operation until the end of the transaction, thus preventing other transaction writes. However, under the isolation level of Repeatable Read of MySQL, the Read operation is not locked, which will not prevent other transactions from writing the same record. Therefore, the results calculated based on the old data in the version chain may be written in the subsequent write operation, which leads to the issue of commit overwrite. To avoid this problem, an additional lock is required.
The current reading
MySQL has two ways to lock reads:
SELECT.LOCK IN SHARE MODE; // Lock the record S until the end of the transaction
SELECT.FOR UPDATE; // Lock the record with X until the end of the transaction
Copy the codeThis type of reading reads the current, most recent version of the record and is called the current read. INSERT, DELETE, and UPDATE operations also need to read the record first and acquire the record’s X lock, which is also a current read. The need to lock records will block the write operations of other transactions, so it is also called lock read or block read.
The current read not only locks the current record but also the data in the query scope space with a GAP LOCK, thus preventing phantom read problems.
conclusion
This article introduces the various concurrency problems of transactions and the isolation levels used to avoid different levels of problems. It also describes in detail how the traditional isolation levels are implemented and how the MySQL isolation levels are implemented. However, the database concurrency mechanism is more complex, this paper is only a general description and introduction, many details also need readers to query relevant information for a more detailed understanding.
The resources
1, mysqL-Innodb-MVCC multi-version concurrency control
2, MySQL how to run: from the root understand MySQL