Multiversion concurrency control

From Wikipedia, the free encyclopedia

In computer science, in the field of databases, multiversion concurrency control (abbreviated MCC or MVCC) is a concurrency control method commonly used by database management systems to provide concurrent access to the database.

From the perspective of the client, MVCC provides each user connected to the database with a "snapshot" of the database for that person to work with. Any changes made will not be seen by other users of the database until the transaction has been committed.

1 Implementation
2 History
3 Databases with MVCC
4 See also
5 References

[edit] Implementation

MCC uses timestamps or increasing transaction IDs to achieve serializability. MCC 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 timestamp TS(T_i).

If T_i wants to write to an object, and if there was another transaction T_j, the timestamp order must be TS(T_i) < TS(T_j) for the object write to succeed.

Every object would also have a read timestamp, and if T_i wanted to write to object P, and TS(T_i) < RTS(P), T_i is aborted and restarted. Otherwise, T_i creates a new version of P and sets the read/write timestamps of P to 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. MCC is particularly adept at implementing true snapshot isolation, something which other methods of concurrency control frequently do either incompletely or with high performance cost.

[edit] History

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

Jim Starkey was working at DEC on their Datatrieve network database product when he came up with an idea for a system to manage concurrent changes by many users. The idea dramatically simplified the existing problems of locking which were proving to be a serious problem for the new relational database systems being developed at the time. He started working on the system at DEC, but at the time DEC had just started a relational database effort which led to the Rdb/VMS product. When they found out about his project a turf war broke out (although the product was released as Rdb/ELN), and Starkey eventually decided to quit.

He had heard that the local workstation vendor Apollo Computer was looking for a database offering on their Unix machines, and agreed to fund development. With their encouragement he formed Groton Database Systems (named after the town, Groton, Massachusetts, where they were located) on September 3rd, 1984 (Labor Day in the United States) and started work on what would eventually be released as InterBase in 1986.

Although InterBase's implementation is much more similar to the system described by Reed in his MIT dissertation than any other database that existed at the time and Starkey knew Bernstein from his previous position at the Computer Corporation of America and later at DEC, Starkey has stated that he arrived at the idea of multiversion concurrency control independently.^[3] In the same comment, Starkey says:

The inspiration for multi-generational concurrency control was a database system done by Prime that supported page level snapshots. The intention of the feature was to give a reader a consistent view of the database without blocking writers. The idea intrigued me as a very useful characteristic of a database system.