OCC和MVCC的區別是什麼？

*最簡單的並發控制演算法是2PL（2 Phase Locking），分為兩階段：

1）獲得鎖階段；

2）釋放鎖階段。

一般2PL被稱為是悲觀並發控制。

與之相對的是樂觀並發控制OCC（ Optimistic Concurrency Control）。OCC假設事務會成功，開始事務時該讀讀，該寫寫，不加鎖。只有到提交時做一下驗證，驗證這個事務是不是能夠成功提交。 OCC分為三階段：

1）Read Phase, 對於讀，放到Read Set，對於寫，把寫記到臨時副本，放到Write Set。因為寫是寫到臨時區的，屬於未提交結果，其它事務讀不到（這點是和MVCC的重要區別）；

2）Validation Phase，重掃Read Set，Write Set，檢驗數據是否滿足Isolation Level，如果滿足則Commit，否則Abort；

3）WritePhase，或者叫做Commit Phase，把臨時副本區的數據更新到資料庫中，完成事務提交。

MVCC（Multiversion Concurrency Control）是另一種並發控制演算法。MVCC為每條記錄維護多個快照（Snapshot），通過起止兩個時間戳（Begin Timestamp / End Timestamp）維護副本的可見性。讀寫進行的不同操作如下：

Update，創建一個新的版本（Version）；

Delete，更新End Timestamp。

Read，通過起止時間戳判定記錄是否對當前事務可見（OCC讀不到未提交的記錄，所以不需要做這個判斷）。

這樣，通過Snapshot，實現了讀寫互不阻塞。但為了實現Serializable，對讀寫規則還是要進行一定的限制。MVCC通過不同的方法實現。有基於鎖定的，MV-2PL，如MySQL。有基於時間排序（Time Ordering）的，叫MV-TO，如PostgreSQL。其實準確來說，PG的實現叫SSI（Serializable Snapshot Isolation），不算MV-TO。也有像OCC那樣基於樂觀演算法的，MV-OCC，即讀寫時不做驗證，延遲到提交時驗證。

效率上，2PL在鎖爭用比較大的情形下較好(維護鎖開銷小於回滾開銷)，OCC在衝突比較少的情形下比較高效(維護鎖開銷大於回滾開銷)，MVCC對不同類型Workload更有很好的適應性，許多RDBMS也都用MVCC，如Oracle，PostgreSQL，MySQL。還有一個效率問題，隨著現在CPU核心數越來越多，考慮並發控制演算法往往需要考慮它的多核擴展性好不好。由於多數MVCC，OCC演算法都需要時間戳分配，時間戳通常對全局變數進行CAS（Compare And Swap）操作來計算，當核心數變大時，CAS的爭用也變大了。在許多時候，2PL反倒是多核擴展性最好的演算法。

另外，現在的許多並發控制方法經常混合了多種演算法。先有人提出了A，後有人提出了B，再後來就有人提出了A+B，那麼A+B應該是叫A呢還是叫B呢？就像上面提到的MV-2PL，MV-TO，MV-OCC。

-------------------------------------

關於並發控制演算法怎麼分類，有不同的意見。

《Transactional Information Systems》對並發控制演算法的分類。把多版本相對於單版本，作為另一個維度看。多版本可以應用在任一演算法上，形成MV-SGT，MV-TO，MV-2PL，MV-OCC等。

而CMU 15-722課程里，把並發控制分為兩類，2PL和TO，OCC和MVCC都歸為TO。

-------------------------------------

感謝 @Ed Huang 糾正關於2PL應用場景的錯誤

如果我們假設CMU15-721可以代表學術界, 又假設學術界定義了名詞概念的話,

那麼最常有的混亂是由於OCC不僅指樂觀並發控制思想, 還指特定的演算法引起的.

悲觀並發控制思想 v.s. 樂觀並發控制思想(OCC)

悲觀控制唯一的實現是2PL

樂觀控制唯一的實現是Timestamps

2PL和Timestamps是唯二解決事務並發的模型.

Timestamps的實現又分為

Basic T/O, 遵循Thomas Write Rule, 每個transaction不用到commit階段就立馬寫進數據結構, 依靠read timestamps和write timestamps檢查保證操作序列化.

OCC演算法(對, 沒錯這也叫OCC, 但這叫OCC演算法), 所有的操作都在本地完成. 比如, 我Get A, 這不阻塞, A就複製到了本地, 之後所有對於A的操作都是在"private memory space"內, 直到commit的時候, 開始檢查衝突, 有正向驗證(validation), 也有反向驗證, 在一定的時間區間(epoch)內.

題外話: epoch思想還用於epoch GC, 例子BW-Tree. 在一個區間內標記為垃圾的資源, 在這個區間以及之前區間的所有線程都退出後, 就可以釋放掉, 不需要引用計數.

MVCC, 百家爭鳴. 在不同的isolation level也有不同的表現形式, 共享的思想是通過保存多個版本來解決衝突. 很多人認為這能解決讀寫衝突和寫讀衝突, 但這是在Snapshopt Isolation(SI)下的情況. SI會導致Write Skew Anomaly. 現有50個男生, 50個女生. 事務1: 如果男生數量跟女生相同, 趕走所有女生, 換成男生. 事務2: 如果男生數量和女生相同, 趕走所有男生, 換成女生. SI等級下, 結果是毛線都沒發生. 但如果我們嚴格遵守序列化操作, 最後要麼只有100個男生, 要麼只有100個女生.

所以MVCC是樂觀並發控制思想的一種體現, 但不是具體嚴格的演算法. MVCC在資料庫系統中必須根據不同的isolation level搭配一些別的CC演算法, 比如MySQL InnoDB的MVCC+2PL. 據我不嚴格判斷, MyRocks的默認實現也是這樣的.

還有lock和latch也是經常被誤會的. lock保護的是transaction, latch保護的是數據結構. Timestamps是lock-free的, 但實現這個目標的數據結構不一定是latch-free的. 2PL不是lock-free的, 但RocksDB的memtable是latch-free的(嗎?).

幫樓上郭靖的答案補篇論文

http://www.vldb.org/pvldb/vol8/p209-yu.pdf

裡面講述了各種事務並發控制的方式和各種場景下的性能。