多版本並行控制

多版本並行控制(Multiversion concurrency control， MCC 或 MVCC)，是資料庫管理系統常用的一種並行控制，也用於程式語言實現事務記憶體。^[1]

MVCC意圖解決讀寫鎖造成的多個、長時間的讀操作餓死寫操作問題。每個事務讀到的數據項都是一個歷史快照，並依賴於實現的隔離級別。寫操作不覆蓋已有數據項，而是建立一個新的版本，直至所在操作提交時才變為可見。快照隔離使得事務看到它啟動時的數據狀態。

演算法[編輯]

MVCC使用時間戳 (TS), 或「自動增量的事務ID」實現「事務一致性」。MVCC可以確保每個事務(T)通常不必「讀等待」資料庫對象(P)。這通過對象有多個版本，每個版本有建立時間戳 與廢止時間戳 (WTS)做到的。

事務T_i讀取對象(P)時，只有比事務T_i的時間戳早，但是時間上最接近事務T_i的對象版本可見，且該版本應該沒有被廢止。

事務T_i寫入對象P時，如果還有事務T_k要寫入同一對象，則(T_i)必須早於(T_k)，即 (T_i) < (T_k)，才能成功。^[2]

MVCC可以無鎖（英語：Non-lock concurrency control）實現。

歷史[編輯]

MVCC在1981年的一篇論文"Concurrency Control in Distributed Database Systems"^[3]被充分論述，並成為經典描述。一般認為原創工作始於1978年David P. Reed（英語：David P. Reed）的博士學位論文^[4]。

資料庫實現[編輯]

現在，多數資料庫系統已經使用MVCC。

Altibase
ArangoDB^[5]
Berkeley DB^[6]
Cloudant
Clustrix^[7]
Couchbase
CouchDB
CUBRID^[8]
IBM Db2 – 從 IBM DB2 9.7 LUW ("Cobra") 在 CS孤立級– currently committed mode^[9]
IBM Cognos TM1 – 從版本9.5.2^[10]
Drizzle
Druid
etcd^[11]
EXASOL
eXtremeDB^[12]
Firebird^[13]
FLAIM
FoundationDB
GE Smallworld Version Managed Data Store
H2 Database Engine –從版本 1.0.57 (2007-08-25)^[14]
HBase
HSQLDB – 從版本 2.0
IBM Netezza
InfiniDB
Ingres^[15]
InterBase – 所有版本^[16]
LMDB
MariaDB (MySQL fork) – 當用於 XtraDB, InnoDB分支^[17] or PBXT^[18]^[19]
MarkLogic Server – 見^[20]
MemSQL
Meronymy SPARQL Database Server
Microsoft SQL Server –當使用 READ_COMMITTED_SNAPSHOT, 從SQL Server 2005^[21]
MongoDB – 當使用 WiredTiger^[22]儲存引擎
MySQL – 使用 InnoDB,^[23]^[24] Falcon,^[25] 或 Archive 儲存引擎
NuoDB
ObjectDB
ObjectStore
Oracle database – 從 Oracle 4^[26]^[27]^[28]
Oracle (née DEC) Rdb
OrientDB^[29]
PostgreSQL^[30]更新的事務如果刪除、修改了數據項並提交，則老的事務將對這些提交結果可見。^[31]
Postgres-XL
Rdb/ELN^[32]
RDM Embedded^[33]
REAL Server
Realm
RethinkDB^[34]
SAP HANA
SAP IQ
sones GraphDB
Splice Machine^[35]
Sybase SQL Anywhere
Tibero –從 Tibero 3
TokuMX^[36]
Actian Vector
Zope Object Database^[37]

參考文獻[編輯]

^ refs （頁面存檔備份，存於互聯網檔案館）. Clojure. Retrieved on 2013-09-18.
^ Ramakrishnan, R., & Gehrke, J. (2000). Database management systems. Osborne/McGraw-Hill.
^ Philp A. Bernstein and Nathan Goodman: 《Multiversion Concurrency Control--Theory and Algorithms》，《ACM Transactions on Database Systems》Vol.8, No.4, December 1983, pages 465-483 (PDF). [2018-11-12]. （原始內容存檔 (PDF)於2017-08-08）.
^ Reed, David P. Naming and Synchronization in a Decentralized Computer System (PDF). MIT dissertation. September 21, 1978 [2018-11-12]. （原始內容存檔 (PDF)於2022-01-21）.
^ ArangoDB Manual Pages: AppendOnly/MVCC. [2018-11-12]. （原始內容存檔於2013-02-23）.
^ Berkeley DB Reference Guide: Degrees of Isolation. [2018-11-12]. （原始內容存檔於2011-03-19）.
^ A new approach: Clustrix Sierra database engine (PDF). [2018-11-12]. （原始內容存檔 (PDF)於2012-04-12）.
^ Database Transaction — CUBRID 10.0.0 documentation. cubrid-manual.readthedocs.io. [2018-11-12]. （原始內容存檔於2017-09-07）.
^ DB2 Version 9.7 LUW Information Center, Currently committed semantics improve concurrency
^ TM1 9.5.2 Information Center, Parallel Interaction
^ etcd3 Documentation | etcd3 API | CoreOS. [2018-11-12]. （原始內容存檔於2019-01-13）.
^ Graves, Steve. Multi-Core Software: To Gain Speed, Eliminate Resource Contention. RTC Magazine. May 1, 2010 [2018-11-12]. （原始內容存檔於2010-06-01）.
^ White paper by Roman Rokytsky Firebird and Multi Version Concurrency Control （頁面存檔備份，存於互聯網檔案館）
^ Multi-Version Concurrency Control in the H2 Database Engine. [2018-11-12]. （原始內容存檔於2006-07-09）.
^ MVCC - Ingres Community Wiki （頁面存檔備份，存於互聯網檔案館）. Community.ingres.com. Retrieved on 2013-09-18.
^ Todd, Bill. InterBase: What Sets It Apart. 2000 [4 May 2006]. （原始內容存檔於2006-02-26）.
^ About XtraDB, About XtraDB （頁面存檔備份，存於互聯網檔案館）
^ MariaDB/Storage Engines, PBXT
^ About PBXT, About PBXT （頁面存檔備份，存於互聯網檔案館）
^ Inside MarkLogic Server^{[永久失效連結]}
^ Snapshot Isolation in SQL Server. [2018-11-12]. （原始內容存檔於2017-04-04）.
^ Multiversion concurrency control in MongoDB, MongoDB CTO: How our new WiredTiger storage engine will earn its stripes （頁面存檔備份，存於互聯網檔案館）
^ MySQL 5.1 Reference Manual, Section 14.2.12: Implementation of Multi-Versioning （頁面存檔備份，存於互聯網檔案館）
^ MySQL 5.1 Reference Manual, Table 14.1. Storage Engine Features （頁面存檔備份，存於互聯網檔案館）
^ or Maria MySQL 5.1 Reference Manual, Section 14.6.1: Falcon Features (Archive) Portuguese Web Archive的存檔，存檔日期2014-10-04
^ Oracle Database Concepts: Chapter 13 Data Concurrency and Consistency Multiversion Concurency Control （頁面存檔備份，存於互聯網檔案館）
^ Oracle 4. Oracle FAQ. [21 March 2013]. （原始內容存檔於2021-01-12）.
^ Oracle Timeline. [21 March 2013]. （原始內容存檔於2021-01-31）.
^ OrientDb Documentation. [2018-11-12]. （原始內容存檔於2015-12-27）.
^ PostgreSQL Current Documentation, Chapter 13: Concurrency Control （頁面存檔備份，存於互聯網檔案館）
^ How does MVCC (Multi-Version Concurrency Control) work. [2018-11-12]. （原始內容存檔於2021-02-09）.
^ VAX Rdb/ELN, Version 2.3 (Relational Database Management System) (PDF). [2018-11-12]. （原始內容 (PDF)存檔於2016-03-03）.
^ RDM Embedded 10.1 Reference Manual, d_trrobegin （頁面存檔備份，存於互聯網檔案館）
^ RethinkDB advanced FAQ. [2018-11-12]. （原始內容存檔於2016-03-28）.
^ Running Transactions - Splice Machine Documentation. doc.splicemachine.com. [2018-11-12]. （原始內容存檔於2018-05-14）.
^ Archived copy. [2015-11-06]. （原始內容存檔於2014-08-11）.
^ Proposal for MVCC in ZODB. [2018-11-12]. （原始內容存檔於2012-02-06）.

延伸閱讀[編輯]

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

[1] refs （頁面存檔備份，存於互聯網檔案館）. Clojure. Retrieved on 2013-09-18.

[2] Ramakrishnan, R., & Gehrke, J. (2000). Database management systems. Osborne/McGraw-Hill.

[3] Philp A. Bernstein and Nathan Goodman: 《Multiversion Concurrency Control--Theory and Algorithms》，《ACM Transactions on Database Systems》Vol.8, No.4, December 1983, pages 465-483 (PDF). [2018-11-12]. （原始內容存檔 (PDF)於2017-08-08）.

[4] Reed, David P. Naming and Synchronization in a Decentralized Computer System (PDF). MIT dissertation. September 21, 1978 [2018-11-12]. （原始內容存檔 (PDF)於2022-01-21）.

[ADB-5] ArangoDB Manual Pages: AppendOnly/MVCC. [2018-11-12]. （原始內容存檔於2013-02-23）.

[BDB-6] Berkeley DB Reference Guide: Degrees of Isolation. [2018-11-12]. （原始內容存檔於2011-03-19）.

[7] A new approach: Clustrix Sierra database engine (PDF). [2018-11-12]. （原始內容存檔 (PDF)於2012-04-12）.

[cubrid_10.0-8] Database Transaction — CUBRID 10.0.0 documentation. cubrid-manual.readthedocs.io. [2018-11-12]. （原始內容存檔於2017-09-07）.

[cur_commit-9] DB2 Version 9.7 LUW Information Center, Currently committed semantics improve concurrency

[10] TM1 9.5.2 Information Center, Parallel Interaction

[11] tcd3 Documentation | etcd3 API | CoreOS. [2018-11-12]. （原始內容存檔於2019-01-13）.

[12] Graves, Steve. Multi-Core Software: To Gain Speed, Eliminate Resource Contention. RTC Magazine. May 1, 2010 [2018-11-12]. （原始內容存檔於2010-06-01）.

[13] White paper by Roman Rokytsky Firebird and Multi Version Concurrency Control （頁面存檔備份，存於互聯網檔案館）

[14] Multi-Version Concurrency Control in the H2 Database Engine. [2018-11-12]. （原始內容存檔於2006-07-09）.

[15] MVCC - Ingres Community Wiki （頁面存檔備份，存於互聯網檔案館）. Community.ingres.com. Retrieved on 2013-09-18.

[IBMVCC-16] Todd, Bill. InterBase: What Sets It Apart. 2000 [4 May 2006]. （原始內容存檔於2006-02-26）.

[17] About XtraDB, About XtraDB （頁面存檔備份，存於互聯網檔案館）

[18] MariaDB/Storage Engines, PBXT

[19] About PBXT, About PBXT （頁面存檔備份，存於互聯網檔案館）

[20] Inside MarkLogic Server^{[永久失效連結]}

[21] Snapshot Isolation in SQL Server. [2018-11-12]. （原始內容存檔於2017-04-04）.

[22] Multiversion concurrency control in MongoDB, MongoDB CTO: How our new WiredTiger storage engine will earn its stripes （頁面存檔備份，存於互聯網檔案館）

[23] MySQL 5.1 Reference Manual, Section 14.2.12: Implementation of Multi-Versioning （頁面存檔備份，存於互聯網檔案館）

[24] MySQL 5.1 Reference Manual, Table 14.1. Storage Engine Features （頁面存檔備份，存於互聯網檔案館）

[25] r Maria MySQL 5.1 Reference Manual, Section 14.6.1: Falcon Features (Archive) Portuguese Web Archive的存檔，存檔日期2014-10-04

[26] Oracle Database Concepts: Chapter 13 Data Concurrency and Consistency Multiversion Concurency Control （頁面存檔備份，存於互聯網檔案館）

[27] Oracle 4. Oracle FAQ. [21 March 2013]. （原始內容存檔於2021-01-12）.

[28] Oracle Timeline. [21 March 2013]. （原始內容存檔於2021-01-31）.

[29] OrientDb Documentation. [2018-11-12]. （原始內容存檔於2015-12-27）.

[30] PostgreSQL Current Documentation, Chapter 13: Concurrency Control （頁面存檔備份，存於互聯網檔案館）

[31] How does MVCC (Multi-Version Concurrency Control) work. [2018-11-12]. （原始內容存檔於2021-02-09）.

[32] VAX Rdb/ELN, Version 2.3 (Relational Database Management System) (PDF). [2018-11-12]. （原始內容 (PDF)存檔於2016-03-03）.

[33] RDM Embedded 10.1 Reference Manual, d_trrobegin （頁面存檔備份，存於互聯網檔案館）

[34] RethinkDB advanced FAQ. [2018-11-12]. （原始內容存檔於2016-03-28）.

[35] Running Transactions - Splice Machine Documentation. doc.splicemachine.com. [2018-11-12]. （原始內容存檔於2018-05-14）.

[36] Archived copy. [2015-11-06]. （原始內容存檔於2014-08-11）.

[37] Proposal for MVCC in ZODB. [2018-11-12]. （原始內容存檔於2012-02-06）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]