Principles of DBMS. MVCC

Many of us have faced in their work with the DBMS. At the moment the database in one form or another all around us, from mobile phones to social networks, including and beloved Habr. Relational DBMS are the most common representatives of the family of the DBMS, and most of them are transactional.
We were forced to learn the definition of ACID and its properties, but somehow the party managed the implementation details of this paradigm. In this article I will try to partially fill this gap, describing MVCC, which is used in such DBMS as Oracle, Postgres, MySQL, etc. and is very simple and clear.

So, you should start with the definition of ACID:
the

Atomicity transactions are atomic, i.e. either all changes of a transaction are recorded (commit) or are all rolled back (rollback);

Consistency — a transaction do not violate consistency of the data, that is, they transferred the database from one valid state to another. You can mention a valid field values, foreign keys and more complex constraints;

Isolation — concurrent transactions do not affect each other, that is multi-threaded transaction processing is performed so that the result of their parallel execution consistent with the result of their sequential execution;

Durability — if the transaction was successfully completed, no external event should not result in the loss of committed her changes.

Each of these requirements looks more than rational, especially when it affects such important areas as banking operations and other operations with currency: agree, will be very unpleasant if your account the money will be written off, but at the expense of the store they will not come (violation of "atomicity"), or as a result of failure of the ABS is lost, the information that you have enlisted salary (violation of "durability").

If you start to talk about how working DBMS that supports ACID transactions, most of the questions will be of the property of Isolation: modern DBMS support hundreds and thousands of concurrent transactions, and they all refer to the same tables. How to make so that they do not interfere? Here comes MVCC (MultiVersion Concurrency Control), that is, the control of competitive access to data through the creation of multiple “versions” of changed data. In simplified form, this mechanism can be summarized as follows: all data operations can be divided into a read (select), insert (insert), delete (delete), updating (update). Here's what happens when these operations:
the

Select — read a valid entry in the table. An entry is considered valid if it is created by a transaction that has been committed (commit) prior to the current transaction;

Insert — a new entry is simply added to the free space table;

Delete — the table entry is marked as invalid, while the record itself is not deleted;

Update — a combination of delete and insert. First, the old version of the record is marked as not valid, then adds a new entry with the updated data.

In General, this approach can be implemented using only one additional bit flag is_valid = 1 for valid entries and 0 for not valid. But there is a problem with multithreading: this approach will be possible only sequential access to data (writers will block readers and other writers).

Let's say we have a “table a” with the following data:


And two transactions that try to update the data in the following way:
the

Transaction 1: update A set value = value || “ transaction 1” where ID = 1;

Transaction 2: update A set value = value || “ transaction 2” where ID = 1; If they allow parallel work on the same data, can get this result:
the

Transaction 1 read a valid value for the row with ID=1: “Hello”;

Transaction 2 read a valid value for the row with ID=1: “Hello”;

Transaction 1 considered new value for the field Value: “Hello transaction 1”;

Transaction 2 considered new value for the field Value: “Hello transaction 2”;

Transaction 1 update the data in the table;

Transaction 2 update data in the table.


Here is the result of such a scenario:


But the result of their sequential execution:


It is obvious that the isolation requirement is violated: the transaction running at the same time influenced by each other. Such errors can be divided into Dirty Reads, Non-repeatable Reads and Phantom Reads.
Thus we can conclude that:
the

One of the validity flag is not enough, you need a more complex mechanism; the

• For some types of transactions require locking. If two transactions attempt to update the same table entry, it is clear that they can do it only sequentially.

Consider how this works in Postgres:

the
1. All transactions in the system have sequence numbers (conditionally on the fact that the number of transactions for each table and under vacuum it is reset to avoid overflow a 4-byte integer, which is used to store the transaction ID);
the
2. There is a global registry of transactions, containing information about which transactions are in progress and which had been rolled back;
the
3. For each record in the table there are technical fields Xmin and Xmax, which stores information about transactions, modifitsirovannyh this entry. Xmin is the transaction ID which added record to the table. Xmax — the transaction ID to delete the record from the table;
the
4. For each record in the table there are technical fields Cmin and Cmax used to ensure the operation of the transaction to multiple commands.

For example, the first transaction adds a table row, then updates, then deletes. Thanks Xmin and Xmax until you commit the transaction (commit), all these operations will be invisible to external transactions. But what about with the transaction that its changes should see, even if they contradict each other (first record added, then removed)? This created SMP and Cmax, working in much the same way as Xmin and Xmax, but in one particular transaction.

With this set of metadata we are much closer to the realization of ACID, than one of the validity flag. Now consider the above-described operation in the context of MVCC:
the

Select — read a valid entry in the table. For each record we have Xmin, Xmax, Cmin, Cmax. If Xmin more current transaction ID is in the list of running or cancelled transaction, the record is not valid. If Xmax is specified and less than the ID of the current transaction and a transaction with this ID is not in the list of running or cancelled transaction, the record is not valid. If Xmin is equal to the ID of the current transaction, to verify the validity of entries looking at Cmin and Cmax (Cmax should be set below the entry was not valid). If Xmax is equal to the current transaction ID, everything is exactly the opposite. If the above test didn't work, the entry to be valid. On this subject there is a very good piece of code from src/backend/utils/time/tqual.c comment author:



Insert — a new entry is simply added to the free space table, she stamped Xmin in the current transaction ID and the min ID in the current operation in the transaction;

Delete — the table entry is marked as invalid, while the record itself is not deleted. It runs as follows: Xmax is placed in the ID of the current transaction, Cmax in the ID of the current operation;

Commit transaction is performed through the delete transaction ID from the list of running;

Rollback transaction is done through a note of the transaction ID as a transaction subject to rollback.


This model of working with transactions is simplified, as it does not cover the locking mechanism as well as distributed transactions. However, this approach is common to many modern DBMS and its understanding will enable to better understand what is happening inside the database engine.

More detailed case studies for Postgres, you can watch here

Article based on information from habrahabr.ru