MemGraph 背后論文《基于內(nèi)存和MVCC 的高速可串行化》詳細(xì)解析（一）

2023-05-24 05:49:10來(lái)源：嗶哩嗶哩  

Memgraph 是一個(gè)內(nèi)存型圖數(shù)據(jù)庫(kù)，使用 OpenCypher 作為查詢(xún)語(yǔ)言，主打小數(shù)據(jù)量、低延遲的圖場(chǎng)景。由于 Memgraph 是開(kāi)源的（repo 在這，使用 C++ 實(shí)現(xiàn)）我們可以一窺其實(shí)現(xiàn)。根據(jù)這行注釋[1]，我們可以看出，其內(nèi)存結(jié)構(gòu)實(shí)現(xiàn)靈感主要來(lái)自論文：Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems[2]。


(資料圖)

本系列主要分為兩大部分，論文解讀和代碼串講，每一部分會(huì)根據(jù)情況拆成幾篇。本篇，是論文解讀（一），主要講論文概述以及如何使用鏈表巧妙的存儲(chǔ)了多版本、控制了可見(jiàn)性。論文解析（二），會(huì)講如何實(shí)現(xiàn)可串行化以及回收多版本數(shù)據(jù)。

概述

從論文題目可以看出，本論文旨在實(shí)現(xiàn)一種針對(duì)內(nèi)存型數(shù)據(jù)庫(kù)的、基于多版本（MVCC）實(shí)現(xiàn)的、支持可串行化隔離級(jí)別的高性能數(shù)據(jù)結(jié)構(gòu)。其基本思想是：

使用列存

復(fù)用 Undo Buffer 數(shù)據(jù)結(jié)構(gòu)

使用雙向鏈表來(lái)串起數(shù)據(jù)的多版本

巧妙設(shè)計(jì)時(shí)間戳來(lái)實(shí)現(xiàn)數(shù)據(jù)的可見(jiàn)性

通過(guò)謂詞樹(shù)（PT）來(lái)判事務(wù)讀集合（Read Set）是否被更改

與一般的多版本不同的是，本論文會(huì)在原地更新數(shù)據(jù)，然后將舊版本數(shù)據(jù)“壓”到鏈表中去，使用 “壓”是因?yàn)殒湵聿捎妙^插法：表頭一側(cè)數(shù)據(jù)較新、表尾一側(cè)數(shù)據(jù)較舊。所有數(shù)據(jù)的鏈表頭由一個(gè)叫?VersionVector的數(shù)據(jù)結(jié)構(gòu)維護(hù)，如果某一行沒(méi)有舊數(shù)據(jù)，對(duì)應(yīng)的位置就是?null。

之后，我們之后會(huì)一直使用上圖例子來(lái)輔助理解原理。這是一個(gè) Sally 持續(xù)向別人轉(zhuǎn)賬的例子。開(kāi)局時(shí)（T0）每人十塊錢(qián)，然后 Sally 每次轉(zhuǎn)給別人 1 塊錢(qián)，一共轉(zhuǎn)了三筆，當(dāng)前時(shí)刻前兩筆已經(jīng)完成：

Sally → Wendy，提交時(shí)間戳為 T3

Sally → Henry，提交時(shí)間戳為 T5

正在進(jìn)行第三筆：

3. Sally → Mike，事務(wù) ID 是 Ty，起始時(shí)間戳為 T6

中間穿插著兩次全表掃描（求所有賬戶(hù)總額）事務(wù) Tx 和 Tz，起始時(shí)間戳分別為 T4 和 T7 ，都已經(jīng)開(kāi)始，但還沒(méi)結(jié)束。

版本管理

每個(gè)事務(wù)在進(jìn)入系統(tǒng)時(shí)會(huì)獲取兩個(gè)時(shí)間戳（uint64）：

transactionID：事務(wù) ID 也是一個(gè)時(shí)間戳（從 2^63 開(kāi)始自增），上圖中的 Tx, Ty, Tz。

startTime-stamp：一個(gè)自增的時(shí)間戳（從 0 開(kāi)始自增），上圖中的 T4, T6, T7。

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

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

作為該字段多版本的一個(gè)舊值。

對(duì)于快照隔離和可串行化隔離級(jí)別來(lái)說(shuō)，原地更新的值，是不為其他事務(wù)所見(jiàn)的，下一小節(jié)我們會(huì)講如何控制可見(jiàn)性。

在事務(wù)提交時(shí)，會(huì)獲取另外一個(gè)時(shí)間戳：commitTime-stamp，該時(shí)間戳和 startTime-stamp 共用一個(gè)自增計(jì)數(shù)器。

在事務(wù)進(jìn)行中，所有的 Undo Buffer 中的舊值會(huì)被打上 transactionID 的時(shí)間戳（圖中第三筆轉(zhuǎn)賬：Ty）；在事務(wù)提交時(shí)，會(huì)統(tǒng)一替換為 commitTime-stamp （圖中前兩筆轉(zhuǎn)賬：T3 和 T5）。

版本可見(jiàn)性

某個(gè)事務(wù)在訪(fǎng)問(wèn)一個(gè)字段的值時(shí)，會(huì)首先進(jìn)行原地訪(fǎng)問(wèn)，然后沿著該值對(duì)應(yīng)的 VersionVector 指向鏈表進(jìn)行訪(fǎng)問(wèn)，直到滿(mǎn)足以下條件后停止：

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

v.pred == null：當(dāng)該值沒(méi)有多版本，或者鏈表到頭時(shí)成立。

v.pred.TS == T：正在進(jìn)行的事務(wù)訪(fǎng)問(wèn)自己更新的數(shù)據(jù)。

v.pred.TS < T.startTime：通過(guò)事務(wù)起始時(shí)間戳，訪(fǎng)問(wèn)已經(jīng)提交的老版本數(shù)據(jù)。

上述條件比較抽象，我們結(jié)合例子來(lái)看。Sally 的多次轉(zhuǎn)賬會(huì)形成以下鏈表：

然后來(lái)看不同事務(wù)訪(fǎng)問(wèn) Sally 的 Bal（Balance）數(shù)據(jù)的可見(jiàn)性：

事務(wù) Ty：（Ty 是一個(gè) > 2^63 的值），所以會(huì)在后繼節(jié)點(diǎn)滿(mǎn)足：pred == (Ty, Bal, 8)（條件2，Ty == Ty）時(shí)停住，此時(shí)訪(fǎng)問(wèn)到的值為 7 ，也即事務(wù) Ty 更新到的值。

事務(wù) Tx：起始時(shí)間戳為 T4，所以會(huì)在后繼節(jié)點(diǎn)滿(mǎn)足?pred == (T3, Bal, 10)（條件3，T3 < T4）時(shí)停住，此時(shí)訪(fǎng)問(wèn)到的 Sally 賬戶(hù)的值為 9，也即此時(shí)剛轉(zhuǎn)過(guò)一次賬，即提交時(shí)間戳為 T3 的那次轉(zhuǎn)賬。

事務(wù) Tz：起始時(shí)間戳為 T7，所以會(huì)在后繼節(jié)點(diǎn)滿(mǎn)足?pred == (T5, Bal, 9)（條件 3，T5 < T7）時(shí)停住，此時(shí)訪(fǎng)問(wèn)到 Sally 的賬戶(hù)值為 8，也即此時(shí)完成了兩次轉(zhuǎn)賬，第三次轉(zhuǎn)賬尚未完成，對(duì) Tz 不可見(jiàn)。

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

比較事務(wù)起始時(shí)間戳和后繼鏈節(jié)時(shí)間戳，是為條件 1：

T0 ~ T3：見(jiàn)到的值是 10

T3 ~ T5：見(jiàn)到的值是 9

T5 ~ ∞：見(jiàn)到的值是 8

其中，Ty （事務(wù) ID）相對(duì)起始時(shí)間戳來(lái)說(shuō)就是無(wú)窮大，這就是我們?cè)谇耙恍」?jié)提到的將 uint64 對(duì)半劈開(kāi)的妙用之處：

起始和提交時(shí)間戳：0 ~ 2^63 -1

事務(wù)ID：2^63 ~ 2^64 - 1

另外，null 就相當(dāng)于 T0 ，是為條件 1 。

最后，為了讓事務(wù)能夠看到自己的更新，于是額外加了條件 2 。

下篇，我們會(huì)詳細(xì)講如何基于上述數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)可串行化隔離級(jí)別的。

參考資料

[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

題圖故事

本篇文章來(lái)自我的小報(bào)童專(zhuān)欄，第二篇解讀也已經(jīng)在專(zhuān)欄更新，歡迎喜歡我文章的朋友訂閱支持，激勵(lì)我產(chǎn)出更多優(yōu)質(zhì)文章。訂閱方式見(jiàn)https://xiaobot.net/p/system-thinking，會(huì)保證每周不低于兩篇更新。

標(biāo)簽：

相關(guān)閱讀

精彩推薦

相關(guān)詞

推薦閱讀