MemGraph 背后论文《基于内存和MVCC 的高速可串行化》详细解析...
共 3671字，需浏览 8分钟
·
2023-05-26 03:42
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
正在进行第三笔：
- 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 指向链表进行访问，直到满足以下条件后停止：
// pred 表示下一个链节
// TS 表示对应链节的关联时间戳
// 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 的值），所以会在后继节点满足：
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 不可见。
可以看出，上述链表把时间轴分成了四段：
临时值（7）----Ty--(8)---T5---(9)---T3---(10)---T0
比较事务起始时间戳和后继链节时间戳，是为条件 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
题图故事
本篇文章来自我的小报童专栏，第二篇解读也已经在专栏更新，欢迎喜欢我文章的朋友订阅支持，激励我产出更多优质文章。订阅方式见👉这里，会保证每周不低于两篇更新。
也可以点击”阅读原文“直接查看专栏免费文章。