TiKV 的 MVCC（Multi-Version Concurrency Control）機制

01-28

並發控制簡介

事務隔離在資料庫系統中有著非常重要的作用，因為對於用戶來說資料庫必須提供這樣一個「假象」：當前只有這麼一個用戶連接到了資料庫中，這樣可以減輕應用層的開發難度。但是，對於資料庫系統來說，因為同一時間可能會存在很多用戶連接，那麼許多並發問題，比如數據競爭（data race），就必須解決。在這樣的背景下，資料庫管理系統（簡稱 DBMS）就必須保證並發操作產生的結果是安全的，通過可串列化（serializability）來保證。

雖然 Serilizability 是一個非常棒的概念，但是很難能夠有效的實現。一個經典的方法就是使用一種兩段鎖（2PL）。通過 2PL，DBMS 可以維護讀寫鎖來保證可能產生衝突的事務按照一個良好的次序（well-defined) 執行，這樣就可以保證 Serializability。但是，這種通過鎖的方式也有一些缺點：

讀鎖和寫鎖會相互阻滯（block）。
大部分事務都是只讀（read-only）的，所以從事務序列（transaction-ordering）的角度來看是無害的。如果使用基於鎖的隔離機制，而且如果有一段很長的讀事務的話，在這段時間內這個對象就無法被改寫，後面的事務就會被阻塞直到這個事務完成。這種機制對於並發性能來說影響很大。

多版本並發控制（Multi-Version Concurrency Control, 以下簡稱 MVCC）以一種優雅的方式來解決這個問題。在 MVCC 中，每當想要更改或者刪除某個數據對象時，DBMS 不會在原地去刪除或這修改這個已有的數據對象本身，而是創建一個該數據對象的新的版本，這樣的話同時並發的讀取操作仍舊可以讀取老版本的數據，而寫操作就可以同時進行。這個模式的好處在於，可以讓讀取操作不再阻塞，事實上根本就不需要鎖。這是一種非常誘人的特型，以至於在很多主流的資料庫中都採用了 MVCC 的實現，比如說 PostgreSQL，Oracle，Microsoft SQL Server 等。

TiKV 中的 MVCC

讓我們深入到 TiKV 中的 MVCC，了解 MVCC 在 TiKV 中是如何實現的。

Timestamp Oracle(TSO)

因為TiKV 是一個分散式的儲存系統，它需要一個全球性的授時服務，下文都稱作 TSO（Timestamp Oracle），來分配一個單調遞增的時間戳。這樣的功能在 TiKV 中是由 PD 提供的，在 Google 的 Spanner 中是由多個原子鐘和 GPS 來提供的。

Storage

從源碼結構上來看，想要深入理解 TiKV 中的 MVCC 部分，src/storage 是一個非常好的入手點。 Storage 是實際上接受外部命令的結構體。

start 這個函數很好的解釋了一個 storage 是怎麼跑起來的。

Engine

首先是 Engine。 Engine 是一個描述了在儲存系統中接入的的實際上的資料庫的介面，raftkv 和 Enginerocksdb 分別實現了這個介面。

StorageHandle

StorageHanle 是處理從sench 接受到指令，通過 mio 來處理 IO。

接下來在Storage中實現了async_get 和async_batch_get等非同步函數，這些函數中將對應的指令送到通道中，然後被調度器（scheduler）接收到並非同步執行。

Ok，了解完Storage 結構體是如何實現的之後，我們終於可以接觸到在Scheduler 被調用的 MVCC 層了。

當 storage 接收到從客戶端來的指令後會將其傳送到調度器中。然後調度器執行相應的過程或者調用相應的非同步函數。在調度器中有兩種操作類型，讀和寫。讀操作在 MvccReader 中實現，這一部分很容易理解，暫且不表。寫操作的部分是MVCC的核心。

MVCC

Ok，兩段提交（2-Phase Commit，2PC）是在 MVCC 中實現的，整個 TiKV 事務模型的核心。在一段事務中，由兩個階段組成。

Prewrite

選擇一個 row 作為 primary row，餘下的作為 secondary row。

對primary row 上鎖. 在上鎖之前，會檢查是否有其他同步的鎖已經上到了這個 row 上或者是是否經有在 startTS 之後的提交操作。這兩種情況都會導致衝突，一旦都衝突發生，就會回滾（rollback）。

對於 secondary row 重複以上操作。

Commit

Rollback 在Prewrite 過程中出現衝突的話就會被調用。

Garbage Collector

很容易發現，如果沒有垃圾收集器（Gabage Collector）來移除無效的版本的話，資料庫中就會存有越來越多的 MVCC 版本。但是我們又不能僅僅移除某個 safe point 之前的所有版本。因為對於某個 key 來說，有可能只存在一個版本，那麼這個版本就必須被保存下來。在TiKV中，如果在 safe point 前存在Put 或者Delete，那麼說明之後所有的 writes 都是可以被移除的，不然的話只有Delete，Rollback和Lock 會被刪除。

TiKV-Ctl for MVCC

在開發和 debug 的過程中，我們發現查詢 MVCC 的版本信息是一件非常頻繁並且重要的操作。因此我們開發了新的工具來查詢 MVCC 信息。TiKV 將 Key-Value，Locks 和Writes 分別儲存在CF_DEFAULT，CF_LOCK，CF_WRITE中。它們以這樣的格式進行編碼：

Details can be found here.

因為所有的 MVCC 信息在 Rocksdb 中都是儲存在 CF Key-Value 中，所以想要查詢一個 Key 的版本信息，我們只需要將這些信息以不同的方式編碼，隨後在對應的 CF 中查詢即可。CF Key-Values 的表示形式。