数据库内核杂谈 (十二)：事务、隔离、并发（3）

之前的文章，我们分别介绍了锁和时间戳机制来管理并发控制，这篇文章我们将介绍最被广泛使用的方法——多版本并发控制 Multi-Version Concurrency Control (MVCC)。

为什么多版本并发控制更受欢迎呢？因为锁和时间戳机制都是通过阻塞或者回滚冲突的事务来确保事务的有序性。比如，一个读操作可能被迫回滚，因为它要读取的数据已经被另一个更新的事务修改了。但是，如果我们把每个数据的所有历史版本都记录下来，就可以避免上述这种情况发生。这也正是多版本控制的由来：对于每个数据 Q，每次写操作 write(Q)都会给 Q 建立一个新版本；而对于读操作 read(Q)，会根据事务的先后关系选择一个正确的版本去读取，来保证事务的有序性。多版本控制能够很好地解决这类读写冲突，尤其是长时间的读操作饿死写操作问题。

插一个能够提升格调的小知识，MVCC 最早出现于 1978 年 Dr. Reed 的博士毕业论文“ Concurrency Control in Distributed Database Systems ”中( https://en.wikipedia.org/wiki/David_P._Reed)，有兴趣的同学可以去看一下。

下面，我们介绍两种多版本并发控制的实现：多版本时间戳和多版本两阶段加锁。

多版本时间戳(Multi-Version Timestamp Ordering)

把时间戳和多版本控制结合就形成了多版本时间戳机制。对于每个事务 Ti，系统都会设置相应的事务时间 TS(Ti)。对于每个数据单元 Q，系统会保存一系列的版本数据 Q1，Q2，Q3，… Qn。其中，每个版本 Qx 保存以下信息：

1. 当前版本的数据值

2. W-TS(Qx): 当 Qx 被某个事务 Ti 创建的时间戳，即 TS(Ti)

3. R-TS(Qx): 由于一个版本的数据可以被多个事务读取，这里存储的是最大的事务时间戳：最近一次被某个事务 Tj 读取成功的时间戳，即 TS(Tj)

当一个事务 Tx 创建了数据 Q 版本 Qk，Qk 会保存 Tx 所写入的数据值，同时，系统会把 W-TS(Qk)和 R-TS(Qk)都初始为 TS(Tx)；当有另一个事务 Ty 并且 TS(Ty) > TS(Tx)读取 Qk，系统会更新 R-TS(Qk)至 TS(Ty)。

现在介绍详细的操作机制：给定当前事务 Ti 对数据 Q 发起了一个读操作 read(Q)或者写操作 write(Q)。并假定，版本 Qk 是 Q 的所有版本中持有最大的但小于或等于 TS(Ti)的 W-TS 的时间戳。则：

1. 如果 Ti 是读操作，则读取成功，返回 Qk 中的值给 Ti。

2. 如果 Ti 是写操作，则需要判断，如果 TS(Ti) < R-TS(Qx)，即说明有一个更新的事务已经读取了数据，因此系统判定更新失败，回滚 Ti。如果 TS(Ti) = W-TS(Qx)，系统可以直接将 Ti 的值覆盖 Qk 的原值；如果 TS(Ti) > R-TS(Qx)，则创建一个新的版本 Q。

规则一很容易理解，一个事务可以读取到在它看来最新的数据。规则二则保证了一个事务被需要被撤销，如果已经有更新的事务读取了某个版本。

多版本时间戳机制的一大好处在于，一个读取数据的事务永远不会失败也不需要等待。在一个读多写少的场景下，相比于先前介绍的两种机制，会有很好的性能提升。

当然，它也是有缺点的。首先，就是在读取操作的事务中，也需要更新相应的 R-TS(Qk)，并且读取数据，这就导致可能产生两次磁盘操作，而非只读一次。另外，当写操作发生冲突时，它会要求回滚失败的事务，相比起等待，回滚操作可能更昂贵一些。下面介绍的另一种的实现可以解决这个问题。

多版本两阶段加锁(Multi-Version Two-Phase Locking)

多版本两阶段加锁机制，相比于上文介绍的多版本时间戳机制，是要集多版本控制和两阶段加锁之所长。它会区分对待只读操作的事务和有更新操作的事务。

有更新数据的事务会遵守两阶段加锁的规则，即事务需要持有所有的锁直至事务结束。这样，这些事务就能够保证有序性(在介绍 两阶段加锁的时候已经讲解过)。这样做的好处在于不同的写事务可以等待并且按照顺序依次完成而不需要回滚后重试。对于只读操作，和上文介绍的多版本时间戳机制一样。不同的是，在多版本两阶段加锁中，事务的时间不再是时间戳，而是表现相对时序的事务计数 TS-Counter。这个 TS-Counter 在每次事务提交时被更新。

对于只读操作的事务 Ti，数据库系统会把 TS(Ti)赋于当前 TS-Counter 的值，这样 Ti 读取数据就和上面介绍的多版本时间戳一样，会读取到最大的但小于或等于 TS(Ti)的 Q 版本的值。对于有更新操作的事务，如果要读取一个数据，首先，它会获取这个数据的共享锁，并且读取最新版本的数据。当事务需要写数据时，首先要获取数据的独占锁并且创建一个新的版本，并把版本的时间戳设置为无穷大，当这个事务要被提交时，把它锁创建的所有数据的新版本的时间戳设置为 TS-Counter+1，并且同时更新系统的 TS-Ccounter，也变为 TS-Counter+1。

多版本并发控制的缺陷

天下没有免费的午餐，我们来讨论它有什么缺陷。

1. 额外的存储和计算资源支出：首先，需要额外存储历史版本数据，并且在执行时，每个事务要快速定位到正确的版本，并且对于更新的事务，通常情况会复制一份或者创建一个新的版本来暂存数据，这些都是需要消耗存储和计算资源的。当然，数据库系统可以定期对老的数据版本进行清理来释放存储空间。

2. 多线程竞争时间戳分配：由于需要保证不同事务的有序性，因此需要有一个共享的时间戳实现来分配(无论是用时间，还是相对的 counter)，免不了不同的事务线程需要去竞争时间戳。

3. 有些情况下，会导致频繁的事务回滚：特别当事务之间存在大量竞争的时候，会造成频繁的事务回滚。

总结一下，我们介绍了两种具体的多版本并发控制的实现，多版本时间戳机制和多版本两阶段加锁，两者都保证了对于只读操作的事务，不会失败也不会被等待。区别在于写操作的事务，多版本时间戳机制会回滚“迟到”的写事务，而多版本两阶段加锁通过共享和独占锁来对多个写操作事务排序。同时，我们也讨论了一些多版本并发控制的缺陷。但是，瑕不掩瑜，它依然是最常见的并发控制实现。

回忆一下在第十期介绍的隔离级别：读未提交；读提交；可重复读和可有序化。那用多版本并发控制实现了哪个隔离级别呢？读者可能会觉得，应该是可有序化。但其实不然，它实现了一个新的隔离级别叫做 Snapshot Isolation(快照隔离)。

快照隔离(Snapshot Isolation)

快照隔离可以看作是对每一个事务，分配了一个独有的数据库快照。事务可以安心地读取这个快照中的数据而不需要去担心其他事务(因此只读事务是不会失败也不会被等待的)。同理，事务对数据的更新也首先暂存在这个独有的快照中，只有当事务提交的时候，这些更新才会试图被写回真正的数据库版本里。当一个事务准备提交时，它依然要确保没有其他事务更新了它所更新过的数据，否则，这个事务会被回滚。

那为什么说快照隔离是一个单独的隔离级别而不是可有序化呢？问题就在于，它提供了“太多”的隔离性(英语中用 too much！貌似更形象一些)。我想借用 CMU 数据库教授 Andy Pavlo 课里举过的一个非常贴切的例子，我们现在假设数据就是围棋的棋子，一部分是黑子，一部分是白子。现在同时有两个更新事务：T1: 把所有的白子变成黑子(写成 SQL 语句可以看作是这样的： UPDATE color = ‘black’ FROM marbles WHERE color = ‘white’ )。T2:把所有的黑子变成白子。执行这两个操作会怎么样呢？由于快照隔离(多版本并发控制)机制，这两个事务更新的数据不一样，因此都会视为成功。这就导致了最终，白子和黑子的颜色互换。见下图示例。

(Credit to https://15721.courses.cs.cmu.edu/spring2020/slides/03-mvcc1.pdf)

但是，根据可有序化的定义，要确保不同的事务最终是可以沿着时间线排成一溜执行，因此无论是 T1 先执行还是 T2 先执行，最终的颜色应该全是黑色或是白色，如下图所示。

(Credit to https://15721.courses.cs.cmu.edu/spring2020/slides/03-mvcc1.pdf)

上述的示例被称为 Write Skew Anomaly。因此，快照隔离是一个区别于可有序化的隔离级别，如果把它安插在我们介绍过的隔离级别，应该如下图所示。

(Credit to https://15721.courses.cs.cmu.edu/spring2020/slides/03-mvcc1.pdf)

大部分的数据库都支持快照隔离。Orcale 和 PostgreSQL 数据库其实是使用快照隔离机制来实现可有序化机制。因此，在极端小概率情况下，数据库的状态是有可能“非有序化”的。

总结

至此，事务、隔离和并发就全部介绍完毕。我们分别介绍了事务的 ACID 属性以及不同的隔离级别，再依次介绍了不同的并发控制实现，两阶段加锁，时间戳机制，和多版本并发控制。

对于单机的数据库系统就介绍得差不多了。下一篇文章，我们聊一个非常有意思的话题：假设给你一个单机的数据库系统实现，要求在这个基础上把它扩建成分布式数据库系统，你会怎么做？这个问题还有个小故事。很久很久以前，在原来公司参与系统设计面试的时候，候选人和我说，我原本准备的面试题另一个面试官已经问过了(当时我的内心是崩溃的…)。这是我临时想出来的面试题，留给大家做思考题。