一、既知“共识”，何求“事务”

鄙人不才，这些年分享了一系列有关共识协议的文章，或详述理论，或细说实践，从状态机到分布式锁，洋洋洒洒，不一而足。正如我在这些文章中一直强调的，共识协议对于分布式系统之所以如此重要，在于其面向数据一致性与服务容错性这两大难题提供了近乎完美的解决方案。不过，任何技术皆非万能，一定是有其应用边界的，那么“共识”技术的作用域在哪里呢？答案见下图：参与“共识”的各方须是一系列副本（Replica），执行着相同的业务逻辑，趋近于相同的状态，故而互相可为容灾备份。

图 1. “共识”的参与方，是为了一个共同目标聚到一起的副本们

聊到“共识”，我们再多聊几句 CAP 性质。所谓 “C” 即 Consistency（一致性，可以理解为写成功的数据，总是能读得出来），“A” 即 Availability（可用性，可以理解为少部分节点故障，对外服务不受影响），“P” 即 Partition tolerance（分区容错性，可以理解为节点之间发生了网络分区，无法通信，也不影响系统响应的正确性）。这个性质是给工业界设置了底限，鱼和熊掌不可兼得，基于容忍网络分区的前提下，究竟选择 “C” 还是 “A”，这是个问题。譬如我们阿里云女娲系统，是典型的 CP 系统，当然，我们也做了很多工程技术的优化（譬如读场景下的各类缓存，写场景的多活解决方案等等），竭力提升网络分区场景下的服务可用性。

话题再说回来，“共识”技术的作用域是一系列副本，但是在现代的分布式系统中，很多时候，我们要面临的挑战并非是能够在副本之间协调的，譬如一个操作可能会涉及不同的逻辑实体（一说是资源管理器，RM，Resource Manager，它们的业务逻辑完全不一样，状态也毫无关系，具体而言，资源可以是下文将提到的分布式存储系统中的不同“数据分区”，甚至可以是不同的“数据库实例”），那么业务系统对这样的操作应该持怎样的预期呢？这里所谓的“预期”，翻译一下，叫做 Serializability，可序列化。事实上，这个也是分布式系统的初始愿景 - 多台（成千上万台）计算机一起工作，在终端用户看来，这就像是一台（没座，关键词是一台）功能强大的超级计算机。就这样，继“共识”之后，分布式系统再有了“事务”这个武器，开始走向成熟，能够让终端用户的上述操作看起来是在一个独享的、不被干扰的环境下执行。

图 2. 无论扩展至多大规模，分布式系统的初衷不变 - 像一台设备那样工作

类似讲“共识”就要介绍 CAP，说“事务”也不得不提 ACID，这个可以更正式地解释什么叫符合业务“预期”的结果。所谓 “A” 即 Atomicity（原子性，可以理解为一个事务内的所有操作，要么全部成功，要么全部失败，不存在中间状态），“C” 即 Consistency（虽说与 CAP 的 "C" 是一个单词，含义却完全不同：这里的 "C" 可以理解为数据完整性的约束，具体如下文所言，保持系统的 invariants），“I” 即 Isolation（隔离性，可以理解为并发事务之间，各自内部的操作状态对对方是不可见的），“D” 即 Durability（持久化，可以理解为一旦写成功的数据，不会因为进程 failover 等异常而导致状态丢失）。

如下图 3 ，最终，一个成熟的分布式事务的实现通常需要考虑三部分：1）最上层的是原子提交协议，主流的自然是鼎鼎大名的 2 PC - 两阶段提交协议；2）中间层是并发访问控制协议，用于提升事务的并发读写效率；3）最下面的是基于共识的复制协议，保证服务的可容错性。图 3 真的很赞，是不是？可谓一图即可清晰地解释共识与事务的关系。备注一下，这个图来自 SOSP'15 的经典论文 - "Building Consistent Transactions with Inconsistent Replication"。

图 3. 主流的分布式事务实现框架，2 PC + MVCC + Paxos，一个都不能少

总结起来，“事务”要解决的问题，在“共识”之上：首先，“事务”的参与方，并非副本，而是不同业务逻辑的资源实体；其次，“事务”包括了一系列子操作，每个操作的作用方可以落在不同的资源实体。通俗一点讲，“共识”是同一个培训班出来的几个人，做的是同一件事情，互为容灾备份；“事务”则是来自五湖四海的一群人，各司其职，组合在一起，干一票大的。实际系统中，我们可以把“事务”典型的应用场景归纳为以下两类：

• 在 SOA（面向服务）架构、Microservices（微服务）架构盛行的今天，一个大型的业务系统通常会拆分出独立的子模块系统。譬如互联网金融网站的 SOA 拆分出交易系统、账务系统、清算系统等等，其中交易系统负责交易管理和记录交易明细，账务系统负责维护用户余额，所有的业务操作都以服务的方式对外发布。如图 4 所示，一笔金融交易操作需要同时记录交易明细和完成用户余额的转账，此时需要分别调用交易系统的交易明细服务和账务系统的用户余额服务，这种跨应用、跨服务的操作必须使用“事务”才能保证金融数据的一致性，万不可出现部分子模块成功，部分子模块失败的情形。“事务”的这个应用场景可以总结为 - 跨应用、跨服务的协同操作如何保证整体的数据一致性；

图 4. 分布式事务的应用场景之一，在不同模块之上的整体数据一致性的维护

• 为了提升扩展性，同时增加并发性能，现代分布式存储系统多采用基于分区的调度架构。如图 5 所示，基于分区模型的业务系统可以划分为管控与数据平面，其中数据平面将用户存储空间按照一定规则分割成若干分区，在运行时一个分区会被分配至某个服务器提供服务，一个服务器可以同时加载多个分区；管控平面负责分区调度，一方面是日常的负载均衡，另一方面当某个服务器宕机的时候，管控负责将相应的分区重新调度，快速迁移至其它健康的服务器。如果一系列读写操作发生在不同分区，如何保证这一系列读写操作要么都成功，要么都失败，并且在成功提交之前任何子操作的应用效果对外不可见？“事务”的这个应用场景可以总结为 - 跨分区的一系列读写操作如何保证整体的数据一致性；

图 5. 分布式事务的应用场景之二，一个系统内不同分区之上的整体数据一致性的维护

事务的上述两类典型应用场景也分化出两大技术方向，其一者，旨在推行分布式事务的通用模型。在这个通用模型中，参与者是事务管理器（TM，Transaction Manager），资源管理器（RM，Resource Manager），甚至还有事务协调器（TC，Transaction Coordinator）。业界也沉淀了一系列有关 TM 与 RM 之间通信的接口协议规范，譬如 XA，TCC 等，诞生了一系列知名的中间件，譬如阿里的 TXC（源于淘宝中间件，2014 年微服务改造的浪潮中应运而生），GTS（始于 2016 年，TXC 云化，推出的阿里云中间件产品），Fescar（TXC/GTS 的社区版），蚂蚁的 XTS，DTX 等等。

本文关注的是其二者 - 关于如何在一个分布式系统内实现不用数据分区之上的分布式事务。接下来，我们会先介绍实现分布式事务的标准范式 —— 2 PC，以及评估分布式事务等级最为重要的标准 —— Isolation；然后是一段进阶学习，如何通过引入多版本并发控制机制 —— MVCC，让分布式事务兼具优秀的隔离性以及良好的并发访问性能；最后，我们一览它山之石，看看业界同仁们在分布式事务这个领域的最佳实践。

二、你该怎么实现分布式事务

2.1. 心中的日月 - invariants

ACID 中的 “I” 很重要。Isolation，隔离性，我们可以认为这个是事务最重要的性质（熟悉共识协议的同学，对于“A”，“D”应该都不会陌生；至于改头换面的“C”，毕竟是新的应用场景，提出新的系统约束，也能理解；至于全新冒出的“I”，可能会有一定距离感）。简单来说，隔离性要求并发执行的事务之间互不影响。如果一个事务在读一个数据，刚好这个数据正在被另一个并发事务修改；又或者两个事务同时修改一个数据 ...... 这会引发什么问题呢 🤔？

我们拿生活中银行转账的场景来举例说明，请看图 6，假如你在某银行有 A，B 两个账户，初始均为 1000 元，现在你要做一个转账操作，从账户 A 转 500 元给账户 B，最终自然是账户 A 余额变成了 500 元，而账户 B 余额变成了 1500 元。看起来没啥问题，是吧？不过，如果你在 t1 与 t2 这时间段之间查看两个账户的余额，你会惊奇的发现两个账户的总额变成了 1500 元，你的钱少了 500 元！这样的情形你能接受吗？不行 ...... 😭 好的，现在你认识到事务的隔离性有多重要了。

图 6. 银行里某人有两个账户 A，B，做了一个转账 500 元的操作

在上面的例子中，用户认定两个账户的总额是 2000 元，这个是他认为的不变量（invariants），不可以被打破。类比来说，分布式系统中的系统状态不变量 - invariants，同样也不能够被打破，否则我们开发一个分布式程序将无所依循。而分布式系统正是依赖的事务，依赖事务的隔离性来维护系统状态的不变量。具体而言，上述例子中破坏系统 invariants 的行为，业界也称之为“脏读”，即读到了一个事务的中间状态。事实上，业界把并发事务可能导致的破坏系统 invariants 的典型行为归纳如下：

• Dirty Write，脏写：两个并发事务，互相干扰，最终结果是两个事务各自覆盖了对方的一部分写，实际上两个事务均没有生效。脏写是被各种事务实现默认禁止的现象，这个是底线；
  
• Dirty Read，脏读：该现象是 SQL-92 定义事务隔离级别时候列举的三大“现象”之一，即一个事务的中间状态被人读取到（这个事务尚不一定成功，最终可能会被回滚）；
  
• Fuzzy Read，不可重复读：该现象是 SQL-92 定义事务隔离级别时候列举的三大“现象”之二，即一个事务中前后两次读取同一个数据记录，两次读取的结果不一样；
  
• Phantom，幻读：该现象是 SQL-92 定义事务隔离级别时候列举的三大“现象”之三，即一个事务中针对同一条件多次查询一组数据，结果两次查询之间被其他并发事务新插入（或者删除）了数据记录，并且是满足查询条件的数据记录，这就导致查询结果集的数量发生了变化。幻读大多发生在范围查询、聚合、统计等业务场景；
  
• Write Skew，写偏斜：根据相同的读记录集合，两个并发事务分别写了不相交的写记录集合，最终导致整体的系统 invariants 被打破。这里最经典的例子是医院排班，两个医生 A、B 同时看到今晚有人值班，然后俩人均以身体不适为由请假，最终导致晚上医院没人值班了。需要提前说明一下，写偏斜这类破坏系统 invariants 的现象，并非第一天就存在的，反而是后期 Snapshot Isolation 这种事务隔离技术普及之后才浮现的，并开始为业界所重视；

事务正是用以维护分布式系统状态 invariants 的大杀器。说到事务之间的隔离性，最理想的效果是并发事务之间的运行结果与他们串行执行的结果是完全一样的，这样也就能够避免上述所有的破坏系统 invariants 的现象。当然，这种级别的事务隔离性，性能也是最差的。事实上，业界也不乏这类隔离级别的事务实现，诸如 VoltDB，Etcd，ZooKeeper，这些软件均采用单线程来执行事务，继而提供了最为严格的隔离性保证，不过性能嘛，属实有点儿一言难尽 ......

除了完全串行化处理并发事务请求，有没有更“高级”的办法来实现事务之间的隔离性？加锁可以吗 ...... 我们在事务开始执行之前，把事务涉及的数据记录都加锁，确保全部成功加锁之后，再执行具体读写操作，这样独占式访问数据对象，可以不 ...... 太可以了！坦白说，这个正是 2 PC 的奥义！我们简要回顾一下分布式事务的主流实现 - 2 PC（Two-phase Commit Protocol）。

2.2. 事务的主流实现 - 2 PC

两阶段提交协议 - 2 PC，可谓分布式系统中实现事务最经典，也是应用最广泛的协议。网上这块学习资料很多，不再赘述。我们在 图 7 中展示了 2 PC 的大体工作流程，进一步解读如下：

• 在 2 PC 实现中，通常存在两类角色，事务协调者（Transaction Coordinator）以及资源管理器（Resource Manager），前者负责收集并管理事务执行过程中状态，后者负责执行具体读写子任务；
• 在 2 PC 实现中，通常有两个阶段，准备（Prepare）阶段与提交（Commit）阶段，前者收集各个资源管理器对待执行任务的响应：如果全部通过，则进入提交阶段（不可逆）；否则，中止事务操作，清理本事务留下的痕迹。具体而言，处于 Prepare 阶段的事务涉及的数据记录修改对其它并发的读写访问是不可见的；

图 7. 有关 Transaction Coordinator 以及 Resource Manager 的状态转换

我们这里再浅析一下 2 PC 协议的奥义。第一步 Prepare 阶段事实上是在每个资源管理器留下有关事务的痕迹，这里所谓的痕迹有二：一者是类似“锁”的痕迹，这样能够解决写-写冲突，甚至是写-读冲突；二者是数据记录的增量修改本身要留痕，但是这个数据留痕须得十分巧妙，一方面要保证可全量恢复，另一方面在事务成功提交之前还不能被其它读请求“看到”。第二步 Commit 阶段的一个小巧思是面向失败的设计：假如本事务执行过程中被其他角色认为过期了，本事务的痕迹将被强制清理，故而本事务在提交之前务必检查一下痕迹是否依旧存在，检查通过方可提交。

强调一下，2 PC 是一种实现分布式事务的指导思路，具体实现时面临着种种权衡，究竟是追求最严格的事务隔离性，还是兼顾并发读写效率，这实在是个丰俭由人的选择。这里的权衡变化主要在第一阶段“留痕”的粒度，即面向事务中读写数据集的“加锁”粒度。

2.3. “锁”粒度决定的隔离级别

废话不多说，我们先看下事务有哪些隔离级别。传统意义上来说，事务有三大隔离级别，ANSI SQL-92 有详细定义，它们分别是 - 读已提交（Read Committed），可重复读（Repeatable Read），可串行化（Serializable），让我们一一解开它们的庐山真面目。

2.3.1. Read Committed

Read Commited，即读已提交，这个属于最基础的事务隔离级别，它保证了读数据时只能读到已经提交的数据，从而没有所谓脏读现象。事实上，很多数据库都实现了 Read Committed 这个隔离级别，它甚至成为了早期很多数据库默认的隔离级别。比如 Oracle 11g、PostgreSQL、SQL Server 2012、 MemSQL 等等。Read Committed 比较好实现，常见的方式是加行锁，一个事务写把自己的数据记录加上行锁，这样就可以避免事务读看到中间态的数据记录。

不过，Read Commited 隔离级别解决不了 Fuzzy Read 问题：一个事务在处理过程中如果重复读取某一个数据，而这个数据恰好被其他事务修改并成功提交了，那么当前重复读取该数据的事务就会面临以下情况：同一个数据在同一个事务中前后两次读取的结果不同。

2.3.2. Repeatable Read

Repeatable Read，即可重复读，该隔离级别解决了 Fuzzy Read 问题。Repeatable Read 隔离级别可以理解为一个事务一旦开始，事务过程中读取的所有数据不允许被其他事务修改。第一反应是拉长事务的加锁区间，很直观，是不是？是的，早期业界使用比较多的是 S2PL（Strict Two-Phase Locking），即通过引入读锁（S-Lock），写锁（X-Lock）来避免可重复读现象，这里的关键点是，无论是 S-Lock，还是 X-Lock，在事务结束之前均不会释放。S2PL 落地的最大挑战还是效率问题，一方面死锁概率增加，需要额外的死锁检测机制；另一方面读写请求互相阻塞现象也是增加明显。

再一个是应对 Phantom 幻读现象，基于 S2PL 的 Repeatable Read 隔离级别的实现机制也是有招的 - 加谓词锁，即对查询谓词对应的索引区间加意向锁甚至是锁整个范围，小样，我看你往哪里躲 ...... 当然这里的问题是，并发事务的冲突概率又增加了 😳。

总的来说，基于 S2PL 的 Repeatable Read 隔离级别的实现机制，效率是个很大问题，并且没什么好的优化办法。故而后来业界落地的 Repeatable Read 隔离级别普遍是基于 MVCC 实现的：

• 每条数据都带有版本号（全局单调递增的时间戳），在事务开始时向全局时间戳服务请求一个快照时间戳 T，用来标记事务，也可以作为数据项版本；
• 所有读请求都只返回版本号小于等于 T 的已提交数据；
• 而对于写请求，总是创建新版本，自然这个“新”版本要“新”于并发的所有读请求的时间戳（必须的，否则如何支持 Repeatable Read）；
• 
  

这样保证对多个分区/节点并发进行读写的时候，同一事务看到的数据快照是全局一致的。基于 MVCC 的 Repeatable Read 隔离级别的实现机制，读写无冲突，对高并发场景优化效果显著。不过引入了多版本存储，也因此引入了定期做后台 GC（Garbage Collection） 的代价。这个自然，天下没有白吃的午餐。

在应对 Phantom 幻读现象方面，基础版的基于 MVCC 的 Repeatable Read 隔离级别的实现机制是存在 Phantom 幻读可能性的，这里主要看具体实现的时候，所谓“看到”的快照版本是数据项粒度还是事务粒度。如果我们整个事务执行过程，事务内的读写请求均只坚持一个版本号，坚持根据这一个版本号去读各相关的已提交数据项，那么是可以规避 Phantom 幻读现象的（这里的实现奥义是，每个事务在开始时获得一个快照时间 start_ts，事务内的读取却只看到 commit_ts ≤ start_ts 的版本，这里的 commit_ts 是其他事务在提交时会被分配一个提交时间戳）。此等进化后的 MVCC 机制，已非吴下阿蒙，仅仅说是 Repeatable Read 隔离级别是不够的，需要“抬旗”...... 业界将这类新形态的隔离机制称为 Snapshot Isolation，它能进一步消除 Phantom 幻读，同时兼顾读写吞吐效率。

有了 Snapshot Isolation，新的破坏系统 invariants 的现象也浮出了水面 - write skew，写偏斜。没办法，MVCC 机制的出现很大程度是因为要提升并发读写的吞吐，故而在 Snapshot Isolation 的实现里，读操作可以只读历史版本，不加行锁，在提交阶段也仅检测是否存在写/写冲突即可。可以看到，Snapshot Isolation 把读集完全排除在冲突检测之外，只要写集不碰撞，就允许事务的并发提交 - 这就给 write skew 现象的出现创造了条件。所谓 write skew 写偏斜，本质上多条数据共同在维护的 invariants 无法被顾及到。怎么办呢？继续往严格串行化方向再挪一步吧！

2.3.3. Serializable

Serializable，即可串行化，该隔离级别自然是王者。正如坤哥在音乐届是顶级的存在，Serializable 在事务隔离性这块也是顶级的存在。在 Serializable 的事务隔离级别之下，系统中所有的事务以串行化的方式逐个执行，保障数据一致性，避免脏读、不可重复读、幻读、写偏斜等现象。有关 Serializable 隔离级别，死忠派排斥并发，严格串行化执行事务请求，这样导致的问题自然是系统并发处理能力的大幅下降。如前文所言，业界诸如 VoltDB，Etcd，ZooKeeper 等都是采用了单线程来执行事务，面临的挑战如出一辙 - 分布式事务难以实现，性能存在单点瓶颈，长时事务会阻塞其他事务执行。

改良派引入了 MVCC 技术，自觉 Serializable 隔离级别在性能改善方面也看到了一丝曙光。事实上，Snapshot Isolation 已经成为目前数据库领域主流的事务隔离级别，其距离 Serializable 也仅一步之遥 - 需进一步避免 write-skew 写偏斜现象即可，这个能力也是可以达成的，但是要出点血，得加钱 ......

Anyway，我们继续看看当今业界主流的基于 MVCC 的并发事务控制协议吧，无论是主流的 Snapshot Isolation 隔离级别，还是追求极致的 Serializable 隔离级别，基于 MVCC 的并发控制协议，你是绕不开的。如图 8 所展示的，有些数据库在实现上选择了 MVCC + 2 PL（Two-phase Locking），也有的数据库选择了 MVCC + OCC（Optimistic Concurrent Control）的，甚至是 SSL（Serializable Snapshot Isolation，这个协议有点厉害，一上来就是奔着 Serializable 隔离级别去的）。MVCC 本身的多版本实现依赖单调递增的时间戳作为版本号，并发事务控制协议，核心要回答的是“谁”阻塞“谁”，同样依赖单调递增的时间戳来仲裁。故而，这里就引入了逻辑时间戳这一强依赖。

图 8. VLDB'17 一篇论文 [5] 统计了业界数据库采用的并发事务控制协议

总体来说，MVCC + 2 PL 代表的还是一种悲观加锁式的可串行化隔离技术，其落地过程中不可避免要面对出现死锁的可能性，故而相应分布式系统需要具备死锁检测能力，主动回滚其中的一个事务来解除死锁。应用层则需要重试这个被回滚的事务。相较于 MVCC + 2 PL 这种悲观加锁式的可串行化隔离技术，还有一种乐观式的可串行隔离技术 - SSI（Serializable Snapshot Isolation），SSI 提供了可串行化隔离，性能只比可重复读这一弱隔离级别的性能差一点儿，但是比 MVCC + 2 PL 的性能还是好不少的。该算法是 2008 年 Michael Cahill 在他的毕业论文中提出的 [14]，为了分析并发事务可串行化调度问题，提出了一种叫做 Dependency Serialization Graph 的技术，通过分析并发事务之间读/读，读/写，写/写之间的依赖关系，形成一个有向图，假如图中无环，那么这批事务就可以串行化调度。这个协议看起来很美好，但是工程实现比较复杂（相信熟悉共识协议的小伙伴，一定看到了 EPaxos 的影子，EPaxos 共识协议提出时间甚至早于 Raft，不过其工程实现复杂度很高，最终泯然众生了 ...... ），目前已知的是 PostgreSQL 和 CockroachDB 两大生产级数据库将 SSI 作为其可串行化隔离级别的事务实现机制。

下一章节，我们就详细聊一聊基于 MVCC 如何实现可串行化隔离级别的事务。提醒一下，这一块内容可不少，打起精神，准备投入知识的海洋吧 😳

三、既要又要？试试 MVCC

MVCC 可谓数据库管理系统（DBMS，Database Management System）中最主流的事务管理机制。究其原因，事务本质上在追求的是操作请求的可序列化（Serializability），这个目标天然存在并发访问的性能瓶颈问题。MVCC 的想法非常朴实：数据库中维护的是一个一个逻辑对象，每个逻辑对象均维护了多个物理版本，这样就能够允许对同一对象的并行操作在不同的物理版本上进行。想一想，这几乎是在追求操作请求可序列化的基本原则之上，提升操作请求并发性（Parallelism）的不二法门。

我们在文章 [4] 中详细阐述过分布式系统中的时空观，介绍过时间戳可以用来刻画分布式系统中读写操作的因果序。一个很直观的想法是，如果我们能够给每个事务分配单调递增的时间戳，DBMS 根据这个时间戳来协调事务的执行顺序，这样是可以坚守操作请求可序列化这条底线的。故而，在 MVCC 机制中，DBMS 会给每个事务 T 分配一个全局唯一的、单调递增的时间戳 Tid，这个时间戳 Tid 用来干嘛呢？其一，它的唯一性，让我们可以利用其标记事务 T 访问过哪些 Tuple 的哪些物理版本；其二，它的单调递增性，让某些 MVCC 的协议使用其来定序事务们的应用（commit）顺序。

除了事务的全局唯一、单调递增的序号，我们还要了解 MVCC 机制下的数据布局。在一个数据库系统中，MVCC 管理对象的基本粒度是 Tuple（即元组，数据表中的一个单独记录或者行。它是关系型数据库中的基本组成单位之一。每个元组包含表中定义的一组属性值，这些属性对应于表中的列），不过它实际管理的是个逻辑对象，数据库针对任一 Tuple，会存在一个逻辑对象与对应的 N 个物理版本实体。图 9 展示了 Tuple 物理版本的布局格式，分成 Header 与 Content 两个部分，其中 Header 部分至少包括 4 个字段：

• txn-id：写锁标志位，默认为 0 （即无人占据写锁），这个值的更改，通常基于 CAS 指令原子更新，严格确保写锁的互斥性；
• begin-ts/end-ts：这两个字段很好地利用起了事务序号的单调递增性 - 描述了该 Tuple 物理版本的生命期。如果我们想要删除某个 Tuple 的某个物理版本，将其 begin-ts 修改为 INF 即可；
• pointer：这个字段是用来串联该 Tuple 其余的物理版本（或指向更旧版本，或指向更新版本，这两种机制各有优缺点，看系统实际的实现选择）；

图 9. MVCC 机制下的一个 Tuple（元组）的物理版本的布局格式

事实上，MVCC 已经成为这些年 DBMS 的主流选择，从早期的 Oracle，Postgres，MySQL-InnoDB，到近些年的 Percolator，DynamoDB，CockroachDB，TiDB，OceanBase，等等。但是，业界对于 MVCC 的实现并没有一个绝对的通用标准。究其原因，MVCC 给系统中引入的额外的存储开销、计算开销，以及冲突控制复杂度，这些考量皆会由于面向的具体业务场景不一样而做出不同的偏向，故而实际落地的 MVCC，从并发控制协议，到版本存储方案，到垃圾回收机制，再到索引管理机制，都有各种权衡考量。

VLDB'17 有篇非常经典的关于 MVCC 的研究文章 [5]，对分布式事务感兴趣的同学建议都读一读。这篇文章好到什么地步呢？据说作者投稿的第一版标题是 - 《This is the Best Paper Ever on In-Memory Multi-Version Concurrency Control》，连评委都觉得这个标题有点亮瞎双眼，最终劝导作者们把标题改得朴实一点 - 《An Empirical Evaluation of In-Memory Multi-Version Concurrency Control》。

这篇文章对 MVCC 机制的功能模块化拆分做的很好，分成 “并发控制协议”，“版本存储”，“垃圾回收”，“索引管理”这四个模块。本章节的内容在很大程度上参考了该经典论文。

3.1. 并发控制篇

3.1.1. MVTO

MVTO = MVCC + Time Ordering，这个可谓 MVCC 最早的版本，始于 1979 年 ...... MVTO 的核心思想很简单，利用每个事务 T 被分配的那个全局唯一的、单调递增的时间戳 Tid 来安排事务的序列化顺序。如图 10 所示，相较于 MVCC 基础款的 Tuple（元组）的物理版本布局格式，MVTO 增加一个条目：read-ts。该条目用来记录读取该 Tuple 相应物理版本的最新事务的序号。注意，在 MVTO 并发控制机制之下，任一事务，尝试读或者更新某个 Tuple 相应的物理版本，而该物理版本的写锁被其它事务占据了，那么该事务将被 DBMS 中止掉。

图 10. MVTO 如何处理一个包含 READ 和 UPDATE 的事务

具体而言，当某个事务 T 要读一个逻辑 Tuple A，DBMS 将会检索其所有的物理版本，如果 Tid 落在了某个物理版本的 [begin-ts, end-ts]，那么该物理版本就是事务 T 要访问的。请看图 10，因为 Tuple A 的物理版本 Ax 的写锁并没有被其它事务持有，故而事务 T 可以读取该 Ax，并且将 Ax 的 read-ts 更新为 Tid（如果 Tid 比 Ax 当前的 read-ts 更大）。

而关于事务 T 中的写操作，写操作总是在 Tuple 最新的物理版本上实施（判断的依据是该物理版本的 end-ts 字段为 INF）。如果满足以下两个条件：1）物理版本 Bx的写锁没有被其它事务占据；2）本事务的序号Tid大于物理版本 Bx的 read-ts 字段。事务 T 将给物理版本 Bx加写锁（相应的 txn-id 字段置为Tid），然后创建一个新的物理版本 Bx+1，同样也给物理版本 Bx+1加写锁（相应的 txn-id 字段置为Tid）。当最终要提交事务 T 的时候，DBMS 将把最新的物理版本 Bx+1的 begin-ts 和 end-ts 分别置为Tid和 INF，将上一个物理版本 Bx的 end-ts 置为Tid。另外，还需要把物理版本 Bx和 Bx+1 的写锁全部释放（txn-id 字段置 0）。

一句话掌握 MVTO：写写冲突，读读不冲突，有写拒绝读，未来读拒绝当前写。

3.1.2. MVOCC

MVOCC = MVCC + Optimistic Concurrency Control，这位是二哥，基于的 OCC 协议始于 1981 年 ...... 该机制是个乐观锁的思路，即实际系统中并发事务存在冲突的几率不高，故而没有必要那么死板，非得持有锁才读写。MVOCC 的大体思路是，事务里面的读写操作先本地做，在正式提交 DBMS 的时候再做校验，这样也大幅压缩了事务持锁周期。如图 11 所示，MVOCC 保持了 MVCC 基础款的 Tuple（元组）的物理版本布局格式。

图 11. MVOCC 如何处理一个包含 READ 和 UPDATE 的事务

具体而言，MVOCC 将事务的执行拆分成三个阶段：「Read」，「Validation」，「Commit」。在「Read」阶段，MVOCC 类似 MVTO，读请求需要根据事务序号 Tid 落在某个物理版本的 [begin-ts, end-ts]，并且该物理版本 Ax 的写锁并没有被其它事务持有，则 Ax 进入 ReadSet；写请求则是找到最新的物理版本（end-ts 字段为 INF），如果该物理版本 Bx 的写锁没有被其它事务持有，则事务 T 将给物理版本 Bx 加写锁（相应的 txn-id 字段置为 Tid），然后创建一个新的物理版本 Bx+1，同样也给物理版本 Bx+1 加写锁（相应的 txn-id 字段置为 Tid ），然后 Bx 进入 WriteSet。

当事务 T 尝试向 DBMS 提交时，事务 T 进入「Validation」阶段，此时 DBMS 再给事务 T 分配一个时间戳 Tcommit（用来给 WriteSet 中新创建的物理版本定义生命期，此值尽可能地新，以减少对并发读的干扰），以最终确定事务的序列化顺序。DBMS 会检查一下事务 T 对应的 ReadSet 中的各个 Tuple 的物理版本们，是否被更新了（被其它事务更新，并且人家事务已经率先一步完成提交）。注意，这个「Validation」阶段的意义在于它是解决并发事务冲突的最后一道防线。这里的检查通过，方可进入后续的「Commit」阶段，所有的 WriteSet 中的新创物理版本，Bx+1 的 begin-ts 和 end-ts 分别置为 Tcommit 和 INF，将上一个物理版本 Bx 的 end-ts 也置为 Tcommit 。另外，还需把物理版本 Bx 和 Bx+1 的写锁全部释放（txn-id 字段置 0）。

一句话掌握 MVOCC：写写冲突，读读不冲突，有写拒绝读，先决写拒绝乐观读。

3.1.3. MV2PL

MV2PL = MVCC + Two-phase Locking，这个机制看名称就知道，悲观锁的流派，一句话总结就是，先抢锁再干活，根据活的类型，决定抢啥类型的锁。如图 12 所示，MVOCC 在 MVCC 基础款的 Tuple（元组）的物理版本布局格式之上，增加了读锁的字段，read-cnt，用来记录当前有多少事务在读这个物理版本。

图 12. MV2PL 如何处理一个包含 READ 和 UPDATE 的事务

具体而言，MV2PL 执行事务 T 中的读操作，类似地，根据事务序号 Tid 落在某个物理版本的 [begin-ts, end-ts]，并且该物理版本 Ax 的写锁并没有被其它事务持有，那么增加该物理版本的 read-cnt 数值，Ax 进入 ReadSet。写操作的判断条件就更加严苛一些，还是找到最新的物理版本（end-ts 字段为 INF），如果该物理版本 Bx 的写锁没有被其它事务持有并且其读锁也没有被其它事务持有（read-cnt 字段为 0），则事务 T 将给物理版本 Bx 加写锁（相应的 txn-id 字段置为 Tid ），然后创建一个新的物理版本 Bx+1，同样也给物理版本 Bx+1加写锁（相应的 txn-id 字段置为 Tid ），然后 Bx 进入 WriteSet。

当事务 T 提交时，DBMS 给事务 T 分配一个时间戳 Tcommit（同样，用来给 WriteSet 中新创建的物理版本定义生命期，此值尽可能地新，以减少对并发读的干扰），所有的 WriteSet 中的新创物理版本， Bx+1 的 begin-ts 和 end-ts 分别置为 Tcommit 和 INF，将上一个物理版本 Bx 的 end-ts 也置为 Tcommit 。另外，还需要把物理版本 Bx 和 Bx+1 的写锁全部释放（txn-id 字段置 0）。此外，ReadSet 中各物理版本也需要逐个释放读锁。

一句话掌握 MV2PL：写写冲突，读读不冲突，有写拒绝读，有读拒绝写。

3.1.4. 进一步讨论

MVTO 和 MV2PL 看起来非常相似，从 Tuple 的物理版本布局格式来看，只是 read-ts 和 read-cnt 两个字段的区别。但是从设计层面来看，两者存在本质区别：MVTO 对并发事务的顺序控制是按照时间先后来排序的，故引入了 read-ts，那么后面开始的事务中的读操作将会阻止前面开始的事务的写操作，故 MVTO 本质是在按照时间顺序来排序事务；而在 MV2PL 中，read-cnt 字段描述的是当前版本的读锁个数，并不关心这些读操作是来自后面的事务还是前面的事务。因此 read-cnt 可以纯纯地视为一个共享锁。

对比上述这两位，在 MVOCC 机制里，一个事务里的读操作是不会更新物理版本中的任何字段的，这里就省掉了一些并发事务之间的协调，即一个事务里的读操作是不会干扰另一个事务针对同一个 Tuple 的相同物理版本的写操作。但是，还是那句经典的话 - “复杂性不会平白无故地消失，它只会转移到其他地方”，MVOCC 面临的挑战是，在提交事务的时候，DBMS 需要检查事务里的所有 ReadSet 是否合适（如果相关物理版本被其它事务更新，并且人家事务率先一步完成了提交，那么整个事务就失败），读操作比较弱势，这个对那些长时间运行的只读事务，并不是个友好的信号。

3.2. 版本存储篇

所有支持 MVCC 的 DBMS 都将版本数据和索引数据分开进行存储。我们可以将索引项看作 KEY-VALUE 键值对，其中 KEY 是被索引数据行中的某个字段值（可以是 PRIMARY KEY，此即为主键索引；亦可为非主键的其它字段，此即为二级索引，SECONDARY INDEX），值是索引对应的数据行的指针。如图 13 所示，通常索引数据的组织方式是 B 树结构以加速检索（B 树军团的阵容也益发强大，从传统的 in-place update 的 B-Tree，B+-Tree，到先今的引入 delta chain 的 Bw-Tree，Bε-tree，一句话，效率为王）。索引项的 VALUE 记录了数据行的指针，DBMS 就是根据这个指针，找到相应 Tuple（元组）的 version chain，扫描该链条以定位到某个事务可见的那个物理版本。

图 13. 版本存储之 Append-only (O2N)

进一步说明，在 MVCC 中，每次更新（UPDATE）都会创建一个新的版本数据。版本数据行中的指针负责指向前一个或者后一个版本数据，以此形成一个单向版本链。版本链不能是双向链表，因为双向链表的修改需要加锁，不能借助原子指令完成。那么该如何高效地组织这个单向版本链条呢？我们来着看看两类典型的机制。

3.2.1. 追加式存储

有关 Version Storage 的版本链组织，第一类为追加式（Append-only）存储机制，即在需要更新一个元组（Tuple）时候，DBMS 直接在主表中申请一个新的空白数据行，然后将该 Tuple 最新版本的数据复制一份到新申请的数据行空间，最后将变更内容应用到新申请的这一行。那么新旧版本的指针指向应该是怎么样的呢？这里分成两个流派，各有讲究：

• O2N（从老到新）：版本数据从老到新排列。如图 13 所示，索引项中指针指向的是该 Tuple 最老的版本数据，因此当有 UPDATE 操作时，索引项中指针指向无需更改，代价则是每次获取较新的版本数据需要遍历整条链表；
• N2O（从新到老）：版本数据从新到老排列。如图 14 所示，索引项中指针指向的是该 Tuple 最新的版本数据，因此当有 UPDATE 操作时，索引项中指针指向需要更改，收益则是可以很快获取到较新的版本数据，无需遍历整条链表；

图 14. 版本存储之 Append-only (N2O)

注意，在 Append-only (O2N) 方案中，由于无用版本的存在，该方案的性能高度依赖于版本数据的垃圾回收效率 - 如果垃圾回收能够将单链表维持在较短长度，那么查询性能将有显著提升，否则会很耗费时间。而对于 Append-only (N2O) 方案，常被诟病的索引项指针频繁修改问题也有解决办法，思路正如 Bw-Tree/Bε-tree 的优化：通过引入一个间接指向层，采用一个叫做 MappingEntry 的对象的值来指向某个 Tuple 版本数据链表的起点，当然， MappingEntry 对象本身的地址是不会变的。这样当某个 Tuple 的新版本数据产生时，只有这里间接指向层的 MappingEntry 对象记录的值需要改变，而索引项中指向 MappingEntry 的指针则不需要变更。这种优化极大利好拥有较多 SECONDARY INDEDX 的表，当然，付出的代价是需要额外的存储空间。

基于 Append-only 的版本存储方案，还面临一个挑战是如何有效管理非内联（non-inline）的属性值（大数据类型，这部分数据通常不存储在 Tuple 内，譬如 BLOB/TEXT 等类型）。按照 Append-only 机制，即使数据行中只有少量字段发生变更并且压根不涉及非内联字段，相应的 BLOB 等类型数据也同样要重复拷贝一份，这个显然带来了存储空间上的极大浪费。解决办法是参考智能指针的引用计数机制，允许同一 Tuple 的不同版本数据行指向同一个 BLOB/TEXT 对象，并且增加一项元数据来记录引用次数，便于后续的垃圾回收。

3.2.2. 增量式存储

有关 Version Storage 的版本链组织，第二类为增量式（Delta Storage）存储机制。如图 15 所示，该机制为版本数据存储维护两张表：一曰主表（Master Table），一曰增量存储空间（Delta Storage），索引项指针指向主表中的版本数据（业界通常的实现，主表维护的是最新版本数据），然后将版本数据链条上其它版本数据（以增量日志方式）存储在额外的 Delta Storage 空间。例如，业界的 MySQL InnoDB 和 Oracle 实现中，Delta Storage 具体是指用于 rollback 的数据段。故而，在更新逻辑数据行时，DMBS 先在 Delta Storage 申请一段空间，然后将被改动的属性的老版本数据写入其中，注意，这里不需要写入完整 Tuple 行。最后 DMBS 再在主表上原地更新（注意！这里是原地更新！） Master 版本的数据行。

图 15. 版本存储之 Delta Storage

Delta Storage 在执行某个 Tuple 的 UPDATE 操作时，表现会很出色，特别当 UPDATE 只是操作了数据行的子集属性（这个很常见的），这样 Delta Storage 就大大减少了内存的分配占用，并且也不存在外联数据版本（TEXT/BLOB 等类型）存储量过大问题。不过，Delta Storage 的缺陷也显而易见，在读为主的场景中，为了获得 Tuple 的某个版本数据，DMBS 需要从各个字段的版本数据链中获取到对应版本的字段值（需要频繁访问 Delta Storage），然后再进行拼凑，这就就带来了额外的访问开销。

3.2.3. 进一步讨论

以上两类有关版本数据的存储机制，可谓各有千秋。举例来说，追加式（Append-only）存储机制在分析场景表现更佳，因为其将版本数据存储在连续空间，这样当进行大范围的扫描时可以有效提升缓存命中率，包括对于配合硬件的预读优化也很友好。追加式存储机制给索引管理系统暴露的是实际的物理版本，这样的索引管理预留了优化空间（例如上文提到的间接指向层，避免频繁修改索引项指针）。不过，无论是 Append-only，还是 Delta Storage，这些版本存储机制都要求 DBMS 从中心化的数据结构（Main table、Delta Storage）为每个事务分配内存。DBMS 自然是要支持并发访问的，此时多个线程将同时访问/更新这里的集中式存储，从而导致访问竞争。为了避免这个问题，DBMS 可以对每个集中式的存储结构分而治之，所谓数据分区也，然后各自维护一系列单独的内存空间。这样，每个工作线程从单独的存储空间获取内存，因此可以消除此间的集中式访问竞争。

3.3. 垃圾回收篇

MVCC 机制在执行事务 UPDATE 操作时候就会创建 Tuple 新的物理版本，所以“存储空间焦虑”可以认为是 MVCC 机制的原罪。自古以来，凡提 MVCC，必配以高效且安全的 GC (Garbage Collection) 机制，否则都不好意思跟人打招呼。通常我们可以把 GC 机制分成三步：

• 找到已过期的物理版本；
• 将这些过期的物理版本从相应的 version chain 中移出，必要的话还要从索引项的指针指向上移除；
• 回收这些物理版本的存储空间；

何谓“过期”的物理版本？一曰成分不好，该物理版本是一个被中止的事务创建的；二曰英雄迟暮，该物理版本已经不在任何活跃事务的视线内。前者好筛选，后者的鉴别机制是：DBMS 会检查一个物理版本的 end-ts 字段，这个字段标明了该物理版本的生命期末尾，假若该数值已经小于所有活跃事务的 Tid 数值，那么可以安全地宣告该版本过期了。当然，这里的“所有活跃事务的 Tid ”这个信息很关键呀，DBMS 需要一个中心化的数据结构来管理、跟踪这部分信息。

为了让这个中心化的数据结构不至于成为访问瓶颈，一个常规优化项是引入粗粒度的 epoch 概念，即每个事务除了被分配一个单调递增的事务 ID，再分配一个 active epoch 值（这个值由 DBMS 整体维护，周期性地提升，同时维护一个 FIFO 队列，记录过往的 epoch）。每个 epoch 都记录了其关联的事务个数，当该 epoch 还是 active 的时候，DBMS 每处理完一个事务，那么该 epoch 相应的事务计数即增一；当某个事务完成了（无论是正常完成，还是被中止），相应的 epoch 的事务计数即减一。如果对于某个 epoch 满足三个条件：1）处于非 active 状态；2）事务计数为 0，即无相关活跃事务；3）前序的 epoch 们皆不持有任何活跃事务。那么 DBMS 可以放心地回收该 epoch 周期内新建的所有物理版本，对吧？

好了，高效的检测过期版本的方法有了，就剩怎么遍历了，这可是纯纯的体力活。以下是两种典型机制，一种是元组粒度（Tuple-level）的扫描，即逐个检查每个元组是否可见；另一种是事务粒度（Transaction-level）的 扫描，即逐个检查每个已经完成的事务，其创建的物理版本是否可见。

3.3.1. 基于元组粒度

基于元组粒度（Tuple-level）的 GC 机制很好理解，也容易实现。通常 DBMS 会引入背景线程周期性地扫描数据库以检测出 Tuple 的过去物理版本。该机制虽然简单但是效率不高，GC 性能在数据量增长时无法同步提升。业界比较好的实践是让 DBMS 维护一个 bitmap，映射发生过数据改动的 BLOCK（Tuple 元组旧的物理版本产生了，该版本将进入 GC 视野），这样 GC 的背景线程就可以跳过上一次 GC 以来没有发生过数据变更的 BLOCK，提升扫描效率。

图 16. 基于元组粒度的 GC 机制 - 扫描 Version Chain

还有一种典型的遍历机制是给背景线程引入“内援”，执行事务的 worker 线程们。DBMS 在执行事务的时候，本身就会遍历 version chain。这个过程中，worker thread 顺带就把过期的物理版本识别出来，记录在一个全局的数据结构中。这样 GC 背景线程就不需要亲自下场揪出过期版本了。不过，这种遍历机制只是跟 Append-only (O2N) 比较搭配，因为这种存储机制就是从 Tuple 最旧的物理版本开始遍历的，不会漏掉本 Tuple 已过期的版本。不过，引入的内援也不是国际主义战士，他存在所谓 “dusty corners” 问题，即只有相关 Tuple 有查询任务的时候，worker thread 这个内援才会顺带干活，假如逻辑数据创建多个物理版本数据，后续没有任何查询任务，那么这些版本数据就一直没办法得到清理。所以，通常 DBMS 还是会依赖 GC 线程做个兜底，定期做个过期版本的全量巡检。

3.3.2. 基于事务粒度

我们还可以通过事务粒度来做过期 Version 的 GC。DBMS 何时认为一个事务过期？答：当该事务创建的所有物理版本对于现有活跃事务均不再可见（这个判断条件，前面说过，看 end-ts）。如果一个 epoch 关联的所有事务均已过期，也即该 epoch 时代结束，而一个 epoch 时代结束意味着该 epoch 期间所有事务产生的所有物理版本均可以被安全清理。

图 17. 基于事务粒度的 GC 机制 - 扫描事务的 write-sets

这个机制相较于上述的元组粒度的，显然要简单多了。不过它也存在不足，如图 17 所示，DBMS 不能仅仅跟进每个 epoch 相关的活跃事务个数了，而要关心每个 epoch 其中的每个事务的 WriteSet，事无巨细，这个复杂度一下子就上来了，有木有？!

3.3.3. 进一步讨论

引入背景线程，基于元组粒度（Tuple-level）扫描过期 Tuple 版本并予以清理，这个机制是当前基于 MVCC 的 DBMS 中最常用的 GC 方案。无论如何，通过增加背景的 GC 线程数量总是可以提升它的清理效率。另外，如果存在长事务，DBMS 的性能会有较大影响，因为长事务意味着它开始之后的所有版本数据都得不到清理，这时候版本数据链就会变得很长，直到长事务完成或者被中止掉。

3.4. 索引管理篇

所有支持 MVCC 的 DBMS 都将版本数据和索引数据分开存储。我们可以将索引看作 KEY-VALUE 键值对，键是被索引的数据行中的字段值，值是索引对应的数据行的指针。

主键索引的情况比较简单，因为主键是保持不变的，索引的 Value 总是指向版本数据链的起点，比如在 InnoDB 中，主键索引的数据行就是指向主表的。在主键索引中，索引的键值对指针会发生什么样的变更，取决于 DBMS 使用了哪种的版本数据存储方式：

• 对于 Delta 存储，主表永远都是存的 master 版本数据，它是原地更新的，主表中数据行位置不发生改变，因此索引项 Value 记录的指针也没有发生改变；
• 对于 Append-only 存储，版本数据链有两种不同方向：
• O2N（从老到新），新的版本数据 Append 在版本链的末端，因此索引的 Value 指针始终指向链表的起点不变。只有在发生 GC 的时候才会调整指针地址；
  
• N2O（从新到老），每当产生新版本时，都需要调整索引值的指针，此时 DBMS 一般会在索引上进行 DELETE & INSERT 操作；

对于二级索引，Secondary Index，被索引的主表中的字段值（同时也是索引项中的 Key）可能发生改变，索引的 Value 指向的版本数据也有可能发生改变。这里的情况明显复杂多了，通常来说，我们有以下方案对索引项中的指针进行管理。

3.4.1. 逻辑指针

如图 18 所示，最常用的方案是建立一层中间表，让索引的 Value 能够一直不变，例如指向主键。这种方案也是 InnoDB 在使用的，所以我们通常说二级索引会包含被索引的字段值以及主键值。通过主键值将索引中的指针固定下来，这样每当版本数据链表起点发生改变时，只需要同时更新主键值对应的指针。如果一个表中存在许多二级索引时，这里的优化收益就很显著了。 当然，对基于二级索引的读就没那么友好，间接访问，需要回表。

图 18. 辅助索引的指针管理机制之逻辑指针

3.4.2. 物理指针

如图 19 所示，DBMS 也可以为二级索引的指针记录实际 Tuple 的物理地址。这种机制只是适用于 Append-only 的版本存储机制，当更新表中的某个 Tuple 的时候，DBMS 会更新所有相关二级索引的指针指向（一个二级索引，甚至可以对应多项物理指针）。在这种模式之下，DBMS 可以直接基于二级索引来查找某个 Tuple，而不需要根据该二级索引的字段值跟所有索引的版本进行比较，读写效率更高一些。但是，不得不说，物理指针的机制，管理起来还是比较复杂的。

图 19. 辅助索引的指针管理机制之物理指针

3.4.3. 进一步讨论

同样，不同的索引管理方式也有各自适合的场景。对于逻辑指针的索引管理机制，在写入频繁的场景下表现更好，因为二级索引只需要在索引字段值发生改变时才会改变，在读取场景下，它还需要对不同的版本链进行对比，因为同一个逻辑值有可能对应不同的物理值，例如 DELETE 后再 INSERT 同一个值；对于物理指针的索引管理机制，缺点之前已经提到过，频繁的更新场景会导致写入性能变差，但是在检索时就有它的优势了。

在文章 [8] 中，Uber 的工程师对 Postgres 吐槽点满满，原因即在于 Postgres 使用了物理指针管理二级索引，在使用过程中，Uber 的应用场景里会有非常多的二级索引，并且 Postgres 的二级索引是指向磁盘中的版本链起点的，故而在版本链起点发生变动时，多个二级索引的指针均需要修改，这个行为对于 Uber 写多读少的负载访问性能影响很大。最终，Uber 做了个决定，从 Postgres 迁移至 MySQL（有趣的是，Uber 起初使用的就是 MySQL，然后招募了一群熟悉并且热衷 Postgres 的工程师们，最后 ...... ）

四、放眼业界，必有我师

在上一篇章，我们详细介绍了几种典型的基于 MVCC 的并发控制协议：TO（Time Ordering），OCC（Optimistic Concurrency Control），以及 2 PL（Two-phase Locking）。整体而言，TO 与 2PL 属于悲观加锁式的并发控制协议，而 OCC 则是乐观验证式的并发控制协议。我们接着看一看云计算时代各家数据库产品是怎么实现 Snapshot Isolation 甚至 Serialization Isolation 事务隔离级别的。

本章节分别调研了 Google 的 Percolator，AWS 的 DynamoDB，Cockroach Labs 的 CockroachDB，Yahoo 的 Omid，以及 PingCAP 的 TiDB。这里面，Percolator 算是开宗立派式的实践，它属于偏向 OCC 这类乐观验证式的并发控制协议，跟随 Percolator 步伐的有 CockroachDB，TiDB，以及 Oceanbase 等等数据库产品；DynamoDB 的事务实现并没有依赖 MVCC，故而其事务的并发控制协议可以认为是另一大流派；Omid 则是少有的中心式事务并发控制协议，也是这些数据库产品的事务并发控制实现得“极其乐观的”，在事务这个领域里，也算是立了一个新门派。

4.1. Percolator

“Google 出品，必属精品”，云计算时代，Google 公开的各类技术在一次一次引领着业界探索的方向（早期的 GFS，BigTable，MapReduce，后来的 Kubernetes，这几年的 Transformer ...... ）。在分布式事务这块，Google 出品的 Percolator 同样值得反复研读，建议大家学习一下原文 [15] 。

Percolator 诞生的原因很朴素：Google 搜索的索引系统需要存储数十 PB 的数据（注：这个是 2010 年甚至更早时间的数据），传统的关系型数据库承载不了如此规模的存储量，故而 Bigtable 这类具备良好水平扩展性的 NoSQL 数据库便应运而生，稳稳地接住了这波流量。但是，日子久了，传统关系型数据库对 SQL 检索的支持，对事务能力的支持，让上层业务始终无法忘怀，尤其是这个分布式事务能力。在这方面，Bigtable 也是有些基础的，已经具备了支持单行的事务能力，故而 Google 的工程师们在 Bigtable 之上再抽象了一层 Percolator，支持跨机器多行的分布式事务能力。

如图 20 所示，正是因为 Bigtable 本身的行事务能力，Percolator 选择了简化架构设计，没有引入单独的事务协调者 - Transaction Coordinator 角色，而是将 Transaction Coordinator 的能力 - 管理事务的状态，打散到了每个客户端自己来管理。

图 20. Percolator 是个客户端实现，没有单独的 Coordinator 角色

从数据模型的角度，Bigtable 可以理解为是一个稀疏多维的持久化的键值对 Map [16]，一个键值对的格式如图 21 所示。在 Bigtable 中，一个 row 可以包含多个 column，Bigtable 提供了针对单行的跨 column 的事务能力，接下来我们也会看到，Percolator 多处利用了 Bigtable 单行事务来保证对同一 row 的多个操作的原子性。

图 21. Percolator 依托在 Bigtable 之上，而 Bigtable 可以视为一个稀疏多维的键值对 Map

为了实现跨行的分布式事务，如图 22 所示，Percolator 中的一列“c.”，在 Bigtable 的就映射出了“c:lock”，“c:write”，“c:data” 等多列出来。其中，“c:lock” 可以认为是持久化的锁，“c:write” 可以认为是记录数据最新可见版本的，“c:data” 则是用来保存数据本身。

图 22. Percolator 的一列，映射到 Bigtable 就成了表征“锁”，“可见性”，“数据”等含义的多列

Percolator 事务实现是标准的两阶段提交，分为 Prewrite 和 Commit 两阶段。在每个 Transaction 开始时会从 TSO 获取 timestamp 作为 start_ts，在 Prewrite 成功后 Commit 前，再从 TSO 获取 timestamp 作为 commit_ts。另外，在最终调用 Commit 之前，Transaction 的所有数据都缓存在客户端。具体协议实现，Percolator 秉承了谷歌一贯简洁而优雅的风格，下面直接对着图 23 来解读。

图 23. Percolator 事务协议的伪码，优雅，真的很优雅

4.1.1. 事务写

1. 事务开启时，即从 TSO 获取一个 timestamp 作为 start_ts_；

2. 选择第一个 Write 请求作为 primary，其它 Writes 请求则是 secondaries；

3. 先 Prewrite primary，成功后再继续 Prewrite secondaries。注意，为什么首先 Prewrite primary，这是有讲究的，后面 Failover 章节会详细解释。对于每个 Write 请求，以 Bigtable 行事务形式执行的 Prewrite 的逻辑如下：

• 以 Write.row 作为 key，检查 Write.col 对应的 “write” 列在 [start_ts, ∞] 之间是否存在数据。如果存在，则说明存在写/写冲突，直接中止整个事务；
• 以 Write.row 作为 key，检查 Write.col 对应的 “lock” 列是否被上锁，如果锁存在，直接中止掉整个事务。这种做法略显粗暴，不过确实简单有效；
• 以 start_ts_ 作为 Bigtable 的 timestamp，将数据写入 “data” 列。由于此时 write 列尚未写入，因此数据对其它事务不可见；
• 以 start_ts_ 作为 Bigtable 的 timestamp，以 {primary.row, primary.col} 作为 value 写入 “lock” 列。注意，这里一个事务内的所有写请求的 “lock” 列记录的都是 primary 信息，具体解释见 Failover 章节；

4. 如果一个事务内的所有 Write 请求均能够 Prewrite 成功，则进入 Commit 阶段，再次从 TSO 获取一个 timestamp 作为 commit_ts；

5. 先 Commit primary，注意，这里同样以 Bigtable 行事务能力执行，如果失败则中止整个事务：

• 以 primary.row 作为 key，检查 primary.col 对应的 “lock” 列的锁是否存在，如果锁已经被其它事务清理，则本事务失败；
• 以 commit_ts 作为 Bigtable 的 timestamp，以 start_ts_ 作为 value 写 “write” 列。相关的读请求会先读 “write” 列获取 start_ts_，然后再以 start_ts_ 去读取 “data” 列中数据；
• 以 primary.row 作为 key，删除 primary.col 对应 “lock” 列中对应的锁；

6. 到了这里，该事务事实上已经成功，对于剩余的 secondaries，异步的进行：将 start_ts_ 作为 value 写 “write” 列；删除 “lock” 列中对应的锁。不用担心，本事务所有写操作的可见性已经没有问题，secondaries 的这里的异步操作也一定会成功，这正是引入 primary lock 精巧之处；

4.1.2. 事务读

1. 事务开启时，即从 TSO 获取一个 timestamp 作为 start_ts_；

2. 读请求同样依赖 Bigtable 的行事务能力。首先，其以 row 作为 key，检查 column 对应的 “lock” 列在 [0，start_ts] 区间是否存在锁，如果有，那么就等待并根据需要在必要的时候主动清理锁。反正要等到这里的锁释放了，继而可以放心地基于 Bigtable 的行事务能力做干净的读；

3. 以 row 作为 key，检查 column 对应的 “write” 列在 [0，start_ts] 区间是否存在数据：如果没有，那么说明没有读到数据；如果存在，则根据 timestamp 的指示，到 “data” 列读取相应版本的数据；

4.1.3. Failover

Percolator 的事务执行过程可能面临两类错误：一类是底层 Bigtable 的 TabletServer 错误，这个无需 Percolator 多虑，Bigtable 作为一个分布式系统本身能够处理并自愈，坚决保证锁信息的持久化；另一类比较棘手，是 Client 遭遇了错误，残留了一些锁信息，阻碍后续的其它事务请求，怎么办？Percolator 的方法比较朴素，采用了一种异步清理机制。

假如事务 A 在执行过程出了问题，Client 挂了，残留了某些锁信息。事务 B 在执行过程需要加锁，遇到了冲突。如果此时 B 能够确定事务 A 是真的挂了，那么 B 可以主动清理 A 残留的这些锁信息。问题在于，B 如何确定事务 A 真的挂了？这个显然并不容易。Percolator 这里的小巧思就是上文反复 cue 到的 primary lock，每个事务都选择一个写请求对象（默认就选择第一个）作为提交（commit）与清理（cleanup）的同步点（synchronizing point）。具体来说：

• 事务 A 提交之前，一定检查一下它是否继续持有 primary lock；
• 事务 B 做清理之前，也一定要先检查 primary lock 是否还在，如果在，就可以安全清理；
• 
  

如果事务 A 的 Client 挂掉的时机已经过了 commit point，也就是至少 primary write 已经提交，那么事务 B 就有义务继续推进事务 A（就是做 4.11 章节的 5.b，5.c），这个情形也容易判别出来：事务 A 的 primary 对应的 “lock” 列已经拿掉，并且 “write” 列已经更新。另一种情形，事务 A 的 primary 对应的 “lock” 列还在，事务 B 可以确定此时事务 A 还没有提交，可以安全地回滚。

虽然 Percolator 提供的清理机制，从安全性上没啥问题，但是还是要谨慎，如果过于敏感地鼓励事务 B 清理事务 A，那么在事务 A 只是偶尔阻塞一下的场景下，会带来业务侧不必要的重试，对性能有影响。故而，Percolator 探索了一些探活机制，类似飞天女娲提供的临时节点，Percolator 中每个 worker 也向 Chubby 写一个 token，通过定期心跳续活，过期则自动被 Chubby 清理掉。故而其它 workers 可以通过观察某个 worker 的 token 文件来判定它是否处于存活态。

4.1.4. 隔离性

Percolator 事务的默认隔离级别是 Snapshot Isolation，自然可以解决“脏读”，“不可重复读”等问题，但是对于“幻读”，“写偏斜”等问题，Percolator 无法直接避免。

其一，Percolator 无法解决“幻读”。“幻读”主要来源于类似范围查询（range query），在一个事务内，两次查询无法阻止“多出”或者“少掉”一条符合查询条件的记录。要解决“幻读”问题，可以进一步引入范围锁（range lock）；

其二，Percolator 无法解决“写偏斜”。这里就不多解释了，Percolator 中的读并不会阻碍之前的写，故而类似上面医生值班的例子中，无法保证最后两个医生都选择了休假，导致无人值班的情形。

4.2. DynamoDB

AWS 的 DynamoDB 与 Dynamo，除了名字之外，在架构上几乎没有什么共通之处。DynamoDB 的作者们对这一点似乎特别在意 [17]，在阐述 DynamoDB 事务实现的相关论文中反复强调 😳。作为一款优秀的 NoSQL 数据库，DynamoDB 一方面具有良好的服务容量的水平扩展性，另一方面也因为不支持 SQL 查询与不支持事务操作而被挑战。相较于业界其它数据库产品，DynamoDB 实现的分布式事务有着很强的新意：

• 事务以单个请求的形式提交，这点类似 ZooKeeper 中的 MultiOps 操作，如图 24 中展示的；
• 虽引入单独的 Transaction Coordinator 来提供 2PC 的事务请求处理，常规且非事务性的读写请求却可不经过 Transaction Coordinator，但是还是能够提供整体上的可串行化的隔离性；
• 事务的更新是原地操作，DynamoDB 不支持 MVCC；
• 事务实现机制无锁，依赖时间戳做可序列化的排序；

所以，在 DynamoDB 中，提交一个事务请求，如图 24，事务写请求是 TransactWriteItems，向其中添加系列子请求，包括 PutItem，UpdateItem，DeleteItem，甚至 CheckItem；事务读请求则是 TransactGetItems，向其中添加子请求 GetItem。这种事务实现方式的好处很明显，一个事务的处理不会长时间阻塞其它请求。

图 24. DynamoDB 支持的两类请求，常规读写请求与事务请求

图 25 则展示了 DynamoDB 中请求处理工作流。无论是事务请求，还是非事务请求，都会首先到达做请求路由的前端机。这些前端机会根据请求要访问的键值，决定将请求路由给哪些存储节点。具体的键值区与存储节点的映射关系，维护在一个元数据的子系统中。此外，负责请求路由的前端机还会做必要的身份认证与权限鉴权的操作。对于事务请求，在通过身份认证与权限鉴权之后，会被进一步路由给 Transaction Coordinator，这里会执行 2 PC，完成一个个事务的执行。

图 25. DynamoDB 中一个读写访问请求（含事务）的工作流

DynamoDB 中的 Transaction Coordinator 会用当前时钟（Clock）的时间作为时间戳分配给接收到的每个事务，这个时间戳关乎事务的执行顺序。事实上，每个 Transaction Coordinator 均在独立分配时间戳，独立处理分布式事务。这些 Transaction Coordinator 之间的时钟是否同步，其实并不会影响事务执行的 serializability，但是 DynamoDB 依旧引入了高精度的时钟同步服务，一则提供事务处理的成功率，二则呈现出类似真实时间的时间戳，便于分析。

4.2.1. 事务写

有关事务写，如图 26，Transaction Coordinator 执行的是同样是标准的 2 PC。在 Prepare 阶段，Coordinator 给每个 SN（Storage Node）发送 Prepare 请求。SN 在处理 Prepare 请求时候，首先检查数据项是否存在：

• 如果数据项存在，首先检查事务附带的 Condition 是否成立，然后是一些系统限制（存储空间等因素）检查，最后再检查两项：
• 该数据项上次写成功的时间戳要小于本事务的时间戳；
• 该数据项没有正在进行中的写事务。这些条件都检查通过的话，将新建数据项的 ongoingTransaction 置为本事务 Id；
• 如果数据项不存在，则创建该数据项，然后同样检查事务附带的 Condition 是否成立，包括系统限制检查，最后再比较本事务的时间戳与数据项所在分区所记录的最新的删除操作对应的时间戳（这是解决数据项被删除的风险，即无法比较这两事务的时间戳大小）。这些条件都检查通过，则将新建数据项的 ongoingTransaction 置为本事务 Id；

在异步地发送 Prepare 请求给相关 SN 之后，Coordinator 进入了同步等待，等待所有的 Prepare 请求响应。然后确认是否所有的 Prepare 请求均是成功的状态：

• 如果全部成功，则进入事务提交阶段，Coordinator 给每个 SN 发送 Commit 请求。SN 在处理 Commit 请求时，同样检查数据项是否存在：假如数据项不存在或数据项当前 ongoingTransaction 并非本事务，那么提交失败；如果数据项存在并且记录的 ongoingTransaction 是本事务 Id，那么开始应用写操作，并将数据项记录的 ongoingTransaction 置空，将数据项记录的上次写成功的时间戳更新为本事务时间戳；
• 如果有 SN 返回的 Prepare 响应是失败态，则进入事务取消阶段，Coordinator 给每个 SN 发送 Cancel 请求。SN 在处理 Cancel 请求时，同样检查数据项是否存在：假如数据项不存在或数据项当前 ongoingTransaction 并非本事务，那么取消失败；如果数据项存在并且记录的 ongoingTransaction 是本事务 Id，那么将数据项记录的 ongoingTransaction 置空，并且如果该数据项正是本事务在 Prepare 阶段创建的话（翻出数据项记录的上次写成功的时间戳，一看便知），还需要清理该数据项；

图 26. DynamoDB 中一个写事务处理流程的伪码

4.2.2. 事务读

有关事务读，很有趣，也是 2 PC 的实现，但是与上述事务写的 2 PC 实现完全不同，很是直白简洁。传统的事务读实现，同样需要引入时间戳，并且该时间戳还需要记录在数据项中，这将本来比较轻的读操作默默变成了一个比较重的写操作。DynamoDB 不愿意承受这样的读延迟，故而另辟蹊径。

在第一阶段，Coordinator 给事务中 read-set 涉及的所有数据项发送读请求，每个 SN 在执行读请求时，如果检查发现该数据项有进行中的写事务，该读请求立即失败；否则，返回给 Coordinator 两部分内容：1）数据项的值；2）该数据项当前记录的已提交的 LSN（Log Sequence Number，数据项上一次写的 Sequence Number，一个单调递增的值）。

在第二阶段，Coordinator 给事务中 read-set 涉及的所有数据项再次发送读请求，这次，每个 SN 检查数据项的 LSN 与上次返回的值是否一致，如果一致，说明数据没有修改，读事务即可成功返回给客户端。

4.2.3. Failover

类似 Percolator 的 TabletServer 本身具备的故障自愈能力，DynamoDB 的 StorageNode 本身也具备容错能力，故而事务在执行过程中，也无需考虑在这些依赖的容错问题。

紧要的是 Transaction Coordinator 本身的服务容错。Transaction Coordinator 将每个事务信息包括它的 2 PC 执行结果一一持久化在 ledger （这是 DynamoDB 的一张表，以事务 Id 作为 Key），然后有个 recovery manager 角色后台定期巡检这个 ledger，如果发现某个事务长时间未完成，recovery manager 会将该事务重新指派给其他的 Transaction Coordinator 执行。注意，即使多个 Transaction Coordinator 执行同一个事务，也没有关系，DynamoDB 的事务请求执行是幂等的，相同的请求会被 SN 节点忽略。

4.2.4. 隔离性

DynamoDB 的事务实现是 Serializable 可序列化的隔离级别。可以解决“脏读”，“不可重复读”，“幻读”，“写偏斜”等等问题。如图 27，如 AWS 官网公示的，DynamoDB 事务 - TransactWriteItems 和 TransactGetItems，与其它操作请求之间的隔离性保障大多也都是 Serializab 隔离级别。

图 27. DynamoDB 对于事务操作与其他操作请求之间的隔离性保证 [18]

4.3. TiDB

TiDB 的事务机制，可谓 Google Percolator 的忠实拥趸。如图 28 所示，当一条事务在会话中启动后，所有的读取和写入都将基于 MVCC 机制访问数据，写入的内容被缓存在事务内存中，直至从客户端收到 Commit 语句，TiDB Server 开始使用 Percolator 的两阶段事务协议将这些更改提交到 TiKV 存储系统。

图 28. TiDB 中一条事务写请求的工作流

值得一提的是，正如 Percolator 论文中提到的一处优化，在收到所有 Prewrite 请求响应并且确认均为成功态，那么 TiDB Server 仅需要再成功提交 primary key，即可确定该事务已经成功，此时可以响应客户端，其余 secondary keys 的提交可异步进行。具体如图 29，当 TiDB Server 收到 COMMIT 指令，需要以下三个步骤方可响应客户端：

• 并发地发送 Prewrite 请求给 TiKV，并等待全部响应；
• 从 TSO 再次获取时间戳，作为提交阶段的时间戳标记（Commit TS）；
• 完成 primary key 的提交；

也就是说，TiDB Server 至少需要两个 RTT 才能提交一条事务。其余的 secondary keys 则可以通过背景任务，异步地提交相关改动。

图 29. 提交一条读写事务，至少需要两个 RTT 方可响应客户端，这里有优化空间吗？

这里要介绍 Percolator 流派的一个关键优化 - Async Commit。其目标很明确：当第一阶段 Prewrite 成功完成即可确认事务成功，继而全部的 Commit 请求（包含 primary key）均可异步推进。这个并不简单，需要解决两大挑战：

• 如何确定，“所有”的 keys 都已经成功完成了 prewrite 请求？
• 如何确定，一个事务对应的 Commit TS？

第一个挑战，如何确定事务中相关的 keys 都已经成功完成了 prewrite 请求。在引入 Async Commit 改动之前，整个事务的状态是可以通过 primary key 的状态来确定的，所有的 secondary key 也都保存了指针指向 primary key。那么引入 Async Commit 之后呢？如图 30，primary key 也要保存所有 secondary keys（原先只要查看 primary key 的“lock”列是否存在即可确认状态，现在则在“lock”列依旧存在的情形下，还需进一步检查所有的 secondary keys 的状态）。自然，这个也就要求事务中包括的 keys 不能太多，否则 primary 不仅仅是担子增加了，更是要被直接压垮了。在 TiDB 的实现中，使用 AsyncCommit 的事务请求最大支持 256 keys，然后这些 keys 的大小最大不超过 4096 字节。

图 30. 为了支持 AsyncCommit，Primary 担子更重了，要记录所有 secondary keys

第二个挑战，如何确定一个事务对应的 Commit TS。事实上，TiDB 事务支持快照隔离性（Snapshot Isolation）以及线性隔离性（Serialization Isolation）两种选择，所以，这里的 Commit TS 计算就很有讲究。具体 TiDB 的实践是：每个数据项引入一个 Max TS 属性，每次事务读，拿自己的事务时间戳来更新这个值。故而，对于一个恢复中的事务，TiDB Server 会收集事务中各数据项的 Max TS，取其中最大值，再加一（这样是为了支持可重复读隔离级别），这个值与从 TSO 获取的时间戳对比，取较大者作为 Commit TS（尽可能地避免其它读事务被阻塞等待）。这样我们可以保证 Failover 恢复的事务不会打破快照隔离性，因为当前本事务确定的 Commit TS 大于过往的全部事务读的时间戳。

4.4. CockroachDB

如图 31 所示，CockroachDB 是为了解决 global 的 OLTP 工作负载而诞生的 SQL DBMS。它的初始目标有三，曰 horizontally scalable，曰 high availability，曰 strong consistency。从名字上就能够直观地感受到这款数据库产品在服务高可用这个维度是多么的顽“强”。另一方面，CockroachDB 在事务实现上做的也是相当惊艳，基于跨地域部署的实际情况，它居然提供了 serializable 的事务隔离级别，并且还保持了不错的读写性能。

图 31. 一个实际的 CockroachDB 的集群部署架构，横跨欧洲、北美、澳洲三地

CockroachDB 的代码是开源的 [28]，其在 SIGMOD'20 也发表了文章详细介绍设计实现 [23] 。网上研究 CockroachDB 的文章很多，属于常看常新的新世代领军 NewSQL 数据库产品，确实值得反复研读的。本文不准备展开做具体分析，我们来看一看 CockroachDB 在实现上与 Percolator 的诸多相似之处（这个倒也不奇怪，毕竟 CockroachDB 创始团队的核心成员 Spencer Kimball，Peter Mattis 和 Ben Darnell 都是从 Google 出来的 😄），甚至可以这么说，CockroachDB 真正把 Percolator 这个分布式事务流派给发扬光大了，不信你瞧：

• 如何保证事务的 atomicity，关键即在于事务提交之前，其所有的写操作都得是临时的。如前文所述，Percolator 中的一列“c.”，在 Bigtable 映射出“c:lock”，“c:write”，“c:data” 等多列。其中，“c:lock” 可以认为是持久化的锁，“c:write” 可以认为是记录数据最新可见的版本，“c:data”自不必多说，是用来保存数据本身的。CockroachDB 有类似的做法 - write intent [29]，这个字段不妨视为“c:lock”与“c:write”的合体，即兼顾了数据可见性以及互斥锁的能力；

• 如何保证事务状态的 consistency，Percolator 选择事务中第一个写请求作为该事务的 primary lock，可以认为 primary lock 成为了 failover 场景下正确恢复事务状态的 synchronizing point。CockroachDB 做法类似，引入了一个 meta 表来记录事务状态。具体做法是，在第一阶段完成之后，transaction coordinator 会在 meta 表中写入事务状态数据，事务状态置为 STAGING。注意，meta 表也是个逻辑存在，其实也是事务中第一个写请求所在的数据分区，meta 表的 key 使用了特殊前缀标识以区分普通数据。另外，meta 表的每行事务状态也都记录了该事务所包含的所有写操作的键值，这个也是为了类似 Async Commit 优化所精心设计的；

• 在保证事务的 isolation 属性上，支持 Repeatable Read 隔离级别已然是常规操作。Percolator 保证 Repeatable Read 隔离级别的关键设计是引入 start_ts，commit_ts 两个阶段的时间戳。事务读会根据自己的时间戳（start_ts），比对“c:lock”以确保没有并发的写事务（由最新写事务的 start_ts 更新），比对“c:write”以确保拿到的是小于自己时间戳的最新版本的数据（由最新写事务的 commit_ts 更新）。CockroachDB 的做法类似，不过更加的简单粗暴：每个分区维护“range”-> “事务读的最大版本号”，事务写的第一阶段给各个写操作发送 write intent 时候，返回值即携带对应“range”的“事务读的最大版本号”，如果事务写当前确定的时间戳版本号小于一众返回值中最大版本号，那么事务写就需要考虑提升自己的时间戳版本号到更安全的水位。简单来说，为了支持 Repeatable Read，Percolator 中的“写”阻塞“读”，而 CockroachDB 则是“读”倒逼“写”升级为更加新的版本；

CockroachDB 之于 Percolator 的创新之处还是在性能优化上，也就是我们在 TiDB 篇提到的 Async Commit。当然，由于 CockroachDB 实现在前，并且一直拥有着活跃的开源社区，我们有理由相信，无论是 TiDB 还是 Oceanbase，在这点上的优化应该都是在致敬 CockroachDB 😄

此外，CockroachDB 在 Snapshot Isolation 的事务隔离级别基础之上，进一步支持 Serializable Isolation 的事务隔离级别选项，它的实现方式也很朴素：相较于给 Range 加读锁这类悲观方式，CockroachDB 的做法更为乐观 - 每个事务写跟踪自己读过的所有数据的 Range，在事务提交之前，检查一下自己读过的这些 Range 是否发生过修改，如果有，该事务就不能提交。是的，就是这么简单直接，一举破解 phantom 与 write skew 两大难。当然，为此要付出的执行效率代价也是很大的，大家想一想，有没有其他更好的办法？

4.5. Omid

Omid 是 Yahoo 的作品，诞生的背景几乎与 Google 的 Percolator 如出一辙，Yahoo! 依赖 Hbase 来处理广告，社交 Feed 等负载，但是 Hbase 仅提供单行原子性（类似 Bigtable），不提供跨行事务，故而，Omid 项目应运而生了，期望在不改变 Hbase RegionServer 的前提下，实现一种高吞吐的 Snapshot Isolation 隔离粒度的事务机制。

Omid 无疑是成功的。首先是学术上，通过布道三部曲，Omid 很好地引领了一波分布式事务的探索浪潮：

• ICDE'14，"Omid: Lock-free transactional support for distributed data stores"；
• FAST'17，"Omid, reloaded: Scalable and highly-available transaction processing"；
• PVLDB'18，"Taking omid to the clouds: fast, scalable transactions for real-time cloud analytics"；

工业上，Omid 自 2013 年在 GitHub 开源，2016 年即捐赠给 Apache 基金会，进入孵化状态，然后 ...... 没有然后了，至今还是孵化状态 😳 。不过，是金子总会发光的，另一顶级开源项目 Apache Phoenix - 在 Hbase 之上提供了 ANSI-SQL 访问能力 [26]，在 2017 年即集成了 Omid 的事务解决方案，随后更是成为 Phoenix 官方默认推荐的事务机制。

相较于 Google Percolator 这类事务实现机制，Omid 绝对是一种乐天派的事务机制，它代表的是中心化的分布式事务机制，架构更加地优雅简洁。有趣的是，作为后起之秀，Omid 毫不掩饰对 Percolator 的吐槽，认为 Percolator 基于 Lock 的方案虽然简化了事务冲突检查，但是将事务驱动完全交给客户端，导致在客户端故障情况下，遗留的 Lock 痕迹会影响到其他事务的执行。另一个吐槽点是 Percolator 引入的 lock 和 write 列，Omid 认为这给数据库系统额外增加了不小的开销。相较而言，Omid 这类 Optimistic 事务方案完全由中心节点来决定 Commit 与否，并且事务 Recovery 机制也会更简单。最重要的是，Omid 更容易适配到不同的分布式存储系统，侵入性很小。

如图 32 所示，TSO 是一种中心化的架构，应用程序将请求发送给事务客户端（Transaction Client），后者总是首先要跟 TSO（Transaction Status Oracle）交互，这里是关键之处，它负责管理事务状态，包括状态仲裁，同时也包含有 Time Oracle 组件（这里插一句，时间戳服务在分布式事务中是如此的关键，其服务稳定高可用一直以来都是研发同学们在追求的目标。阿里云自研了无主高可用时间戳服务，相关工作发表在 VLDB'24，感兴趣的同学可以了解一下 [30]）。Transaction Client 首轮与 TSO 交互就是取号，该单调递增的时间戳序号也会作为事务本身的序号标志，然后呢，Transaction Client 乐（无）观（脑）地将请求直接写入 DataStore。可是这个写入不一定作数的：一来，什么时候可见需要遵循 Snapshot Isolation 隔离性要求；二来，假如违背了 Snapshot Isolation 隔离性的要求，那么这个写请求甚至是要被废弃。这里的仲裁权在 TSO，Transaction Client 随即要把事务包含的各个写请求一股脑地发送给 TSO 仲裁。

图 32. Omid 事务解决方案的三大组件：事务客户端，TSO，DataStore

这里要首先强调一下，Omid 支持的是 Snapshot Isolation 的事务隔离级别。在前文描述中，我们可以看到，SI 事务隔离级别更多关注的还是 write-write 冲突，故而实际 TSO 要仲裁的只有事务中的写操作们。具体来说，我们看下 Omid 中事务写的整个过程：

• Client 向 TSO 申请一个时间戳，作为事务标记，亦是事务起始时间戳 start_ts；
• Client 乐观地向 DataStore 写所有行，注意，如图 33 所示，这里的数据项包括版本信息（即 start_ts，同时也是这个事务标志），还包括一个 commit 列，初始为空，用来标记这个数据项版本是否已经提交。具体实现中，commit 列使用 Hbase 的 "shadow cell"，这里最终会保存提交时间戳 commit_ts。它存在的目的可以概括为一句话 - 让客户端和 RegionServer 都能在不加锁、不中断写路径的情况下判断某个版本是不是已经提交，从而实现 SI 快照事务隔离级别；
• Client 向 TSO 发起仲裁，仲裁请求中包括了事务里面所有写请求的的键值，以及事务的初始时间戳 start_ts。TSO 拿到仲裁请求后，检查该事务中所有写请求对应数据项的 last_commit 是否大于本事务的 start_ts：
• 如果存在大于的情形，则仲裁事务失败，TSO 向 Commit Table 发起一次写（注意，这里是条件更新），将事务状态标记为 Abort；
• 如果不存在大于情形，则仲裁事务成功，TSO 为该事务再申请一个提交时间戳 commit_ts，向 Commit Table 发起一次写（注意，这里是条件更新），将事务状态置为成功（即更新 Commit Table 中该事务项 commit 时间戳）；
• 后台线程异步地更新数据状态：如果事务 commit 成功，则异步地修改 DataStore 中对应数据项的 commit 列为 commit_ts，并异步地删除 Commit Table 中相应的事务项；

图 33. Omid 中的数据（存放在 Data Table）与 metadata（存放在 Commit Table）

再继续看 Omid 中事务读的整个过程：

• Client 向 TSO 申请一个时间戳，作为事务标记，亦是事务起始时间戳 start_ts；
• 根据这个时间戳，直接到 DataStore 读数据：
• 如果对应数据项的 commit 列（也即最新事务写的 commit_ts）小于自己的事务时间戳（start_ts），那么可以直接安全返回；
• 如果对应数据项的 commit 列为空，那么就去 Commit Table 查询对应的事务状态：
• 如果事务已经提交，那么该版本有效，只是 commit 列尚未修改，Client 可以“主动”帮忙修改下 commit 列，然后正常读取即可；

• 如果事务还未提交，这个时候其实会不同的选择，简单粗暴的办法，Client 可以选择“主动”abort 掉该事务，不犹豫，直接坐实该事务的失败态；

总体而言，通过引入中心化的轻量 TSO，叠加上 shadow cell 以及 commit table 这两个精巧的设计组合，Omid 实现了简单高效的 Snapshot Isolation 隔离级别的事务实现，并且基于一个大前提 - Omid 是在不修改 HBase 内核的情况下实现的上述目标。所以，相较于 Percolator 流派，我们必须要承认，Omid 在 HBase/Phoenix 场景下给出了一个优雅的、工程化程度很高的分布式事务解决方案，让我们为 Omid 点赞！

五、厚积薄发，功不唐捐

行文到最后，聊一些与本文主题 - 分布式事务不太相关的一些感想吧。

这几年 AI 浪潮一波一波涌来，相信每一位技术人员都无法置身事外。我也一样，从逐步习惯 ChatGPT 替换传统的 Google 搜索，到全面拥抱 Cursor 这类编程 Agent，从年初 DeepSeek 大热后开始学习基模，到近期自身服务主动拥抱 MCP Agent 生态 ...... 纵然这般，我相信，传统的分布式系统技术需要坚守，需要重视，需要演进。

不仅仅是我，相信每位同学或主动拥抱，或被动裹挟，都在全面进入由 AI 开启的新一轮的大争之世，各位的选择，或加入基模训练的军备竞赛，或选择助力 MCP/A2A 生态建设，或投身 Agent 探索前沿，即使选择观望，可能也在将自身服务以 MCP 形式暴露出去，躬身入局，等待被大生态集成 ...... 纵然这般，我坚信，并非要做个二选一的取舍。须知 AI 也非无本之木，终是在存储/计算/网络等基础设施之上长出的最茂盛大树，故而当此之时基础设施之稳定性亦处于前所未有之重要时刻。从事基础设施研发的同学们，谨记厚积薄发，功不唐捐这八字箴言，加油 💪！

参考资料：

[1] 共识协议的技术变迁 -- 既要“高”容错，又要“易”定序，还要“好”理解

[2] “日志＝数据库”？聊一聊日志背后的抽象

[3] Seata, an easy-to-use, high-performance, open source distributed transaction solution，https://github.com/apache/incubator-seata；

[4] 聊一聊分布式系统中的时空观构建

[5] An Empirical Evaluation of InMemory MultiVersion Concurrency Control，https://www.vldb.org/pvldb/vol10/p781-Wu.pdf；

[6] Multi Version Concurrency Control，https://marsishandsome.github.io/2019/06/Multi_Version_Concurrency_Control；

[7] Paper Reading：聊一聊 MVCC，https://jiekun.dev/posts/mvcc/；

[8] Why Uber Engineering Switched from Postgres to MySQL，https://eng.uber.com/postgres-to-mysql-migration/；

[9] The Part of PostgreSQL We Hate the Most，https://www.cs.cmu.edu/~pavlo/blog/2023/04/the-part-of-postgresql-we-hate-the-most.html；

[10] Building Consistent Transactions with Inconsistent Replication，https://irenezhang.net/papers/tapir-sosp15.pdf；

[11] Introduction to the OceanBase Transaction Engine: Features and Applications，https://en.oceanbase.com/blog/2615446272；

[12] 事务的弱隔离级别之 Serializability，https://zhuanlan.zhihu.com/p/440149077；

[13] 事务的隔离级别介绍，https://zhuanlan.zhihu.com/p/639326508；

[14] Serializable Isolation for Snapshot Databases，https://ses.library.usyd.edu.au/bitstream/handle/2123/5353/michael-cahill-2009-thesis.pdf；

[15] Large-scale Incremental Processing Using Distributed Transactions and Notifications，https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf；

[16] Database · 原理介绍 · Google Percolator 分布式事务实现原理解读，http://mysql.taobao.org/monthly/2018/11/02/；

[17] Distributed Transactions at Scale in Amazon DynamoDB，https://www.usenix.org/system/files/atc23-idziorek.pdf；

[18] Amazon DynamoDB Transactions: How it works，https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/transaction-apis.html#transaction-isolation；

[19] TiDB Development Guide - Transaction，https://pingcap.github.io/tidb-dev-guide/understand-tidb/transaction.html；

[20] Async Commit, the Accelerator for Transaction Commit in TiDB 5.0，https://www.pingcap.com/blog/async-commit-the-accelerator-for-transaction-commit-in-tidb-5-0/；

[21] OceanBase: A 707 Million tpmC Distributed Relational Database System，https://vldb.org/pvldb/vol15/p3385-xu.pdf；

[22] PALF: ReplicatedWrite-Ahead Logging for Distributed Databases，https://www.vldb.org/pvldb/vol17/p3745-xu.pdf；

[23] SIGMOD 2020 | CockroachDB: The Resilient Geo-Distributed SQL Database，https://www.cockroachlabs.com/guides/cockroachdb-the-resilient-geo-distributed-sql-database-sigmod-2020/；

[24] CockroachDB Transaction Layer，https://www.cockroachlabs.com/docs/stable/architecture/transaction-layer；

[25] 分布式事务：从 2PC 到 OMID，https://zhuanlan.zhihu.com/p/32858033；

[26] Apache Phoenix - OLTP and operational analytics for Apache Hadoop，https://phoenix.apache.org/；

[27] Apache Omid，https://omid.incubator.apache.org/index.html；

[28] CockroachDB source code，https://github.com/cockroachdb/cockroach；

[29] CockroachDB docs - Architecture - Transaction Layer，https://www.cockroachlabs.com/docs/stable/architecture/transaction-layer#write-intents；

[30] Timestamp as a Service, not an Oracle，https://www.vldb.org/pvldb/vol17/p994-li.pdf；

来源  |  阿里云开发者公众号

作者  |  朱云锋