preface

We all know that the repeatable read-level implementation of transactions is implemented using MVCC, but how much do you know about the underlying implementation of MVCC? Interview frequently. You deserve it.

What is MVCC?

MVCC is the multi-version controller, which is characterized by different transactions can read different versions of data at the same time, so as to solve the problem of dirty read and unrepeatable read.

You must have read that explanation dozens of times! But do you really understand what a multiversion controller is?

Life case: Moving

Recently, Xiao Q moved to a new home with his girlfriend. When he left the community, he needed to pay the property fee of the month.

Then small Q with his girlfriend at the same time logged in the property payment system that the village provides.

Pessimistic concurrency control

Assume that when Q is checking the amount of the fee to be paid in the current month, the data queried by Q has been locked.

So Q’s girlfriend is unable to access the data, until Q completed the payment or exit the system to release the pessimistic lock, Q’s girlfriend can query the data.

Pessimistic locking guarantees that only one thread can access data at a time. By default, data will collide when accessed, and the lock will be applied throughout the process.

Such a system is no experience for users. If more than one person needs to access a message at the same time, they can only read it on one device.

Optimistic concurrency control

When Q checks the arrears of property fees and pays them, his girlfriend can also access the data.

Optimistic locks assume that even in a concurrent environment, there is no conflict problem, so they do not lock.

Instead, it checks when the data is submitted and returns a conflict message if it is found.

summary

Innodb's MVCC mechanism is a manifestation of optimistic locking, read without lock, read and write without conflict, in the case of no lock can let multiple transactions concurrent read and write, and solve the problem of read and write conflict, greatly improve the system concurrency

Two, pessimistic lock, optimistic lock

Locks are classified into table locks, row locks, and page locks by granularity.

According to the way of use, it is divided into shared lock and exclusive lock.

According to the thought is divided into optimistic lock, pessimistic lock.

Either optimistic locking or pessimistic locking is just an idea, not an actual locking mechanism, it must be clear.

1. Pessimistic locking (pessimistic concurrency control)

Pessimistic locking is actually pessimistic concurrency control, abbreviated PCC.

Pessimistic locking is a negative attitude that every time data is accessed, there will always be a conflict. Therefore, data must be locked for each access and the lock will be released after the access is complete.

Ensure that only a single thread can access data at the same time to achieve exclusivity. At the same time, pessimistic lock is realized by the locking mechanism of database itself, which can solve the conflicts of read-write and writ-write.

In what circumstances can pessimistic locks be used?

Pessimistic locking is applicable to the concurrent environment with more write and less read. Although the concurrency efficiency is not high, it ensures data security.

2. Optimistic locking (Optimistic concurrency control)

Like pessimistic locks, optimistic locks are actually optimistic concurrency control, abbreviated OCC.

Optimistic locking, compared with pessimistic locking, considers that even in a concurrent environment, external operations on data will not conflict, so it will not lock, but will formally check whether data conflict when submitting update.

If a conflict is found, either try again or switch to a pessimistic policy.

Optimistic concurrency control aims to solve the write – write conflict in the database concurrency scenario, which is solved in a lock – free way

Iii. What problems MVCC solves

The following problems arise in the case of concurrent transactions.

  • Dirty read: Reads data not committed by other transactions.
  • Non-repeatable read: when a transaction reads a piece of data, another transaction modifies the data and commits the transaction, causing the data to be inconsistent when read again
  • Phantom read: one transaction reads a range of data, and another transaction adds a range of data. The results obtained by the two transactions are inconsistent.

The implementation of MVCC in Innodb storage engine is mainly to improve the database concurrency ability, with a better way to deal with read-write conflicts, and at the same time do not lock, non-blocking concurrent read and write.

MVCC can solve dirty read and unrepeatable read. MVCC uses snapshot read to solve part of phantom read problem, but it still uses current read when modifying, so phantom read problem still exists. Phantom read problem is finally solved by gap lock.

Current read and snapshot read

Before you can understand how MVCC solves the problem of transaction concurrency, you need to understand two concepts: current read and snapshot read.

1. The current reading

Add shared locks to read operations, exclusive locks, and exclusive locks to DML operations, and these operations are the current read.

Shared and exclusive locks are also called read and write locks.

A shared lock and a shared lock coexist, but can be modified, added, or deleted only after the shared lock is released.

Because in the Innodb storage engine, DML operations implicitly add exclusive locks.

Therefore, the record read by the current read is the latest record. When reading data, a lock is added to ensure that other transactions cannot modify the current record.

2. The snapshot to read

If you see this, you have some understanding of the isolation level.

The prerequisite for snapshot reads is that the isolation level is not serial. Snapshot reads at the serial level are degraded to current reads.

Snapshot reads are designed to improve transaction concurrency, and their implementation is based on MVCC, or multi-version controller, which is the protagonist of this article.

MVCC can be considered a variant of row locking, but it avoids locking in many cases.

Therefore, the snapshot may read data of a previous version rather than the latest one.

Why mention snapshot reading! Because the read-view is generated by snapshot reading, it is explained here to prevent ambiguity.

3. How to distinguish current read from snapshot read

A simple select without locking is a snapshot read.

select id name user where id = 1;
Copy the code

Select (); select ();

select id name from user where id = 1 lock in share mode;

select id name from user where id = 1 for update;
Copy the code

Five, MVCC realization of three elements

Finally comes to the most important part of this paper, the previous description is to pave the way for the principle of this piece.

Before you do that, you need to know that MVCC only works at REPEATABLE READ and READ COMMITTED isolation levels.

MVCC is implemented by two implicit fields, undo log and Read View.

1. Implicit fields

In the Innodb storage engine, two fields are hidden in each row if there is a clustered index, and a 6byte hidden primary key if there is no clustered index.

The two hidden columns are one for when it was created and one for when it was deleted.

Do not read this as a record of the time, store the transaction ID.

The two implicit fields are DB_TRX_ID and DB_ROLL_PTR, and the DB_ROW_ID field is not included in the clustered index.

  • DB_TRX_ID: Records the transaction ID of the last time this data was modified
  • DB_ROLL_PTR: Rollback pointer to the previous version of this record

An implicit field also has a delete Flag field, that is, the record is updated or deleted. The delete flag in this field does not mean that the record is actually deleted, but changes the delete flag in this field to true.

2. Undo log

Previously, undo log only mentioned the atomicity of the rollback operation, but now you need to know about the implementation of MVCC multi-version controller.

The undo log is divided into two types: the undo log generated during insert, update, and delete

Undo logs generated by inserts in Innodb are deleted after the transaction is committed. There is no need to maintain undo logs because the newly inserted data has no historical version.

Undo logs generated by update and DELETE operations belong to the same type and are required for transaction rollback and snapshot reads, so multiple version information needs to be maintained. The purge thread removes the log only if the log is not involved in snapshot reads and transaction rollback.

The Purge thread cleans up the historical version of the undo log, as well as the del Flag record.

The role of undo log in MVCC

The estimate of undo log’s role in MVCC is still masked.

Undo log saves a version chain, which is connected using the DB_ROLL_PTR field.

The consistency view read View is generated when the database executes a SELECT statement.

The read view consists of an array of uncommitted transaction ids at the time of the query. The smallest transaction ID in the array is min_id and the largest transaction ID created is max_id. The result of the query should be compared with the read-view to obtain the snapshot result.

The purpose of undo log in MVCC is to compare the stored transaction ID with the consistency view to obtain the snapshot result.

3. Low-level implementation of undo log

Suppose we start with the following data

Update user set name = ‘niuniu WHERE id = 1’ update user set name = ‘niuniu WHERE id = 1

This means that when an update statement is executed, the original data is copied to the undo log.

You can also see that the latest record has a line at the end, meaning that DB_ROLL_PTR records the address of the pointer to the undo log.

Eventually, you might need Pointers to find historical data.

4. read-view

A consistency view, known as read-view, is generated when an SQL statement query is executed, which consists of an array of all uncommitted transaction ids at the time of the query and the maximum transaction ids that have been created.

The smallest transaction ID in this array is called min_id and the largest transaction ID is called max_id. The results of the query are compared against read-view to obtain the snapshot result.

The result is the following comparison rule, which compares the trx_id of the current record against read-view, as follows.

5. Version chain comparison rules

If trx_id<min_id, this version was generated by a committed transaction, and the data is visible because the transaction has been committed

Trx_id >max_id indicates that this version was generated by a future transaction and is definitely not visible

If the min_id < = trx_id < = max_id

  • If the row’s TRx_id is in the array, it means that the version was generated by a transaction that has not yet committed and is not visible, but its own transaction is visible
  • If the trx_ID of the row is not in the array, it indicates that the committed transaction generated the version

There is also a special case for deleting data. Update and DELETE are the same type of Undo log, and delete can also be considered as a special case for update.

When deleting a data, the latest data in the version chain will be copied, and trx_id will be changed to the deleted trx_id. At the same time, there is a Delete flag in the header information of the record, which is written true to indicate that the current record has been deleted.

The corresponding record is queried according to the rules of the version chain. If the DELETE flag bit is true, data has been deleted, and no data is returned.

If you don’t understand the read-view generation and version-chain comparison rules here, don’t worry, don’t waste your time, read on, as Kaka recreates the above rules using a simple case and a complex case.

Six, THE underlying principle of MVCC

Case a

Select returns niUNIu as the result of transaction 102

From the figure above, you can see that there are three transactions in progress.

SQL > alter table 101; SQL > alter table 102; SQL > alter table 101;

Let’s see if the select column returns the same result as the transaction ID 102.

The generated read-view is [100,101],102

Now you can go back to the read-view rule, where transaction ID100 is min_id and transaction ID102 is max_id.

The select statement must return niUNIu.

So let’s look at how data is found in MVCC.

Current version chain.

Trx_id = 102 and max_id = 102

Then you look at the third case in the version chain comparison rule

If min_id<=trx_id<=max_id, there are two situations

Transaction ID102 is not in the array, so this version is visible.

No doubt the query will return the value niuniu

This simple example will give you a simple understanding of version chains, and then I will use a more complicated case to show you again.

Case 2

This example asks to know the second query result of select. Dark black font.

Again, based on kaka’s record.

When the transaction ID100 is updated twice, the version chain will also change. The current version chain is shown in the figure below. The red part is the latest data, and the blue data is the undo log version chain data.

What questions do you have about the read-view generated at this point, at the RR level, which is the isolation level for repeatable reads?

When a query is executed under a transaction, all read-views are generated using the first query statement.

Then the read-view is [100,101],102

Take a look at the underlying lookup steps

  • The transaction ID of the data is currently 100
  • Min_id <=trx_id<=max_id according to the rule
  • The transaction ID100 of the current row is in the array of read-view, indicating that the transaction is not visible until committed
  • Further down the version chain, the transaction ID is still 100, as described above
  • By looking up the version chain, you will find the transaction ID is 102
  • 102 is the max_id of the read-view, and will also fall within min_id<=trx_id<=max_id, but the transaction 102 is not in the array, indicating that this version of the transaction has been committed and therefore is visible
  • And the last thing that comes back isniuniu

Case 3

To give you a taste of the read-view generated at the repeatable read level based on the first snapshot read in the same transaction, let’s take another example

Transaction ID101 updates the data twice, and then performs a query to see what value will be returned

After case 1, case 2 familiar with the undo log version chain and comparison rules have a certain understanding of it!

Case three is not so detailed.

The version chain is as follows

The read-view is still [100,101],102.

Transaction 101 and transaction 100 will be in the min_id<=trx_id<=max_id range, and also in the array, so the data is not visible.

So if you go down the version chain you get transaction 102, which is the largest transaction ID and it’s not in the array, so it’s visible.

So the final result is niuniu.

Four cases

As you can see in case 3, the difference is that a new query statement is added. If the two statements are executed at the same time, will they return the same result?

The value in case 3 is niuniu

In fact, the version chain is the same as case three

So let’s take a look at the search

  • First of all, the read-view here has changed, and now the read-view is zero[101], 102
  • Compare the current transaction ID101 with the version chain rule, drop disk min_id<=trx_id<=max_id, and in the array, then the data is not visible
  • Then go to the version chain and find the transaction ID of the next data, again 101, which is the same as the previous one
  • Next comes transaction ID100
  • Transaction ID100 falls on trx_id
  • So the final result is zeroniuniu2

summary

A query within the same transaction uses the read-view generated by the first query (provided the isolation level is repeatable)

Through the above four cases, in the process of version chain search, you can sum up a small skill

You can quickly tell if the version is visible by following this trick.

  • If the current transaction ID in green is committed, the data is visible
  • If the current transaction ID is in blue, the uncommitted transaction is not visible if the current transaction ID is in the Read-view array, and the data is not visible if the current transaction ID is not in the array
  • If it falls in the red part, you don’t think about it, you don’t think about the future.

Seven,

After reading this, one of the most likely questions to be asked during an interview is what you know about MVCC.

This article describes the implementation principle of MVCC step by step from shallow to deep, from what is MVCC to the underlying implementation of MVCC.

Summary of this article

  • MVCC solves the magic problem of dirty reads, unrepeatable reads, and snapshot reads without locking. You must not assume that magic is completely solved by MVCC
  • To understand the current read and snapshot read, simply say that the current read is locked, and the snapshot read is not locked.
  • The three main elements of an MVCC implementation are implicit fields, rollback logs, and read-view
  • Two implicit fields: DB_TRX_ID: specifies the transaction ID of the record that was last modified when the record was created, and DB_ROLL_PTR: specifies the rollback pointer to the previous version of the record
  • The undo log generates a version chain when updating data, which is a prerequisite for read-view to retrieve data
  • Read-view This object is generated when SQL executes a query and consists of an array of transaction ids for the submitted transaction and the maximum transaction ID created
  • Version chain rules see the summary in section 6

Insist on learning, insist on writing, insist on sharing is the belief that Kaka has been holding since he started his career. I hope the articles on the Internet can bring you a little help. I’m Kaka. See you next time.