MySQL InnoDB transaction lock source code analysis

Premise of this article:

Code MySQL 8.0.13

Only the current read of Repeatable Read is sorted. Read Committed is much simpler. In addition, snapshot reads are based on MVCC and do not require locking, so they are not discussed in this article.

1. Lock and Latch

lock in InnoDB is a lock added to the accessed/modified record in the transaction, which is generally released when the transaction is committed or rolled back. Latch is a lock added to Btree pages when locating record on BTree. It usually locks the corresponding record in the page and releases it after access/modification. The lock range of latch is much smaller than that of lock. In the specific implementation, a large transaction will be split into several small mini transaction（mtr ), as shown in the following figure: There is a transaction that performs insert , select…for update and update operations in sequence. These three operations correspond to three mtrs respectively. Each mtr completes:

• Find the target record in btree and add關page latch ;
• Add target record lock and modify the corresponding record
• Release page latch


Why do this? For the sake of concurrency, for each operation in the transaction, after step 2 is completed, the corresponding record has been protected by a lock to ensure that other concurrent transactions cannot modify it. Therefore, there is no need to occupy page latch where record is located at this time. Otherwise, when other transactions access/modify different record of the same page , which can be done in parallel, they will be stuck here by page latch .

The lock is在lock_sys->rec_hash .個record lock is identified in rec_hash by <space_id , page_no , heap_no>

latch is in block of bufferpool corresponding to page , corresponding to block->lock

This article only focuses on lock related things, latch will be sorted out in a separate article later

2. Repeatable Read

I will not elaborate on each isolation level in detail. Here I will mainly talk about RR. As the name suggests, RR supports repeatability, that is, in a transaction, multiple executions of the same SELECT…FOR UPDATE should see the same result set (except for modifications made by this transaction). This requires that no other transaction can insert new records in the SELECT interval. Therefore, in addition to locking the records that meet the conditions, SELECT also needs to lock the corresponding interval to protect it. In the implementation of InnoDB, there is no lock that locks a specified interval at once. Instead, a large interval lock is split and placed on multiple records already in the interval. Therefore, the concepts of Gap lock and Next-key lock are introduced. They are added to a specific record.

• Gap lock protects the open interval between this record and the previous record
• Next-key lock protects the left-open and right-closed interval between this record and its previous record.
  

They are all to protect this interval from being inserted into new records by other transactions, thus implementing RR.

Next, let's look at how Insert and Select are locked from the source code implementation. By combining them, we can understand how InnoDB's RR is implemented. Insert locks are distributed throughout the Insert operation and in multiple related functions, while Select locks are more concentrated in在row_search_mvcc .

3. Insert locking process

3.1 lock mode

The lock modes are mainly Share (S) and Exclusive (X) [corresponding to LOCK_S and LOCK_X in the code]

The gap modes of lock mainly include Record lock, Gap lock, Next-key lock [corresponding to LOCK_REC_NOT_GAP, LOCK_GAP, LOCK_ORDINARY in the code]

In actual use, the actual type of lock is after mode|gap_mode. Record lock is a record lock applied to a single record. Although Gap lock/Next-key lock is also applied to a specific record, it is used to ensure that no other concurrent transactions insert into the gap before the record. How is this implemented? InnoDB introduces an insert intention lock, whose actual type is

（LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION）

Mutually exclusive with Gap lock/Next-key lock . If a lock is detected on the next record at the insertion position before insertion, an insertion intention lock will be added to the next record, indicating that the transaction intends to insert a new record into the gap. If another transaction has already set Gap/Next-key lock here, it means that it wants to protect this place, so the current insertion intention lock needs to wait for the relevant transaction to be committed. This detection is only one-way, that is, the insertion intention Gap/Next-key lock lock, but any lock does not need to wait for the release of the insertion intention lock, otherwise it will seriously affect the concurrency of non-conflicting Insert operations in this gap.

The specific lock conflict detection is in the lock_rec_has_to_wait function. The general principle is: to determine whether two locks are compatible or incompatible, first perform a mode conflict detection

If there is no conflict, it means the locks are compatible and there is no need to wait. If there is a conflict, the gap mode conflict exception detection is performed, which is summarized as follows:

If the gap modes do not conflict, the locks are considered compatible as an exception and no waiting is required. You can see:

• Inserting the intention lock requires waiting for Gap lock and Next-key lock
• Any lock does not need to wait for the insertion of the intention lock
• Gap lock does not need to wait for any lock
• Next-key lock needs to wait for other Next-key lock及Record Lock , and vice versa
  

Now that we understand these lock compatibility principles, we can see how to use them in the actual Insert process.

3.2 Locking process

The order of Insert is to insert the primary key index first, and then insert the secondary index in sequence. The following is the process sorted out from the code, the operation of inserting an entry ,

For primary key index:

(1) First search the Btree, add the relevant page latch , and locate record (<= entry)

(2) If the entry to be inserted already exists, that is, entry = record , then the following is judged:

• If it is INSERT ON DUPLICATE KEY UPDATE , add X Next-key lock to record
• If it is a normal INSERT , add S Next-key lock to record

Then determine whether the record is a deleted mark:

• If it is not a delete mark, it means there is indeed a duplicate, DB_DUPLICATE_KEY is returned to the upper layer. The upper layer then determines whether to convert the operation to an update or report a duplicate error to the user based on whether it is INSERT ON DUPLICATE KEY UPDATE or a normal INSERT.
• If it is a deleted mark, it means there is actually no duplicate record , so go down

(3) Determine whether there is a lock on the next record of the record. If so, add an insertion intention lock to it to ensure that there is no other Gap lock/Next-key lock protection in the interval where the entry is to be inserted.

(4) Insert entry

(5) Release page latch , which still holds the lock

For secondary indexes

(1) First search the Btree, add the relevant page latch, and locate record (<= entry)

(2) If the entry to be inserted already exists, that is, entry = record , and the current index is unique:

• If it is INSERT ON DUPLICATE KEY UPDATE , add X Next-key lock to record
• If it is a normal INSERT, add S Next-key lock to record2

Determine whether record and entry are equal:

If they are equal and it is a normal INSERT, then determine whether the record is a deleted mark:

• If it is not a delete mark, it means there is indeed a duplicate, DB_DUPLICATE_KEY is returned to the upper layer. The upper layer then determines whether to convert the operation to an update or report a duplicate error to the user based on whether it is INSERT ON DUPLICATE KEY UPDATE還a normal INSERT.
• If it is a delete mark, there is actually no duplicate, so go down

(3) If it is INSERT ON DUPLICATE KEY UPDATE and the current index is unique, a record X Gap lock is set for the next transaction to prevent the same entry from being inserted by other transactions.

(4) Determine whether there is a lock on the next record of the record. If so, add an insert intention lock to it.

（LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION）


Make sure the range where you want to insert the entry is not protected by other Gap lock/Next-key lock

(5) Insert entry

(6) Release the page latch

Note : Step 3 of [Secondary Index] seems redundant, because even if other concurrent transactions use INSERT ON DUPLICATE KEY UPDATE to insert the same record, step 1 can only be entered serially, just like the [Primary Key Index] process. The first thread does not find the same record as the entry, so it goes to step 4 to insert it. The second thread can only enter step 1 after step 6 ends and the page latch is released. At this time, in step 2, it will be stuck on X Next-key lock of the added record, and can only continue after the transaction of thread 1 is committed. So it seems that there will be no conflict?

The above process is in the row_ins_index_entry function, and the specific entry is as follows:

mysql_parse->mysql_execute_command->Sql_cmd_dml::execute->
Sql_cmd_insert_values::execute_inner->write_record->handler::ha_write_row->
ha_innobase::write_row->row_insert_for_mysql->row_insert_for_mysql_using_ins_graph->
row_ins_step->row_ins->row_ins_index_entry_step->row_ins_index_entry

The insert intention lock is added in the lock_rec_insert_check_and_lock function, and the entry is as follows:

row_ins_index_entry->row_ins_clust_index_entry/row_ins_sec_index_entry->
btr_cur_optimistic_insert/btr_cur_pessimistic_insert->btr_cur_ins_lock_and_undo->
lock_rec_insert_check_and_lock

3.3 Implicit Lock

Another point to mention is that the Insert operation will not explicitly lock. Each Insert record has an implicit lock by default, which is detected through the hidden field trx_id of the record. For the primary key index, if the record to be inserted is found in the Btree, it only needs to compare the trx_id of the existing record. If the transaction corresponding to this trx_id is still an active transaction, it means that the insert transaction of this record has not been committed. It implicitly means that there is a lock on this record. At this time, it will be converted into an explicit lock and put into lock_sys and wait. This is done to improve performance and minimize operations on lock_sys. Implicit lock detection for secondary indexes is not as easy as for primary key indexes, because secondary index records do not record trx_id . We can only compare max_trx_id on the page where it is located with the minimum trx_id in the current active transaction list. If it is smaller than the max_trx_id, it means that the last transaction that modified this page has been committed, so there is no implicit lock on the record. If it is greater than or equal to the max_trx_id, we need to go back to the primary key to find the corresponding primary key record and traverse the undo historical version to confirm whether there is an implicit lock. The specific implementation is in row_vers_impl_x_locked_low .

4. Select Locking Process

The locking process for SELECT to do current reading is in row_search_mvcc. A SELECT statement will enter this function multiple times. The first time is through index_read->row_search_mvcc , which is usually the first access to the index to find the exact record in WHERE. Each subsequent access is through general_fetch->row_search_mvcc , and prev/next record is traversed according to specific conditions until all records that meet the WHERE conditions are retrieved. The specific locking is performed during the process of accessing and traversing records. The row_search_mvcc code is very long. Here I will only summarize the locking-related process:

• Find the record corresponding to search_tuple on index. (The record here may be the first search for the record corresponding to search_tuple through the index Btree mentioned above, or it may be the previous/next record obtained by restoring the last access position through the previously saved cursor after multiple general_fetches.)
• If it is index_read and mode is PAGE_CUR_L or PAGE_CUR_LE , add GAP LOCK to the next record of the located record
• If record is infimum, jump to step 9 next_rec. If it is supremum, add Next-key Lock and jump to step 9 next_rec.
• If it is index_read, record is not equal to search_tuple, add GAP LOCK to record and return NOT FOUND
• Here we show that record is equal to search_tuple, and add Next-key Lock to record. With two exceptions, only Rec Lock is added:

1. For index_read, if the current index is a primary key index and mode is PAGE_CUR_GE and the number of fields in search_tuple is equal to the number of unique fields in the index,
2. Check if it is unique_search, that is, the number of fields in search_tuple is equal to the number of unique fields in the current index and the current index is a primary key index or (it is a secondary index and search_tuple does not contain NULL fields) and the record is not a deleted mark
   

• This indicates that the lock is successful, and then handle the case where the record is marked as deleted:
  

1. The current index is a primary key index and is unique_search , returning NOT FOUND
2. Otherwise, jump to step 9 next_rec
   

• If the current index is a secondary index and the primary key index needs to be checked, find the corresponding primary record in the primary key index and add Rec Lock . If the primary record is marked as deleted, the current secondary index will jump to step 9 next_rec
• Success, returns DB_SUCCESS
• next_rec: Get the corresponding prev/next record according to mode, jump to step 3 to continue
  

Let's focus on step 3. Generally, when the record is infimum or supremum, multiple genera_fetches are performed on a page to get the prev/next record and then reach the edge of the page. For infimum, no lock is added, and the previous prev record (that is, the supremum of the prev page) is directly accessed. For supremum, a gap lock is added to protect the gap between the last user record of the current page and the first user record of the next page.

There is nothing else to the process:

1. For the records that meet the conditions, the default is to add the Next-key lock.
2. When the secondary index is returned to the table, only the primary key will be rec locked.
3. For some special scenarios, some Next-key lock will be downgraded to Rec lock (step 5)
4. There are also some special scenarios where only Gap lock will be added (steps 2 and 4)
   

Summarize:

The above is basically the process of adding transaction locks to InnoDB . By combining the locking processes of Insert and Select , the principles and implementation of transaction locks are basically revealed.

This is the end of this article about MySQL InnoDB transaction lock source code analysis. For more relevant MySQL InnoDB transaction lock source code analysis content, please search 123WORDPRESS.COM's previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!