Detailed explanation of MySQL multi-version concurrency control mechanism (MVCC) source code

1. Introduction

As a database enthusiast, I have written a simple SQL parser and storage engine by myself, but it still feels not satisfying enough. <<Transaction Processing - Concepts and Technologies>> is indeed very thorough, but it can only give you a general idea and cannot help you to play with a real database. Thanks to cmake, I can use xcode to debug MySQL on Mac, so that I can appreciate its various implementation details.

(Note: The MySQL version used in this article is MySQL-5.6.35)

2. MVCC (Multi-version Concurrency Control Mechanism)

Isolation can also be called concurrency control, serializability, etc. When talking about concurrency control, the first thing that comes to mind is locks. MySQL implements serializability of updates by using two-phase locks. At the same time, in order to speed up query performance, the MVCC (Multi Version Concurrency Control) mechanism is adopted, so that consistent versions can be obtained without locks.

2.1 Repeatable Read

MySQL implements Repeatable Read through MVCC and Next-Key Lock. The idea of ​​MVCC is to record the version changes of data and present consistent results to users by cleverly selecting different versions of data. As shown in the following figure:

In the figure above, the initial version of (A=50|B=50) is 1.

1. When transaction t1 selects A, it sees version 1, that is, A=50

2. Transaction t2 modifies A and B and upgrades the version to 2, that is, A=0, B=100

3. When transaction t1 selects B again, the version it sees is still 1, that is, B=50

This isolates the impact of the version, and A+B is always 100.

2.2 Read Commit

If the latest committed result is read without version control mechanism, the isolation level is read commit, as shown in the following figure:

In this case, you need to use a lock mechanism (such as select for update) to lock the A and B records to obtain the correct and consistent results, as shown in the following figure:

2.3 Advantages of MVCC

When we need to perform some read-only operations on some data to check consistency, such as checking whether the accounts are aligned, we do not want to add locks that will cause a large performance loss. At this time, the consistent version of MVCC has a great advantage.

3. MVCC (implementation mechanism)

This section will start to talk about the implementation mechanism of MVCC. Note that MVCC is only valid for pure select (excluding lock operations such as select for update, lock in share mode, and update\insert, etc.).

3.1、Select the running stack

First, let's trace the running process of a common query SQL in the MySQL source code. The SQL is (select * from test);

Its running stack is:

handle_one_connection MySQL's network model is one request one thread

|-do_handle_one_connection

|-do_command

|-dispatch_command

|-mysql_parse Parsing SQL

|-mysql_execute_command

|-execute_sqlcom_select Execute the select statement

|-handle_select

... a bunch of parse join and other operations, which I don't care about at the moment

|-*tab->read_record.read_record read record

Since the default isolation level of MySQL is repeatable_read (RR), read_record is overloaded as
rr_sequential (Currently we are not concerned with the process of selecting rows by scanning through index and then filtering through condition). Continue tracking:

read_record

|-rr_sequential

|-ha_rnd_next

|-ha_innobase::rnd_next This is the innodb engine.

|-general_fetch

|-row_search_for_mysql

|-lock_clust_rec_cons_read_sees This is where the version is determined and selected

Let's take a look inside this function:

bool lock_clust_rec_cons_read_sees(const rec_t* rec /*a row scanned by innodb*/,....){
	...
	// Get the last modified version trx_id (transaction id) from the currently scanned row
	trx_id = row_get_rec_trx_id(rec, index, offsets);
	// Determine the row snapshot seen by parameters (consistent snapshot view and transaction id) return(read_view_sees_trx_id(view, trx_id));
}

3.2. Creation process of read_view

Let's first focus on the creation process of the consistency view. Let's first look at the read_view structure:

struct read_view_t{
	// Because it is in reverse order, low/up are reversed // You can see the high water mark of the current row version, and >= low_limit_id cannot be seen trx_id_t low_limit_id;
	// You can see the low water mark of the current row version, < up_limit_id can be seen trx_id_t up_limit_id;
	// The number of currently active transactions (i.e., uncommitted transactions) ulint n_trx_ids;
	// Get the array of currently active transaction IDs in reverse order // Its up_limit_id<tx_id<low_limit_id
	trx_id_t* trx_ids;	
	// Create the transaction id of the current view
	trx_id_t creator_trx_id;
	//Consistency view list in the transaction system UT_LIST_NODE_T(read_view_t) view_list;
};

Then through debugging, it is found that the creation of the read_view structure is also operated in the above rr_sequential, and the call stack is continued:

rr_sequential

|-ha_rnd_next

|-rnd_next

|-index_first Go to the current branch index_first when start_of_scan is true

|-index_read

|-row_search_for_mysql

|-trx_assign_read_view

Let's look at a branch in row_search_for_mysql:

row_search_for_mysql:
// The consistency view will be created only when the lock-free mode is selected else if (prebuilt->select_lock_type == LOCK_NONE) { // Create a consistency view trx_assign_read_view(trx);
		prebuilt->sql_stat_start = FALSE;
}

The above comment is the reason why select for update (in share model) does not follow MVCC. Let's further analyze the trx_assign_read_view function:

trx_assign_read_view

|-read_view_open_now

|-read_view_open_now_low

Well, we have finally reached the main stage of creating read_view. The main process is shown in the following figure:

The code process is:

static read_view_t* read_view_open_now_low(trx_id_t cr_trx_id,mem_heap_t* heap)
{
	read_view_t* view;
	// In the current transaction system, max_trx_id (i.e., trx_id that has not been assigned) is set to low_limit_no
	view->low_limit_no = trx_sys->max_trx_id;
	view->low_limit_id = view->low_limit_no;
	// The CreateView constructor will remove non-current transactions and transactions that have been committed in memory, that is, the judgment condition is // trx->id != m_view->creator_trx_id&& !trx_state_eq(trx, TRX_STATE_COMMITTED_IN_MEMORY) // and then add them to the current view list ut_list_map(trx_sys->rw_trx_list, &trx_t::trx_list, CreateView(view));
	if (view->n_trx_ids > 0) {
		// Set the minimum id in the current transaction system to up_limit_id, because it is in reverse order view->up_limit_id = view->trx_ids[view->n_trx_ids - 1];
	} else {
		// If there is no active transaction other than the current transaction, set it to low_limit_id
		view->up_limit_id = view->low_limit_id;
	}
	// Ignore the purge transaction. When purging, the current transaction id is 0
	if (cr_trx_id > 0) {
		read_view_add(view);
	}
	// Return the consistent view return(view);
}

3.3. Row Version Visibility

From the lock_clust_rec_cons_read_sees above, we can see that row version visibility is determined by the read_view_sees_trx_id function:

/************************************************************************//**
Checks if a read view sees the specified transaction.
@return true if sees */
UNIV_INLINE
bool
read_view_sees_trx_id(
/*===================*/
	const read_view_t* view, /*!< in: read view */
	trx_id_t trx_id) /*!< in: trx id */
{
	if (trx_id < view->up_limit_id) {

		return(true);
	} else if (trx_id >= view->low_limit_id) {

		return(false);
	} else {
		ulint lower = 0;
		ulint upper = view->n_trx_ids - 1;

		ut_a(view->n_trx_ids > 0);

		do {
			ulint mid = (lower + upper) >> 1;
			trx_id_t mid_id = view->trx_ids[mid];

			if (mid_id == trx_id) {
				return(FALSE);
			} else if (mid_id < trx_id) {
				if (mid > 0) {
					upper = mid - 1;
				} else {
					break;
				}
			} else {
				lower = mid + 1;
			}
		} while (lower <= upper);
	}

	return(true);
}

In fact, the above function is a binary search. read_view actually saves all transaction IDs of the current active transaction. If the transaction ID corresponding to the modification of the current row version is not in the current active transaction, it returns true, indicating that the current version is visible, otherwise it is invisible, as shown in the following figure.

Following the return of lock_clust_rec_cons_read_sees above:

if (UNIV_LIKELY(srv_force_recovery < 5)
			    && !lock_clust_rec_cons_read_sees(
				    rec, index, offsets, trx->read_view)){
	// Currently processing the situation where the current version is not visible // Use undolog to return to a consistent visible version err = row_sel_build_prev_vers_for_mysql(
					trx->read_view, clust_index,
					prebuilt, rec, &offsets, &heap,
					&old_vers, &mtr);			    
} else{
	// Visible, then return }

3.4. Undolog search process for visible versions

Let's now examine the row_sel_build_prev_vers_for_mysql function:

row_sel_build_prev_vers_for_mysql

|-row_vers_build_for_consistent_read

Mainly, the row_ver_build_for_consistent_read method is called to return the visible version:

dberr_t row_vers_build_for_consistent_read(...)
{
	......
	for(;;){
		err = trx_undo_prev_version_build(rec, mtr,version,index,*offsets, heap,&prev_version);
		......
		trx_id = row_get_rec_trx_id(prev_version, index, *offsets);
		// If the current row version conforms to the consistent view, return if (read_view_sees_trx_id(view, trx_id)) {
			......
			break;
		}
		// If the current row version does not match, continue to backtrack to the previous version (return to the for loop)
		version = prev_version;
	}
	......
}

The whole process is shown in the figure below:

As for how undolog restores the corresponding version of row records, it is a complicated process. Due to space constraints, it is omitted here.

3.5. Discuss when to create read_view

In the code of row_search_for_mysql that creates a consistent view

// Only selects in non-lock mode create consistent views else if (prebuilt->select_lock_type == LOCK_NONE) { // Create consistent views trx_assign_read_view(trx);
		prebuilt->sql_stat_start = FALSE;
}

There is such a code in trx_assign_read_view

// A consistent view is created only once in a transaction if (!trx->read_view) {
		trx->read_view = read_view_open_now(
			trx->id, trx->global_read_view_heap);
		trx->global_read_view = trx->read_view;
	}

Therefore, combining these two pieces of code, in a transaction, a consistent view is created only when the select is run for the first time (without locking), as shown in the following figure:

The author has constructed such a scenario and simulated it, and it is indeed true.

4. Some phenomena caused by the simultaneous action of MVCC and locks

MySQL uses MVCC and two-phase locking (2PL) to balance performance and consistency. However, since MySQL only creates a consistent view when selecting and does not do so during locking operations such as update, some strange phenomena will occur. As shown in the following figure:

If you understand that update does not follow the consistent view (read_view), but select follows the consistent view (read_view), this phenomenon can be well explained.
As shown in the following figure:

V. Conclusion

MySQL uses a lot of complex mechanisms to balance performance and ACID, 2PL (two-phase locking) and MVCC are typical examples of its implementation. Fortunately, it is convenient to debug through IDEs such as Xcode, so that the implementation of various mechanisms can be tracked very accurately and conveniently. I hope this article can help readers who like to study MySQL source code.

The above is a detailed explanation of the MySQL multi-version concurrency control mechanism (MVCC) source code. For more information about the MySQL concurrency control mechanism MVCC, please pay attention to other related articles on 123WORDPRESS.COM!