0. 概述
好久前读过 @郁白老师写的 Paxos 三部曲 [1]，当时也是似懂非懂的，其中描述了 Paxos 一个经典的问题就是 幽灵复现。后来在实际接触了一些一致性协议的东西，又看到了文献 [2]， @陈宗志 重新梳理了这个问题，分析了 raft 解决“幽灵复现”其实就是解决分布式系统中常见的 第三态 问题。自己也打算“新瓶装旧酒”，通过对比分析常见一致性协议（Paxos，Raft，Pacifica）上“幽灵复现” 问题及其相关的解决方案，加深大家对所谓 “幽林复现” 问题和一致性协议的理解，并且文中会从 线性一致（Linearizability）的角度来解读“幽灵复现”是如何违背线性一致性的。
1. 描述
- 什么是幽灵复现
首先来回顾下什么是“幽灵复现”问题，这部分直接来自 @郁白 老师的文章 [1]
使用 Paxos 协议处理日志的备份与恢复，可以保证确认形成多数派的日志不丢失，但是无法避免一种被称为“幽灵复现”的现象，如下图所示：
1. 轮中A被选为 Leader，写下了 1-10 号日志，其中 1-5 号日志形成了多数派，并且已给客户端应答，而对于 6-10 号日志，客户端超时未能得到应答。
2. 第二轮，A宕机，B被选为Leader，由于B和C的大的 logID 都是5，因此B不会去重确认 6-10 号日志，而是从 6 开始写新的日志，此时如果客户端来查询的话，是查询不到6-10号日志内容的，此后第二轮又写入了6-20号日志，但是只有6号和20号日志在多数派上持久化成功。
3. 第三轮，A又被选为Leader，从多数派中可以得到大logID为20，因此要将7-20号日志执行重确认，其中就包括了A上的7-10号日志，之后客户端再来查询的话，会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。
- “幽灵复现” 有什么问题 ？
对于将 Paxos 协议应用在数据库日志同步场景的情况，幽灵复现 问题是不可接受，一个简单的例子就是转账场景，用户转账时如果返回结果超时，那么往往会查询一下转账是否成功，来决定是否重试一下。如果次查询转账结果时，发现未生效而重试，而转账事务日志作为幽灵复现日志重新出现的话，就造成了用户重复转账。
如果熟悉 Raft [5] 和 MultiPaxos [3] 朋友应该会发现第三轮，新选的 Leader A 在 Recovery 的时候做了一件很危险的事情：提交了不是自己任期的 log entry。
2. 分析
幽灵复现既然不对，那它到底不对在哪里 ？或者说它违背了什么呢 ？
实际上幽灵复现违背了线性一致性，因为 Paxos/Raft/Pacifica 都是实现了全序广播，是满足线性一致性的，为了便于分析，首先我们简单看看线性一致性的基本定义：
Linearizable semantics (each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response)
详细的线性一致性的描述定义和验证，更详细和通俗的解释可以参考 [6、7]，这里将不再赘述。
下面来看看 “幽灵复现” 是如何违背线性一致性的：
（1）违背了线性一致性 write
同一个 write 被写两次，违背了 exactly once，所以其违背了线性一致性写
（2）违背了线性一致性 read
这里实际上也违背了线性一致性 read，这里将上面的场景简化为对一个register x 的修改，假设 x=0 是其初值，Op 的序列和返回值如下（注意 w1、r1、r2 是顺序 Op，没有并发）：
step 1：w1: x=1，ret timeout
step 2：r1: x，ret x=0
step 3：r2: x，ret x=1显然对于 w1 timetout 来说，只能呈现出一种语义，就是要么成功，要么失败，如果成功，r1和r2 的返回应该分别都是 x=1，如果失败，r1 和 r2 的返回值应该都是 x=0。而不应该出现 x=0，x=1 这种反转情况，所以 “幽灵复现” 也违背了线性一致性读
3. 解决
3.1. Paxos
这里首先还是给文献 [1] 郁白老师描述的 Paxos 方案。
为了处理“幽灵复现”问题，我们在每条日志的内容中保存一个 generateID，leader 在生成这条日志时以当前的leader ProposalID 作为 generateID。按 logID 顺序回放日志时，因为 leader 在开始服务之前一定会写一条StartWorking 日志，所以如果出现 generateID 相对前一条日志变小的情况，说明这是一条“幽灵复现”日志（它的generateID会小于 StartWorking日志），要忽略掉这条日志。
解释：
其实上面的做法和 Raft 的很类似，就是 Leader 刚当选的时候，首先就是做 Recovery，其遵循 “大 commit 原则”，保证所有已经 commit 的数据肯定会被提交，不会丢数据，也就是 Leader Completeness：
Leader Completeness: if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms
具体实现就是 new leader 当选后，会向集群的大多数获取大的 log id 作为恢复重新确认的结束位置，然后在提交一条StartWorking 日志（类似 raft 里面的 noop log entry，但是不完全一样），然后才开始提供服务，在文献 [2] 中的那副图好像有些问题（待讨论）。
一旦 StartWorking 日志被提交，实际上就是将 A 上 6~10 号日志标记为了丢弃，这样再步骤 3 Leader 当选之后，会抛弃掉 7~10 号日志。1）大 commit 原则保证数据不会丢，2）StartWorking 则给生效 Op 作了一个分界线，StartWorking 日志前面的 log entry 将认为是有效的，而 StartWorking 之后的日志则是的，从而在 new leader 开始服务之前，没有处于模棱两可状态的请求，即使是在 client 端来看是 timeout 的 request，
3.2. Raft
在 Raft 中，new leader 当选的时候，leader 并不知道当前新的 committed index，因为之前 leader 向 follower 更新 committed index 是由滞后的，所以当选的 leader 上面的日志状况可能会同时还有以下两种日志：
- 已经被 committed log entry
- 未被 committed log entry
由于 new leader 并不知道新的 committed index，所以这两种日志，leader 更本就不能分辨，那么自然如何处理这些 log entry 将是一个问题 ？raft 的解决方案如下：
做法和 Paxos 中提到的 大 commit 原则 和 StartWorking 日志其实是一致，通过提交一条 noop 的 log entry，实现前面未决日志全部隐式提交
这样能解决两个问题：
- 通过大 commit 原则保证不会丢数据，也就是所有的已经 commit 的 log entry 不会丢，也就是 Leader Completeness；
- 保证不会出现 stale read，因为只有 noop 被提交了之后，才能开始 read；noop log entry 本身也是一个分界线，noop 之前的 log entry 被提交，之后的 log entry 将会被抛弃，noop log entry 提交之后，leader 将指导新的 committed index
综上，线性一致性 read 看上去是没有问题了（当然还要解决 leader 被隔离的情况，这里不再赘述，详细的参考论文）。但是线性一致性 write 呢 ？这个实际上在 raft 中被放在和 client 交互中解决的，通常的解决方案有两种：
- 系统本身对外接口本身或者通过一定手段使其是幂等，这样重复 write 重复被 write 并不会有问题，尽管这里看上去并不满足线性一致性 write，但是从语义的角度来看，其不会有任何的问题。当然在 paxos “幽灵复现”例子中的 update 显然不是幂等的
- 就是 raft 论文给出的方法，client 发起每个 op 的时候会携带上的序列号，server 端保存一定窗口期的已经被 committed 的序列号，这样一个 op 过来首先会在序列号 list 中检查其是否被 committed 过，如果没有，则处理，否则直接拒绝
Notes:
Raft 协议本身并没有要求 client 端的 Op 是幂等的哦
3.3. PacificA
PacificaA[4] 是微软 2008 发表数据复制框架，在 Change of Primary 的时候，会执行一次 Reconciliation process，来保持 Primary/Secondary 数据的一致，主要过程是 Primary 将自己的 prepare list 上 uncommited 的 request 通过 prepare message 发送从节点，直到这些 request 全部提交，其中落后的补齐，领先的截断，保证 Primary-secondary 的数据一致。下图给出一个例子：
实际上这里和 Raft 类似，因为 new Primary (Leader) 并不知道当前的 commit point 在哪里，所以需要将当前的 prepare list 上的所有 Op log entry 都提交掉，保证不会丢数据，也保证了不会出现类似 raft 的 stale read。实际上这个过程和 raft 几乎是一致的，也是遵循大 commit 原则，保证不会丢数据，而且在 Reconciliation 完成之后，Leader 才能开始提供服务，可以避免 stale read。
更多 PacificA 的细节可以参考另外一篇博文 [8]：
4. 总结
综上可知，“幽灵复现” 的问题其实是 Paxos/Raft/Pacifica 等一致性协议在 Follower 当选为 leader 的时候，new leader 不清楚当前的 committed index，也就是不知道哪些 log entry 已经被 committed，哪些没有被 committed，所以需要通过一定的日志同步手段，保证已经提交的日志不会被丢掉（也就是大 commit 原则，也就是 Leader Completeness），并且通过一个分界线 来决定哪些日志将被提交，哪些将被抛弃，从而避免模棱两可的状态，终使得 Paxos/Raft/Pacifica 等协议在 Leader 挂掉这种异常情况下依然能够满足线性一致性。
参考文献
[1]. [Paxos三部曲之二] 使用Multi-Paxos协议的日志同步与恢复. http://oceanbase.org.cn/?p=111
[2]. 关于Paxos "幽灵复现"问题看法. https://zhuanlan.zhihu.com/p/40175038
[3]. Paxos summary. https://ramcloud.stanford.edu/~ongaro/userstudy/paxossummary.pdf
[4]. PacificA: Replication in Log-Based Distributed Storage Systems. https://www.microsoft.com/en-us/research/wp-content/uploads/2008/02/tr-2008-25.pdf
[5]. Ongaro D, Ousterhout J K. In search of an understandable consensus algorithm[C]//USENIX Annual Technical Conference. 2014: 305-319.
[6]. Kleppmann M. Designing Data-Intensive Applications[J]. 2014.
[7]. 什么是线性一致性?. https://zhuanlan.zhihu.com/p/42239873
[8]. PacificA-Replication in Log-Based DSS. https://zhuanlan.zhihu.com/p/4...
