MemGraph 背后論文《基于內存和MVCC 的高速可串行化》詳細解析（一）

2023-05-24 05:49:10來源：嗶哩嗶哩

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 持續向別人轉賬的例子。開局時（T0）每人十塊錢，然后 Sally 每次轉給別人 1 塊錢，一共轉了三筆，當前時刻前兩筆已經完成：

Sally → Wendy，提交時間戳為 T3

Sally → Henry，提交時間戳為 T5

正在進行第三筆：

3. Sally → Mike，事務 ID 是 Ty，起始時間戳為 T6

中間穿插著兩次全表掃描（求所有賬戶總額）事務 Tx 和 Tz，起始時間戳分別為 T4 和 T7 ，都已經開始，但還沒結束。

版本管理

每個事務在進入系統時會獲取兩個時間戳（uint64）：

transactionID：事務 ID 也是一個時間戳（從 2^63 開始自增），上圖中的 Tx, Ty, Tz。

startTime-stamp：一個自增的時間戳（從 0 開始自增），上圖中的 T4, T6, T7。

如前所述，所有的更新是原地的（in-place），但會在 undo buffer 中保存舊值。舊版本的數據有兩個作用：

before-image value，作為事務 undo log 的一部分。

作為該字段多版本的一個舊值。

對于快照隔離和可串行化隔離級別來說，原地更新的值，是不為其他事務所見的，下一小節我們會講如何控制可見性。

在事務提交時，會獲取另外一個時間戳：commitTime-stamp，該時間戳和 startTime-stamp 共用一個自增計數器。

在事務進行中，所有的 Undo Buffer 中的舊值會被打上 transactionID 的時間戳（圖中第三筆轉賬：Ty）；在事務提交時，會統一替換為 commitTime-stamp （圖中前兩筆轉賬：T3 和 T5）。

版本可見性

某個事務在訪問一個字段的值時，會首先進行原地訪問，然后沿著該值對應的 VersionVector 指向鏈表進行訪問，直到滿足以下條件后停止：

下面我們逐一看下三個子條件各自適用情況：

v.pred == null：當該值沒有多版本，或者鏈表到頭時成立。

v.pred.TS == T：正在進行的事務訪問自己更新的數據。

v.pred.TS < T.startTime：通過事務起始時間戳，訪問已經提交的老版本數據。

上述條件比較抽象，我們結合例子來看。Sally 的多次轉賬會形成以下鏈表：

然后來看不同事務訪問 Sally 的 Bal（Balance）數據的可見性：

事務 Ty：（Ty 是一個 > 2^63 的值），所以會在后繼節點滿足：pred == (Ty, Bal, 8)（條件2，Ty == Ty）時停住，此時訪問到的值為 7 ，也即事務 Ty 更新到的值。

事務 Tx：起始時間戳為 T4，所以會在后繼節點滿足?pred == (T3, Bal, 10)（條件3，T3 < T4）時停住，此時訪問到的 Sally 賬戶的值為 9，也即此時剛轉過一次賬，即提交時間戳為 T3 的那次轉賬。

事務 Tz：起始時間戳為 T7，所以會在后繼節點滿足?pred == (T5, Bal, 9)（條件 3，T5 < T7）時停住，此時訪問到 Sally 的賬戶值為 8，也即此時完成了兩次轉賬，第三次轉賬尚未完成，對 Tz 不可見。

可以看出，上述鏈表把時間軸分成了四段：

比較事務起始時間戳和后繼鏈節時間戳，是為條件 1：

T0 ~ T3：見到的值是 10

T3 ~ T5：見到的值是 9

T5 ~ ∞：見到的值是 8

其中，Ty （事務 ID）相對起始時間戳來說就是無窮大，這就是我們在前一小節提到的將 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

題圖故事

本篇文章來自我的小報童專欄，第二篇解讀也已經在專欄更新，歡迎喜歡我文章的朋友訂閱支持，激勵我產出更多優質文章。訂閱方式見https://xiaobot.net/p/system-thinking，會保證每周不低于兩篇更新。

標簽：

MemGraph 背后論文《基于內存和MVCC 的高速可串行化》詳細解析（一）

概述

版本管理

版本可見性

參考資料

相關閱讀

精彩推薦

閱讀排行

相關詞

推薦閱讀