分布式系统的一个核心问题就是数据的一致性。Paxos算法是分布式共识中的经典算法，用于解决分布式系统如何对某个值（分辨率）达成共识的问题。本文从Paxos的问题入手介绍EPaxos，介绍EPaxos的基本概念和直观理解。阅读本文需要一些分布式共识算法（如Paxos或Raft）的背景知识。EPaxos（EgalitarianPaxos）作为备受业界关注的下一代分布式共识算法，具有广阔的应用前景。但是放眼业界，目前还没有EPaxos的工程化实现，我什至没有看到一篇文章可以用更通俗的方式来解释EPaxos。EPaxos算法虽然理论很好，但由于难以理解，在工程实现上存在诸多挑战，实际应用还不成熟。本文旨在通俗易懂地介绍EPaxos算法，由浅入深，循序渐进，让只有Paxos或Raft等分布式共识算法基础的同学也能轻松理解EPaxos，真正让默默无闻的EPaxos变得平易近人，走进千家万户。Paxos的问题要从Paxos说起。Paxos是分布式共识算法的鼻祖，可以同时容忍2F+1个副本中的F个副本失效。一般情况下，Paxos需要两个阶段来达成决议：Prepare阶段和Accept阶段。在Prepare阶段，各副本竞争提案权，在Accept阶段，竞争提案权的副本发起提案，使提案在副本之间达成一致。使用Paxos就一系列值达成一致的过程如图1所示。三个副本，用不同的颜色标识，A、B、C、D是他们提出的值。他们竞争每个Instance并提出自己的价值：图1使用Paxos商定一系列价值Paxos独立决定每个Instance的价值。对于每一个Instance，运行完整的Paxos两阶段流程来确定Instance的值。Paxos需要至少两次网络往返才能达成决议。在并发情况下，可能需要更多的网络往返。极端情况下甚至会形成活锁，效率低下。为了解决这些问题，Multi-Paxos应运而生。Multi-Paxos在每个副本中选举一个Leader，提案由Leader发起，无竞争，解决了活锁问题。当提案都由Leader发起时，可以跳过Prepare阶段，将两个阶段改为一个阶段，提高效率。使用Multi-Paxos对一系列值达成一致的过程如图2所示。三个副本，用不同颜色标记，先进行leader选举，绿色副本被选为leader，然后不断提出A、B、C、D四个值：图2使用Multi-Paxos达成共识一系列的值Multi-Paxos首先选举出Leader。AftertheLeaderiselected,theInstance'sproposalrightbelongstotheLeader,andthereisnoneedtocompetefortheInstance'sproposalright.因此Prepare阶段可以省略，只需要一个阶段。Leader的存在提高了达成决议的效率，但也成为性能和可用性的瓶颈。leader需要处理的消息比其他replica多，各replica负载不均衡，资源利用率不高。leader宕机后，系统不可用，服务无法恢复，直到选出新的leader，降低了可用性。BasicPaxos的每个副本都可以提出，可用性高，但由于竞争冲突导致效率低下；Multi-Paxos通过选举Leader来避免冲突，提高效率，但同时引入了Leader瓶颈，降低了可用性。效率和可用性能否平衡？EPaxos就是为了解决这个问题而提出的。不同于Multi-Paxos引入Leader来避免冲突，EPaxos采用了另一种思路。它面对冲突并试图解决冲突。EPaxos的解决方案EPaxos是一种Leaderless共识算法。任何副本都可以发起提案。通常，需要一到两次网络往返才能达成解决方案。EPaxos没有leader选举开销，如果一个副本不可用，可以立即访问其他副本，可用性更高。每个副本都是负载均衡的，没有leader瓶颈，吞吐量更高。客户端可以选择就近的副本提供服务，在跨AZ、跨地域场景下延迟更小。与Paxos不同的是，所有的Instance都是预先编号的，然后每个Instance的值一个一个独立约定。EPaxos可以并发处理多个Instance，不需要预先给Instance编号，而是在运行时动态确定Instance之间的顺序。EPaxos不仅对每个Instance的值进行了约定，而且对Instance之间的相对顺序也进行了约定。EPaxos将不同Instance之间的相对顺序作为一致性问题，在replicas之间达成共识。因此，每个副本可以同时在不同的实例中发起提案。这些Instance的值和相对顺序约定好后，replicas再按照相对顺序重新排序，形成一致的顺序。使用EPaxos商定一系列值的过程如图3所示：三个副本，用不同颜色标示，每个副本都有自己的Instance空间，在每个Instance中提出自己的值，A，B，C、D是他们的建议值。每个Instance不仅在值上达成一致，而且在相对顺序上与其他Instance达成一致。图3使用EPaxos就一系列值达成一致。EPaxos的实例空间是二维的。每个副本在二维实例空间中都有一行。无需竞争提议Instance的权利。每个副本都可以在自己的实例空间中同时启动。Proposals在保持Instance之间的相对顺序的同时，就Instance的值和相对顺序达成一致。最后，每个副本根据相对顺序确定性地对Instance重新排序，即就一系列值达成一致。EPaxos引入了依赖关系（deps）的概念作为Instance的一个属性来表示Instance之间的相对顺序。A←B表示B依赖于A，也就是说A在B之前。每个Instance都有自己的依赖集。EPaxos维护了Instance之间的依赖关系，并允许依赖集和值在副本之间达成一致。最后，每个副本根据依赖关系对Instances进行重新排序，得到一致的值序列。在图3的情况下，最后每个replica商定的一系列值是：A←B←C←D。把EPaxos的Instance看成图上的一个节点，Instance的依赖集作为节点的出边。在Instance的值和依赖集达到分辨率后，图的节点和边在副本之间达成一致，因此每个副本都会看到相同的图。EPaxos对实例重新排序的过程类似于图的确定性拓扑排序。但是需要注意的是，EPaxos的Instances之间的依赖关系可能会形成一个循环，即图中可能存在循环，所以不是完全的拓扑排序。为了处理循环依赖，EPaxos的重新排序Instances的算法需要首先找到图的强连接组件。循环包含在强连接组件中。所有的强连通分量组成一个有向无环图（DAG），然后连通分量进行确定性的拓扑排序。EPaxosreorderinginstances的过程如图4所示，其中stronglyconnectedcomponents被背景色圈出：Figure4EPaxosreorderingprocessofInstancestofindthestronglyconnectedcomponents一般使用Tarjan算法，这是一个递归算法，实际压测发现递归实现容易爆栈，也给工程应用带来了一定的挑战。不同强连通分量中的实例根据确定的拓扑顺序进行排序。同一个强连通分量中的实例被并发提出，理论上可以按照任何确定性规则进行排序。EPaxos提出了一种方案，为每个实例维护一个seq序号。seq的大小大致反映了instanceproposals的顺序。期望全局唯一增量。同一个强连通分量中的实例根据seq的大小进行排序。在实现过程中，测试发现seq可能会重复，EPaxos论文中没有考虑到这一点。后续文章会更详细的介绍这个问题和解决方法。当一个Instance达到了分辨率，并且它所依赖的所有实例也都达到了分辨率时，排序过程就可以开始了。事实上，随着新Instance的不断运行，旧的Instance可能依赖于新的Instance，新的Instance也可能依赖于更新后的Instance。结果，依赖链不断延伸，没有尽头，排序过程一直无法进行，形成了活锁。这也是EPaxos工程应用面临的一大挑战。因为Instance排序算法是确定性的，每个replica根据一致的依赖图对Instance进行重新排序，得到一致的Instance序列，即对一系列值达成共识。总结EPaxos通过引入动态排序结合了BasicPaxos和Multi-Paxos的优点，兼顾了效率和可用性，具有广阔的应用前景。本文简要介绍了EPaxos的基本概念和直观认识，希望能让读者对EPaxos有一个整体的印象。想一想最后几个问题，有兴趣的同学可以想一想：EPaxosInstance没有预先编号，那么如何识别Instance呢？EPaxos如何确定Instance的依赖集，如何让依赖集达成共识？EPaxosInstances之间为什么会形成循环依赖，什么情况下会形成循环依赖？【本文为专栏作者《阿里巴巴官方技术》原创稿件，转载请联系原作者】点此查看作者更多好文
