MemGraph 背后論文《基于內存和MVCC 的高速可串行化》詳細解析...
Memgraph 是一個內存型圖數據庫，使用 OpenCypher 作為查詢語言，主打小數據量、低延遲的圖場景。由于 Memgraph 是開源的（repo 在這，使用 C++ 實現）我們可以一窺其實現。根據這行注釋[1]，我們可以看出，其內存結構實現靈感主要來自論文：Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems[2]。
本系列主要分為兩大部分，論文解讀和代碼串講，每一部分會根據情況拆成幾篇。本篇，是論文解讀（一），主要講論文概述以及如何使用鏈表巧妙的存儲了多版本、控制了可見性。論文解析（二），會講如何實現可串行化以及回收多版本數據。
概述
從論文題目可以看出，本論文旨在實現一種針對內存型數據庫的、基于多版本（MVCC）實現的、支持可串行化隔離級別的高性能數據結構。其基本思想是：
- 使用列存
- 復用 Undo Buffer 數據結構
- 使用雙向鏈表來串起數據的多版本
- 巧妙設計時間戳來實現數據的可見性
- 通過謂詞樹（PT）來判事務讀集合（Read Set）是否被更改
與一般的多版本不同的是，本論文會在原地更新數據，然后將舊版本數據“壓”到鏈表中去，使用 “壓”是因為鏈表采用頭插法：表頭一側數據較新、表尾一側數據較舊。所有數據的鏈表頭由一個叫 VersionVector 的數據結構維護，如果某一行沒有舊數據，對應的位置就是 null。
之后，我們之后會一直使用上圖例子來輔助理解原理。這是一個 Sally 持續(xù)向別人轉賬的例子。開局時（T0）每人十塊錢，然后 Sally 每次轉給別人 1 塊錢，一共轉了三筆，當前時刻前兩筆已經完成：
- Sally → Wendy，提交時間戳為 T3
- Sally → Henry，提交時間戳為 T5
正在進行第三筆：
- Sally → Mike，事務 ID 是 Ty，起始時間戳為 T6
中間穿插著兩次全表掃描（求所有賬戶總額）事務 Tx 和 Tz，起始時間戳分別為 T4 和 T7 ，都已經開始，但還沒結束。
版本管理
每個事務在進入系統(tǒng)時會獲取兩個時間戳（uint64）：
- transactionID：事務 ID 也是一個時間戳（從 2^63 開始自增），上圖中的 Tx, Ty, Tz。
- startTime-stamp：一個自增的時間戳（從 0 開始自增），上圖中的 T4, T6, T7。
如前所述，所有的更新是原地的（in-place），但會在 undo buffer 中保存舊值。舊版本的數據有兩個作用：
- before-image value，作為事務 undo log 的一部分。
- 作為該字段多版本的一個舊值。
對于快照隔離和可串行化隔離級別來說，原地更新的值，是不為其他事務所見的，下一小節(jié)我們會講如何控制可見性。
在事務提交時，會獲取另外一個時間戳：commitTime-stamp，該時間戳和 startTime-stamp 共用一個自增計數器。
在事務進行中，所有的 Undo Buffer 中的舊值會被打上 transactionID 的時間戳（圖中第三筆轉賬：Ty）；在事務提交時，會統(tǒng)一替換為 commitTime-stamp （圖中前兩筆轉賬：T3 和 T5）。
版本可見性
某個事務在訪問一個字段的值時，會首先進行原地訪問，然后沿著該值對應的 VersionVector 指向鏈表進行訪問，直到滿足以下條件后停止：
//?pred?表示下一個鏈節(jié)
//?TS?表示對應鏈節(jié)的關聯時間戳
//?T?表示當前事務以及當前事務?ID
v.pred?==?null?||?v.pred.TS?==?T?||?v.pred.TS?<?T.startTime
下面我們逐一看下三個子條件各自適用情況：
-
v.pred == null：當該值沒有多版本，或者鏈表到頭時成立。 -
v.pred.TS == T：正在進行的事務訪問自己更新的數據。 -
v.pred.TS < T.startTime：通過事務起始時間戳，訪問已經提交的老版本數據。
上述條件比較抽象，我們結合例子來看。Sally 的多次轉賬會形成以下鏈表：
7(in-place)?-pred->?(Ty,?Bal,?8)?-pred->?(T5,?Bal,?9)?
????????????-pred->?(T3,?Bal,?10)?-pred->?null
然后來看不同事務訪問 Sally 的 Bal（Balance）數據的可見性：
-
事務 Ty：（Ty 是一個 > 2^63 的值），所以會在后繼節(jié)點滿足：
pred == (Ty, Bal, 8)（條件2，Ty == Ty）時停住，此時訪問到的值為 7 ，也即事務 Ty 更新到的值。 -
事務 Tx：起始時間戳為 T4，所以會在后繼節(jié)點滿足
pred == (T3, Bal, 10)（條件3，T3 < T4）時停住，此時訪問到的 Sally 賬戶的值為 9，也即此時剛轉過一次賬，即提交時間戳為 T3 的那次轉賬。 -
事務 Tz：起始時間戳為 T7，所以會在后繼節(jié)點滿足
pred == (T5, Bal, 9)（條件 3，T5 < T7）時停住，此時訪問到 Sally 的賬戶值為 8，也即此時完成了兩次轉賬，第三次轉賬尚未完成，對 Tz 不可見。
可以看出，上述鏈表把時間軸分成了四段：
臨時值（7）----Ty--(8)---T5---(9)---T3---(10)---T0
比較事務起始時間戳和后繼鏈節(jié)時間戳，是為條件 1：
- T0 ~ T3：見到的值是 10
- T3 ~ T5：見到的值是 9
- T5 ~ ∞：見到的值是 8
其中，Ty （事務 ID）相對起始時間戳來說就是無窮大，這就是我們在前一小節(jié)提到的將 uint64 對半劈開的妙用之處：
- 起始和提交時間戳：0 ~ 2^63 -1
- 事務ID：2^63 ~ 2^64 - 1
另外，null 就相當于 T0 ，是為條件 1 。
最后，為了讓事務能夠看到自己的更新，于是額外加了條件 2 。
下篇，我們會詳細講如何基于上述數據結構來實現可串行化隔離級別的。
參考資料
[1]MemGraph 參考論文注釋: https://github.com/memgraph/memgraph/blob/master/src/storage/v2/storage.hpp#L57
[2]Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems: https://db.in.tum.de/~muehlbau/papers/mvcc.pdf
題圖故事
本篇文章來自我的小報童專欄，第二篇解讀也已經在專欄更新，歡迎喜歡我文章的朋友訂閱支持，激勵我產出更多優(yōu)質文章。訂閱方式見??這里，會保證每周不低于兩篇更新。
也可以點擊”閱讀原文“直接查看專欄免費文章。