之前的文章，我们分别介绍了锁和时间戳机制来管理并发控制，这篇文章我们将介绍最被广泛使用的方法——多版本并发控制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保存以下信息：

当前版本的数据值
W-TS(Qx): 当Qx被某个事务Ti创建的时间戳，即TS(Ti)
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的时间戳。则：

如果Ti是读操作，则读取成功，返回Qk中的值给Ti。
如果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。

多版本并发控制的缺陷

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

额外的存储和计算资源支出：首先，需要额外存储历史版本数据，并且在执行时，每个事务要快速定位到正确的版本，并且对于更新的事务，通常情况会复制一份或者创建一个新的版本来暂存数据，这些都是需要消耗存储和计算资源的。当然，数据库系统可以定期对老的数据版本进行清理来释放存储空间。
多线程竞争时间戳分配：由于需要保证不同事务的有序性，因此需要有一个共享的时间戳实现来分配(无论是用时间，还是相对的counter)，免不了不同的事务线程需要去竞争时间戳。
有些情况下，会导致频繁的事务回滚：特别当事务之间存在大量竞争的时候，会造成频繁的事务回滚。

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

回忆一下在第十期介绍的隔离级别：读未提交；读提交；可重复读和可有序化。那用多版本并发控制实现了哪个隔离级别呢？读者可能会觉得，应该是可有序化。但其实不然，它实现了一个新的隔离级别叫做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属性以及不同的隔离级别，再依次介绍了不同的并发控制实现，两阶段加锁，时间戳机制，和多版本并发控制。

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

创作场景

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