关于 Percolator 的进一步论述

发表于 |

将 关于 TiKV、TiDB、TiFlash 的一些思考中关于 Percolator 事务的部分独立出来。

Percolator 的性能优化

一些问题

Percolator 主要定义了事务提交模型，因此有一些不够完备的地方：

  • 对于提交前的行为没有作规定
    • Modify Set 的储存方式
    • Snapshot Isolation Read 的实现方式，当然 SI Read 一般都是在 Snapshot 上基于 MVCC 实现的
  • 对于悲观事务的支持

在性能上，也有一些缺点：

  • 依赖一个 BigTable 类似的一致性 KVStore 作为底座。容易产生跨节点的分布式事务。这种情况下，Percolator 也是 2PC 的，任何一个参与节点的 failure 或者 jitter 都会影响事务提交的性能。
  • 乐观事务，回滚开销大。
  • 依赖一个全局单点生成时间戳为事务定序。

加锁的时机

无论是悲观锁还是乐观锁，都面临加锁时机的选取。

在提交时加锁存在下面的问题：

  1. 乐观锁的问题
  2. 因为整个事务需要缓存在内存中，所以大事务面临 OOM

在 DML 时加锁存在下面的问题：

  1. 每写一个 key 都要和 TiKV 通讯一次
  2. 多次对同一个 key 的 prewrite 无法确认先后（网络可能被任意延迟）
  3. 对 TiFlash 而言，因为列需要按照 commit_ts 排序，所以最好等到 commit 之后再行转列，而 DML 加锁意味着 DML 阶段 prewrite，那么在 DML 阶段就可以行转列了

Percolator 事务和共识层乱序

在什么程度上共识层可以乱序呢？我的结论是：

  1. 跨 Region 情况下会破坏线性一致读，并且从事务层修正的难度比较大，可能引入很长的等待
  2. 单 Region 上，如果保证 Lock 和 Write 的全局序，但只在发现事务 A 的第一个 commit 的时候，将事务相关的所有的 Default 写入，这种情况应该是可以的。对于较为基础的 case 我有 tla 证明
    根据具体实现，需要落盘 Default 和 Lock 是一起的，比如先落盘 Lock 再落盘 Default。可以不用原子落盘两个 cf。

Async Commit

Async Commit 的核心思想是：

  • 在 Prewrite 阶段完成后，不需要等待所有键都被确认提交。
  • Primary Key 的提交操作即被视为事务完成，其它 Secondary Key 的提交可以异步完成。

这使得事务提交延迟主要取决于 Prewrite 的耗时，而不是整个 2PC 流程。

实现方式是在每个 key 的 lock 中声明一个 min_commit_ts，表示事务不会在这个之前提交。后续的读取可能会继续推高 min_commit_ts。当事务提交时，需要选择所有 min_commit_ts 中最大的一个作为 commit_ts。

因此，在这个优化后，不同事务的 commit_ts 可能相同，但是 start_ts 依然是不相同的。

Bypass lock 机制

这是 Learner read 层的优化。
TiFlash 存在 remote read 的机制。在第一次遇到 lock 的时候，会由 client-c 去 resolve lock。此时，会有几种情况：

  1. 事务已经 commit 了，并且 commit_ts 大于 read_ts
  2. 事务还没有 commit，但是 min_commit_ts 大于 read_ts
  3. 其他情况

对于第一、二种情况，我们不应该读到这个锁对应的数据。它们都保证了事务已经或者最终要以高于 read_ts 的 ts 来提交。因此，既然这个 lock 对应的写入是不需要对 read_ts 的读可见的，因此在下一次读的时候，就可以 bypass 掉这个 lock，而不需要等待它们的 commit 了。

Read through lock 机制

这是一个事务层的优化。
Read through lock 特性指的是当确定某个事务可以被 commit 的时候，跳过 resolve lock 的过程，而直接读。而这锁最终会被下一次写同一个 key 的时候 resolve。
具体做法是，它首先是事务上一个 secondary key 的锁，我们在通过 secondary lock 去查询 PK 的 lock 的时候，会发现 PK 上的事务提交了。因此，这个事务一定是提交了的，所以可以 read through lock。
这个“lazy”地 resolve lock 的方式也被用在了大事务的支持上。

基于共识层之上的事务

事务的“序”

几个问题

不妨考虑几个问题：

  • 是不是 start_ts 越大的事务，体现在 log index 上更大？commit_ts 呢？
  • 两个事务可以有相同的 start_ts 么？
  • 两个事务可以有相同的 commit_ts 么？
  • 假设一个事务 [ST1, CT1] 准备提交了，它可以看到另一个事务 [ST2, ?]，并且 ST2 小于 ST1。请问此时它是否可以立即提交？

答案：

  • 不一定
    参考下面的双重定序
  • 不可以
  • 可以
    比如 Async Commit 特性就会产生这样的现象。
  • 不能
    参考“一个两难问题”

一个两难问题

假设一个事务 [ST1, CT1] 准备提交了，它可以看到另一个事务 [ST2, ?]，并且 ST2 小于 ST1。请问此时它是否可以立即提交？

答案是不行，因为不知道 ST2 这个事务的 Commit TS 是多少。在一个异步系统中，这个消息总是可以被任意延迟的。

在 Percolator 中的解决方式是：ST2 意味着会读到一个 Lock，所以 ST1 这个事务要先 Resolve Lock。

这个问题，就展现了事务序和共识序之间的相互关联。这就如同之前全序广播中论述的一样，核心是能够确保消息被不重不漏地编号，例如 TCP 的 seq 一样。共识系统通过日志的全序性来保障了这一点。

共识层和事务层的关系

Percolator 事务提交模型中，commit_ts(R) < start_ts(T) 的事务 R 对事务 T 可⻅。不满⾜该关系的事务为并发事务，并发事务如果访问相同的 key 将会导致其中⼀个事务会碰到 Lock ⽽回滚。因此，Percolator 本质上是一个 2PL 协议，因为一个事务会在 Prewrite 阶段尝试获得自己所有需要的锁。start_ts 此时被用来决议这些锁的 order。

Raft 的 Read Index 模型中，一个读请求需要等到 applied_index 大于等于 read_index 时，才能读取数据。但并不保证是否能读到 applied_index = x + 1 时的数据。实际上无论是否读到，都不违背强一致读的原则。因为如果一个读 A 能读到 applied_index = x + 1，而另一个读 B happen after 读 A，那么读 B 一定会读到 applied_index >= x + 1 的数据。

TiKV 的共识层在事务层之下。在事务 Commit 之前的很多数据也会被复制到多数节点上，这产生了一些写放大。但也需要注意其带来的好处：

  1. 共识层实际为 Percolator 提供了类似 BigTable 的一致性存储保障。
    首先提供了外部一致性。
    然后提供了 PUT default/PUT lock 和 PUT write/DEL lock 的原子性写入。
    当然，这里要先读后写，可能会有 Write Skew。
  2. 共识层本身也可以作为一个 Raw KV 对外服务。
  3. 共识层参与定序。这个在后面介绍。
  4. 多个 Raft Group 组成的共识层提高了并发能力。
  5. Lock 的存在性和⼀致性由该⾏所处的 Raft Group 保障。
  6. 事务提交后，会写⼊ Write 并删除 Lock，其原⼦性由 Raft Write Batch 保障。
  7. 共识层提供了全序广播语义。
    “在 xx 之前，一定不会有别的 Lock 和 Write 了”

当然这也存在一个 argue 点，因为 Raft Log 本身也是 total order 的。虽然我们目前不是全局一个 Raft Group 的，但看起来会有一些冗余，在后面会讨论。
特别地，在 CDC 服务和 TiFlash 中，实际上不会处理未 Commit 的数据。

双重定序

事务层的实现中，为了满足隔离性，通常会给事务分配 id 来表示相互依赖的事务之间的偏序关系。TiDB 中使用了 TSO，Spanner 中使用了 TrueTime，CRDB 中使用了 HLC。
共识层的实现中，为了实现容灾和高可用，使用共识算法在各个 RSM 之间复制日志，这些日志为全序关系，RSM 可以应用这个全序关系确保线性一致。

事务层生成 TSO 和共识层生成 Log 两个行为：

  1. 不是原子的
  2. 也不构成全序关系
    实际上也没必要，两个不相交的事务按照事务序本来可以并行 Commit 的，但因为要写到共识层，必须又要排出一个全序关系来。
  3. 甚至一个事务的 commit_ts （相比某个特定事务）更小，而 index 更大
    下面会展示这种情况，并详细阐述。

总而言之：

  • Percolator 协议保证了事务层能够生成一个特定的排序，并且按照它的二阶段方式写入到共识层
  • 共识层保证了所有的副本都会应用该特定排序

共识层为事务层提供帮助

目前 TiKV 通过一个 pd 分配一个全局的 tso 来作为事务的 start_ts 和 commit_ts，所以它们之间彼此构成全序关系。当然，实际上不同的事务可能具有同一个 commit_ts，但这并不影响下面的讨论。通过 start_ts 和 commit_ts 可以构建有依赖的事务之间偏序关系，也可以用来判断事务是否是 concurrent 的。如果在单个节点上串行地 commit 这些事务，则面临问题：

  1. 整个系统毫无并行度
    这个应该算是 MultiRaft 的一个 bonus，正如后面讲的，如果没有 MultiRaft，同样可以做 partitioning。
    因此，TiKV 在多个线性一致的存储(Region)上储存这些事务，它保证了每个事务在每个 Region 上都遵循了 start_ts 和 commit_ts 所 imply 的顺序，也 Percolator 那一套。这样尽管各个 Region 之间是并发的了，但只要 Region 内遵循这个 order 就行了。

    当然，这个切分也未必是按照 Region 来，比如 CDC 会使用表来切分。无论按照哪种方式来切分，我觉得一个实现的要点是每个 shard 在调度上是不可以再分的了。比如一个 Region 的一部分数据在 store 1 上，另一部分数据在 store 2 上，这样做实际上会导致无论在 store 1 和 store 2 上都很难独立构建出该 Region 上数据的全序关系，比如 store 1 如果不和 store 2 交互，那么就很难知道 store 2 上还有没有 happen before 它的事务了。比如说，如果两个 store 上 apply 这个 Region 的 log 的进度不一样。

  2. 如何判断某个 tso 之前还有没有其他 Lock 或者 Write？
    因此，读事务会在取得 start_ts 后，再通过 ReadIndex 请求一下 Region Leader 上的 commit_index。那么假设在这之前 Region 上有写入任意的 Lock 或者 Write，都能被 ReadIndex 扫到。这样就保证了读事务能看到 start_ts 之前的所有修改。至于 start_ts 之后的也有 Lock 可以帮忙。
    同样考虑一个Snapshot Isolation(SI)/一个两难问题，这里不再详细展开具体内容。但 ReadIndex 提供了一个保证，就是截止到 read_index，这个 Region 上到底有没有 Write，是很确定的。我理解这实际上就是一种全序广播了。破坏这种全序广播可能会有严重后果，比如如果将 Write 乱序到 Lock 前面，则违反了 Percolator 事务的约束。我们实际上也没办法很好的处理，在“跨 Region 提交事务”中，就构造出了这样的场景。

此外，对于并发事务，共识层也会对它们之间排出一个串行的顺序，比如两个并发的事务不能同时 Commit，而要等到 Log 按序 apply 而这可能有点过强。诸如 ParallelRaft 或者 MultiPaxos 的算法允许并行 apply，可以解决此问题，但会导致 Leader 和 Follower 之间的 apply order 难以统一，从而无法实现 Follower Read。

共识层对并发事务的乱序

刚才说过，共识层未必会按照事务序写入。这也很容易理解，因为取 start_ts 和 commit_ts 和真正写共识层不是原子的。
TiKV 事务在读取时，需要同时接收事务层和共识层的定序。为了满⾜线性⼀致读，需要⾸先带上 start_ts，发送⼀个 ReadIndexRequest 给对应的 Region，求出⼀个 applied_index。在实际实现中，start_ts 并⽆作⽤。
如下所示，Key a 和 Key b 属于两个事务。在事务提交前，可以看到或者得到的保证是：

  1. start_ts(a) < commit_ts(a)
  2. start_ts(b) < commit_ts(b)
  3. start_ts(a) < start_ts(b)
  4. 并且这两个是并发事务，也就是说 commit_ts(a) > start_ts(b)

共识层的序至少保证了同一个 key 的 prewrite 在 commit 前面。

不妨假设 commit_ts 分别为 4 和 6，然后再假如以 (read_ts=7, read_index=202) 读取，如下所示。

  1. Key a：(start_ts: 1, applied_index: 100), (commit_ts: 4, applied_index: 210）
  2. Key b：(start_ts: 3, applied_index: 101), (commit_ts: 6, applied_index: 200)

从事务层上讲，Key a 和 Key b 的写入对 read_ts=7 的读取事务可见，从共识层上讲 applied_index 等于 read_index，或者超过它的的任意时刻都可以读了。因此，此时可能读到一个锁和 Key b（刚好 apply 到 read_index），或者读到 Key a 和 Key b（apply 超过 read_index 很多，比如到 211 了）。前者需要 ResolveLock，实际上导致以新的 read_index 来重新读取。

反过来讲，如果共识层给出下面的顺序，我们看到了中间的 a 或者 b 上有锁。因为这两个事务是并发事务，所以这也是 OK 的

  1. Key a：(start_ts: 1, applied_index: 100), (commit_ts: 4, applied_index: 200）
  2. Key b：(start_ts: 3, applied_index: 101), (commit_ts: 6, applied_index: 210)

可以看到，尽管将事务拆到了 N 个线性一致的存储上执行，并且这些存储可能对并发事务任意定序，但最终读到的结果还是满足了线性一致，以及事务隔离层的要求的。

并发事务的共识序

并发事务 1 和 2，假设 start_ts1 < start_ts2 < commit_ts1 < commit_ts2，那么两个事务彼此不可见，或者说是并发事务。假设这两个事务写入同一个 region，那么在 raft log entry 层面，完全可以出现 commit_ts1 对应的 raft log 的 index 更靠后，而 commit_ts2 对应的更靠前。比如

1
2
index 10: Put Write CF commit_ts2
index 11: Put Write CF commit_ts1

跨 Region 提交事务？

能不能在看到第一个 write 记录时“提交”该事务的所有 key？

这里的“提交”指的是写入下层存储，比如将 Default 写过去，但并不包含删除 Lock 等。

现在比如考虑两个事务，假设 a 在一个 region r1，b 和 c 在另一个 region r2 让：

1
2
commit a(applied_index@r1=100), commit b(applied_index@r2=300), commit_ts=4
                                commit c(applied_index@r2=200), commit_ts=1

从事务层上来看，一定有读事务能看到 c，或者 a、b、c。现在如果看到 a 提交了，能不能跑到 b 的 region 上把 b 也提交了呢？我认为是不可以的，因为从共识层上来说，b 在 c 的后面被 commit 的，如果用 (start_ts > 4, read_index = 250) 去读的话，可能读到 lock b，甚至可能连 lock b 也还没被写入，当然也有可能读到 b。但如果我们在 apply a 的 write 记录的时候发现了 a 被 write 了，就直接写 b 的 write 记录，那么就导致 b 一定在 c 前面就能被读到，实际上违反了共识层的序。

具体来说，不妨考虑 client 先后从 Learner 和 Leader 读：

  1. 在 Learner 上，它使用 read_index = 250 读，但是因为 commit a 已经被 apply 的原因，所以它一定读到了 commit b。
    当然细究下来，因为 lock + default 是原子的，所以实际上 write 无法被正确执行。但这就是 orphan write key 的问题，之前在处理 multi rocks 的时候就解过，我觉得很复杂。在这个场景下，我觉得免不了要去进行等待。在异步系统中的等待，我觉得可以理解为是一种活性问题。
  2. 在 Leader 上，此时 Leader apply 到了 260，所以此时 Leader 上一定没有 commit b，这导致它读不到 commit b。

这里线性一致读就被破坏了。反之，如果按共识序 commit，则不会有这种情况。具体就不展开了。

单 Region 上提交事务？

限定事务只在一个 Region 中发生，能不能在看到第一个 write 记录时“提交”该事务的所有 key？

上述场景在单 Region 上无法构造，原因是单 Region 是串行的。

尽管“在看到第一个 write 记录时‘提交’该事务的所有 key”可能相当于让一部分 Write 被乱序，但这种乱序不是直接去把 Write 挪到 Lock 之前。比如说，因为 Percolator 的特性，单 Region 上的某个事务的 Prewrite 一定都在 Commit 前面。因此，就算在看到第一个 Write 时候，将该事务的所有 Default 都提前写到下层存储，也不至于提前到某个 Lock 前面。这样被写的 Key 始终有 Lock 保护，直到看到它对应的 Write。

而在多 Region 中不同 Region 可以说是完全异步的（不考虑 Split 等），那我就可以构造一个无比提前的 Write，让它失去 Lock 的保护。