Lecture
MVCC (multiversion concurrency control) — is one of the DBMS mechanisms for providing concurrent access to databases, consisting of giving each user a so-called «snapshot» of the database, with the property that changes made by a user are invisible to other users until the transaction is committed. This method of control makes it possible to ensure that writing transactions do not block readers, and reading transactions do not block writers.
Rdb is considered the first DBMS to implement this mechanism; similar mechanisms based on it appeared in the late 1980s in InterBase and Oracle Database ), the mechanism was implemented in PostgreSQL in the 1990s, and by the 2000s — in almost all mature relational DBMSs. Later this mechanism was also adopted by a number of systems classified as NoSQL and NewSQL (including MongoDB, CouchDB, CockroachDB[en] and many others), and even some software systems not classified as DBMSs (for example, etcd[en], ehcache[en] and others).
Without concurrency control, if someone reads from a database at the same time as writing to it, the reader may see half-written or inconsistent data. For example, during a bank transfer between two bank accounts, if the reader checks the balance at the point when money has been withdrawn from the source account but before it has been deposited into the destination account, it may appear that the money has disappeared from the bank. Isolation is the property that provides guarantees for concurrent access to data. Isolation is implemented via a concurrency control protocol. The simplest way is to make all readers wait until the writer has finished, which is called read-write locking. It is well known that locks create contention, especially between long-running read transactions and update transactions. MVCC aims to solve this problem by keeping multiple copies of each data item. In this way, every user connected to the database sees a snapshot of the database at a particular point in time. Any changes made by the author are not visible to other database users until the changes are complete (or in database terms: until the transaction is committed).
When an MVCC database needs to update a piece of data, it does not overwrite the original data item with new data, but instead creates a newer version of the data item. In this way multiple versions are stored. The version that each transaction sees depends on the isolation level implemented. The most common isolation level implemented via MVCC is snapshot isolation. With snapshot isolation, a transaction observes the state of the data as it was when the transaction began.
MVCC provides consistent point-in-time views. Read transactions in MVCC typically use a timestamp or transaction identifier to determine which state of the database to read, and then read those versions of the data. In this way, read and write transactions are isolated from each other without any locking. However, although locks are not strictly necessary, they are still used by some MVCC databases, such as Oracle. A write creates a new version, while a concurrent read is given access to the older version.
MVCC presents the problem of how to remove versions that are outdated and will never be read. In some cases a process of periodically scanning and removing obsolete versions is implemented. This is often a stop-the-world process that scans the entire table and overwrites it with the latest version of each data item. PostgreSQL applies this approach in its VACUUM process. Other databases split storage blocks into two parts: a data part and an undo log. The data part always keeps the latest committed version. The undo log allows old versions of the data to be recovered. The main inherent limitation of this latter approach is that under update-intensive workloads the undo log part can run out of space, after which transactions are aborted because they cannot be given their snapshot. For a document-oriented database, this approach also allows the system to optimize documents by writing entire documents to contiguous disk sections — on update the whole document can be rewritten rather than cutting out individual fragments or storing them in a linked, non-contiguous structure.
MVCC uses timestamps ( TS ) and incrementing transaction identifiers to achieve transaction consistency . MVCC guarantees that a transaction ( T ) never has to wait to read a database object ( P ), by maintaining multiple versions of the object. Each version of object P has both a read timestamp ( RTS ) and a write timestamp ( WTS ), which allows a specific transaction T i to read the most recent version of the object that precedes the transaction's read timestamp RTS ( Ti ).
If transaction T i wants to write to object P , and there is also another transaction T k, operating on the same object, the read timestamp RTS ( T i ) must precede the Read Timestamp RTS ( T k ), i.e. RTS ( T i ) < RTS ( T k ) [ clarification needed ] for the object's write operation ( WTS ) to succeed. A write cannot complete if there are other outstanding transactions with an earlier read timestamp ( RTS ) on the same object. Much like standing in a checkout line, you cannot complete your transaction until those ahead of you have completed theirs.
To reiterate; every object ( P ) has a timestamp ( TS ), however, if transaction T i wants to write to an object, and the transaction has a timestamp ( TS ) that precedes the object's current read timestamp, TS ( T i ) < RTS ( P ), then the transaction is aborted and restarted. (This is because a later transaction already depends on the old value.) Otherwise, T i creates a new version of object P and sets the read/write timestamp TS of the new version to the transaction's timestamp TS ← TS ( T i ).
The drawback of this system is the cost of storing multiple versions of objects in the database. On the other hand, reads are never blocked, which can be important for workloads primarily concerned with reading values from the database. MVCC is particularly good at implementing true snapshot isolation, which other concurrency control methods often achieve only incompletely or at a high performance cost.
At Time = 1 the state of the database might be:
| Time | Object 1 | Object 2 |
|---|---|---|
| 0 | "Foo", by T0 | "Bar" by T0 |
| 1 | "Hello" by T1 |
T0 wrote Object 1 = "Foo" and Object 2 = "Bar". After that, T1 wrote Object 1 = "Hello", leaving Object 2 at its original value. The new value of Object 1 will replace version 0 for all transactions that begin after T1 is committed, after which version 0 of Object 1 can be garbage collected.
If a long-running transaction T2 starts a read operation on Object 2 and Object 1 after T1 has committed, and there is a concurrent update transaction T3 which deletes Object 2 and adds Object 3 = «Foo-Bar», the state of the database will look as shown at time 2:
| Time | Object 1 | Object 2 | Object 3 |
|---|---|---|---|
| 0 | "Foo", by T0 | "Bar" by T0 | |
| 1 | "Hello" by T1 | ||
| 2 | (deleted) T3 | "Foo-Bar" by T3 |
At time 2, a new version of Object 2 has appeared, marked as deleted, along with a new Object 3. Since T2 and T3 execute concurrently, T2 sees the version of the database prior to 2, i.e. before T3 committed the write, and as such T2 reads Object 2 = «Bar» and Object 1 = «Hello». Thus, multiversion concurrency control allows reads with snapshot isolation to be performed without any locking.
Multiversion concurrency control is described in more detail in a 1981 paper, «Concurrency Control in Distributed Database Systems» by Phil Bernstein and Nathan Goodman, who later worked at Computer Corporation of America. Bernstein and Goodman's paper cites David P. Reed's 1978 dissertation , which describes MVCC quite clearly and claims it as original work.
The first commercial database software product to feature MVCC was VAX Rdb/ELN, created at Digital Equipment Corporation by Jim Starkey. Starkey went on to create the second commercially successful MVCC database, InterBase.
Comments