分布式论文阅读 II
2PC、Spanner 笔记
前言 #
本文是我学习分布式事务的笔记，另外我没有详细写过 Multi-Paxos，不了解，因此不会谈论 paxos 的底层细节
没有精读原论文，借助 blog 和 gemini 进行学习
引用的 [!cite] 部分可以略过不读
2PC #
讲一下我对 2PC 的理解
分布式事务，我们先讨论原子性，它的问题在于，不同的机器，可能有的commit成功，有的失败
为什么呢？本质是对 commit 事件没有达成共识
因此我们需要一个单点的、第三方的协调者，这就是“事务协调器”
从最简单的想法开始：1PC
直接获取各个 shard 上的 lock，随后发送 RW 指令，直到各个 shard 回复 ok 就认为事务成功
这么做的缺陷是什么？
最常见的是宕机问题，如果一个 server 回复 ok 前 crash 了会怎样？
server A 已经完成 commit，而 server B 没有
这就产生了不一致性
遇到这种问题，我们应该 rollback，但是 server A 上的操作是不可逆的，数据已经落盘 commit
单机上的 commit 是无法回滚的，我们孤立地看待 server A，它经过了三个阶段：
- 从网络获取 data
- 将 data 提交到本地 db，执行事务
- 事务完成，回复 ok
server B 也是一样，我们由此发现问题的根源：系统的并发性
解释一下，网络具有延迟，因此各个 server 间的进度是不同步的，可能 A 到了 3 阶段，B 还在 1 阶段等待 data
此时如果 B 宕机了，A 却感知不到，就导致状态的不一致
把 server 看作孤立的状态机，每个人的状态都是随机取值的，这样我们就把问题形式化了
解决方案很明显。
既然状态间相互独立，我们就建立同步点，让 server 间互相等待
简单来说，我们在阶段 2 强制同步，等待所有 server 都从网络获取到 data 后，再允许执行本地事务，这就是 2PC 的 prepare 和 commit 阶段
此时再回到宕机的问题
我们用 A1, B2 表示 A 在阶段 1，B 在阶段 2，默认 B 宕机
A1, B2 | A1, B3
2PC 的 Prepare 设计，这种情况不可能发生
A2, B3 | A3, B3
A 正常运行，B 已经落盘，但是还没回复 ok，协调器需要一直等待 B 重启回复 ok
A2, B2 | A3, B2
A 正常运行，B 收到 data 缓存，但还没落盘 commit，B 需要重启并继续之前的事务
要处理这个问题，我们需要在 B 端进行 persist，保存事务执行的上下文（包括状态和 data 缓存），这样重启时就能继续工作
具体时机是我们到达同步点 commit 阶段时，server 将当前状态进行 WAL 持久化
[!note] 持久化的理由是，我们到达了一个 ”不可逆“ 的阶段，在 2PC 中表现为 commit 不可逆
这里引申一个小问题，阶段 2 需要获取锁，如果此时宕机会发生什么？
由于我们已经写入了 WAL，重启时直接读取，重新获取锁即可（这里的锁是本地内存锁）
重启完成前，B 会拒绝后续到达的任何操作
如果 B 一直不能重启，那么 协调器 会无限等待 B 重启，因为已经进行到 Commit 阶段，不允许回退
针对这种阻塞情况，我们选择提高 server B 的可用性，具体说就是换用多副本集群（Paxos、Raft），以此减少 B 宕机的频率
另外 协调器 作为单点服务，本身也应该用 Paxos 集群实现高可用性
如果协调器宕机了，重启继续运行即可，因为协调器在设计上就是具有全局信息的，不像 server 是孤立的
3PC 本质是将 阶段 3 也作为同步点，并增加超时检测，但缺点很多，不常用
3PC 增加了超时等待机制，使得 server 能够自行推进阶段，这就导致 server 的决策 ”不强依赖于全局状态“，自然失去了 safety
Spanner #
简单讲一下 Spanner 的事务机制
读写事务上，采用 2PL+2PC 保证 safety，Paxos 集群保证 liveness
只读事务上，采用快照隔离 + TrueTime API，实现类似单机 Leveldb 上的隔离读
这里只讨论如何实现 分布式系统 上的快照隔离
我们先明确，它和单机上的 snapshot 有何不同
单机上的 snapshot，每次读写都会分配独有的事务时间戳，进行只读事务时，就记录当前的时间戳，扫描本地 db，忽略那些更加新的数据，读出”最新的旧版本“
单机的时钟是自洽的，自然可以对事件进行全局排序
可是分布式系统中，各个 server 的时钟是不同步的，全局排序不可行
因此我们的重点就在于如何分配这个时间戳
明确一点，我们针对只读事务进行设计的本意，就是通过减少网络通信，直接本地读，以此提升性能
容易想到的是，我们提供一个第三方的单点时钟，这就是 TSO 方案（TiDB 采用）
不过中心化时钟的做法，和我们的本意冲突了，这其实是一种 trade-off
看起来 TSO 和 2PC 都是中心化服务，但二者的定位不同
2PC 的工作是维护事务状态池，而 TSO 是高速吞吐分配时间戳
二者的优化方向不同，2PC 可以通过分片进行扩展，但 TSO 只能是单点
Spanner 没有采用 TSO 方案，而是设计了 TrueTime API
本地时钟存在固有偏差，但我们可以将误差降到最小，从而创造一段可以接受的”置信区间“
Google 在各个机房设置 GPS 和原子时钟，确保时钟的同步误差极小
这样，我们为每个事务分配的就不是”时间点“了，而是”时间区间“
server 进行快照读时，只需要读出本地”时间点“，与事务”区间“的最晚时刻进行比对，就可以保证排序的正确性
这也引出我们在考虑事件排序时的一个倾向：必须尽可能的保守
假设本地时钟为
[5]，写序列时间戳为[1, 2]
此时我们是不能贸然读取的，要等下去，因为 3,4 的消息可能还在网络中
本地时钟为
[5]，写序列时间戳为 `[1, 2, 6]
这时就能读了吗？也不行
尽管 6 已经提交，但是 3,4 的 commit 也可能延迟
Spanner 为每个 replica 维护一个 t_safe 变量，用于确定当前读是否安全
推进 T_safe #
分布式的另一个问题，就是网络延迟
收到 6 不代表后面不会再收到 3,4，这导致我们必须等待一个绝对安全的时机
这就是 $t_{safe}$ 的作用了，分三个来源：
- Paxos 可见的 commit 记录 t1
- 协调器中已经 Prepare 但还没 commit 的记录 t2
- leader 的时钟保证 t3
t1 很好理解，t2 则是要求我们等待该记录完成 commit
[!note] 这里注意，Leader 的 Paxos 会进行两次写入，一次 Prepare，一次 Commit，最后的时间戳以 Commit 为准，Prepare 只是为了完成集群内部同步，同时提示上层：”仍有事务没有 commit，这个旧事务的时间戳可能更小"，因此会影响
t_safe
t3 的作用是什么呢？
在 Prepare 阶段，协调器会向 leader 发信息，而 leader 会根据本地时钟，去要求协调器修正自己分配的时间戳，不应该早于 leader
类似于 basic paxos 中的 prepare 承诺，leader 承诺不会接收任何早于 t3 的 prepare 事件
这样三者就分别对应了三种延迟到达的信息阶段：
- 已 commit
- 已 prepare 未 commit
- 未 prepare
t1 由 Paxos 空洞机制保证，t2 由协调器的状态记录保证，t3 由 leader 时钟保证
取三者的最小值，就是 t_safe
另外，t3 通过 heartbeat RPC 传递，又可以定期推进 t_safe，保证可用性