如何解决分布式系统中的“幽灵复现”？

1、“幽灵复现”问题

我们知道，当前业界有很多分布式一致性复制协议，比如 Paxos，Raft，Zab 及 Paxos 的变种协议，被广泛用于实现高可用的数据一致性。Paxos 组通常有 3 或 5 个互为冗余的节点组成，它允许在少数派节点发生停机故障的情况下，依然能继续提供服务，并且保证数据一致性。作为一种优化，协议一般会在节点之间选举出一个 Leader 专门负责发起 Proposal，Leader 的存在，避免了常态下并行提议的干扰，这对于提高 Proposal 处理的效率有很大提升。

但是考虑在一些极端异常，比如网络隔离，机器故障等情况下，Leader 可能会经过多次切换和数据恢复，使用 Paxos 协议处理日志的备份与恢复时，可以保证确认形成多数派的日志不丢失，但是无法避免一种被称为“幽灵复现”的现象。考虑下面一种情况：

如上表所示，在第一轮中，A 成为指定 Leader，发出 1-10 的日志，不过后面的 6-10 没有形成多数派，随机宕机。随后，第二轮中，B 成为指定 Leader，继续发出 6-20 的日志（B 没有看到有 6-10 日志的存在），这次，6 以及 20 两条日志形成了多数派。随机再次发生切换，A 回来了，从多数派拿到的最大 LogId 为 20，因此决定补空洞，事实上，这次很大可能性是要从 6 开始，一直验证到 20。我们逐个看下会发生什么：

1. 针对 Index 6 的日志，A 重新走一轮 basic paxos 就会发现更大 proposeid 形成决议的 6，从而放弃本地的日志 6，接受已经多数派认可的日志；

2. 针对 Index 7 到 Index 10，因为多数派没有形成有效落盘，因此 A 随机以本地日志发起提议并形成多数派；

3. 针对 Index 11 到 Index 19，因为均没有形成有效落盘数据，因此，以 noop 形成补空洞；

4. 针对 Index 20，这个最简单，接受已经多数派认可的日志；

在上面的四类情况分析中，1，3，4 的问题不大。主要在场景 2，相当于在第二轮并不存在的 7~10，然后在第三列又重新出现了。按照 Oceanbase 的说法，在数据库日志同步场景的情况，这个问题是不可接受的，一个简单的例子就是转账场景，用户转账时如果返回结果超时，那么往往会查询一下转账是否成功，来决定是否重试一下。如果第一次查询转账结果时，发现未生效而重试，而转账事务日志作为幽灵复现日志重新出现的话，就造成了用户重复转账。

2、基于 Multi-Paxos 解决“幽灵复现”问题

为了处理“幽灵复现”问题，基于 Multi-Paxos 实现的一致性系统，可以在每条日志内容保存一个 epochID，指定 Proposer 在生成这条日志时以当前的 ProposalID 作为 epochID。按 logID 顺序回放日志时，因为 leader 在开始服务之前一定会写一条 StartWorking 日志，所以如果出现 epochID 相对前一条日志变小的情况，说明这是一条“幽灵复现”日志，要忽略掉这条日志（说明一下，我认这里顺序是先补空洞，然后写 StartWorkingID，然后提供服务）。

以上个例子来说明，在 Round 3，A 作为 leader 启动时，需要日志回放重确认，index 1~5 的日志不用说的，epochID 为 1，然后进入 epochID 为 2 阶段，index 6 会确认为 epochID 为 2 的 StartWorking 日志，然后就是 index 7~10，因为这个是 epochID 为 1 的日志，比上一条日志 epochID 小，会被忽略掉。而 Index 11~19 的日志，EpochID 应该是要沿袭自己作为 Leader 看到的上上一轮 StartWorkingID（当然，ProposeID 还是要维持在 3 的），或者因为是 noop 日志，可以特殊化处理，即这部分日志不参与 epochID 的大小比较。然后 index 20 日志也会被重新确认。最后，在 index 21 写入 StartWorking 日志，并且被大多数确认后，A 作为 leader 开始接收请求。

3、基于 Raft 解决“幽灵复现”问题

3.1 关于 Raft 日志恢复

首先，我们聊一下 Raft 的日志恢复，在 Raft 中，每次选举出来的 Leader 一定包含已经 Committed 的数据（抽屉原理，选举出来的 Leader 是多数中数据最新的，一定包含已经在多数节点上 Commit 的数据），新的 Leader 将会覆盖其他节点上不一致的数据。虽然新选举出来的 Leader 一定包括上一个 Term 的 Leader 已经 Committed 的 Log Entry，但是可能也包含上一个 Term 的 Leader 未 Committed 的 Log Entry。这部分 Log Entry 需要转变为 Committed，相对比较麻烦，需要考虑 Leader 多次切换且未完成 Log Recovery，需要保证最终提案是一致的，确定的，不然就会产生所谓的幽灵复现问题。

因此，Raft 中增加了一个约束：对于之前 Term 的未 Committed 数据，修复到多数节点，且在新的 Term 下至少有一条新的 Log Entry 被复制或修复到多数节点之后，才能认为之前未 Committed 的 Log Entry 转为 Committed。

为了将上一个 Term 未 Committed 的 Log Entry 转为 Committed，Raft 的解决方案如下：

Raft 算法要求 Leader 当选后立即追加一条 Noop 的特殊内部日志，并立即同步到其它节点，实现前面未 Committed 日志全部隐式提交。

从而保证了两个事情：

• 通过最大 Commit 原则保证不会丢数据，即是保证所有的已经 Committed 的 Log Entry 不会丢；

• 保证不会读到未 Committed 的数据，因为只有 Noop 被大多数节点同意并提交了之后（这样可以连带往期日志一起同步），服务才会对外正常工作；Noop 日志本身也是一个分界线，Noop 之前的 Log Entry 被提交，之后的 Log Entry 将会被丢弃。

3.2 Raft 解决“幽灵复现”问题

针对第一小节的场景，Raft 中是不会出现第三轮 A 当选 leader 的情况，首先对于选举，候选人对比的是最后一条日志的任期号(lastLogTerm)和日志的长度(lastLogIndex)。B、C 的 lastLogTerm（t2）和 lastLogIndex（20）都比 A 的 lastLogTerm（t1）和 lastLogIndex（10）大，因此 leader 只能出现在 B、C 之内。假设 C 成为 leader 后，Leader 运行过程中会进行副本的修复，对于 A 来说，就是从 log index 为 6 的位置开始，C 将会把自己的 index 为 6 及以后的 log entry 复制给 A，因此 A 原来的 index 6-10 的日志删除，并保持与 C 一致。最后 C 会向 follower 发送 noop 的 log entry，如果被大多数都接收提交后，才开始正常工作，因此不会出现 index 7-10 能读到值的情况。

这里考虑另一个更通用的幽灵复现场景。考虑存在以下日志场景：

1）Round 1，A 节点为 leader，Log entry 5，6 内容还没有 commit，A 节点发生宕机。这个时候 client 是查询不到 Log entry 5，6 里面的内容。

2）Round 2，B 成为 Leader, B 中 Log entry 3, 4 内容复制到 C 中， 并且在 B 为主的期间内没有写入任何内容。

3）Round 3，A 恢复并且 B、C 发生重启，A 又重新选为 leader, 那么 Log entry 5, 6 内容又被复制到 B 和 C 中，这个时候 client 再查询就查询到 Log entry 5, 6 里面的内容了。

Raft 里面加入了新 Leader 必须写入一条当前 Term 的 Log Entry 就可以解决这个问题, 其实和 MultiPaxos 提到的写入一个 StartWorking 日志是一样的做法, 当 B 成为 Leader 后，会写入一个 Term 3 的 noop 日志，这里解决了上面所说的两个问题：

• Term 3 的 noop 日志 commit 前，B 的 index 3，4 的日志内容一定会先复制到 C 中，实现了最大 commit 原则，保证不会丢数据，已经 commit 的 log entry 不会丢。

• 就算 A 节点恢复过来, 由于 A 的 lastLogTerm 比 B 和 C 都小，也无法成了 Leader, 那么 A 中未完成的 commit 只是会被 drop，所以后续的读也就不会读到 Log Entry 5，6 里面的内容。

4、基于 Zab 解决“幽灵复现”问题

4.1 关于 Zab 的日志恢复

Zab 在工作时分为原子广播和崩溃恢复两个阶段，原子广播工作过程也可以类比 raft 提交一次事务的过程。

崩溃恢复又可以细分为 Leader 选举和数据同步两个阶段。

早期的 Zab 协议选举出来的 Leader 满足下面的条件：

a) 新选举的 Leader 节点含有本轮次所有竞选者最大的 zxid，也可以简单认为 Leader 拥有最新数据。该保证最大程度确保 Leader 具有最新数据。

b) 竞选 Leader 过程中进行比较的 zxid，是基于每个竞选者已经 commited 的数据生成。 zxid 是 64 位高 32 位是 epoch 编号，每经过一次 Leader 选举产生一个新的 leader，新的 leader 会将 epoch 号+1，低 32 位是消息计数器，每接收到一条消息这个值+1，新 leader 选举后这个值重置为 0。这样设计的好处在于老的 leader 挂了以后重启，它不会被选举为 leader，因此此时它的 zxid 肯定小于当前新的 leader。当老的 leader 作为 follower 接入新的 leader 后，新的 leader 会让它将所有的拥有旧的 epoch 号的未被 commit 的 proposal 清除。

选举出 leader 后，进入日志恢复阶段，会根据每个 Follower 节点发送过来各自的 zxid，决定给每个 Follower 发送哪些数据，让 Follower 去追平数据，从而满足最大 commit 原则，保证已 commit 的数据都会复制给 Follower，每个 Follower 追平数据后均会给 Leader 进行 ACK，当 Leader 收到过半 Follower 的 ACK 后，此时 Leader 开始工作，整个 zab 协议也就可以进入原子广播阶段。

4.2 Zab 解决“幽灵复现”问题

对于第 1 节的场景，根据 ZAB 的选举阶段的机制保证，每次选举后 epoch 均会+1，并作为下一轮次 zxid 的最高 32 位。所以，假设 Round 1 阶段，A,B,C 的 EpochId 是 1，那么接下来的在 Round 2 阶段，EpochId 为 2，所有基于这个 Epoch 产生的 zxid 一定大于 A 上所有的 zxid。于是，在 Round 3，由于 B, C 的 zxid 均大于 A，所以 A 是不会被选为 Leader 的。A 作为 Follower 加入后，其上的数据会被新 Leader 上的数据覆盖掉。可见，对于情况一，zab 是可以避免的。

对于 3.2 节的场景，在 Round 2，B 选为 leader 后，并未产生任何事务。在 Round 3 选举，由于 A,B,C 的最新日志没变，所以 A 的最后一条日志 zxid 比 B 和 C 的大，因此 A 会选为 leader，A 将数据复制给 B,C 后，就会出现”幽灵复现“现象的。

为了解决“幽灵复现”问题，最新 Zab 协议中，每次 leader 选举完成后，都会保存一个本地文件，用来记录当前 EpochId（记为 CurrentEpoch），在选举时，会先读取 CurrentEpoch 并加入到选票中，发送给其他候选人，候选人如果发现 CurrentEpoch 比自己的小，就会忽略此选票，如果发现 CurrentEpoch 比自己的大，就会选择此选票，如果相等则比较 zxid。因此，对于此问题，Round 1 中，A,B,C 的 CurrentEpoch 为 2；Round 2，A 的 CurrentEpoch 为 2，B,C 的 CurrentEpoch 为 3；Round 3，由于 B,C 的 CurrentEpoch 比 A 的大，所以 A 无法成为 leader。

5、 进一步探讨

在阿里云的女娲一致性系统里面，做法也是类似于 Raft 与 Zab，确保能够制造幽灵复现的角色无法在新的一轮选举为 leader，从而避免幽灵日志再次出现。从服务端来看“幽灵复现”问题，就是在 failover 情况下，新的 leader 不清楚当前的 committed index，也就是分不清 log entry 是 committed 状态还是未 committed 状态，所以需要通过一定的日志恢复手段，保证已经提交的日志不会被丢掉（最大 commit 原则），并且通过一个分界线（如 MultiPaxos 的 StartWorking，Raft 的 noop，Zab 的 CurrentEpoch）来决定日志将会被 commit 还是被 drop，从而避免模糊不一的状态。“幽灵复现”的问题本质属于分布式系统的“第三态”问题，即在网络系统里面, 对于一个请求都有三种返回结果：成功，失败，超时未知。对于超时未知，服务端对请求命令的处理结果可以是成功或者失败，但必须是两者中之一，不能出现前后不一致情况。在客户端中，请求收到超时，那么客户端是不知道当前底层是处于什么状况的，成功或失败都不清楚，所以一般客户端的做法是重试，那么底层 apply 的业务逻辑需要保证幂等性，不然重试会导致数据不一致。

参考文章：

1. In Search of an Understandable Consensus Algorithm - Diego Ongaro and John Ousterhout

2. https://raft.github.io/raft.pdf?spm=ata.13261165.0.0.337d6f55qtohyc&file=raft.pdf
   

3. Paxos Made Simple – Leslie Lamport

4. https://lamport.azurewebsites.net/pubs/paxos-simple.pdf?spm=ata.13261165.0.0.337d6f55qtohyc&file=paxos-simple.pdf
   

5. Oceanbase 列传 – 郁白

6. http://oceanbase.org.cn/?spm=ata.13261165.0.0.337d6f55qtohyc&p=111
   

7. 关于 Paxos "幽灵复现"问题看法 – 陈宗志

8. https://zhuanlan.zhihu.com/p/40175038?spm=ata.13261165.0.0.337d6f55qtohyc
   

9. zookeeper 原理解析

10. https://www.cnblogs.com/wxd0108/p/6251729.html?spm=ata.13261165.0.0.337d6f55qtohyc
    

本文转载自公众号阿里技术（ID：ali_tech）。

原文链接：

https://mp.weixin.qq.com/s/0D2vwh5jW29ZH0Fio-eqqg