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

本篇文章选自数据库内核杂谈系列文章。

上一篇文章我们介绍了事务的 ACID 属性和数据库针对事务的不同隔离级别，本文我们将继续讨论实现事务的不同方法。

与教科书直接列出实现方法不同，本文将会由浅入深地介绍加锁实现机制和时间戳机制这两种不同实现方法的形成过程。

加锁实现机制(Lock-based protocols)

实现事务隔离的最简单方法就是在对任何数据进行读写时，都保证互斥性，即当一个事务在读写数据时，保证其他事务不能对数据进行修改。最常见的实现就是对数据进行加锁(lock)。

假设，我们对数据库设置了一把唯一的全局锁：任何事务需要执行时，都需要获取这把锁。那么，全局锁就保证了事务之间的有序性，从而保证了 ACID 属性。因此，从正确性角度考虑， 全局锁是可行的方法。但全局锁的缺点也显而易见，事务之间，即使读写的数据完全无关，也没有任何并行，这对性能的影响不言而喻。

有什么办法可以改进吗？一个方法是把锁的粒度变细，即仅对要读写的数据加锁而非全局锁。通过加锁来确保在同一时间，只有获得锁的事务可以对数据进行处理。

另一个方法是定义不同类型的锁。因为并不是所有的事务对数据都是写操作，如果两个事务同时对某一数据进行读操作，它们之间并不需要互斥。因此，我们可以通过定义不同类型的锁，以及它们之间的兼容程度来获得更细粒度的控制。

通常，我们定义两种类型的锁：1）共享锁(share-mode lock; S-lock)，即当事务获得了某个数据的共享锁，它仅能对该数据进行读操作，但不能写，共享锁有时候也被称为读锁。2）独占锁(exclusive-mode lock; X-lock)，即当事务获得了某个数据的独占锁，它可以对数据进行读和写操作，独占锁也常被叫做写锁。共享锁和独占锁的兼容模式如下：

仅 S-lock 之间互相兼容，只有当多个事务同时持有共享锁时才能同时对数据进行读操作。

定义了锁之后，在事务中对数据的操作必须持有相应的锁。但是问题又来了，什么时候该加锁，什么时候又该释放锁呢？是否应该在事务的开始就对所有的数据都加锁？(这显然不是一个高效的办法，甚至在事务开始的时候，我们可能并不知道要操作哪些数据)。

我们可以先从简单的情况来尝试，比如只在读取和修改数据的时候申请相对应的锁。如下图所示：

(图 1：T1)

(图 2: T2)

图 1 和图 2 分别显示了两个事务对账号 A 和 B 进行操作(假设 A 初始值是 100；B 是 200)，事务 T1 用了 X-lock，因为需要对数据进行修改， 而 T2 仅需要使用 S-lock，因为只是读取数据。乍看之下，好像没有问题。无论是 T1 先执行，还是 T2 先执行，T2 中 display(A+B)都会是 300。但是，如果 T1 和 T2 的执行顺序如下：

(图 3：T1 + T2）

这时候，T2 中的 display(A+B)的值就是 250，这是错误的数据。问题出在哪呢？T1 中释放对 B 的 X-lock 过早，使得 T2 获得了一个不正确的数值。既然原因是释放过早，那能不能通过延迟释放锁来解决这个问题。我们把 T1 和 T2 分别改写为 T3 和 T4(唯一的区别就是延缓了锁的释放到最后)，如下图所示

(图 4: T3 + T4)

经过验证，这种情况下，无论 T3 和 T4 如何交互，都不再会出现 display(A+B)等于 250 的错误了。把释放锁放在事务的最后是否就解决了所有问题呢？答案是否定的。它确实解决了数据读取不正确的问题，但也同时引入了新问题。

(图 5: T3 + T4)

T3 和 T4 分别获取了对 B 和对 A 的锁并且相互请求对 A 和对 B 的锁。相信大家都看出来了，这导致了死锁(dead lock)。这里就不具体介绍死锁的检查和破坏机制了(详情参见操作系统课)，你只需要知道，数据库系统是可以发现死锁的。解决方法也简单，选择其中一个参与的事务，回滚并放弃执行(如果一个不行，就两个)。相对于错误的数据，死锁显然是我们更愿意接受的，所谓两害取其轻。

我们引入了第一个加锁实现：两阶段加锁机制(Two-phase locking protocol)。它要求事务在加锁的过程中遵循下面两步：

1）获取锁阶段(growing phase)：在这个过程中，事务只能不断地获取新的锁，但不能释放锁。

2）释放锁阶段(shrinking phase)：在这个过程中，事务只能逐渐释放锁，并且无权再获取新的锁。

重要的事情说三遍：千万不要和两阶段提交(Two-phase commit (2PC))搞混；千万不要和两阶段提交搞混；千万不要和两阶段提交搞混。两阶段提交是针对分布式事务的概念，我会在以后的文章中详细讲。

上述的 T3 和 T4 就是遵循两阶段加锁机制，因此数据的正确性是可以保证的。但就像上述所说，两阶段加锁不能避免死锁，依然需要数据系统来检测并破坏死锁。并且，基本款的两阶段提交还会遇到连锁回滚(cascading rollback)。

(图 6: T5 + T6 + T7)

当 T5 执行到 bad thing happen 时，导致出错，那 T6 和 T7 都会需要被回滚。为了避免连锁回滚，我们可以引入两阶段提交的升级版：严格的两阶段加锁(strict two-phase locking protocol)。**除了需要遵循加锁和释放锁的两阶段外，它还规定，对于独占锁(X-lock)必须等到事务结束时才释放。这个规定避免了其他事务对未提交的数据进行读写操作，因此也避免了连锁回滚。另一个更严格的升级本叫做更严格的两阶段加锁(rigorous two-phase locking protocol)，**规定了所有获得的锁都得等到事务结束时才释放。

以上就是关于加锁的实现，如果我们总结一下，主要是介绍了这些内容：

1）引入共享锁(S-lock)和独占锁(X-lock)来获得对数据细粒度的控制；

2）引入两阶段加锁(Two-phase locking protocol)来保证数据的正确性；

3）两阶段加锁不能避免死锁，依然需要数据库系统来检查并破坏死锁，破坏死锁可以通过回滚相关的事务来进行；

4）两阶段加锁的两个升级版本：(更)严格的两阶段加锁(rigorous/strict two-phase locking)通过规定把释放锁等到事务结束来避免连锁回滚(cascading rollback)。

时间戳机制(Timestamp-based protocols)

加锁实现是通过比较哪个事务先获得锁来决定事务执行的顺序，以此来保证事务之间的有序性。那除了锁之外，有没有其他方式来衡量先后呢？大家可能都已经想到了，时间戳(Timestamp)。如果每个事务开启的时候，系统可以记录这个事务开启的时间 TS(Ti)，记为事务 Ti 的时间，通过比较不同事务的时间戳，我们就能给事务排序了。

如果两个事务的时间戳一模一样呢？其实，有个方法来避免这种情况，通过一个统一的事务管理机制来分发时间戳：每一个事务，不能自行根据执行时间来得到时间戳，而是必须调用一个方法(这个方法可以是由单个线程或者进程管理的)来获得。这个线程就能够保证事务之间的时间戳总有先后关系。

如果你还要考虑极限情况，例如某个方法性能特别高，可以在一个纳秒里面连续发送两个时间戳。面对这种极限情况，我们的解决方法是不必用真实的时间来表示时间戳，可以用数字计数(logical counter)来表示相对时间。管理线程只需维护一个计数，在分发计数的同时不断自增即可。

我们可以通过比较事务的时间戳来保证事务之间的有序性。假定 Ti 和 Tj 的时间戳分别为 TS(Ti)及 TS(Tj)。如果 TS(Ti)<TS(Tj)，数据库系统就需要保证无论如何调度实现，都和序列化执行 Ti 然后 Tj 一致。

如何实现呢？首先，我们引入两个概念：

1）W-timestamp(A): 记录对于数据 A，最近一次被某个事务修改的时间戳。

2）R-timestamp(A): 记录对于数据 A，最近一次被某个事务读取的时间戳。

一旦有一个更新的事务成功地对数据进行读取，相对应的读写时间戳就会被更新。

下面，我们给出用时间戳机制实现事务的定义：

对于事务 Ti 要读取数据 A read(A):

1. 如果 TS(Ti) < W-timestamp(A)，说明 A 被一个 TS 比 Ti 更大的事务改写过，但 Ti 只能读取比自身 TS 小的数据。因此 Ti 的读取请求会被拒绝，Ti 会被回滚。

2. 如果 TS(Ti) > W-timestamp(A)，说明 A 最近一次被修改小于 TS(Ti)，因此读取成功，并且，R-timestamp(A)被改写为 TS(Ti)。

对于事务 Ti 要修改数据 A write(A):

1. 如果 TS(Ti) < R-timestamp(A)，说明 A 已经被一个更大 TS 的事务读取了，Ti 对 A 的修改就没有意义了，因此 Ti 的修改请求会被拒绝，Ti 会被回滚。

2. 如果 TS(Ti) < W-timestamp(A)，说明 A 已经被一个更大 TS 的事务修改了，Ti 对 A 的修改也没有意义了，因此 Ti 的修改请求会被拒绝，Ti 会被回滚。

3. 其他情况下，Ti 的修改会被接受，同时 W-timestamp(A)会被改写为 TS(Ti)。

一旦一个事务因为任何原因被回滚，再次重新执行时，会被系统分配一个新的 TS。

通过上述规则，系统就可以保证对于任意 Ti 和 Tj，如果 TS(Ti)<TS(Tj)，Ti 比 Tj 先运行完。我们通过一个示例来看时间戳是如何运行的。

假定下面两个事务 T1 和 T2，并且 TS(T1) < TS(T2)。

(图 7: T1 + T2)

那么如下的调度根据时间戳机制就是合理的调度

(图 8: T1 + T2 调度)

两边的 display(A+B)都会返回正确的数据。时间戳机制保证了有序性，因为读写都会根据事务的时间戳进行比较再回滚。这种机制同时也避免了死锁，虽然有可能导致饥饿(starvation)：某些运气不好的长事务因为不停地失败被回滚然后重试。

有什么方法能够让时间戳机制进一步提高并发性？

(图 9: T3 + T4)

我们假定 TS(T3) < TS(T4)。首先，T3 的 read(A)会成功。其次，T4 的 write(A)也会成功，因为 T4 的时间戳大于 T3。最后，当 T3 试图 write(A)时会失败，因为 TS(T3) < W-timestamp(A) = TS(4)。因此根据时间戳机制，T3 的 write(A)会失败并被回滚。但事实上，即使不回滚 T3 也不会有问题。因为 T4 已经修改了 A 的值，那么 T3 的修改从时间戳角度来看，已经没有意义，因为不会被其他事务读取：任何 TS 小于 T4 对 A 的读取都会被拒绝然后回滚(因为 TS(Ti) < W-timestamp(A) = TS(T4))；而任何 TS 大于 T4 对 A 的读取都会读取 T4 修改后的 A 值。利用这个发现，我们可以改进时间戳机制来使得无意义的修改操作可以直接被忽略。

这个改进策略被称为托马斯的修改规则(Thomas’ write rule): 假设 Ti 要 write(A):

1. 如果 TS(Ti) < R-timestamp(A)，说明 A 已经被一个更大 TS 的事务读取了，Ti 对 A 的修改就没有意义了，因此 Ti 的修改请求会被拒绝，Ti 会被回滚。

2. 如果 TS(Ti) < W-timestamp(A)，说明 Ti 的修改没有意义，因此这个修改操作会被忽略。

3. 其他情况下，Ti 的修改会被接受，同时 W-timestamp(A)会被改写为 TS(Ti)。

可见，仅第二条规则被改进了。

总结

这篇文章主要介绍了两类对事务隔离的实现，分别是加锁实现机制和时间戳机制。

在加锁实现机制中，介绍了两阶段加锁(Two-phase locking protocol)，通过将事务划分成获取锁阶段和释放锁阶段来保证数据的正确性。同时引入了改进机制，严格的两阶段加锁(rigorous/strict two-phase locking protocol)来避免连锁回滚。两阶段加锁虽然能够保证正确性，却无法避免死锁。因此，需要数据库系统能够检查并破坏死锁。

时间戳机制是通过对每个事务定义时间戳，以及对读写数据记录时间戳来保证正确性。时间戳机制本身也避免了死锁，托马斯的修改规则可以进一步优化时间戳机制。但这两种机制并不是目前常见的实现，下一篇文章，我们会介绍更主流的多版本并发控制(MVCC)。