MVCC multi-version concurrency control

What is a MVCC?

Concurrency Control. MVCC, for Multi-version Concurrency Control. MVCC is a method of concurrency control, which can realize concurrent access to database in database management system and transaction memory in programming language.

MVCC in MySQL InnoDB implementation is mainly to improve database concurrency performance, with a better way to deal with read-write conflict, even if there is read and write conflict, can also do not lock, non-blocking concurrent read, that is how to do it? We need to understand what current reads and snapshot reads are.

What are current and snapshot reads?

  • Current read: like select lock in share mode, select for update; Update, INSERT,delete(exclusive lock) operations are a type of current read, why are they called current read? It reads the latest version of the record and locks the read record to ensure that other concurrent transactions cannot modify the current record.

  • Snapshot read: For example, the unlocked SELECT operation is snapshot read, that is, unlocked non-blocking read. The prerequisite for snapshot reads is that the isolation level is not serial. Snapshot reads at the serial level are degraded to current reads. The reason for the occurrence of snapshot read is to improve concurrency performance. The implementation of snapshot read is based on multi-version concurrency control, namely MVCC. MVCC can be considered as a variant of row lock, but it avoids locking operations and reduces overhead in many cases. Since it is based on multiple versions, snapshot reads may not necessarily read the latest version of data, but may read the previous historical version.

To put it bluntly, MVCC is designed to achieve read-write conflict without locking, and this read refers to snapshot read, not current read. Current read is actually a locking operation, which is the implementation of pessimistic locking. So what specific problems can MVCC solve?

What problem does MVCC solve

There are three database concurrency scenarios:

  • Read-read: There are no problems and no concurrency control is required
  • Read-write: Has thread safety issues, may cause transaction isolation issues, may encounter dirty reads, unreal reads, unrepeatable reads
  • Write – write: There are thread safety issues and there may be update loss issues, such as type 1 update loss, type 2 update loss

Multi-version concurrency control (MVCC) is a lock-free concurrency control used to resolve read-write conflicts. This means that a transaction is assigned a time-stamp of unidirectional growth, a version is saved for each change, and the version is associated with the transaction timestamp. The read operation reads only the snapshot of the database before the transaction started. So MVCC can solve the following problems for databases:

  • When concurrent read and write operations are performed on a database, neither write operation nor read operation is blocked, which improves the performance of concurrent read and write operations

  • At the same time, it can solve the problem of transaction isolation such as dirty read, unreal read and unrepeatable read, but it cannot solve the problem of update loss

Realization principle of MVCC

The purpose of MVCC is multi-version concurrency control. The realization of MVCC in the database is to solve Read and write conflicts. Its realization principle is mainly based on the three implicit fields in the record, undo log and Read View. So let’s take a look at this three-point concept

Implicit field

Each row contains DB_TRX_ID,DB_ROLL_PTR,DB_ROW_ID, and other fields that are implicitly defined by the database.

  • DB_ROLL_PTR: 7byte, a rollback pointer to the last version of this record (stored in the rollback segment).

  • DB_TRX_ID: 6byte, last modified (modified/inserted) transaction ID: specifies the ID of the transaction in which the record was created or last modified.

  • DB_ROW_ID: 6byte, implied increment ID (hidden primary key). InnoDB automatically generates a cluster index DB_ROW_ID if the table does not have a primary key.

DB_ROW_ID is the only implicit primary key that the database generates for this record by default, DB_TRX_ID is the transaction ID that operates on this record, and DB_ROLL_PTR is a rollback pointer that is used with undo logs to point to the previous version.

The undo log

Undo logs are classified into two types:

  • Insert undo log: Represents the undo log generated when a transaction inserts a new record, is only needed when a transaction is rolled back, and can be discarded immediately after a transaction is committed.

  • Update undo log: The undo log generated when the transaction is updated or deleted. Not only when a transaction is rolled back, but also when a snapshot is read; The purge thread will purge the log only if the log is not involved in a quick read or transaction rollback.

purge

  • From the previous analysis, we can see that in order to implement InnoDB’s MVCC mechanism, the update or delete operation is just to set the old record’s deleted_bit, and does not actually delete the old record. Before InnoDB 1.2, this cleaning was done by the Master thread.
  • To save disk space, InnoDB has a purge thread to purge records whose deleted_bit is true. To keep the MVCC in order, the Purge thread maintains a Read view of its own (the read view of the oldest active transaction on the system); If a record’s deleTED_bit is true and DB_TRX_ID is visible relative to the Purge thread’s read view, the record must be safe to purge.

Read View

What is Read View?

When a snapshot is Read, a snapshot of the current database system is generated. The ID of the current active transaction is recorded and maintained. (When each transaction is started, Each transaction is assigned an ID, which is incremented, so the latest transaction has a larger ID.)

So we know that Read View is mainly used for visibility judgment, that is, when a transaction performs a snapshot Read, we create a Read View of the record, which is compared to a condition to determine which version of the data can be seen by the current transaction. It could also be a version of the undo log recorded in the row.

The Read View follows a visibility algorithm that takes the DB_TRX_ID (the current transaction ID) from the latest record of the data to be modified and compares it with the ids of other currently active transactions on the system (maintained by the Read View). If DB_TRX_ID is not visible, use the DB_ROLL_PTR rollback pointer to retrieve the DB_TRX_ID from Undo Log. Until a DB_TRX_ID is found, the old record where the DB_TRX_ID resides will be the latest old version visible to the current transaction.

Before I show you, let me simplify a Read View. We can simply think of a Read View as having three global properties

Trx_list (I’m just picking names)

A list of values used to maintain Read View generating transaction ids that are active on the system at the time

up_limit_id

Record the smallest transaction ID in the TRx_List list

low_limit_id

ReadView generates the next transaction ID that has not been assigned by the system at the moment, that is, the maximum transaction ID that has occurred so far +1

  • DB_TRX_ID < up_limit_id = DB_TRX_ID = up_limit_id = up_limit_id = up_limit_id = up_limit_id = up_limit_id = up_limit_id = up_limit_id = up_limit_id = up_limit_id
  • Then judge DB_TRX_ID greater than or equal to low_limit_id, if greater than or equal to represents DB_TRX_ID’s record in the Read View generated before, that affirmation is not visible on the current affairs, if less than the judgment to the next
  • Trx_list. Contains (DB_TRX_ID) trx_list. Contains (DB_TRX_ID) trx_list. If not, your transaction was committed before the Read View was generated, and the result of your modification is visible to the current transaction.

What is the difference between InnoDB snapshot reads at RC and RR levels?

It is the difference in the generation time of the Read View that causes the difference in the Read results at the RC and RR levels

  • The first snapshot Read of a record by a transaction at the RR level creates a snapshot and a Read View, which records other transactions that are currently active in the system. The same Read View is used when snapshot reads are invoked later. Therefore, as long as snapshot reads are used by the current transaction before other transactions commit updates, Subsequent snapshot reads use the same Read View, so subsequent changes are invisible;
  • That is, when a RR snapshot Read generates a Read View, the Read View records snapshots of all other active transactions at that time. The changes made to these transactions are not visible to the current transaction. Changes made by transactions created before the Read View are visible
  • In RC level transactions, each snapshot Read creates a new snapshot and Read View, which is why we see updates committed by other transactions in RC level transactions

At the RC isolation level, each snapshot Read generates and retrieves the latest Read View. In RR isolation, a Read View is created only for the first snapshot Read in the same transaction, and all subsequent snapshot reads obtain the same Read View.