idea's blog

学习分布式一致性协议的程序员, 或早或晚都会面临所谓的"Paxos 日志幽灵复现"的问题. 就跟学习 TCP 总会遇到所谓的"拆包粘包"问题一样. 这类问题非常之经典, 人们对它们抱有非常顽固的似是而非的误解, 有时这些误解是对的, 但本质其实是错的. 原因就在于, 它们超过了人们的日常理解, 是一种违反常理的东西.

比如 "TCP 粘包"问题, 你能说它不存在吗? 现象确实是这个现象, 但问题本质不是字面上的原因. "TCP 粘包"问题的本质, 是 TCP 对上层提供的是"流", 根本就没有"包"这个概念. 但是, 上层的常理认为, "TCP 应该提供报文服务". 常理如此强烈和普遍, 但 TCP 又拒绝满足常理需求, 所以造成了经典的误解.

Paxos 所谓的"幽灵复现", 有多篇较流行的文章: 1, 2, 3.

假设某个集群, 集群节点是 A, B, C, 用户在不同时刻访问不同的节点. 用上帝视角观察, 其内部日志序列是这样变化的:

对应的外部操作是:

• t0 时刻, 用户访问 A, 发起转账1. 于是 A 节点将请求写入自己的 2 号位置的日志. 为什么不写入 1 号位置呢? 原因是 Multi Paxos 支持所谓的"Paxos 日志空洞", 所以这里造了这样的 case. 没问题, 这样的 case 是可以造出来的. 因为超时, 或者 A 马上宕机, 用户并不知道自己的转账是否成功.
• t1 时刻, A 宕机, 所以它的日志没有复制到集群节点, 所以 B 和 C 的日志都是空的.
• t2 时刻, 用户访问 B, 发起一次转账查询. 由于转账请求没有复制给 B 和 C, 所以, 查询的结果肯定没有转账记录.
• t3 时刻, A 恢复了.
• t4 时刻, A 从 B, C 复制过来 1 号日志, 同时把自己的 2 号日志复制给 B 和 C(幽灵复现了).
• t5 时刻, 用户访问A, (因为查询不到转账记录, 误认为之前的转账失败)发起转账2. 转账2被写为 3 号日志, 然后复制到 B 和 C.

这样看来, 系统执行了两次转账.

那么, 问题出在哪里呢? 问题就出现在t2 时刻, 用户查询转账结果, 发现没有转账记录. 但是, 到了 t4 时刻, 之前的转账记录又出现了. 这就是所谓的"幽灵复现".

现象是这么个现象, 似乎是因为 Multi Paxos 日志空洞的原因造成的? 其实, 这个问题的解释比较简单, 但有点不符合常理, 一般人很难理解.

这个问题, 应该从"并发"操作的角度去解释. 根据 Martin Kleppmann 对并发(Concurrency)的定义:

For defining concurrency, exact time doesn’t matter: we simply call two operations concurrent if they are both unaware of each other, regardless of the physical time at which they occurred.

要定义并发, 时间并不是一个影响因素: 如果两个操作不知道对方(的开始和结束以及结果), 无论物理时间上他们何时发生, 我们都称这两个操作是并发的.

我们可以判定:

• t0 时刻发起转账1(仅发起, 未结束)
• t2 时刻查询转账结果(发起并结束)

这两个操作是并发的. 虽然它们在时间上是先后发生(开始)的, 但是, 因为它们不知道对方的结果, 所以, 它们是"并发的"! 是不是很难理解? 既然是并发操作, 那么, t2 时刻查询到的转账记录, 就不能轻率地认为转账1未来不会发生.

所以, 结论很明显了, 责任全在用户, 和 Multi Paxos 空洞无关.

哈哈, 很难理解吧? 我也认为责任全在用户, 是用户自己没有理解什么是"并发", 错误地认为之前的转账已经失败, 其实并没有, 之前的转账还在进行中(pending).

但是, 现象是这么个现象, 问题就在那里, 总归要解决吧? 可以解决...... 例如, "TCP 粘包"问题, 我们可以要求 TCP 做一下改变, 不仅提供流服务, 还必须提供报文服务, 这确实是一种解决方案, 不过, 你可以要求, 但 TCP 不会同意. 所以, 我们可以要求 Multi Paxos 不要支持空洞, 但是, 好像 Multi Paxos 也不同意.

那么, 我们就进行改进, 于是, 出现了 Raft. Raft 通过选主和任期, 确保"2=转账1"一定会被丢弃. 问题"似乎解决了".

当然, 也可以在应用层去解决, 这是另一个层次了.

实际上, "幽灵复现"和 Paxos 日志空洞没有必然联系, 即使是 Raft 也有"幽灵复现", 也能造出同样的外部表现. 甚至和分布式没有一丁点关系, 即使单机数据库也能幽灵复现. 注意, 是外部表现, 不是内部逻辑, 所以前面用了"似乎解决了".

可以想想:

用户向 server 发了一个请求, 这个请求在 server 内部被卡住了, 例如 server 是多线程的, 因为操作系统严重 bug 或者别的原因, 这个线程被阻塞了. 然后, client 超时后去查询, 也同样没有查询到转账记录. 之后, 没想到线程被调度执行, 之前的请求得以被处理, 转账1竟然"幽灵复现了"...

甚至请求在 IP 链路层卡住了, 导致客户端超时, 然后重新创建一条 TCP 连接发起查询, 之后, 原来的 IP 报文被传输, server 还是会"复现"处理转账1.

真正的本质还是在于对"并发"的理解, 以及对"三态"问题的忽视. 一个操作, 不是只有两个结果(状态), 而是有三个结果(状态): 成功, 失败, 未知. 未知就是 pending, pending 就是未知, 你不应该针对 pending 状态下任何结论, 下任何结论都是错的, 它既没有成功, 也没有失败, "未知"才是真正的"幽灵".

相关资料:

• 什么是 Paxos 的日志空洞?
• 数据库的并发操作与一致性
• Paxos Made Simple
• Raft - In Search of an Understandable Consensus Algorithm
• 可靠通信三原则

这个问题其实是 Andrew S.Tanenbaum 在《计算机网络》一书中提到的两军问题.

Related posts:

1. Paxos 和 Raft 的结构差异
2. Paxos 与分布式强一致性
3. Paxos vs Raft 的争论
4. 什么是 Paxos 的日志空洞?
5. 为什么极少有开源的Paxos库?