Multiversion concurrency control

Multiversion concurrency control (MCC or MVCC), is a concurrency control method commonly used by database management systems to provide concurrent access to the database and in programming languages to implement transactional memory.

If someone is reading from a database at the same time as someone else is writing to it, it is possible that the reader will see a half-written or inconsistent piece of data. There are several ways of solving this problem, known as concurrency control methods. The simplest way is to make all readers wait until the writer is done, which is known as a lock. This can be very slow, so MVCC takes a different approach: each user connected to the database sees a snapshot of the database at a particular instant in time. Any changes made by a writer made will not be seen by other users of the database until the changes have been completed (or, in database terms: until the transaction has been committed.)

When an MVCC database needs to update an item of data, it will not overwrite the old data with new data, but instead mark the old data as obsolete and add the newer version elsewhere. Thus there are multiple versions stored, but only one is the latest. This allows readers to access the data that was there when they began reading, even if it was modified or deleted part way through by someone else. It also allows the database to avoid the overhead of filling in holes in memory or disk structures but requires (generally) the system to periodically sweep through and delete the old, obsolete data objects. For a document-oriented database it also allows the system to optimize documents by writing entire documents onto contiguous sections of disk—when updated, the entire document can be re-written rather than bits and pieces cut out or maintained in a linked, non-contiguous database structure.

MVCC provides point in time consistent views. Read transactions under MVCC typically use a timestamp or transaction ID to determine what state of the DB to read, and read these versions of the data. This avoids managing locks for read transactions because writes can be isolated by virtue of the old versions being maintained, rather than through a process of locks or mutexes. Writes affect a future version but at the transaction ID that the read is working at, everything is guaranteed to be consistent because the writes are occurring at a later transaction ID.

Implementation

MVCC uses timestamps or increasing transaction IDs to achieve transactional consistency. MVCC ensures a transaction never has to wait for a database object by maintaining several versions of an object. Each version would have a write timestamp and it would let a transaction (T_i) read the most recent version of an object which precedes the transaction timestamp (TS(T_i)).

If a transaction (T_i) wants to write to an object, and if there is another transaction (T_k), the timestamp of T_i must precede the timestamp of T_k (i.e., TS(T_i) < TS(T_k)) for the object write operation to succeed. Which is to say a write cannot complete if there are outstanding transactions with an earlier timestamp.

Every object would also have a read timestamp, and if a transaction T_i wanted to write to object P, and the timestamp of that transaction is earlier than the object's read timestamp (TS(T_i) < RTS(P)), the transaction T_i is aborted and restarted. Otherwise, T_i creates a new version of P and sets the read/write timestamps of P to the timestamp of the transaction TS(T_i).

The obvious drawback to 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 mostly involving reading values from the database. MVCC is particularly adept at implementing true snapshot isolation, something which other methods of concurrency control frequently do either incompletely or with high performance costs.

Example

At Time = "t1", the state of a database could be:

Time	Object 1	Object 2
t1	"Hello"	"Bar"
t0	"Foo"	"Bar"

This indicates that the current set of this database (perhaps a key-value store database) is Object 1="Hello", Object 2="Bar". Previously, Object 1 was "Foo" but that value has been superseded. It is not deleted because the database holds multiple versions, but it will be deleted later.

If a long running transaction starts a read operation, it will operate at transaction "t1" and see this state. If there is a concurrent update (during that long-running read transaction) which deletes Object 2 and adds Object 3="Foo-Bar", the database state will look like:

Time	Object 1	Object 2	Object 3
t2	"Hello"	(deleted)	"Foo-Bar"
t1	"Hello"	"Bar"
t0	"Foo"	"Bar"

Now there is a new version as of transaction ID "t2". Note, critically, that the long-running read transaction still has access to a coherent snapshot of the system at "t1", even though the write transaction added data as of "t2", so the read transaction is able to run in isolation from the update transaction that created the "t2" values. This is how MVCC allows isolated, ACID reads without any locks. (Note, however, that the write transaction does need to use locks.)

History

Multiversion concurrency control is described in some detail in the 1981 paper "Concurrency Control in Distributed Database Systems" by Philip Bernstein and Nathan Goodman, then employed by the Computer Corporation of America. Bernstein and Goodman's paper cites a 1978 dissertation by David P. Reed which quite clearly describes MVCC and claims it as an original work.

The first shipping, commercial database software product featuring MVCC was Digital's VAX Rdb/ELN. The second was InterBase, which is still an active, commercial product.

Databases with MVCC

• Altibase
• ArangoDB
• Berkeley DB
• Bigdata
• Clustrix
• CouchDB
• IBM DB2 – since IBM DB2 9.7 LUW ("Cobra") under CS isolation level - in currently committed mode
• IBM Cognos TM1 – in versions 9.5.2 and up.
• Drizzle
• eXtremeDB
• Firebird
• FLAIM
• GE Smallworld Version Managed Data Store
• H2 Database Engine – experimental since version 1.0.57 (2007-08-25)
• Hawtdb
• Apache HBase
• HSQLDB – starting with version 2.0
• HypergraphDB is a Typed Hypergraph Database. Hypergraphs are an extension of Graph, ObjectOriented, and list based data structures.
• SAP HANA – SAP HANA DATABASE
• InfiniDB
• Ingres
• InterBase – all versions
• MariaDB (MySQL fork) when used with XtraDB (developped by Percona Inc.)(XtraDB is a storage engine that is a InnoDB fork and that is included in MariaDB sources and binaries) or PBXT (developped by PrimeBase Technologies).
• MarkLogic Server - a bit of this is described in
• MemSQL
• MDB
• Meronymy SPARQL Database Server
• Microsoft SQL Server – when using READ_COMMITTED_SNAPSHOT, starting with SQL Server 2005
• MySQL when used with InnoDB, Falcon, or Archive storage engines.
• NuoDB - Elastic Cloud Database
• Netezza
• ObjectStore
• Oracle database – all versions since Oracle 3
• OrientDB
• PostgreSQL
• Rdb/ELN
• RDM Embedded
• REAL Server
• RethinkDB
• ScimoreDB
• sones GraphDB
• Sybase SQL Anywhere
• Sybase IQ
• ThinkSQL
• Zope Object Database
• HBase

Other software with MVCC

• JBoss Cache – v 3.0
• EHcache – v 1.6.0-beta4
• Clojure – language software transactional memory
• Subversion – and many other source code repositories
• pojo-mvcc - a lightweight MVCC implementation written in Java
• JVSTM Software Transactional memory that implements the concept of Versioned Boxes proposed by João Cachopo and António Rito Silva, members of the Software Engineering Group - INESC-ID

See also

• Timestamp-based concurrency control
• Clojure
• Read-copy-update
• Vector clock

Further reading

• Gerhard Weikum, Gottfried Vossen, Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery, Morgan Kaufmann, 2002, ISBN 1-55860-508-8