分布式一致性（Consensus）作为分布式系统的基石，一直是计算机系统领域的研究热点。近年来，随着分布式系统的规模越来越大，对可用性和一致性的要求越来越高，分布式一致性的应用也越来越广泛。纵观分布式一致性在业界的应用，从Paxos的鼻祖一统天下，到Raft的火爆，再到现在无人领导的EPaxos备受关注。它背后的技术是如何演变的？本文将从技术角度探讨分布式一致性在业界的应用，从可理解性、易用性、效率、适用场景等角度进行对比分析。分布式一致性分布式一致性，简单的说就是在一个或多个进程提出一个值后，让系统中的所有进程都同意这个值。为了就某个值达成一致，每个进程都可以提出自己的提议，最后通过分布式共识算法，让所有正确运行的进程都学习到相同的值。分布式一致性在业界的应用是构建多副本状态机模型（ReplicatedStateMachine），实现高可用和强一致性。分布式一致性使得多台机器拥有相同的状态，运行相同的确定性状态机，当少数机器出现故障时整体仍然可以正常工作。PaxosPaxos至少需要两个阶段（Prepare阶段和Accept阶段）才能达成决议。Prepare阶段的作用：争取求婚权。只有赢得了求婚权，才能在Accept阶段发起求婚，否则需要重新战斗。学习之前提出的价值观。接受阶段使提案能够形成多数。一旦提案形成多数，决定就达成了，决定就可以开始学习了。如果Accept阶段被拒绝，则需要重新经过Prepare阶段。Multi-PaxosBasicPaxos需要至少两次网络往返才能达成决议。在并发情况下，可能需要更多。极端情况下甚至会形成活锁，效率低下。Multi-Paxos就是为了解决这个问题而提出的。Multi-Paxos选举一个Leader，由Leader发起提案。没有竞争，活锁问题就解决了。当提案都由Leader发起时，可以跳过Prepare阶段，将两个阶段改为一个阶段，提高效率。Multi-Paxos不假定一个唯一的领导者。它允许多个Leader同时提议而不影响安全性。在极端情况下，它会退化为BasicPaxos。Multi-Paxos和BasicPaxos的区别不在于它是Multi（BasicPaxos也可以是Multi），而是当同一个Proposer进行连续提案时，可以优化跳过Prepare直接进入Accept阶段，就这样。与直接从分布式一致性问题衍生出来的Paxos不同，Raft是从多副本状态机的角度提出的，使用更强的假设来减少需要考虑的状态，更容易理解和实现。Raft和Multi-Paxos有着千丝万缕的联系。下面总结一下Raft和Multi-Paxos的异同点。Raft和Multi-Paxos的概念相似：Raft的Leader是Multi-Paxos的Proposer。Raft的Term和Multi-Paxos的ProposalID本质上是一回事。Raft的LogEntry是Multi-Paxos的Proposal。Raft的LogIndex就是Multi-Paxos的InstanceID。Raft的Leader选举与Multi-Paxos的Prepare阶段本质上是一样的。Raft的日志复制是Multi-Paxos的Accept阶段。Raft和Multi-Paxos的区别：Raft假设系统任何时刻至多有一个Leader，提案只能由Leader（强Leader）发送，否则会影响正确性；而Multi-Paxos也会选举Leader，但只是为了提高效率，并没有限制提案只能由Leader（弱Leader）发送。StrongLeaders在工程上一般使用LeaderLease和LeaderStickiness来保证：LeaderLease：在上一个Leader的Lease到期后，随机等待一段时间再发起Leader选举，保证新旧Leader的Lease不重叠.LeaderStickiness：LeaderLease未到期的Followers拒绝新的Leader选举请求。Raft限制最新提交日志的节点才有资格成为领导者，而Multi-Paxos没有这样的限制。在确认日志之前，Raft会检查日志的连续性。如果检测到日志不连续，则会拒绝该日志，保证日志的连续性。Multi-Paxos不做这个检查并允许在日志中出现漏洞。Raft在AppendEntries中携带Leader的提交索引。一旦日志形成多数，Leader更新本地的commitindex完成提交，下一个AppendEntries会携带新的commitindex通知其他节点；Multi-Paxos不承担日志连通性，需要额外的提交消息通知其他节点。EPaxosEPaxos（EgalitarianPaxos）是在SOSP'13中提出的，比Raft早一点。然而，当Raft在业界大行其道时，EPaxos却长期被忽视。直到最近，EPaxos才开始受到业界的关注。EPaxos是一种Leaderless共识算法。任何副本都可以提交日志。通常，一次日志提交需要一到两次网络往返。EPaxos没有leader选举开销，如果一个副本不可用，可以立即访问其他副本，可用性更高。每个副本都是负载均衡的，没有leader瓶颈，吞吐量更高。客户端可以选择就近的副本提供服务，在跨AZ、跨地域场景下延迟更小。与Paxos和Raft不同的是，所有的Instance编号都是预先排序好的，然后得出每个Instance的值。EPaxos并没有预先指定Instance的顺序，而是在运行时动态确定Instance之间的顺序。EPaxos不仅对每个Instance的值进行了约定，而且对Instance之间的相对顺序也进行了约定。EPaxos将不同Instance之间的相对顺序视为一致性问题，并在replica之间达成共识，因此每个replica都可以在各自的Instance中并发发起提案。这些Instance的值和相对顺序约定好之后，再按照相对顺序重新排序，最后按顺序应用到状态机上。从图论的角度来看，对数就是图的节点，对数之间的顺序就是图的边。EPaxos分别对节点和边进行约定，然后使用拓扑排序来确定日志的顺序。图中也可能存在循环，EPaxos需要处理循环依赖。EPaxos引入了日志冲突的概念（类似于ParallelRaft，不是并发冲突的概念）。如果两个日志之间没有冲突（比如访问不同的key），它们的相对顺序无所谓，所以EPaxos只处理冲突的日志之间的相对顺序。如果并发提议的日志之间没有冲突，EPaxos只需要运行PreAccept阶段提交（FastPath），否则需要运行Accept阶段提交（SlowPath）。PreAccept阶段试图就日志与其他日志的相对顺序达成一致，同时维护日志与其他日志之间的冲突关系。如果运行PreAccept阶段，该日志与其他并发提出的日志没有冲突，该日志与其他日志的相对顺序已经约定好，直接发送异步Commit消息提交；否则，如果该日志与其他并发提出的日志存在冲突，日志的相对顺序尚未达成共识，则需要运行Accept阶段，让冲突的依赖关系达到多数，然后发送Commit消息以提交。EPaxos的FastPathQuorum为2F，可以优化为F+[(F+1)/2]，与Paxos和Raft在3副本和5副本时一致。SlowPath是PaxosAccept阶段，Quorum固定为F+1。EPaxos还有一个主动学习算法，可以用来在恢复时追赶日志。这里不做具体介绍。有兴趣的可以看看论文。从Paxos到Raft再到EPaxos的对比分析，其背后的技术是如何演进的，我们可以从算法本身做对比，下面主要从可理解性、效率、易用性和适用场景等角度进行对比。1可理解性众所周知，Paxos是出了名的晦涩难懂，不仅难以理解，而且难以实现。另一方面，Raft的目标是可理解性和易于实施。Raft的提出大大降低了分布式一致性的使用门槛，让分布式一致性变得大众化、平民化。因此，当Raft一经提出，便迅速获得青睐，异常火爆。地球推动了分布式一致性的工程应用。EPaxos比Raft更早被提出，但是很长一段时间都没有人关心它。一个很大的原因是EPaxos实在是太难懂了。EPaxos基于Paxos，但是比Paxos更难理解，这极大地阻碍了EPaxos的工程化应用。然而，金子总会发光。EPaxos由于其独特的优势，终于被人们发现并拥有广阔的前景。2效率从Paxos到Raft再到EPaxos，效率提升了吗？我们主要从负载均衡、消息复杂度、Pipeline和并发处理等方面来对比Multi-Paxos、Raft和EPaxos。负载均衡Multi-Paxos和Raft对Leader的负载较高，副本间负载不均衡，Leader很可能成为瓶颈。但是EPaxos不需要Leader，副本之间的负载是完全均衡的。消息复杂度Multi-Paxos和Raft选出leader后，只需一次网络往返就可以提交一条日志，但是Multi-Paxos需要额外的异步Commit消息提交，而Raft只需要推进本地commitindex，不需要使用额外的消息，根据日志冲突情况，EPaxos需要一到两次网络往返。因此，Raft的消息复杂度最低，其次是Paxos，EPaxos最高。Pipeline我们将Pipeline分为顺序Pipeline和乱序Pipeline。Multi-Paxos和EPaxos支持乱序流水线，而Raft只支持顺序流水线，因为假设日志是连续的。然而，Raft也可以实现乱序流水线。只需要在leader上为每个follower维护一个类似于TCP的滑动窗口，对应在每个follower上维护一个接收窗口，允许窗口内的日志不连续，而窗口外已经是连续的日志，一旦log是连续的，窗口会向前滑动，pipeline在窗口中可以乱序。并发处理Multi-Paxos沿用了Paxos的策略。一旦发现并发冲突，就会回滚重试，直到成功；Raft使用强leader避免并发冲突，Follwer不与leader竞争避免并发冲突；EPaxos直接面对并发冲突的问题，将冲突的依赖当做一致性问题来解决并发冲突。Paxos是冲突回退，Raft是冲突避免，EPaxos是冲突解决。Paxos和Raft的日志都是线性的，而EPaxos的日志是graph-like的，所以EPaxos有更好的并行性和更高的吞吐量。3可用性EPaxos的任何副本都可以提供服务。如果副本不可用，可以立即切换到另一个副本。复制失败对可用性的影响很小；而Multi-Paxos和Raft都依赖于Leader，当Leader不可用时需要重新选举Leader。在选举出新的领导者之前，该服务不可用。很明显EPaxos的可用性比Multi-Paxos和Raft要好，但是Multi-Paxos和Raft谁更易用呢？Raft是一个强有力的领导者。Followers必须等待旧Leader的Lease到期才能发起选举。Multi-Paxos是一个弱领导者。追随者可以随时竞选领导者。虽然一定程度上会影响效率，但是在leader失效的时候可以更快一些。恢复服务，所以Multi-Paxos比Raft有更好的可用性。4适用场景EPaxos比较适用于跨AZ、跨区域的场景，对可用性要求高的场景，Leader容易形成瓶颈的场景。Multi-Paxos和Raft很相似，适用场景也很相似。适用于内网场景、一般高可用场景、Leader不易形成瓶颈的场景。思考的最后，有几个思考题。有兴趣的同学可以考虑一下。欢迎大家在评论区留言：1）Paxos的ProposalID是否需要唯一，不唯一会影响正确性吗？2）如果Paxos不区分MaxProposalID和AcceptedProposalID合并为一个MaxProposalID，过滤掉ProposalID小于或等于MaxProposalID的Prepare和Accept请求会影响正确性吗？3）Raft的PreVote的作用是什么？PreVote是必要的吗？
