分布式数据库（五）

小注

极客时间 - 分布式数据库 30 讲

隔离性（乐观控制协议）

乐观锁：TiDB

TiDB 的乐观锁基本上就是 Percolator 模型，它的运行过程可以分为三个阶段。

1、选择 Primary Row

收集所有参与修改的行，从中随机选择一行，作为这个事务的 Primary Row，这一行是拥有锁的，称为 Primary Lock，而且这个锁会负责标记整个事务的完成状态。所有其他修改行也有锁，称为 Secondary Lock，都会保留指向 Primary Row 的指针。

2、写入阶段

按照两阶段提交的顺序，执行第一阶段。每个修改行都会执行上锁并执行“prewrite”，prewrite 就是将数据写入私有版本，其他事务不可见。注意这时候，每个修改行都可能碰到锁冲突的情况，如果冲突了，就终止事务，返回给 TiDB，那么整个事务也就终止了。如果所有修改行都顺利上锁，完成 prewrite，第一阶段结束。

3、提交阶段

这是两阶段提交的第二阶段，提交 Primary Row，也就是写入新版本的提交记录并清除 Primary Lock，如果顺利完成，那么这个事务整体也就完成了，反之就是失败。而 Secondary Rows 上的锁，则会交给异步线程根据 Primary Lock 的状态去清理。

这个过程中不仅有锁，而且锁的数量还不少。为什么又说它是乐观协议呢？

并发控制的三个阶段

在经典理论教材 "Principles of Distributed Database Systems" 中，作者将乐观协议和悲观协议的操作，都统一成四个阶段，分别是有效性验证（V）、读（R）、计算（C）和写（W）。两者的区别就是这四个阶段的顺序不同：悲观协议的操作顺序是 VRCW，而乐观协议的操作顺序则是 RCVW。因为在比较两种协议时，计算（C）这个阶段没有实质影响，可以忽略掉。那么简化后，悲观协议的顺序是 VRW，而乐观协议的顺序就是 RVW。

RVW 的三阶段划分，也见于研究乐观协议的经典论文 "On Optimistic Methods for Concurrency Control"。

关于三个阶段的定义在不同文献中稍有区别，其中“Principles of Distributed Database Systems”对这三个阶段的定义通用性更强，对于 RVW 和 VRW 都是有效的，先看下具体内容。

读阶段（Read Pharse）

每个事务对数据项的局部拷贝进行更新。

需要注意的是：此时的更新结果对于其他事务是不可见的。这个阶段的命名特别容易让人误解，明明做了写操作，却叫做『读阶段』。我想它大概是讲：那些后面要写入的内容，先要暂时加载到一个仅自己可见的临时空间内。这有点像抄录的过程，先读取原文并在脑子里记住，然后誊写出来。

有效性确认阶段（Validation Pharse）

验证准备提交的事务。

这个验证就是指检查这些更新是否可以保证数据库的一致性，如果检查通过就进入下一个阶段，否则取消事务。再深入一点，这段话有两层意思。首先这里提到的检查与隔离性目标有直接联系；其次就是检查可以有不同的手段，也就是不同的并发控制技术，比如可以是基于锁的检查，也可以是基于时间戳排序。

写阶段（Write Pharse）

将读阶段的更新结果写入到数据库中，接受事务的提交结果。

这个阶段的工作就比较容易理解了，就是完成最终的事务提交操作。

还有一种关于乐观与悲观的表述，也与三阶段的顺序相呼应。乐观，重在事后检测，在事务提交时检查是否满足隔离级别，如果满足则提交，否则回滚并自动重新执行。悲观，重在事前预防，在事务执行时检查是否满足隔离级别，如果满足则继续执行，否则等待或回滚。

再回到 TiDB 的乐观锁。虽然对于每一个修改行来说，TiDB 都做了有效性验证，而且顺序是 VRW，可以说是悲观的，但这只是局部的有效性验证；从整体看，TiDB 没有做全局有效性验证，不符合 VRW 顺序，所以还是相对乐观的。

狭义乐观并发控制（OCC）

Transactional Information Systems : Theory, Algorithms, and the Practice of Concurrency Control and Recovery 给出了一个专用于 RVW 的三阶段定义。也就是说，它是专门描述乐观协议的。其中主要差别在『有效性确认阶段』，是针对可串行化的检查，检查采用基于时间戳的特定算法。

这个定义是一个更加具体的乐观协议，严格符合 RVW 顺序，所以把它称为狭义上的乐观并发控制（Optimistic Concurrency Control），也称为基于有效性确认的并发控制（Validation-Based Concurrency Control）。很多学术论文中的 OCC，就是指它。而在工业界，真正生产级的分布式数据库还很少使用狭义 OCC 进行并发控制，唯一的例外就是 FoundationDB。与之相对应的，则是 TiDB 这种广义上的乐观并发控制，说它乐观是因为它没有严格遵循 VRW 顺序。

乐观协议的挑战

为啥乐观要改成悲观呢？主要是两方面的挑战：

一是事务冲突少是使用乐观协议的前提，但这个前提是否普遍成立；

二是现有应用系统使用的单体数据库多是悲观协议，兼容性上的挑战。

事务频繁冲突

首先，事务冲突少这个前提，随着分布式数据库的适用场景越来越广泛，显得不那么有通用性了。比如，金融行业就经常会有一些事务冲突多又要保证严格事务性的业务场景，一个简单的例子就是银行的代发工资。代发工资这个过程，其实就是从企业账户给一大批个人账户转账的过程，是一个批量操作。在这个大的转账事务中可能涉及到成千上万的更新，那么事务持续的时间就会比较长。如果使用乐观协议，在这段时间内，只要有一个人的账户余额发生变化，事务就要回滚，那么这个事务很可能一直都在重试、回滚，永远也执行不完。这个时候，就一点也不要乐观了，像传统单体数据库那样，使用最悲观的锁机制，就很容易实现也很高效。

当然，为了避免这种情况的出现，TiDB 的乐观锁约定了事务的长度，默认单个事务包含的 SQL 语句不超过 5000 条。但这种限制其实是一个消极的处理方式，毕竟业务需求是真实存在的，如果数据库不支持，就必须通过应用层编码去解决了。

遗留应用的兼容性需求

回到悲观协议还有一个重要的原因，那就是保证对遗留应用系统的兼容性。这个很容易理解，因为单体数据库都是悲观协议，甚至多数都是基于锁的悲观协议，所以在 SQL 运行效果上与乐观协议有直接的区别。一个非常典型的例子就是 select for update。这是一个显式的加锁操作，或者说是显式的方式进行有效性确认，广义的乐观协议都不提供严格的 RVW，所以也就无法支持这个操作。

select for update 是不是一个必须的操作呢？其实也不是的，这个语句出现是因为数据库不能支持可串行化隔离，给应用提供了一个控制手段，主导权交给了应用。但是，这就是单体数据库长久以来的规则，已经是生态的一部分，为了降低应用的改造量，新产品还是必须接受。

乐观协议的改变

因为上面这些挑战，TiDB 的并发控制机制也做出了改变，增加了“悲观锁”并作为默认选项。TiDB 悲观锁的理论基础很简单，就是在原有的局部有效性确认前，增加一轮全局有效性确认。这样就是严格的 VRW，自然就是标准的悲观协议了。具体采用的方式就是增加了悲观锁，这个锁是实际存在的，表现为一个占位符，随着 SQL 的执行即时向存储系统（TiKV）发出，这样事务就可以在第一时间发现是否有其他事务与自己冲突。

另外，悲观锁还触发了一个变化。TiDB 原有的事务模型并不是一个交互事务，它会把所有的写 SQL 都攒在一起，在 commit 阶段一起提交，所以有很大的并行度，锁的时间较短，死锁的概率也就较低。因为增加了悲观锁的加锁动作，变回了一个可交互事务，TiDB 还要增加一个死锁检测机制。

小结

1. 并发控制分为乐观和悲观两种，它们的语义和自然语言都是对未来正面或负面的预期。乐观协议预期事务冲突很少，所以不会提前做什么，悲观协议认为事务冲突比较多，所以要有所准备。
2. 按照经典理论，并发控制都是由三个阶段组成，分别是有效性确认（V）、读（R）和写（W）。悲观协议的执行顺序是 VRW，乐观协议的执行顺序是 RVW。所以，又可以得到两个乐观协议的定义，狭义上必须满足 RVW 才是乐观并发控制，而且三阶段有更具体的要求，这个就是学术论文上的 OCC。另外广义的定义，只要不是严格 VRW 的并发控制，都是相对乐观的，都是乐观并发控制，TiDB 就是相对乐观。生产级的分布式数据库很少有使用狭义的 OCC 协议，FoundationDB 是一个例外。
3. 乐观协议的挑战来自两个方面。第一点，乐观协议在事务冲突较少时，因为避免了锁的管理开销，能提供更好的性能；但在事务冲突较多时会出现大量的回滚，效率低下。总的来说，乐观协议的通用性并不好。第二点，传统单体数据库几乎都是基于锁的悲观协议，乐观协议在语义层面没有对等的 SQL，例如 select for update。因此，TiDB 和 CockroachDB 都由乐观协议转变为悲观协议，并且是基于锁的悲观协议。
4. TiDB 的悲观协议符合严格的 VRW 顺序，在原有的两阶段提交前，增加了一轮悲观锁占位操作，实现全局有效性确认。但是随着悲观锁的引入，TiDB 转变为一个可交互事务模式，出现死锁的概率大幅提升，对应增加死锁检测功能。

隔离性（悲观控制协议）

悲观协议的分类

要搞清楚悲观协议的分类，其实是要从并发控制技术整体的分类体系来看。

事实上，并发控制的分类体系，连学术界的标准也不统一。比如，"Principles of Distributed Database Systems" 的分类是按照比较宽泛的乐观协议和悲观协议进行分类，子类之间又有很多重叠的概念，理解起来有点复杂。

而 "Transactional Information Systems : Theory, Algorithms, and the Practice of Concurrency Control and Recovery" 采用的划分方式，是狭义乐观协议和其他悲观协议。这里狭义乐观协议，是指基于有效性验证的并发控制，也是学术上定义的 OCC。

这里以 "Transactional Information Systems : Theory, Algorithms, and the Practice of Concurrency Control and Recovery" 中的划分体系为主。下面摘录了书中的一幅图，用来梳理不同的并发控制协议：

这个体系首先分为悲观和乐观两个大类。因为这里的乐观协议是指狭义乐观并发控制，所以包含内容就比较少，只有前向乐观并发控制和后向乐观并发控制；而悲观协议又分为基于锁和非锁两大类，其中基于锁的协议是数量最多的。

两阶段封锁（Two-Phase Locking，2PL）

基于锁的协议显然不只是 2PL，还包括有序共享（Ordered Sharing 2PL, O2PL）、利他锁（Altruistic Locking, AL）、只写封锁树（Write-only Tree Locking, WTL）和读写封锁树（Read / Write Tree Locking， RWTL）。但这几种协议在真正的数据库系统中很少使用，重点放在数据库系统主要使用的 2PL 上。

2PL 就是事务具备两阶段特点的并发控制协议，这里的两个阶段指加锁阶段和释放锁阶段，并且加锁阶段严格区别于紧接着的释放锁阶段。我们可以通过一张图来加深对 2PL 理解。

在 t1 时刻之前是加锁阶段，在 t1 之后则是释放锁阶段，可以从时间上明确地把事务执行过程划分为两个阶段。2PL 的关键点就是释放锁之后不能再加锁。而根据加锁和释放锁时机的不同，2PL 又有一些变体。

保守两阶段封锁协议（Conservative 2PL，C2PL），事务在开始时设置它需要的所有锁。

严格两阶段封锁协议（Strict 2PL，S2PL），事务一直持有已经获得的所有写锁，直到事务终止。

强两阶段封锁协议（Strong Strict 2PL，SS2PL），事务一直持有已经获得的所有锁，包括写锁和读锁，直到事务终止。SS2PL 与 S2PL 差别只在于一直持有的锁的类型，所以它们的图形是相同的。

理解了这几种 2PL 的变体后，再回想一下 Percolator 模型。当主锁（Primary Lock）没有释放前，所有的记录上的从锁（Secondary Lock）实质上都没有释放，在主锁释放后，所有从锁自然释放。所以，Percolator 也属于 S2PL。TiDB 的乐观锁机制是基于 Percolator 的，那么 TiDB 就也是 S2PL。

事实上，S2PL 可能是使用最广泛的悲观协议，几乎所有单体数据都依赖 S2PL 实现可串行化。而在分布式数据库中，甚至需要使用 SS2PL 来保证可串行化执行，典型的例子是 TDSQL。但 S2PL 模式下，事务持有锁的时间过长，导致系统并发性能较差，所以实际使用中往往不会配置到可串行化级别。这就意味着我们还是没有生产级技术方案，只能期望出现新的方式，既达到可串行化隔离级别，又能有更好的性能。最终，我们等到了一种可能是性能更优的工程化实现，这就是 CockroachDB 的串行化快照隔离（SSI）。而 SSI 的核心，就是串行化图检测（SGT）。

串行化图检测（SGT）

SSI 是一种隔离级别的命名，最早来自 PostgreSQL，CockroachDB 沿用了这个名称。它是在 SI 基础上实现的可串行化隔离。同样，作为 SSI 核心的 SGT 也不是 CockroachDB 首创，学术界早就提出了这个理论，但真正的工程化实现要晚得多。

理论来源：PostgreSQL

PostgreSQL 在论文 "Serializable Snapshot Isolation in PostgreSQL" 中最早提出了 SSI 的工程实现方案，这篇论文也被 VLDB2012 收录。

为了更清楚地描述 SSI 方案，要先了解一点理论知识。

串行化理论的核心是串行化图（Serializable Graph，SG）。这个图用来分析数据库事务操作的冲突情况。每个事务是一个节点，事务之间的关系则表示为一条有向边。那么，什么样的关系可以表示为边呢？

串行化图的构建规则是这样的，事务作为节点，当一个操作与另一个操作冲突时，在两个事务节点之间就可以画上一条有向边。

具体来说，事务之间的边又分为三类情况：

1. 写读依赖（WR-Dependencies），第二个操作读取了第一个操作写入的值。
2. 写写依赖（WW-Dependencies），第二个操作覆盖了第一个操作写入的值。
3. 读写反依赖（RW-Antidependencies），第二个操作覆盖了第一个操作读取的值，可能导致读取值过期。

通过一个例子，看看如何用这几条规则来构建一个简单的串行化图。

图中一共有三个事务先后执行，事务 T1 先执行 W(A)，T2 再执行 R(A)，所以 T1 与 T2 之间存在 WR 依赖，因此形成一条 T1 指向 T2 的边；同理，T2 的 W(B) 与 T3 的 R(B) 也存在 WR 依赖，T1 的 W(A) 与 T3 的 R(A) 之间也是 WR 依赖，这样就又形成两条有向边，分别是 T2 指向 T3 和 T1 指向 T3。

最终，产生了一个有向无环图（Directed Acyclic Graph，DAG）。能够构建出 DAG，就说明相关事务是可串行化执行的，不需要中断任何事务。

可以使用 SGT，验证一下典型的死锁情况。我们知道，事务 T1 和 T2 分别以不同的顺序写两个数据项，那么就会形成死锁。

用串行化图来体现就是这个样子，显然构成了环。

在 SGT 中，WR 依赖和 WW 依赖都与我们的直觉相符，而 RW 反向依赖就比较难理解了。在 PostgreSQL 的论文中，专门描述了一个 RW 反向依赖的场景。

这个场景一共需要维护两张表：一张收入表（reciepts）会记入当日的收入情况，每行都会记录一个批次号；另一张独立的控制表（current_batch），里面只有一条记录，就是当前的批次号。也可以把这里的批次号理解为一个工作日。

同时，还有三个事务 T1、T2、T3。

• T2 是记录新的收入（NEW-RECEIPT），从控制表中读取当前的批次号，然后在收入表中插入一条新的记录。
• T3 负责关闭当前批次（CLOSE-BATCH），而具体实现是通过将控制表中的批次号递增的方式，这就意味着后续再发生的收入会划归到下一个批次。
• T1 是报告（REPORT），读取当前控制表的批次号，处理逻辑是用当前已经加一的批次号再减一。T1 用这个批次号作为条件，读取收据表中的所有记录。查询到这个批次，也就是这一日，所有的交易。

其实，这个例子很像银行存款系统的日终翻牌。

因为 T1 要报告当天的收入情况，所以它必须要在 T3 之后执行。事务 T2 记录了当天的每笔入账，必须在 T3 之前执行，这样才能出现在当天的报表中。三者顺序执行可以正常工作，否则就会出现异常，比如下面这样的：

T2 先拿到一个批次号 x，随后 T3 执行，批次号关闭后，x 这个批次号其实已经过期，但是 T2 还继续使用 x，记录当前的这笔收入。T1 正常在 T3 后执行，此时 T2 尚未提交，所以 T1 的报告中漏掉了 T2 的那笔收入。因为 T2 使用时过期的批次号 x，第二天的报告中也不会统计到这笔收入，最终这笔收入就神奇地消失了。

在理解了这个例子的异常现象后，用串行化图方法来验证一下。通过把事务中的 SQL 抽象为对数据项的操作，可以得到下面这张图。

图中 batch 是指批次号，reps 是指收入情况。

接下来，按照先后顺序提取有向边，先由 T2.R(batch) -> T3.W(batch)，得到 T2 到 T3 的 RW 依赖；再由 T3.W(batch)->T1.R(batch)，得到 T3 到 T1 的 WR 依赖；最后由 T1.R(reps)->T2.W(reps)，得到 T1 到 T2 的 RW 依赖。这样就构成了下面的串行化图。

显然这三个事务之间是存在环的，那么这三个事务就是不能串行化的。

这个异常现象中很有意思的一点是，虽然 T1 是一个只读事务，但如果没有 T1 的话，T2 与 T3 不会形成环，依然是可串行化执行的。这里就澄清了一点：直觉上认为的只读事务不会影响事务并发机制，其实是不对的。

工程实现：CockroachDB

RW 反向依赖是一个非常特别的存在，而特别之处就在于传统的锁机制无法记录这种情况。因此在论文 "Serializable Snapshot Isolation in PostgreSQL" 中提出，增加一种锁 SIREAD，用来记录快照隔离（SI）上所有执行过的读操作（Read），从而识别 RW 反向依赖。本质上，SIREAD 并不是锁，只是一种标识。但这个方案面临的困境是，读操作涉及到的数据范围实在太大，跟踪标识带来的成本可能比 S2PL 还要高，也就无法达到最初的目标。

针对这个问题，CockroachDB 做了一个关键设计，读时间戳缓存（Read Timestamp Cache），简称 RTC。

基于 RTC 的新方案是这样的，当执行任何的读取操作时，操作的时间戳都会被记录在所访问节点的本地 RTC 中。当任何写操作访问这个节点时，都会以将要访问的 Key 为输入，向 RTC 查询最大的读时间戳（MRT），如果 MRT 大于这个写入操作的时间戳，那继续写入就会形成 RW 依赖。这时就必须终止并重启写入事务，让写入事务拿到一个更大的时间戳重新尝试。

具体来说，RTC 是以 Key 的范围来组织读时间戳的。这样，当读取操作携带了谓词条件，比如 where 子句，对应的操作就是一个范围读取，会覆盖若干个 Key，那么整个 Key 的范围也可以被记录在 RTC 中。这样处理的好处是，可以兼容一种特殊情况。

例如，事务 T1 第一次范围读取（Range Scan）数据表，where 条件是『>=1 and <=5』，读取到 1、2、5 三个值，T1 完成后，事务 T2 在该表插入了 4，因为 RTC 记录的是范围区间 [1,5]，所以 4 也可以被检测出存在 RW 依赖。这个地方，有点像 MySQL 间隙锁的原理。

RTC 是一个大小有限的，采用 LRU（Least Recently Used，最近最少使用）淘汰算法的缓存。当达到存储上限时，最老的时间戳会被抛弃。为了应对缓存超限的情况，会将 RTC 中出现过的所有 Key 上最早的那个读时间戳记录下来，作为低水位线（Low Water Mark）。如果一个写操作将要写的 Key 不在 RTC 中，则会返回这个低水位线。

相对乐观

SGT 的运行机制，和传统的 S2PL 一样属于悲观协议。但 SGT 没有锁的管理成本，所以性能比 S2PL 更好。

CockroachDB 基于 SGT 理论进行工程化，使可串行化真正成为生产级可用的隔离级别。从整体并发控制机制看，CockroachDB 和上一讲的 TiDB 一样，虽然在局部看是悲观协议，但因为不符合严格的 VRW 顺序，所以在全局来看仍是一个相对乐观的协议。

这种乐观协议同样存在问题，所以 CockroachDB 也在原有基础上进行了改良，通过增加全局的锁表（Lock Table），使用加锁的方式，先进行一轮全局有效性验证，确定无冲突的情况下，再使用单个节点的 SGT。

小结

1. 并发控制机制的划分方法很多，没有统一标准，我们使用了 "Transactional Information Systems : Theory, Algorithms, and the Practice of Concurrency Control and Recovery" 提出的划分标准，分为悲观协议与乐观协议两种。这里的乐观协议是上一讲提到的狭义乐观协议，悲观协议又分为锁和非锁两大类，这里简单介绍了 2PL 这一个分支。
2. 回顾了 Percolator 模型，按照 S2PL 的定义，Percoloatro 本质就是 S2PL，因此 TiDB 的乐观锁也属于 S2PL。
3. S2PL 是数据库并发控制的主流技术，但是锁管理复杂，在实现串行化隔离级别时开销太大。而后，我们讨论了非锁协议中的串行化图检测（SGT）。PostgreSQL 最早提出了 SGT 的工程实现方式 SSI。CockroachDB 在此基础上又进行了优化，降低了 SIREAD 的开销，是生产级的可串行化隔离。
4. CockroachDB 最初和 TiDB 一样都是局部采用悲观协议，而不做全局有效性验证，是广义的乐观协议。后来，CockroachDB 同样也将乐观协议改为悲观协议，采用的方式是增加全局的锁表，进行全局有效性验证，而后再转入单个的 SGT 处理。

学习资料

Gerhard Weikum and Gottfried Vossen: Transactional Information Systems : Theory, Algorithms, and the Practice of Concurrency Control and Recovery

H. T. Kung and John T. Robinson: On Optimistic Methods for Concurrency Control

M. Tamer Özsu and Patrick Valduriez: Principles of Distributed Database Systems

最早的 SSI 工程实现方案：Serializable Snapshot Isolation in PostgreSQL

按照狭义乐观协议和其他悲观协议划分并发控制协议：Transactional Information Systems : Theory, Algorithms, and the Practice of Concurrency Control and Recovery