阿里妹介绍：“重现”问题本质上是分布式系统的“第三态”问题，即在网络系统中，一个请求的返回结果有成功、失败、未知三种类型暂停。对于未知超时，服务器处理请求命令的结果可以是成功也可以是失败，但必须是两者之一，不能出现不一致。1、“幽灵再现”问题我们知道，业界有很多分布式一致性复制协议，如Paxos、Raft、Zab以及Paxos的变种，广泛用于实现高可用的数据一致性。Paxos组通常由3个或5个互为冗余的节点组成，即使在少数节点故障的情况下，也能保证服务的继续和数据的一致性。作为一种优化，协议一般会在节点中选出一个领导者负责发起提案。领导者的存在避免了正常情况下并行提案的干扰，大大提高了提案处理的效率。但是考虑到在一些极端的异常情况下，比如网络隔离、机器故障等，Leader可能会进行多次切换和数据恢复。在使用Paxos协议处理日志备份和恢复时，可以保证确认多数形成的日志不会丢失。但无法避免一种被称为“重影”的现象。考虑如下情况：如上表所示，第一轮A成为指定的leader，发出1-10条日志，但后面的6-10条不占多数，随机关闭。然后在第二轮，B成为指定的leader，继续发出6-20条日志（B没有看到6-10条日志的存在）。这一次，6和20的日志占了多数。随机切换再次发生，A回来了。从多数得到的LogId最大为20，所以决定补缺。其实这次很有可能是从6开始，验证到20。下面一一看看会发生什么：对于Index6的log，A会再经过一轮basicpaxos，会发现较大的proposeid形成了6的解析，从而放弃本地log6，接受已经有的log获得大多数人的认可；对于Index7UptoIndex10，因为多数没有形成有效的顺序，所以A随机发起了一个带有本地日志的proposal，形成了多数；对于Index11到Index19，由于没有形成有效的订单数据，因此形成noop来填补空缺；对于Index20，这是被大多数人认可的最简单的日志；以上四种情况分析，1、3、4问题不大。主要在场景2，对应的是第二轮不存在的7~10，然后又出现在第三列。按照Oceanbase的说法，在数据库日志同步场景下，这个问题是不可接受的。一个简单的例子是传输场景。如果用户转账时返回结果超时，他们会经常检查转账是否成功，以决定是否重试。一度。如果第一次查看转账结果，发现未生效重试，转账交易日志重新出现为幽灵重现日志，会导致用户重复转账。2、基于Multi-Paxos解决“重影”问题为了解决“重影”问题，基于Multi-Paxos实现的一致性体系，可以在每条日志内容中保存一个epochID，Proposer生成这个日志的时候可以指定使用当前的ProposalID作为epochID。在按照logID顺序回放日志时，因为leader在启动服务前必须写入一条StartWorking日志，如果epochID变得比之前的日志小，说明这是一条“幽灵重现”的日志，应该忽略。（说明一下，我觉得这里的顺序是先填坑，再写StartWorkingID，再提供服务）。上面的例子说明，在Round3中，当A作为leader开始时，需要通过日志回放重新确认。不用说，index1~5的日志epochID为1，然后进入epochID为2的阶段，index6会被确认为2的StartWorking日志的epochID，然后是index7~10，因为这是epochID为1的日志，比上一条日志的epochID小，将被忽略。至于Index11~19的日志，EpochID应该跟上一轮你看到的作为leader的StartWorkingID（当然ProposeID还是要维持在3），或者因为是noop日志，可以specializeit，也就是这部分日志不参与epochID的大小比较。那么索引20的日志也会被重新确认。最后，当索引21被写入StartWorking日志并得到多数人确认后，A作为leader开始接收请求。三、解决基于Raft的“重影”问题3.1关于Raft日志恢复首先说说Raft日志恢复。在Raft中，每次选出的Leader都必须包含已提交的数据（抽屉原则，选出的Leader是多数中最新的数据，必须包含大多数节点上已提交的数据），新的Leader会覆盖不一致的其他节点上的数据。AlthoughthenewlyelectedleadermustincludetheLogEntrythattheleaderoftheprevioustermhascommitted,itmayalsoincludethelogentrythattheleaderoftheprevioustermhasnotcommitted.这部分LogEntry需要改成Committed，比较麻烦。需要考虑到Leader发生了多次切换，LogRecovery还没有完成。需要保证最终的proposal是一致的、确定的，否则就会出现所谓的ghostrecurrence问题。因此在Raft中增加了一个约束：对于上一个Term未提交的数据，只有修复到大多数节点，并且至少有一个新Term下的新LogEntry被复制或修复到大多数节点，才可以以前未提交的数据被视为已提交的日志条目更改。InordertoconverttheuncommittedLogEntryoftheprevioustermtoCommitted,Raft'ssolutionisasfollows:RaftalgorithmrequirestheLeadertoaddaspecialinternallogofNoopimmediatelyafterbeingelected,andimmediatelysynchronizetoothernodestorealizealltheprevious未提交的日志隐式提交。这保证了两件事：通过最大提交原则，不会丢失任何数据，即所有CommittedLogEntry都不会丢失；未提交的数据不会被读取，因为只有Noop被大多数节点同意并提交后（这样可以和之前的日志同步），服务才会对外正常工作；Noop日志本身也是一个分界线，提交Noop之前的LogEntry，之后的LogEntry会被丢弃。3.2Raftsolvesthe"ghostreappearance"problemForthescenariointhefirstsection,therewillbenosituationinRaftwhereAiselectedleaderinthethirdround.首先，为了选举，候选人将最后一个日志的任期号(lastLogTerm)与日志的长度(lastLogIndex)进行比较。B和C的lastLogTerm(t2)和lastLogIndex(20)都大于A的lastLogTerm(t1)和lastLogIndex(10)，所以leader只能出现在B和C内部。假设C成为leader后，leader会在运行过程中修复副本。对于A，它从logindex为6的位置开始，C会将自己的index为6及以后的日志条目复制给A。因此，A原来index6-10的日志被删除，并与C保持一致。最后，C将向跟随者发送一条noop日志条目。如果被大部分接收和提交，就会开始正常工作，所以不会出现索引7-10可以读取到值的情况。在这里考虑另一个更普遍的幽灵再现场景。考虑以下日志场景：1）第1轮，节点A是领导者，日志条目5和6尚未提交，节点A已关闭。此时客户端无法查询到Logentry5和6的内容。2）第2轮，B成为leader，将B中的Logentry3和4的内容复制到C，期间不写入任何内容当B是领导者时。3)Round3,ArecoversandBandCarerestarted,Aisre-electedastheleader,thenthecontentsofLogentry5and6arecopiedtoBandCagain,andatthistime,theclientqueriesagainand发现Logentry5和6的内容都没有了。Raft中添加了一个新的领导者。这个问题可以通过写一个当前Term的LogEntry来解决。其实和MultiPaxos说的写一个StartWorking日志是一样的。当B成为Leader后，会写入一个Term3的入口Noop日志，这里解决了上面提到的两个问题：在Term3的noop日志提交前，会先将B的索引3和4的日志内容复制到C，实现最大提交原则，保证不丢失数据，已经提交的日志条目不会丢失。即使A节点恢复了，由于A的lastLogTerm小于B、C，无法成为leader，所以A中未完成的commits只会被丢弃，所以后续读取不会读取LogEntry5、6里面的内容。4、解决基于Zab的“重影”问题4.1关于Zab的日志恢复Zab分为原子广播和崩溃恢复两个阶段。原子广播的过程也可以类比为raft提交交易的过程。崩溃恢复可以细分为两个阶段：Leader选举和数据同步。早期Zab协议选出的Leader满足以下条件：a)新选出的Leader节点包含本轮所有候选者中最大的zxid，也可以简单认为Leader拥有最新的数据。这种保证可以最大程度地确保Leader拥有最新的数据。b)leader选举过程中用于比较的zxid是根据每个candidate提交的数据生成的。zxid为64位，高32位为epoch号。leader每选举出一个新的leader，新的leader都会将epoch数加1，低32位为消息计数器。每收到一条消息，这个值+1，新的leader选举后这个值重置为0。这样设计的好处是老leader挂掉重启后，不会再被选举为leader，所以此时它的zxid必须小于当前的新leader。当旧领导者作为追随者连接到新领导者时，新领导者将清除所有具有旧纪元编号的未提交提案。Leader选出后，进入日志恢复阶段。会根据每个Follower节点发送的zxid，决定给每个Follower发送哪些数据，让Follower追上数据，从而满足最大提交原则，保证提交后的数据会被复制到Follower，每个Follower在追上数据后都会向Leader发送一个ACK。当Leader收到半数以上Follower的ACK，此时Leader会开始工作，整个ZAB协议就可以进入原子广播阶段。4.2Zab解决“幽灵重现”问题对于Section1的场景，根据ZAB选举阶段的机制保证，每次选举后epoch都会+1，作为下一轮zxid的最高32位.因此，假设在Round1阶段，A、B、C的EpochId为1，那么在接下来的Round2阶段，EpochId为2，所有基于这个Epoch生成的zxids必须大于所有zxidsonA、因此在Round3中，由于B和C的zxids都大于A，所以A不会被选为leader。A作为follower加入后，其上的数据会被新leader上的数据覆盖。可以看出对于情况一，zab是可以避免的。对于3.2节的场景，在Round2之后，B被选为leader，没有交易产生。在Round3选举中，由于A、B、C的最新日志没有变化，所以A的最后一条日志的zxid比B、C大，所以A会被选为leader。A将数据复制给B、C后，就会出现“重影”现象。为了解决“幽灵再现”的问题，在最新的Zab协议中，每次leader选举完成后，都会在本地保存一个文件，记录当前的EpochId（记为CurrentEpoch）。在选举过程中，CurrentEpoch会被首先读取并添加到选票中，发送给其他候选人。如果候选人发现CurrentEpoch比自己的小，他将忽略本次投票。如果他发现CurrentEpoch比他自己的大，他就会选择这个ballot。如果相等，他就比较zxid。因此，对于这个问题，在Round1中，A、B、C的CurrentEpoch为2；在Round2中，A的CurrentEpoch为2，B和C的CurrentEpoch为3；在第3轮中，由于B和C的CurrentEpoch大于A的CurrentEpoch，因此A无法成为领导者。5.进一步讨论在阿里云的Nuwa一致性体系中，采用类似Raft和Zab的做法，保证可以造成ghost重现的角色在新一轮中不会被选为leader，从而避免ghostlog来自再次出现。从服务端的角度来看，“幽灵再现”问题是在故障转移的情况下，新的leader并不知道当前的committedindex，也就是分不清日志条目是committed还是uncommitted，所以一定logrecovery是需要手段保证提交的日志不会丢失（最大提交原则），通过一个分界线（比如MultiPaxos的StartWorking，Raft的noop，Zab的CurrentEpoch）来决定日志是commit还是dropped，所以以免混淆不同的身份。“幽灵重现”问题的本质属于分布式系统的“第三状态”，即在网络系统中，一次请求有三种返回结果：成功、失败、未知超时。对于未知超时，服务器处理请求命令的结果可以是成功也可以是失败，但必须是两者之一，不能出现不一致。在client端，如果收到请求超时，client不知道底层当前状态，是成功还是失败，所以一般client的做法是重试，所以底层apply的业务逻辑需要要幂等，否则重试会导致数据不一致。
