并發控制簡介
事務隔離在資料庫系統中有着非常重要的作用，因為對于使用者來說資料庫必須提供這樣一個“假象”：目前隻有這麼一個使用者連接配接到了資料庫中，這樣可以減輕應用層的開發難度。但是，對于資料庫系統來說，因為同一時間可能會存在很多使用者連接配接，那麼許多并發問題，比如資料競争（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 的表示形式。