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

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

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


(資料圖)

本系列主要分為兩大部分,論文解讀和代碼串講,每一部分會(huì)根據(jù)情況拆成幾篇。本篇,是論文解讀(一),主要講論文概述以及如何使用鏈表巧妙的存儲(chǔ)了多版本、控制了可見性。論文解析(二),會(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)

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

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

通過謂詞樹(PT)來判事務(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ù),如果某一行沒有舊數(shù)據(jù),對(duì)應(yīng)的位置就是?null。

之后,我們之后會(huì)一直使用上圖例子來輔助理解原理。這是一個(gè) Sally 持續(xù)向別人轉(zhuǎn)賬的例子。開局時(shí)(T0)每人十塊錢,然后 Sally 每次轉(zhuǎn)給別人 1 塊錢,一共轉(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

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

版本管理

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

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

startTime-stamp:一個(gè)自增的時(shí)間戳(從 0 開始自增),上圖中的 T4, T6, T7。

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

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

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

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

在事務(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)。

版本可見性

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

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

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

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

v.pred.TS < T.startTime:通過事務(wù)起始時(shí)間戳,訪問已經(jīng)提交的老版本數(shù)據(jù)。

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

然后來看不同事務(wù)訪問 Sally 的 Bal(Balance)數(shù)據(jù)的可見性:

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

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

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

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

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

T0 ~ T3:見到的值是 10

T3 ~ T5:見到的值是 9

T5 ~ ∞:見到的值是 8

其中,Ty (事務(wù) ID)相對(duì)起始時(shí)間戳來說就是無窮大,這就是我們?cè)谇耙恍」?jié)提到的將 uint64 對(duì)半劈開的妙用之處:

起始和提交時(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)來實(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

題圖故事

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

標(biāo)簽:

相關(guān)閱讀

精彩推薦

相關(guān)詞

推薦閱讀