一、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 Paging 和 WAL（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 的隔离级别必须被设置为串行化，而这会导致性能的巨大损失。

三、略去关于一个经典分布式事务数据库的讨论

四、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