MVCC & SI: 协议

98F9A3FE-E697-417F-8A84-0987DDEEEFF0

MVCC 是现代商业数据库非常常用的机制，MySQL InnoDB, Postgres, WiredTiger 都使用了 MVCC，适用范围可见上图，但是 MVCC 本身也引入了问题：

  1. MVCC 如何实现协议？
  2. 在存储、GC 等方面，MVCC 需要一些 trade off

Snapshot Isolation 是个更令人脑壳痛的东西，你会发现很多 DB 实现的就是 SI，但是这些 DB 本身其实没有实现 Generalized SQL definition 里面的 SI，实现的可能只是 monotonic atomic view。

这两个事情在一起比较让人头晕，下面会讲 MVTS，MV2PL 和 SI。

这里仅仅介绍协议，暂时不介绍 MVCC 的存储和 GC，这几个坑还挺大的。

MVCC: 协议

MVCC 的目的是：

Writers do not block readers. Readers do not block writers.

（当然，实际上我感觉还是取决于实现。TS 协议其实都可以 block 呢）

MVCC 需要大量引入 timestamp 的概念，reader 以 timestamp 来读，并决定自己能读到什么。

在逻辑视图上，MVCC record 需要引入额外的记录：

  1. begin
  2. end

这两个表示对象的生命周期，也决定了读者来读什么。写入的时候，写者会创建一条记录，给 end 标记上自己的对应的 ts。读者根据自己的 ts 来决定“应该读到什么”。

实际上 MVCC 和 SI 可能关系比较大，经常用于实现 SI，但是 ts 用来决定读并不代表只能 SI。它可以实现 RC 和 Serializable。但同时，这个协议也会影响具体实现后隔离的表现。

MVCC 有下面一些 trade-off:

  • Concurrency Control Protocol
  • Version Storage
  • Garbage Collection
  • Index Management
  • Foreign Key

MVTS

MVTS 协议源于 1979 年，是最早的 MVCC 协议。

TS 协议中，每个事务在开始的时候都会定下一个 commit-ts. 记作 $TS(T_i)$, 同时, 以 commit-ts 为标准，来限制 Tuple 读写，如果不能满足需求，就会被 abort. 同时，tuple 有 read-ts 和 write-ts, 表示单条记录读写。

6EC5DFC5-AC8C-4565-A9DA-59AA31CF6BD3

MVTS 中：

end-ts 相当于之前的 write-ts, read-ts 相当于这个版本对应的最大 read-ts

写入

一个事务写入时，如果：

  1. 另一个事务在更新这条记录，有一个最新的正在写入的版本
  2. 已存在的最高版本的 record begin_ts 大于自身
  3. 已存在的最高版本的 record begin_ts 小于自身，但 read-ts 大于自身

它都会 abort。

事务写入 tuple 的时候，会在上述的 txn-id 字段设置成自己，相当于 grab 写锁。

如果 tuple Q 最高版本 k 满足 TS(T) == W-TS(Q_k), 那么说明是本事务写入，可以放心写。

如果上述条件都不满足，它会创建一个新的版本，把之前的 end-ts 设置成 TS(T)，然后创建一条新的纪录，把 end-ts 设置成无限，begin-ts 设置成 TS(T).

读取

  1. $T_i$ 读取时，数据库找到 [begin-ts, end-ts] 包含 $TS(T_i)$ 的记录，即事务读到它之前最近的请求
  2. 如果上面有 T_id 的写锁，那么abort或者 wait

Relaxed

数据库系统实现里面模型比上面的 relax 一些，读取的时候，如果大于最大的 ts, 那直接读最大的记录。这样读永远不会 abort, 感觉这样实现比较有问题= =

缺点

  1. 仍然需要一定的更改，才能让 MVTS 是 Recoverable 的
  2. 很多时候读取要更新 ts, 可能会放大磁盘写

MV2PL

6993165C-819A-4BA7-8B63-DE5F8AFFC552

TS 的时间戳来自事务开始时分配的 commit-ts, MVTS 沿用了这个 ts。2PL 的 Commit 时间被当成是全局唯一的时间，准确说是释放第一个锁锁的时间。在 Rigirous 2PL 协议下，可以当成它们等效。

MV2PL 维护了一个全局单调递增的 ts-counter。事务 Commit 的时候，会把这个 counter 递增，同时赋予自己这个 counter。实际上，MV2PL 使用的不是 timestamp，而是“事务提交的 counter”。

读取: 只读事务

只读事务在读取时，对于只读事务，事务 TS = ts-counter, 然后用这个 ts-counter 去读。

已知：事务获取 ts-counter 时，之前所有的事务都已经提交。

即：读取的时候，没有 blocking, 没有 abort。事务记录是完整的。

读写事务

读写事务读取时，获得 S-Lock, 读取最新版本，写入时，先对现在的最新，写入后的次新上一个 X-Lock，然后再写一个新版本。然后设置新版本的 end-ts 为无穷，当 Commit 阶段时，事务获得一个 CommitTS, 然后把自己的 ts 对应成这个 commit-ts, 然后设置自己修改所有内容的begin-ts 为自身，设置次新版本 end-ts 为自身，

实际上，在这里事务的外部时间顺序被削弱了，read 可能可以慢于写。但是时间和事务的 order 被不同的 ts-counter 給 fence 开了。

16D1F158-2844-4A7E-9DAD-060F95C86CE6

在论文 Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems 中，对于这点提出了证明。

此外，MV2PL 冲突处理，有如下 comments:

The key difference among 2PL protocols is in how they handle deadlocks. Previous research has shown that the no-wait policy [9] is the most scalable deadlock prevention technique [48]. With this, the DBMS immediately aborts a transaction if it is unable to acquire a lock on a tuple (as opposed to waiting to see whether the lock is released). Since transactions never wait, the DBMS does not have to employ a background thread to detect and break deadlocks.

Snapshot Isolation

Snapshot Isolation 是一种特殊的并发控制方案，已在包括 Oracle，PostgreSQL 和SQL Server在内的商业和开源系统中得到广泛认可。

实现上，SI 通常依赖 MVCC，但是 MVCC 却不止能实现 SI。

  1. 事务在开始的时候，拿到一个 Snapshot，就是开始时刻事务对应的一致性的视图。
  2. 事务在自己的 space 中进行修改。
  3. 事务 Commit 的时候，需要验证和别的事务是否有冲突
  4. 事务原子性的 Commit, 一旦 Commit ，要么对别的所有 Snapshot 不可见，要么一下子全部可见。

那么，采用多版本实现的时候，我们通常需要：

  1. $StartTS(T_i)$, is the time at which transaction $T_i$ started.
  2. The second timestamp, $CommitTS(T_i)$ is the time when the transaction $T_i$ requested validation.

事务读取时，不会看到其后的任何写。

注: MySQL 的 RR 下，有两种读，一种读一致性 Snapshot, 一种全局。实际上 SELECT + SELECT for Update 混用，实际表现会略显混乱.

对于更新事务而言，需要 Commit 之前，要 validate 自身是否是合理合法的。首先，需要了解的是，SI 已经有了 PL-2 的级别，能够防止 G0 G1. 在 SI 的情况下，加入实现的时候，有两个事务，更新了同一条记录，然后提交，可能会造成“某个事务的更新被丢失”，即 lost update。在一些满足 LWW, 即“最近写入为准”的系统中，这是可以的，但是这样可能会违反事务的一致性约束。所以也要避免它。

可能的情况有：

1
2
StartTS(Tj) ≤ StartTS(Ti) ≤ CommitTS(Tj), or
StartTS(Ti) ≤ StartTS(Tj) ≤ CommitTS(Ti).

有两种策略：

  1. first committer wins
  2. first updater wins

这些策略按照实现而定具体应该选用什么。

SSI

Postgres 实现了 SSI，这个和 Generalized SQL 那篇论文强相关。PG 靠防止 anti dependency 成环，abort 掉可能成环的事务，来实现了 SSI 的调度。同时做了对只读事务的优化。

Reference

  • An Empirical Evaluation of In-Memory Multi-Version Concurrency Control
  • Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems
  • https://zhuanlan.zhihu.com/p/54979396
  • 数据库系统概念，第七版。