Talk about MVCC and next-key Locks

preface

In the previous article, WE talked about MySQL’s RR isolation level using MVCC+ next-key Locks to solve the phantom read problem. Let’s take a closer look at what these two mechanisms are.

MVCC(Multi-version Concurrency Control)

The Multi-version Concurrency Control (MVCC) is a concrete way for MySQL’s InnoDB storage engine to implement isolation levels for both committed reads and repeatable reads. The uncommitted read isolation level always reads the latest row, without MVCC. Serializable isolation levels require locks on all read rows, which cannot be achieved using MVCC alone.

Most of Mysql’s transactional storage engine implementations are not simple row-level locking. To improve concurrency, multiple versions of concurrency control (MVCC) have been implemented, including Oracle and PostgreSQL. Implementations vary, however.

MVCC is implemented by saving a snapshot of the data at a point in time. This means that no matter how long the implementation takes, everything will see the same data.

It is divided into optimistic concurrency control and pressimistic concurrency control.

How MVCC works:

InnoDB’s MVCC is implemented by storing two hidden columns at the end of each row. These two columns hold the creation time of the row and the expiration time (deletion time) of the row. Of course, the stored time is not the real time, but the system version number. The system version number is automatically added every time a new transaction is started. The system version number at the transaction start time will be used as the transaction version number, and the version number of each row record will be queried for comparison.

The version number

System Version:Is an incrementing number. The system version number automatically increments with each new transaction.

Transaction version number:The system version number at the start of the transaction.

Hidden columns

MVCC keeps two hidden columns after each row to store two version numbers:

Create version number: When creating a row of data, assign the current system version number as the creation version number.
Delete version number: When deleting a row of data, assign the current system version number as the deleted version number. If the deleted version number of the snapshot is greater than the current transaction version number, the snapshot is valid; otherwise, the snapshot has been deleted.

REPEATABLE READ How MVCC works at isolation level:

It is important to understand that when a new transaction is started, the version number of the transaction will certainly be greater than the creation version number of all current data row snapshots.

1. SELECT

InnoDB checks each row based on the following criteria:

1. InnoDB only looks for rows whose version is earlier than the current transaction version. This ensures that the transaction reads rows that either existed before the transaction started or were inserted or modified by the transaction itself.

2. The deleted version number of the row is either undefined or greater than the current transaction version number
Ensure that rows read by the transaction are not deleted before the transaction beginsThe transaction will not see rows that have expired before the transaction begins.

Only those that meet the above two conditions will be queried

2. INSERT

Use the current system version number as the creation version number of the data row snapshot.

3. DELETE

Use the current system version number as the deleted version number of the data row snapshot.

4. UPDATE

The current system version is used as the deleted version of the data row snapshot before update, and the current system version is used as the creation version of the data row snapshot after update.
Perform DELETE first and then INSERT.

Save both versions so that most operations are unlocked. Makes data manipulation simple, performs well, and guarantees that only the rows required by the composition will be read. The downside is that each row requires additional storage, more row checking, and some additional maintenance.

MVCC only works at COMMITTED READ and REPEATABLE READ isolation levels.

MVCC can be considered a variant of row-level locking, but it avoids locking in many cases and costs less. Although the implementation mechanism varies from database to database, most implement non-blocking reads (reads are unlocked and avoid unrepeatable reads and phantom reads), and writes lock only the necessary rows (writes must be locked otherwise data inconsistency will occur due to concurrent writes from different transactions).

Snapshot read and current read

At the RR level, the MVCC mechanism makes the data repeatable, but the data we read may be historical data, not the latest data in the database. This way of reading historical data, we call it
Snapshot Read, and the way to read the latest version of the database is called
Current read.

1. Read the snapshot

When performing a select operation, InnoDB will perform a snapshot read by default. Innodb will record the result of the select, and then return the snapshot data during the select, even if other transactions have committed data that does not affect the current select, thus achieving repeatable read. The snapshot is generated when the first select is performed, that is, when A starts A transaction and then does nothing, B inserts A data and then commits, and A performs A select, then the data returned by B will have the data added by B. It doesn’t matter if there are any other transactions commit after that, because the snapshot has already been generated and the subsequent SELECT is based on the snapshot.

With MVCC, data is read from a snapshot, which reduces the overhead of locking.

select * from table … ;

2. The current reading

Operations that modify data (update, INSERT, delete) use the current read mode. The most recent record is read during these operations, even if the data committed by other transactions can be queried. If you want to update a record, but the data has been deleted and committed in another transaction, the update will cause a conflict, so you need to know the latest data at the time of the update.

Read is the latest data, need to lock. The first statement below requires an S lock, and all others require an X lock.

select * from table where ? lock in share mode; 
select * from table where ? for update; 
insert; 
update; 
delete;Copy the code

How to solve phantom reading

It is clear that repeatable isolation levels are not a complete solution to phantom problems, but there are two ways to solve phantom problems if necessary:

Isolation level using serialized reads
MVCC+next-key LOCKS: Next-key locks consist of record locks(index locks) and gap locks(gap locks), which lock not only the data that needs to be used, but also the data in the vicinity of that data.

InnoDB has three algorithms for row locking:

Record Lock: a Lock on a single row Record.

2, Gap Lock: Gap Lock, Lock a range, but not the record itself. The purpose of the GAP lock is to prevent the illusion of two current reads of the same transaction.

Next-key Lock: 1+2 locks a range and locks the record itself. For the query of rows, this method is used, the main purpose is to solve the illusion problem.

Record Locks

Locks an index on a record, not the record itself.

If the table is not indexed, InnoDB automatically creates hidden clustered indexes on primary keys, so Record Locks are still available.

Gap Locks

Locks gaps between indexes, but not the indexes themselves. For example, when one transaction executes the following statement, other transactions cannot insert 15 in t.c.

SELECT c FROM t WHERE c BETWEEN 10 and 20 FOR UPDATE;

Next-Key Locks

Next-key Locks is a locking implementation of MySQL’s InnoDB storage engine.

MVCC does not solve the phantom problem, which next-key Locks are designed to solve. At the REPEATABLE READ isolation level, the phantom problem is solved using MVCC + next-key Locks.

When the query index contains unique attributes, next-key Lock optimizes and demotes it to a Record Lock, which locks only the index itself, not the range.

It is a combination of Record Locks and Gap Locks, locking not only the indexes on a Record, but also the gaps between the indexes.

Create a new table:

CREATE TABLE `test` ( 
`id` int(11) primary key auto_increment, 
`xid` int.KEY `xid` (`xid`))ENGINE=InnoDB DEFAULT CHARSET=utf8; 
insert into test(xid) values (1), (3), (5), (8), (11);Copy the code

Note that there is an index on the XID because the algorithm always locks the index record.

Now, the index can be locked in the following range:

(- up, 1), (1, 3), (3, 5), (5, 8], (8, 11), (11, + up)

Enable transaction execution SQL as follows:

The scope that Session A will lock after execution:

(5, 8], (8, 11]

In addition to locking the range 8, it also locks the Next range, called next-key.

So Session B will block until step 6, skip step 6, block step 7, but not block step 8, and not block step 9.

The above result does not seem to meet expectations, because the value 11 seems to be in the (8, 11] interval, and the value 5 is not in the (5, 8] interval.

Take a look at the picture below:

This SQL statement locks the range of (5,8) and the next key value range is (8,11), so any insert between 5 and 11 will be locked and wait. Insert 5,6,7,8,9,10 will be locked. Inserting values outside this range is fine.

summary

Under this article summarizes the MVCC and InnoDB three row lock algorithm, the principle of these knowledge belongs to the MySQL level, with the understanding, the use of MySQL can be more handy in the future, but as I am concerned about the last question why xid is 11 will not be blocked when there’s a little don’t understand, Innodb’s B+ tree is ordered, so it does not block subsequent inserts. I’ll have to go back and look at the detailed implementation description of Next-Key locks in mysq Tech Insider to make more sense.

Refer to the

zhuanlan.zhihu.com/p/35477890