前言

关于分布式事务基本原理，相关资料比较多写的比较全面，这里罗列一些需要了解的基本原理文章：

首先我们需要了解传统的分布式事务模型，2PC 与 3PC：

https://developer.aliyun.com/article/1199985

接下来我们需要了解一下，Google 的 Percolator 事务模型：

https://tikv.org/deep-dive/distributed-transaction/percolator/

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

我们看一下 TIKV 实现的 Percolator 事务模型：

https://cn.pingcap.com/blog/tidb-transaction-model/

https://cn.pingcap.com/blog/tikv-source-code-reading-12/

最后，TIKV Percolator 事务模型下数据的读取：

https://cn.pingcap.com/blog/tikv-source-code-reading-13/

2PC 与 3PC

对于传统的事务模型来说，一般都有两种角色，coordinator (协调者) 和 participant (参与者)

2PC 有个无法避免的 case：

假如事务参与者 participant 有 3 个，分别是 p1, p2, p3，协调者有一个 c1
事务过程中，p2、p3 已经 Prepare 成功，事务状态有以下几种可能：
- p1 还未收到 Prepare，当前事务总状态为 Prepare
- 或者, p1 Prepare 成功，还未收到协调者 Commit/Rollback 请求，当前事务总状态为 Prepare
- 或者, p1 Prepare 失败，协调者 c1 向 p1 发送了 Rollback 请求，p1 返回 ok，当前事务总状态为 Rollback
- 或者, p1 Prepare 成功，协调者 c1 向 p1 发送 Commit 请求，p1 返回 ok，当前事务总状态为 Commit
协调者 c1 与事务参与者 p1 全部 Down
协调者 c2 被启动，这个时候，c2 查询 p2、p3 的状态为 Prepare，但是事务总状态完全无法肯定，Prepare/Commit/Rollback 均有可能，只能等待 p1 服务或者 c1 的故障恢复后才能完全确定事务状态。

3PC 通过在 Prepare 和 Commit 中间添加一个 PreCommit 状态来解决这个问题。

当 c1 与 p1 都 down 的状态下，新启动的 c2 查询 p2、p3 的当前状态就可以确定当前事务状态

假如 p2、p3 都是 Prepare 状态的话，
- p1 的状态可能是 Prepare 或者 PreCommit，不可能是 Commit 或者 Rollback
- 所以事务都不算生效，可以放心回滚事务
假如 p2、p3 分别是 PreCommit 、Prepare状态的话
- p1 的状态可能是 Prepare 或者 PreCommit，不可能是 Commit 或者 Rollback
- 所以事务都不算生效，可以放心的回滚事务
假如 p2、p3 都是 PreCommit 状态的话，说明 p1、p2、p3 都 Prepare 成功，
- p1 的状态可能是 Prepare、PreCommit 或者 Commit，不可能是 Rollback
- 由于 p1 可能已经提交，因此需要提交事务

然而 3PC 状态下，多了一次交互，性能肯定会有所下降，而且也无法解决网络分区的问题：

假如事务参与者 participant 有 3 个，分别是 p1, p2, p3，协调者有一个 c1
p1, p2 已经 Precommit 成功，p3 还未 Precommit, 这时候发生网络分区状况，p3 被单独隔离到一个网络分区
p1, p2选举出 coordinator c2，c2 查询 p1、p2 状态是 Precommit 后，提交了事务
p3 选举出 c3，c3 查询 p3 状态为 Prepare 状态，回滚了事务
事务的状态存在不一致的问题

Percolator 事务模型

对于 Percolator 事务模型来说，已经不存在传统意义的 coordinator (协调者) 和 participant (参与者)，所有的事务状态都存储在参与者中。

也可以说 coordinator 不再存储 Prewrite、Commit、Rollback 状态，所有的状态都存储在参与者 participant 中。

Percolator 实现分布式事务主要基于3个实体：Client、TSO、BigTable。

Client 是事务的发起者和协调者
TSO 为分布式服务器提供一个精确的，严格单调递增的时间戳服务。
BigTable 是 Google 实现的一个分布式存储的

Percolator 事务模型是 2PC 的一种实现方式，为了解决 2PC 的容灾问题，参与者 participant 会将 Prepare、Commit 等状态通过分布式协议 RAFT、Paxos 进行分布式存储。确保参与者 participant 即使 Fail Down，恢复回来以后事务状态不会丢失。

还是以之前的例子:

假如事务参与者 participant 有 3 个，分别是 p1, p2, p3，协调者有一个 c1
事务过程中，p2、p3 已经 Prewrite 成功
- p1 还未收到 Prewrite，当前事务总状态为 Prewrite
- 或者, p1 Prewrite 成功，还未收到协调者 Commit/Rollback 请求，当前事务总状态为 Prewrite
- 或者, p1 Prewrite 成功，协调者 c1 向 p1 发送 Commit 请求，p1 通过 RAFT 协议同步事务状态后，当前事务总状态为 Commit
- 或者, p1 Prewrite 失败，协调者 c1 向 p1 发送了 Rollback 请求，p1 通过 RAFT 协议同步事务状态后，当前事务总状态为 Rollback
协调者 c1 与事务参与者 p1 全部 Down
协调者 c2 被启动，参与者 p1 虽然 Down，但是会有容灾节点 p1-1 被启动。c2 查询 p1-1 节点的存储状态
- 如果 p1-1 的状态为 None，那么可以放心的 Rollback
- 如果 p1-1 的状态为 Prewrite，那么可以放心的 Rollback
- 如果 p1-1 的状态为 Rollback，那么可以放心的 Rollback
- 如果 p1-1 的状态为 Commit，那么必须进行 Commit

在 2PC 中，最关键的莫过于 Commit Point（提交点）。

因为在 Commit Point 之前，事务都不算生效，并且随时可以回滚。而一旦过了 Commit Point，事务必须生效，哪怕是发生了网络分区、机器故障，一旦恢复都必须继续下去。

事务的流程

由于采用的是乐观事务模型，写入会缓存到一个 buffer 中，直到最终提交时数据才会被写入到 TiKV；

而一个事务又应当能够读取到自己进行的写操作，因而一个事务中的读操作需要首先尝试读自己的 buffer，如果没有的话才会读取 TiKV。

当我们开始一个事务、进行一系列读写操作、并最终提交时，在 TiKV 及其客户端中对应发生的事情如下表所示：

Percolator 事务模型举例：

Let’s see the example from the paper of Percolator. Assume we are writing two rows in a single transaction. At first, the data looks like this:

This table shows Bob and Joe’s balance. Now Bob wants to transfer his $7 to Joe’s account. The first step is Prewrite:

Get the start_ts of the transaction. In our example, it’s 7.

For each row involved in this transaction, put a lock in the lock column, and write the data to the data column. One of the locks will be chosen as the primary lock.

After Prewrite, our data looks like this:

Then Commit:

Get the commit_ts, in our case, 8.

Commit the primary: Remove the primary lock and write the commit record to the write column.

Commit all secondary locks to complete the writing process.

TIKV 事务接口概览

这里大致写一下乐观事务中，2PC 的大致流程，各个接口的详细逻辑与样例场景可以参考后续文章。

Prewrite 接口

2PC 的第一阶段，预提交。目的是将事务涉及的多个 KEY-VALUE 写入 default_cf，同时将在 lock_cf 上加锁

主要流程

检查在 lock_cf 中没有记录，也就是没有锁
检查在 write_cf 中没有大于等于当前事务 start_ts 的记录
将 KEY-VALUE 写入 default_cf
将 lock 信息写入 lock_cf 上加锁

样例讲解

以上述 Bob and Joe’s 事务 t0 为例，t0 开始之前，Bob 有 10 元，Joe 有 2 元

Bob and Joe’s 事务 t0 目标是 Bob 转账给 Joe 7 元，Bob 就变成了 3 元，Joe 变成了 9 元。

Prewrite 后的结果是：

值得注意的是，tidb 指定 Bob 是 primary key，Bob 写入的 lock 是 primary lock。指定 Joe 是 secondary key，Joe 写入的 lock 是 secondary lock。

通过 Joe 的 secondary lock 我们可以定位到其 primary key 是 Bob。Bob 的当前状态代表了整个事务 t0 当前的状态

异常场景

如果发现其中一个 Key 已经被加锁，判断这个 lock 是不是本事务的 (lock.ts=t.start_ts)
- 如果是的话，那么就是接口重复调用，保持幂等，返回 OK
- 否则的话，说明这个 lock 不是本事务的，需要继续搜索 write_cf 中是否含有本事务的记录 (record.start_ts = t.start_ts | record.commit_ts = t.start_ts )
  - 搜索到 Commit 记录的话，说明本事务已经提交，那么就是接口重复调用，保持幂等，返回 OK
  - 搜索到 Rollback 记录的话，说明本事务已经回滚，会返回 WriteConflict
  - 没有找到本事务的记录，会返回 KeyIsLocked 错误，附带 lock 信息，等待后续 CheckTxnStatus 查看 lock 对应的事务状态 (异常场景一)
如果发现其中一个 Key 的 write_cf 已经有新的记录 (record.commit_ts >= t.start_ts)
- 继续搜索 write_cf 中是否含有本事务的记录 (record.start_ts = t.start_ts | record.commit_ts = t.start_ts )
  - 如果是 Commit 记录的话，说明本事务已经提交，那么就是接口重复调用，保持幂等，返回 OK
  - 如果是 Rollback 记录的话，说明本事务已经回滚，会返回 WriteConflict
  - 没有找到本事务的记录，说明有其他事务并行更新，会返回 WriteConflict，可能需要业务重试事务 (异常场景二)

异常场景样例

由于 Prewrite 的异常场景过多，我们这里只举两个非常典型的场景，其他场景可以查看后续 Prewrite 详解文章。

场景一：KeyIsLocked

以上述 Bob and Joe’s 事务 t0 为例，t0 已经 Commit the primary 成功，状态结果是：

假如此时有个和 t0 并行的事务 t1，目标是扣除 Joe 的账户 4 元，start_ts 为 8。

此时对 t1 进行 Prewrite 后，扫描到 Joe t0 事务的 secondary lock 记录
同时 write_ts 并没有 Joe ts 为 8 的记录
返回 KeyIsLocked 错误，等待后续调用 CheckTxnStatus 检查 t0 事务状态

场景二：WriteConflict

以上述 Bob and Joe’s 事务 t0 为例，t0 已经 Commit the secondary成功，状态结果是：

假如此时有个和 t0 并行的事务 t1，目标是扣除 Joe 的账户 4 元，事务 t1 的 start_ts 是 8

此时对 t1 进行 Prewrite 后，没有扫描到 Joe t0 事务的 lock 记录
扫描到了Joe commit_ts 是 9 的 commit_ts 记录
继续搜索
write_ts 没有扫描到Joe ts 是 8 的记录
因此返回了 WriteConflict 错误。

CheckTxnStatus 接口

如果 Prewrite 失败，返回 KeyIsLocked，那么 tidb 可能会调用 CheckTxnStatus 接口来查看 lock 涉及的 primary key 当前状态

主要流程

如果 primary key 的 lock 已经被清理，同时 write_cf 存在提交记录 (场景一)
- 说明 lock 涉及的 primary key 已经提交，代表整个事务已经提交
- 返回 committed_ts 等待 tidb 调用 ResolveLock 接口将 lock 涉及的 secondary key 也进行提交
如果 primary key 的 lock 已经被清除，同时 write_cf 存在回滚记录
- 说明 lock 的 primary key 已经回滚，代表整个事务已经回滚
- 返回 0 (代表事务已回滚)，等待 tidb 调用 ResolveLock 接口将 lock 的 secondary key 也进行回滚

样例讲解

场景一：committed

以上述 Bob and Joe’s 事务 t0 为例，t0 Commit the primary 后的结果是：

此时 t0 已经完成了 primary key (Bob) 的 Commit，还未来得及对 secondary key (Joe) 进行 commit。

假如此时有个和 t0 并行的事务 t1，目标是扣除 Joe 的账户 4 元。

此时对 t1 进行 Prewrite 后，扫描到 Joe 的 secondary lock 记录，返回了 KeyIsLocked 错误。
tidb 将会通过 Joe 的 lock 查询到 t0 事务的 primary key，也就是 Bob
- 调用 CheckTxnStatus 来查看 Bob 此时的状态。
- CheckTxnStatus 发现了 Bob 的 write_cf 的 Commit 记录
- 确认事务 t0 已经提交，向 tidb 返回了 t0 的 committed_ts(8)
tidb 将会利用 committed_ts(8) 调用 ResolveLocks ，对 Joe 这个 secondary key 进行 t0 事务 commit secondary 操作。
最后 tidb 对 Bob 这个 key 进行 t1 Prewrite 重试

tidb 利用 committed_ts 调用 ResolveLocks 后，Joe 这个 t0 的 secondary key 会被提交

异常场景

如果 primary key 的 lock 还存在，那么查看 primary key lock 的状态

如果 primary key 的 lock 已经过期 (场景一)
- 说明 primary key 相关事务已经 Down 了，需要对该事务进行回滚
- 对 primary key 进行回滚
- 返回 0 (代表事务已回滚)，等待 tidb 调用 ResolveLock 接口将 lock 的 secondary key 也进行回滚
如果 primary key 的 lock 还未过期(场景二)
- 说明本事务和其他事务存在并发，需要等待
- 返回 uncommitted，tidb 将会等待一段时间后重新调用 CheckTxnStatus 接口

异常场景样例

场景一：lock 已过期

以上述 Bob and Joe’s 事务 t0 为例，假如目前 t0 Priwrite 已完成，但是 t0 被异常阻塞，目前状态结果是：

由于 t0 事务的异常阻塞，其中 Bob、Joe 的 lock TTL 已经超时。

假如此时有个和 t0 并行的事务 t1，目标是扣除 Joe 的账户 4 元。

此时对 t1 进行 Prewrite 后，扫描到 Joe t0 事务的 secondary lock 记录，返回了 KeyIsLocked 错误。
tidb 将会通过 Joe 的 lock 查询到 t0 事务的 primary key，也就是 Bob，调用 CheckTxnStatus 来查看 Bob 此时的状态。
- CheckTxnStatus 发现了 Bob 的 lock_cf 记录，而且 lock 已经过期，说明整个 t0 事务已经 Down 了
- 对 primary key 也就是 Bob 进行回滚，包括清除 lock_cf、default_cf 记录，对 write_cf 写入 rollback 记录
- 返回结果 0，代表事务 t0 已经回滚完成
tidb 收到结果 0 后，调用 ResolveLocks ，对 Joe 这个 secondary key 也进行 t0 事务 rollback secondary 操作。
最后 tidb 对 Bob 这个 key 进行 t1 Prewrite 重试

tidb 调用 CheckTxnStatus 前，t0 事务状态：

由于 Bob 的 primary lock 已经过期，tidb 调用 CheckTxnStatus 后，t0 事务状态：

可以看到 t0 的 primary key 也就是 Bob 已经被回滚，lock_cf、default_cf 被清理， write_cf 被追加 rollback 记录

tidb 调用 ResolveLocks 后，t0 的 secondary key 也就是 Joe 也被回滚，Joe 的 lock_cf、default_cf 被清理， write_cf 被追加 rollback 记录：

场景二：lock 未过期

以上述 Bob and Joe’s 事务 t0 为例，假如目前 t0 Priwrite 刚刚完成, 目前状态结果是：

假如此时有个和 t0 并行的事务 t1，目标是扣除 Joe 的账户 4 元。

此时对 t1 进行 Prewrite 后，扫描到 Joe t0 事务的 secondary lock 记录，返回了 KeyIsLocked 错误。
tidb 将会通过 Joe 的 lock 查询到 t0 事务的 primary key，也就是 Bob，调用 CheckTxnStatus 来查看 Bob 此时的状态。
- CheckTxnStatus 发现了 Bob 的 lock_cf 记录，而且 lock 还未过期，说明整个 t0 事务还未提交
- 返回了 uncommitted 错误
tidb 收到 uncommitted 状态错误后，会等待一段时间后重试 CheckTxnStatus 查看 t0 状态

ResolveLocks 接口

根据 CheckTxnStatus 接口的返回值，挨个对 lock 绑定的 key 进行提交或者回滚。

主要流程

如果 CheckTxnStatus 接口返回了 committed_ts，说明 lock 涉及的事务已经提交，ResolveLocks 将会对 lock 绑定的 secondary key 进行提交
- 如果存在 lock key 对应的 lock_cf 记录，直接执行 Commit 提交操作
  - 去除 lock_cf 记录
  - 向 write_cf 写入 Commit 记录
如果 CheckTxnStatus 接口返回了 0，说明 lock 涉及的事务已经回滚，ResolveLocks 将会对 lock 绑定的 secondary key 进行回滚
- 如果存在 lock key 对应的 lock_cf 记录，直接执行 Rollback 回滚操作
  - 去除 lock_cf、default_cf 记录
  - 向 write_cf 写入 Rollback 记录

样例讲解

场景一：提交事务

tidb 调用 ResolveLocks 前，t0(start_ts=7) 当前状态是：

可以看到 t0 的 primary key Bob 已经被提交，Joe 这个 t0 的 secondary key 还未提交。

tidb 利用 start_ts(7)-committed_ts(8) 调用 ResolveLocks 后，Joe 这个 t0 的 secondary key 也会被提交：

清除了 Joe 的 lock_cf 记录，添加了 write_cf Commit 记录

场景二：回滚事务

tidb 调用 ResolveLocks 前，可以看到 t0(start_ts=7) 事务的 primary key 已经被回滚：

tidb 利用 start_ts(7)-committed_ts(0) 调用 ResolveLocks 后，可以看到 t0 的 secondary key 也就是 Joe 也被回滚：

Joe 的 lock_cf、default_cf 被清理， write_cf 被追加 rollback 记录

异常场景

如果 CheckTxnStatus 接口返回了 committed_ts，说明 lock 涉及的事务已经提交，ResolveLocks 将会对 lock 绑定的 secondary key 进行提交
- 如果没有找到 lock key 对应的 lock_cf 记录，进一步去 write_cf 去查找记录
  - 如果在 write_cf 找到了对应的 Commit 记录，直接返回即可，说明接口被重复调用
  - 如果在 write_cf 找到了回滚记录，返回报错 TxnLockNotFound
  - 如果在 write_cf 没有找到任何记录，返回报错 TxnLockNotFound
如果 CheckTxnStatus 接口返回了 0，说明 lock 涉及的事务已经回滚，ResolveLocks 将会对 lock 绑定的 secondary key 进行回滚
- 如果没有找到 lock key 对应的 lock_cf 记录，进一步去 write_cf 去查找记录
  - 如果在 write_cf 找到了对应的 Rollback 记录，直接返回 OK 即可，说明接口被重复调用
  - 如果在 write_cf 找到了 Commit 记录，返回报错 Committed
  - 如果在 write_cf 没有找到任何记录，写入回滚记录, 返回 ok

Commit 接口

当对所有的 key 执行 Prewrite 均成功后，TIDB 将会对事务 t 的 primary key 执行 commit 操作。当 commit 完成后，标志这事务 t 已经被提交。

这个时候已经可以把提交成功的结果返回给 Client，后续 TIDB 将会异步对 secondary key 继续执行 commit 操作

主要流程

如果存在 lock key 对应的 lock_cf 记录，直接执行 Commit 提交操作
- 去除 lock_cf 记录
- 向 write_cf 写入 Commit 记录

样例讲解

tidb 调用 Commit 前，t0(start_ts=7) 当前状态是：

tidb 调用 Commit 后，Bob 这个 t0 的 primary key 会被提交：

清除了 Bob 的 lock_cf 记录，添加了 write_cf Commit 记录

异常场景

如果没有找到 lock key 对应的 lock_cf 记录，进一步去 write_cf 去查找记录
- 如果在 write_cf 找到了对应的 Commit 记录，直接返回即可，说明接口被重复调用
- 如果在 write_cf 找到了回滚记录，返回报错 TxnLockNotFound
- 如果在 write_cf 没有找到任何记录，返回报错 TxnLockNotFound

Rollback 接口

当事务的某些 key 执行 Prewrite 失败后，TIDB 将会对事务 t 的 key 执行 rollback 操作。

当 rollback 完成后，事务相关 key 被 Prewrite 加上的 lock 将会被清除。

主要流程

如果存在 lock key 对应的 lock_cf 记录，直接执行 Rollback 回滚操作
- 去除 lock_cf、default_cf 记录
- 向 write_cf 写入 Rollback 记录

样例讲解

tidb 调用 Rollback 前：

tidb 调用 Rollback 后，可以看到 t0 的 key 均被回滚：

异常场景

如果没有找到 lock key 对应的 lock_cf 记录，进一步去 write_cf 去查找记录
- 如果在 write_cf 找到了对应的 Rollback 记录，直接返回 OK 即可，说明接口被重复调用
- 如果在 write_cf 找到了 Commit 记录，返回报错 Committed
- 如果在 write_cf 没有找到任何记录，写入回滚记录, 返回 ok

TIKV 分布式事务--乐观事务 2PC 概览

前言

2PC 与 3PC

Percolator 事务模型

事务的流程

TIKV 事务接口概览

Prewrite 接口

主要流程

样例讲解

异常场景

异常场景样例

场景一：KeyIsLocked

场景二：WriteConflict

CheckTxnStatus 接口

主要流程

样例讲解

场景一：committed

异常场景

异常场景样例

场景一：lock 已过期

场景二：lock 未过期

ResolveLocks 接口

主要流程

样例讲解

场景一：提交事务

场景二：回滚事务

异常场景

Commit 接口

主要流程

样例讲解

异常场景

Rollback 接口

主要流程

样例讲解

异常场景