一、InnoDB ACID

正确理解事务的 ACID 性质不是一件简单的事。本章尝试从概念上讲述 InnoDB 事务 ACID 的实现。

A database system must ensure proper excution of transactions despite failures —— either the entire transaction executes, or none of it does. Furthermore, it must manage concurrent execution of transactions in a way that avoids the introduction of inconsistency.

书中这句话很好的解释了 ACID 之间的关系。Consistency(一致性)是数据库事务的根本目标,Atomicity(原子性)、Isolation(隔离性)、Durability(持久性)则是保证一致性的协同手段。

原子性指的是事务中的多个操作要么都成功执行,要么都没有执行。用转账来举例子,就是用户 A 的钱减少和用户 B 的钱增加这两个步骤必须要么都成功,要么都失败。

但是,原子性不足以保证一致性。考虑下面的例子,A 和 C 同时和 B 转账:


// A.money = B.money = C.money = 100
// A -> B:
A.money -= 100;
B.money += 100;


// C -> B:
C.money -= 100;
B.money += 100;

即便我们能保证这两个转账操作是原子的,但是这两个事务面临着典型的并发问题。最终 B.money 的结果可能是 200,导致了整个系统的不一致。

为了保证并发竞态下的一致性,事务引入了隔离性,保证每个事务的执行不会被系统中其他正在并发执行的事务所影响。

类似的,原子性和隔离性保障了数据库系统在正常运行时的一致性,持久性则保障了数据库系统崩溃后,也能恢复到一致的状态。

接下来会介绍 WAL、Locking、MVCC 等 InooDB 用来达成 ACID 的技术。

1.1 WAL

实现 Atomicity 和 Durability 一般而言有两种方式:Shadow PagingWAL(Write-Ahead Logging)。例如旧版 SQLite 就是使用 Shadow Paging 技术,不过这种技术缺陷较大,现代 DBMS 一般都采用 WAL,包括 InnoDB。

WAL 是用于保证原子性和持久性的技术。简单来讲,WAL的核心思想是数据文件(真实表数据)的修改必须在这些动作由日志记录之后再写入。遵循这个原则,数据库不需要每个事务提交时都刷写数据页面到磁盘(随机写),只需要保证日志提交到磁盘上即可(顺序写)。

WAL 一般由两部分组成:Redo Log 和 Undo Log。

Redo Log(重做日志)用来实现事务的持久性。Redo Log 由两部分组成,一是内存中的 Redo Log Buffer,二是磁盘上的 Redo Log File。在一次事务中的每条 SQL 都会产生一条 Redo Log 保存在 Buffer 中,在最后 Commit 时,将 Buffer 中的日志写入到磁盘上的文件中,确认写入完毕后,事务的提交操作才算完成。Redo Log 记录的一般是物理日志,也就是会保存具体逻辑行所在的物理页信息,来保证快速重做。‘

Undo Log(回滚日志)用来保证事务的原子性。当事务需要回滚时,需要通过 Undo Log 来回滚记录。具体来说, Undo Log 保存的是逻辑日志,也就是一条 INSERT 语句对应的 Undo Log 是相应的 DELETE 语句,UPDATE 语句对应的是相反的一条 UPDATE。另外,Undo Log 还是 InnoDB 实现 MVCC 的关键。

具体 Redo Log 和 Undo Log 的协作我们将在 Crash Recovery 一节中详细阐述。

1.2 Lock

InnoDB 通过 WAL 获得了原子性和持久性,通过锁机制来保证隔离性。

类似于线程同步中使用的读写锁,InnoDB 实现了标准的行级锁:

  • 共享锁(S 锁):允许事务读一行数据
  • 互斥锁(X 锁):允许事务删除或更新一行数据

同时,InnoDB 还支持表锁,为了不同级别锁之间的高效率,InnoDB 引入了意向锁(Intention Lock)。

意向锁的主要用途是为了表示是否有事务锁定了表中的某一行数据,提高申请表锁的效率(如果没有意向锁,那么申请一个表锁就需要遍历每行数据看是否有互斥的锁存在)。

对于行锁而言,InnoDB 有三种算法:

  • Record Lock:单个行记录上的锁
  • Gap Lock:间隙锁,锁定一个范围,但不包括记录本身
  • Next-Key Lock:Gap Lock + Record Lock,锁定一个范围,并且锁定记录本身。

举例而言,假设我们有这么一张表:

a (Primary Key) b (Key)
1 1
3 1
5 3
7 6
10 8

那么,其中存在的 Gap Lock 为:(-wq, 1), (1, 3), (3, 6), (6, 8), (8, wq),而 Record Lock 即使主键索引的各行。

于是,当我们执行

SELECT * FROM z WHERE b = 3 FOR UPDATE

在 REPEATABLE READ 隔离级别下,由于 b 是辅助索引,首先会为主键加上 Record Lock,即锁住了 (a = 5),然后是 Next-Key Lock对,即(1, 3],同时,InnoDB 还会为辅助索引的下一个键值加上 Gap Lock,即(3, 6)。

于是:


// 下面三个语句因为锁的存在不能立即执行,会阻塞住
SELECT * FROM z WHERE a = 5 LOCK IN SHARE MODE;
INSERT INTO z VALUES (4, 2);
INSERT INTO z VALUES (6, 5);
// 下面的语句可以正常执行
INSERT INTO z VALUES (8, 6);
INSRET INTO z VALUES (2, 0);

Next-Key Lock 和 Gap Lock 主要是为了解决幻读问题,对于 InnoDB 而言,REPEATABLE READ 隔离级别即已经完全解决了锁引发的问题(脏读、不可重复读、幻读)

需要注意的是,对于唯一键的索引,Next-Key Lock 会降级为 Record Lock。

1.3 MVCC

InnoDB 通过 MVCC(Multiversion Concurrency,多版本并发控制)来实现一致性非锁定读(Consistent Nonlocking Read),在保证隔离性的基础上,极大的提高了数据库的并发读性能。

MVCC 是通过 Readview 和 Undo Log 来实现的。具体来说,InnoDB 对每一个数据行(聚簇索引叶子节点)都会增加三个字段:

  • DB_TRX_ID:该数据行对应的最后修改事务号;
  • DB_ROLL_PTR:该数据化对应的 Undo Log 指针,指向上一个状态数据,构成该数据行的版本链;
  • DB_ROW_ID:单调隐藏 ID,缺省聚簇索引。

Readview 是 InnoDB 为每个事务开启时(第一次普通 SELECT 语句)构造的数据结构:


ReadView::ReadView()
    :
    m_low_limit_id(),
    m_up_limit_id(),
    m_creator_trx_id(),
    m_ids(),
    m_low_limit_no()
{
    ut_d(::memset(&m_view_list, 0x0, sizeof(m_view_list)));
}

其中:

  • m_low_limit_id 为活跃事务链表(trx_sys)中的最大值;
  • m_up_limit_id 为活跃事务链表的最小值;
  • m_ids 为当前活跃事务链表。

那么,有了 Undo Log 构成的数据版本链和当前事务所游泳的 Readview,就可以做到非锁定一致读了。当前事务的普通读请求都会通过 Readview 来判断该版本是否对该事务可见,如果不可见,则通过版本链回溯上一版本,直到该数据可见位置。那么如何判断一个数据行是否对当前事务可见呢?具体算法总结为:

该版本数据行对应的事务 ID 为 trx_id

  1. 若 trx_id < m_up_limit_id,则该数据是当前事务开启前提交的,可见;
  2. 若 trx_id >= m_low_limit_id,则该数据是当前事务开启后提交的,不可见;
  3. 若 trx_id == m_creator_trx_id,则该数据是被当前事务修改的,可见;
  4. 若 trx_id 落在 [m_up_limit_id, m_low_limit_id) 之间的话,则需要在 m_ids 中查找该 trx_id 是否存在,如果存在,则不可见,不存在,则可见。

1.4 Crash Recovery

InnoDB 使用 Redo 和 Undo 协作完成恢复的过程,首先来看下一个事务的正常流程:

UPDATE Z SET A = 2 WHERE A = 1;
  1. 事务开始;
  2. 记录 A = 1 到 Undo Log;
  3. 修改 A = 2;
  4. 记录 A = 2 到 Redo Log;
  5. 写入 Redo Log 到磁盘;
  6. 事务提交完毕。

在恢复过程中,有两种策略可供选择:

  1. 只重做已经提交了事务;
  2. 重做所有记录,然后通过 Undo Log 来回滚未提交事务。

InnoDB 选择了第二种策略(为什么?),于是,在重做 Redo Log 时,不关心事务性,重做日志中的所有记录,然后根据 Undo Log 进行选择性的回滚。

不过,这就要求 Undo Log 也要持久化到磁盘中,为了避免两种日志持久化带来的复杂度,InnoDB 将 Undo Log 视为数据的一种,将其记录到 Redo Log 中,重做 Redo Log 的过程也包含了重做 Undo Log。

于是更新后的流程为:

  1. 事务开始;
  2. 记录 A= 1的 Undo Log 到 Redo Log;
  3. 修改 A = 2;
  4. 记录 A = 2 到 Redo Log;
  5. 写入 Redo Log 到磁盘;
  6. 事务提交完毕。

InnoDB 的恢复过程可以简要描述为:

  1. 根据 Redo Log 恢复记录(这个过程中也恢复了 Undo 段)
  2. 对 ACTIVE 状态的事务直接回滚;
  3. 对 PREPARE 状态的事务 进入 XA Recover 阶段;
  4. 扫描最后一个 binlog 文件,搜集其中的 XID;
  5. 然后与 Undo 中记录的 XID 进行对比;
  6. XID 存在于 binlog 中,认为提交,否则,需要回滚。

二、2 Phase Commit

两阶段提交协议是为了保证多节点在进行事务提交时保持一致性的一种算法。

2PC 在提交事务时分为两个阶段:

第一是提交请求阶段,协调者向所有参与节点询问是否可以执行提交操作,等待相应

第二是提交执行阶段,如果所有参与者都返回“可以提交”,则发送提交命令,否则发送回滚命令。

2.1 Binlog and Redolog

在 InnoDB 内部就使用了2PC来保证 binlog 和 redolog 的一致性。我们知道,binlog 是 Mysql 自身产生的日志,用以备份和主从同步,redolog 是 InnoDB 作为 Mysql 的存储引擎,自身产生的 WAL 日志。

于是,这就存在两个不同节点(Mysql 和 InnoDB)之间的一致性问题:

  • 如果先写 redo log 再写 binlog:写完 redo log 之后 Mysql 异常重启,结果该 Mysql 实例有该条数据,通过 binlog 恢复的库或同步的从库没有这条数据,引发不一致;
  • 如果先写 binlog 再写 redo log:写完 binlog 之后 Mysql 异常重启,结果该 Mysql 实例无数据,依赖 binlog 的库却有数据,引发不一致。

所以,我们最常见的 2PC 就存在于 binlog 和 InnoDB 存储引擎之间。其中,binlog 作为协调者,InnoDB 作为参与者:

  1. 事务提交命令
  2. InnoDB 写入 redo log,状态置为 PREPARE;
  3. Mysql 写入 binglog;
  4. 提交事务,InnoDB 状态置为 COMMIT。

2.2 XA

2PC 真正的威力是应用于分布式事务上,即一个事务跨多个异构的数据库资源,同时要保证事务一致性。

为此,Open Group 提出了一套 XA 规范,用以支持基于 2PC 的分布式事务标准。XA 事务由如下组成:

  • 资源管理器(RM):提供访问事务资源的方法。通常一个数据库实例就是一个资源管理器;
  • 事务管理器(TM):作为 2PC 的协调者,需要和所有的资源管理器进行通信;
  • 应用程序(AP):定义事务的边界,指定全局事务中的操作。

InnoDB 实现了 XA 接口,提供的语句如下:

不过如果我们需要构建一套支持分布式事务的分布式数据库,事情还没这么简单,无论是 2PC 协议还是 Mysql 实现的 XA 规范,都存在一些问题。

2.3 Disadvantage in 2PC

基础 2PC 协议存在如下几个缺点:

  • 同步阻塞问题

    在进入 2PC 后,RM 的事务资源需要一直被锁住,知道 TM 指定执行或者回滚命令位置。这会影响分布式系统的性能。

  • 单点问题

    在 2PC 协议中,TM 的作用非常关键。如果 TM 出现故障,分布式事务将无法进行,如果在第二阶段前 TM 故障,所有 RM 都将一直持有资源锁,无法继续推进分布式事务。

  • 不一致问题

    如果仅仅是 TM 和 RM 单独挂了,那还可以通过互相询问,达到一致性,如果 TM 和 RM 都在第二阶段挂了,再恢复过来之后,就无从得知是否有部分 RM 已经执行了操作,如果没有合理的容错机制,就会出现不一致问题。

2.4 Disadvantage in MySQL XA

2.4.1 Mysql 主库挂掉后,存在主从不一致

Mysql 5.7.7 已修复该问题

这个问题是这样的,我们回顾第一章的 Crash Recovery 过程,在 Mysql 内部 XA 中,

XA PREPARE:

  • binlog:空操作
  • InnoDB:redo log 落盘,标记为 prepared

XA COMMIT:

  • binlog:binlog 落盘
  • InnoDB:事务提交,标记为 commited

对于外部 XA 事务,Mysql 的 Crash Recovery 与之前类似,不过,如果发现该 prepared 事务是外部 XA 事务,则不会根据 binlog 是否写入为依据进行提交或回顾,而是等待外部应用(TM)决定。不过:

  • 事务 binlog 未落盘

    外部应用提交该事务,会导致主从不一致,回滚该事务,导致分布式写不一致

  • 事务 binlog 已落盘

    外部应用提交该事务,一切OK,但外部应用无法知道内部事务处于哪种情况,如果回滚了事务,则导致主从不一致和写不一致

2.4.2 客户端连接断开,导致分布式写不一致

问题产生:

在 Mysql 实现中,当连接断开后,无论该连接是客户端发起的正常断开,还是网络问题导致的异常断开,如果该连接上持有一个未提交事务,那么该事务都会被回滚。

于是,当 TM 向多个 RM 发起 XA COMMIT 命令时,如果某个 RM 上的连接异常断开,为收到 COMMIT 请求,则会回滚该事务,导致分布式写不一致。

2.4.3 分布式死锁问题

分布式死锁是由于事务间跨 RM 的锁等待环而导致整体 hang 住。

分布式死锁不等价于单个分片中的死锁,RM 自身无法检测出分布式死锁。

2.4.4 分布式读一致的隔离级别问题

在单实例下,InnoDB 的 REPEATABLE READ 隔离级别完美解决了隔离带来的问题,通过 Lock 和 MVCC 既达到了隔离性,也获得了非锁定一致性读

但是,在分布式事务下,REPEATABLE READ 却会导致非一致性读问题。

具体来说:

将 TM 上的分布式事务 Ti 在 RM1 和 RM2 的分支事务分别记为 ti1 和 ti2 . 假设 TM 上有两个分 布式事务 T1 和 T2 均在 RM1 和 RM2 上有分支事务, 如果某时 t11 在 RM1 已经成功提交, 而 t12 在 RM2 上正在提交, 与此同时, 如果这个时刻 T2 去 RM1 和 RM2 上读取 T1 涉及的数据记录, 那么:

  • 在可重复读隔离级别下,t21 能看到 t11 提交后的数据, 但 t22 却看不到 t12 对数据的更改, 使用 MVCC 回溯到老版本, 从而产生分布式读不一致.
  • 在串行化隔离级别下,SELECT 会隐式上 S 锁, 所以虽然 t21 能看到 t11 提交后的数据, 但 t22 却不会使用 MVCC 回溯, 而是等待 t12 提交后才读取最新数据, 所以最后 TM 读到的是 分布式一致性数据.

简而言之,在使用 XA 分布式事务,InnoDB 的隔离级别必须被设置为串行化,而这会导致性能的巨大损失。

三、NesoiDB

NesoiDB 是百度钱包和 DBA 联合开发的一款支持分布式事务的分布式数据库,其整体架构如下:

其中经过 DBA 改造后的 Mysql 作为 XA 事务中的 RM,DTM 就是 XA 事务中的 TM,额外的 Redis 集群是 DTM 用来辅助达成分布式事务 ACID 性质的工具,下面就让我们仔细看看 NesoiDB 如果突破 2PC 和 XA 的缺点,达成分布式事务 ACID 的。

我们在最开始说过,对于事务的 ACID 性质,Consistency 是最核心目的,也是 A、D、I的最终结果,对于分布式事务来说,也是如此,保证分布式事务的原子性、持久性、隔离性,同时要求业务无跨RM的约束(外键等),就保障了分布式事务的一致性。

3.1 Atomicity

为了达到分布式事务的原子性,也就是分布式写一致性,首先要解决 Mysql XA 事务的几个影响写一致问题。

3.1.1 主从不一致问题(见2.4.1)

这个问题的本质就是 binlog 未正确的实现 2PC,在 prepare 阶段没有做到锁住资源,也就是记录 binlog

所以解决方案就是:

  • 类似于 redo log 的prepare阶段,为 binlog 也增加 binlog prepare 日志,在 xa prepare 阶段,保证 prepare 日志已经记录到 binlog 中。
  • 同时,MySQL 主从之间使用半同步机制,保证 binlog 已同步到 Slave。

3.1.2 连接断开导致不一致问题(见2.4.2)

该问题的构建就是在于当连接断开后,RM 不能无脑回滚该事务,解决方案为:

  1. 对于异常断开的连接,如果该连接上持有 XA 事务,且处于 PREPARED 状态,该 XA 事务不允许 RM 直接回滚;
  2. 对于正常断开的连接,如果连接上的 XA 事务状态为 PREPARED,如果新增的变量 rollback_xz_trans_when_disconnect = 0,则不回滚该事务,否则可以回滚。
  3. 以上的未回滚的 XA 事务称为孤儿事务,TM 可以使用新增的 SQL 命令 “ XA STATUS [XA_PREAPRED]” 来查询当前的孤儿事务,然后决定提交或者回滚。

到目前为止,算是解决了影响分布式事务原子性上 Mysql XA 的问题,接下来,就是 2PC 缺陷的修正。

3.1.3 2PC 容错

2PC 容错的关键就在于异常恢复,异常发生,通过合理的恢复机制,能使系统继续达到一致性。

具体来说,NesoiDB 通过将 TM 的状态转移到 Redis 中,使得 TM 无状态,解决 TM 单点问题,然后再来处理恢复问题。

在 2PC 中,每个过程都有可能失败,问题的关键在于第二阶段(收到所有 prepared请求后),此时任一步骤,或者 TM,或者RM挂掉后,任何一个参与者(TM/RM)都无法确定其他人的真实状态。

从 TM 角度上看:

  1. 一直没收到所有的 Preapred 怎么办?
  2. 发出 commit/rollback 后一直没收到所有的回应怎么办?

从 RM 角度上看:

  1. 发出 prepared 后,一直没有二阶段命令过来怎么办?

我们仔细分析,可以得知,恢复的关键在于分布式系统中的时序关系问题。比如说经典 2PC 模型不知道 TM 挂之前有没有发出 COMMIT 请求,不知道RM挂之前有没有执行 COMMIT 请求。

于是,NesoiDB 的思路就是通过 Logical Time 来解决分布式时钟问题:

  1. TM 在 XA START 后,往 Redis 中记录分布式事务状态为 START;
  2. TM 在接收到所有 RM Prepared 后,往 Redis 中记录分布式事务状态为 PREPARED;
  3. TM 发送 XA Commit 命令;
  4. TM 接收到所有 RM Commit ok 还有,记录 Redis 中的分布式事务状态为 COMMIT。

这里的关键就在于 TM 第3步发送 commit命令一定要在第 2 步记录 prepared 状态之后,使得其在分布式环境下,逻辑有序。

这样子,也就引入了 DTM_RECOVER 进程,其逻辑为:

  1. 通过 redis 获取分布式锁;
  2. 遍历所有 redis,获取超时事务(当前状态是start/prepare,且最后更新时间超过了1s)的 xid
  3. 遍历超时事务,找出悬挂事务(去mysql上执行 XA STATUS xid,如果结果是 state=PREPARED && recover_mode=yes)
  4. 对于状态为 start 的事务,执行回滚;
  5. 对于状态为 prepare 的事务,执行 commit;
  6. 释放分布式锁。

3.2 Durability

NesoiDB 的全局持久性由全局事务原子性加上各 RM(Mysql)的持久性来保证。

3.3 Isolation

2.4.4 指出,对于社区版 MySQL,为了保证分布式读一致性,也就是分布式事务的隔离性,必须使用串行化隔离级别,也就是每个普通 SELECT 都会加上 S 锁。这势必会导致极大的性能损失。

我们在最开始已经说明了单实例 MySQL 是如何保证隔离性的同事提升性能的,也就是通过 MVCC 达到的非阻塞一致性读。于是我们的思路就是沿用 MVCC 的思想,实现分布式MVCC,即 DMVCC。为了达到这个目的,MySQL 需要做如下更改:

3.3.1 事务提交时返回 Committed ReadView

非阻塞 SELECT 要读取指定记录,实际上就是为这个 SELECT 指定一个 ReadView。NesoiDB 的 MySQL 将在事务 InnoDB commit 阶段生成一个 ReadView,称之为 Committed readview。之所以选择在 InnoDB Commit 阶段是因为该阶段是一个串行化的过程,从而保证每次生成的readview能看到所有在此之间提交事务的数据。

另一方面,MySQL 并不会将 readview 这个数据结构返回,而是将 binlog commit 时生成的 group id 作为 readview 的索引,即 creation_order 返回给 TM。

3.3.2 扩展语法,允许 TM 自定事务所使用的 ReadView

在有了一系列 ReadView 后,从 MySQL 层面可以回溯到任一状态的数据,不过全局分布式 readview 是由 TM 来协调组织的。

所以,MySQL 需要扩展预发,允许 TM 发起事务时,指定某个 readview 作为本次本地子事务的 readview,即:

XA START `xid WITH READVIEW `creation_order`;

事务开启时,语句带上指定的 readview,则依照 REPEATABLE READ 的隔离性,整个事务都会使用该 readview 来实现非阻塞一致性读。

3.3.3 更改 InnoDB Purge 逻辑,避免 InnoDB purge 掉需要的 undo log

InnoDB 自带的 purge 逻辑会定期清理无用的 undo log,但是在使用 DMVCC 后,单机 InnoDB 不能随意的清理 undo log,否则会引起错误。

所以,更改后的 purge 逻辑交由 TM 告知,哪些 undo log 可以被清理。即:

PURGE READVIEW `creation_order`;

该操作的意思是通知 InnoDB 所有 binlog group id 小于等于 creation order 的事务的 undo log 已经可以被清理了。

于是,对于 TM 而言,每次事务 Commit 后都会收到涉及到的分片的 Committed ReadView,剩下的事就是如何组织协调 DMVCC。

3.3.4 基线

对此,NesoiDB 引入了基线的概念。基线指的就是每个分片 Mysql ReadView 的集合,也就是一个全局分布式 ReadView。它要满足两个特点:

  1. 分布式一致,即该基线要么包含任意分布式事务在各分片上所有的子 ReadView,要么都不包含;
  2. 不断推进构建,新分布式事务拿到最新的基线。

为了保证这两个关键点,同时保障基线构建的性能,NesoiDB 使用的基线构建算法可以简单描述为:

  1. 对每个分片都维护两个变量:当前见过的提交的最大 id (MaxID);目前比基线id大的id总数(CountID)
  2. 如果每个分片都满足 MaxID - CurrID = CountID;
  3. 则说明不包含空洞,且由全部事务组成,可以构建推进基线。

具体细节不再展开。

3.3.5 Redis Recover

我们在 3.1.3 中提到,为了保证 2PC 容错,我们的设计是使得 TM 无状态,便于快速恢复和横向扩展,那么我们的基线信息如何保存呢?

目前 NesoiDB 是将这些信息保存在 Redis 中。既然引入了 Redis 这个新组件,自然需要有 Redis 容错的措施,也就是 Redis Recover,简单来说,其功能如下:

  1. 建立与所有数据库分片的连接;
  2. 获取所有功能锁,强制停止功能进程的运行;
  3. 遍历redis,保证没有处于 prepare 状态的事务(通过 dtm_recover 来处理);
  4. 遍历所有数据库分片中的未完成 XA 事务;并判断其提交或回滚;
  5. 强制初始化基线;
  6. 释放所有锁。

3.4 Consistency

到此,就把 NesoiDB 的核心思想和关键挑战介绍完毕了,当然,还有非常多的实现细节被省去了,如各类辅助进程、长时间空洞管制、基线两阶段构建、CommitWaitBuild等。

下面来看对于 NesoiDB 而言,一个正常流程的全景图:

四、Spanner

更进一步的分布式事务思想来源于 Percolator 和 Spanner 的论文。其核心思路还是 2PC,暂时没精力看,TODO

https://pingcap.com/blog-cn/mvcc-in-tikv/

https://pingcap.com/blog-cn/percolator-and-txn/

https://ai.google/research/pubs/pub36726

https://ai.google/research/pubs/pub39966

https://zhuanlan.zhihu.com/p/20868175

https://zhuanlan.zhihu.com/p/34419461