Jump to content

Multiversion concurrency control

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by MystBot (talk | contribs) at 21:24, 8 December 2011 (r2.7.1) (Robot: Modifying fr:Multiversion Concurrency Control). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Multiversion concurrency control (abbreviated MCC or MVCC), in the database field of computer science, 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.[1]

For instance, a database will implement updates not by deleting an old piece of data and overwriting it with a new one, but instead by marking the old data as obsolete and adding the newer "version." Thus there are multiple versions stored, but only one is the latest. This allows the database to avoid 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 such as CouchDB 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 also provides potential "point in time" consistent views. In fact 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 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.

In other words, 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.

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 (Ti) read the most recent version of an object which precedes the transaction timestamp (TS(Ti)).

If a transaction (Ti) wants to write to an object, and if there is another transaction (Tk), the timestamp of Ti must precede the timestamp of Tk (i.e., TS(Ti) < TS(Tk)) 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 Ti wanted to write to object P, and the timestamp of that transaction is earlier than the object's read timestamp (TS(Ti) < RTS(P)), the transaction Ti is aborted and restarted. Otherwise, Ti creates a new version of P and sets the read/write timestamps of P to the timestamp of the transaction TS(Ti).

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" [2] by Philip Bernstein and Nathan Goodman—then employed by the Computer Corporation of America. Bernstein and Goodman's paper cites a 1978 dissertation[3] by David P. Reed which quite clearly describes MVCC and claims it as an original work.

Databases with MVCC

Other software with MVCC

See also

References

  1. ^ http://clojure.org/refs
  2. ^ Philip Bernstein and Nathan Goodman (1981). "Concurrency Control in Distributed Database Systems". ACM Computing Surveys.
  3. ^ Reed, D.P. (September 21, 1978). "Naming and Synchronization in a Decentralized Computer System". MIT dissertation.
  4. ^ Berkeley DB Reference Guide: Degrees of Isolation
  5. ^ Bigdata Blog
  6. ^ DB2 Version 9.7 LUW Information Center, Currently committed semantics improve concurrency
  7. ^ TM1 9.5.2 Information Center, Parallel Interaction
  8. ^ Graves, Steve (May 1, 2010). "Multi-Core Software: To Gain Speed, Eliminate Resource Contention". RTC Magazine.
  9. ^ White paper by Roman Rokytsky Firebird and Multi Version Concurrency Control
  10. ^ Multi-Version Concurrency Control in the H2 Database Engine
  11. ^ http://community.ingres.com/wiki/MVCC
  12. ^ Todd, Bill (2000). "InterBase: What Sets It Apart". Archived from the original on 26 February 2006. Retrieved 4 May 2006.
  13. ^ MySQL 5.1 Reference Manual, Section 14.2.12: Implementation of Multi-Versioning
  14. ^ or Maria MySQL 5.1 Reference Manual, Section 14.6.1: Falcon Features
  15. ^ Oracle Database Concepts: Chapter 13 Data Concurrency and Consistency Multiversion Concurency Control
  16. ^ PostgreSQL 8.4 Documentation, Chapter 13: Concurrency Control
  17. ^ RDM Embedded 10.1 Reference Manual, d_trrobegin
  18. ^ [1]
  19. ^ Proposal for MVCC in ZODB
  20. ^ [2]
  21. ^ ehcache site
  22. ^ pojo-mvcc project home

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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Multiversion_concurrency_control&oldid=464838047"