首頁 > 行業(yè) > 正文

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

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

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


(資料圖)

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

概述

從論文題目可以看出,本論文旨在實現(xiàn)一種針對內存型數(shù)據(jù)庫的、基于多版本(MVCC)實現(xiàn)的、支持可串行化隔離級別的高性能數(shù)據(jù)結構。其基本思想是:

使用列存

復用 Undo Buffer 數(shù)據(jù)結構

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

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

通過謂詞樹(PT)來判事務讀集合(Read Set)是否被更改

與一般的多版本不同的是,本論文會在原地更新數(shù)據(jù),然后將舊版本數(shù)據(jù)“壓”到鏈表中去,使用 “壓”是因為鏈表采用頭插法:表頭一側數(shù)據(jù)較新、表尾一側數(shù)據(jù)較舊。所有數(shù)據(jù)的鏈表頭由一個叫?VersionVector的數(shù)據(jù)結構維護,如果某一行沒有舊數(shù)據(jù),對應的位置就是?null。

之后,我們之后會一直使用上圖例子來輔助理解原理。這是一個 Sally 持續(xù)向別人轉賬的例子。開局時(T0)每人十塊錢,然后 Sally 每次轉給別人 1 塊錢,一共轉了三筆,當前時刻前兩筆已經(jīng)完成:

Sally → Wendy,提交時間戳為 T3

Sally → Henry,提交時間戳為 T5

正在進行第三筆:

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

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

版本管理

每個事務在進入系統(tǒng)時會獲取兩個時間戳(uint64):

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

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

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

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

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

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

在事務提交時,會獲取另外一個時間戳:commitTime-stamp,該時間戳和 startTime-stamp 共用一個自增計數(shù)器。

在事務進行中,所有的 Undo Buffer 中的舊值會被打上 transactionID 的時間戳(圖中第三筆轉賬:Ty);在事務提交時,會統(tǒng)一替換為 commitTime-stamp (圖中前兩筆轉賬:T3 和 T5)。

版本可見性

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

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

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

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

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

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

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

事務 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 不可見。

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

比較事務起始時間戳和后繼鏈節(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 。

下篇,我們會詳細講如何基于上述數(shù)據(jù)結構來實現(xiàn)可串行化隔離級別的。

參考資料

[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

題圖故事

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

標簽:

相關閱讀

精彩推薦

相關詞

推薦閱讀