關于 MVCC 的基礎

作為第一篇對 MVCC 的學習材料，以下內容翻譯自 Wikipedia。

1. 什么是MVCC

1.1 基礎概念

MVCC，Multi-Version Concurrency Control，多版本并發控制。MVCC 是一種并發控制的方法，一般在數據庫管理系統中，實現對數據庫的并發訪問；在編程語言中實現事務內存。

如果有人從數據庫中讀數據的同時，有另外的人寫入數據，有可能讀數據的人會看到『半寫』或者不一致的數據。有很多種方法來解決這個問題，叫做并發控制方法。最簡單的方法，通過加鎖，讓所有的讀者等待寫者工作完成，但是這樣效率會很差。MVCC 使用了一種不同的手段，每個連接到數據庫的讀者，在某個瞬間看到的是數據庫的一個快照，寫者寫操作造成的變化在寫操作完成之前（或者數據庫事務提交之前）對于其他的讀者來說是不可見的。

當一個 MVCC 數據庫需要更一個一條數據記錄的時候，它不會直接用新數據覆蓋舊數據，而是將舊數據標記為過時（obsolete）并在別處增加新版本的數據。這樣就會有存儲多個版本的數據，但是只有一個是最新的。這種方式允許讀者讀取在他讀之前已經存在的數據，即使這些在讀的過程中半路被別人修改、刪除了，也對先前正在讀的用戶沒有影響。這種多版本的方式避免了填充刪除操作在內存和磁盤存儲結構造成的空洞的開銷，但是需要系統周期性整理（sweep through）以真實刪除老的、過時的數據。對于面向文檔的數據庫（Document-oriented database，也即半結構化數據庫）來說，這種方式允許系統將整個文檔寫到磁盤的一塊連續區域上，當需要更新的時候，直接重寫一個版本，而不是對文檔的某些比特位、分片切除，或者維護一個鏈式的、非連續的數據庫結構。

MVCC 提供了時點（point in time）一致性視圖。MVCC 并發控制下的讀事務一般使用時間戳或者事務 ID去標記當前讀的數據庫的狀態（版本），讀取這個版本的數據。讀、寫事務相互隔離，不需要加鎖。讀寫并存的時候，寫操作會根據目前數據庫的狀態，創建一個新版本，并發的讀則依舊訪問舊版本的數據。

一句話講，MVCC就是用 同一份數據臨時保留多版本的方式 的方式，實現并發控制。

這里留意到 MVCC 關鍵的兩個點：

1. 在讀寫并發的過程中如何實現多版本；
2. 在讀寫并發之后，如何實現舊版本的刪除（畢竟很多時候只需要一份最新版的數據就夠了）；

1.2 實現

MVCC 使用時間戳（TS）、遞增的事務 ID（T）實現事務一致性。

MVCC 通過維護多版本數據，保證一個讀事務永遠不會被阻塞。對象 P 維護有多個版本，每個版本會有一個讀時間戳（Read TimeStamp, RTS）和 寫時間戳（Write TimeStamp, WTS），事務 Ti 讀對象 P 的最新版本，該版本早于事務 Ti 的讀時間戳 RTS(Ti)。

事務 Ti 要對 P 執行寫操作，如果有其他事務 Tk 同時對 P 操作，則 RTS(Ti）必須要早于 RTS(Tk)，即有 RTS(Ti) < RTS(Tk)，這樣對 Ti 對 P 的寫操作才能完成。一般地，如果其他事務擁有 P 的一個更早的讀時間戳的情況下，寫操作是不能完成的。打個比方就是在存儲前面有一道線，只有等你前面的人的完成了他們的事務，你的修改事務才可以提交完成。

重復說一下：每個對象 P 有一個時間戳 TS，如果事務 Ti 想要對 P 執行寫操作，（寫要先讀）事務的讀時間戳是 RTS(Ti)，如果有其他事務擁有一個比較早的時間戳，有 TS(P) < RTS(Ti)，這時事務 Ti 會退出并重新開始。否則，事務 Ti 創建一個 P 的新版本，并設置新版本 P 的時間戳，似的 TS = TS(Ti)。

MVCC 系統明顯的缺點是會存儲多個版本數據的冗余開銷。但同時，讀操作永不會被阻塞，這對那些以讀操作為主的數據庫來說非常重要。MVCC 實現了真的快照隔離（snapshot isolation），然后其他的并發控制方法要么是不完整的快照隔離方式，要么需要較高的性能損耗。

Wikipedia 中的內容有點繁瑣，簡單地，上面的描述，闡明了在同一數據版本下寫操作的限制，已經通過多版本實現快照隔離的優越性。

1.3 示例

Time	Object1	Object2
0	"Foo" by T0	"Bar" by T0
1	"Hello" by T1

Time=1的時候數據庫的狀態如上：

T0 寫 Object1 為 "Foo"，寫 Object2 為 "Bar"；之后 T1 寫 Object1 為 "Hello"，保留 Object2 為原始值。 Object1 的新值將取代 Time=0 時刻的舊值，并提供給 T1提交之后的發生的所有事務。Object1的版本號為0的舊數據會被 GC 掉。

如果有一個長事務 T2，在 T1之后對 Object1和 Object2 進行讀操作，同時并行地，有事務 T3 做更新：刪除 Object2、增加 Object3="Foo-Bar"，在 Time=2 數據的狀態如下所示：

Time	Object1	Object2	Object3
0	"Foo" by T0	"Bar" by T0
1	"Hello" by T1
2		(delete)by T3	"Foo-Bar" by T3

在 Time=2 Object2有一個新版本：標記刪除，同時增加了新對象 Object3 。T2 和 T3 并發執行，T2 看到的是數據在 Time=2 且 T3提交前的版本，這樣 T2讀到了 Object2="Bar""且Object1="Hello"。

以上就是 MVCC 在不加鎖的情況下實現的快照隔離的讀的原理。

1.4 歷史

最早于1978年，論文『Naming and Synchronization in a Decentralized Computer System』清晰地介紹了 MVCC，這是公認關于 MVCC 最早的工作。

在1981年，論文『Concurrency Control in Distributed Database System』介紹MVCC的一些細節。

目前支持 MVCC 的數據庫，包括 DB2、Oracle、Sybase、SQL Server、MySQL、PG 等所有主流數據庫，以及 HBase、Couchbase、Berkeley DB 等 NoSQL 數據庫

參考

1. Wikipedia: Multiversion concurrency control
2. List of databases using MVCC