当前位置: 首页 > 科技观察

一文看懂EPaxos核心协议流程_0

时间:2023-03-15 22:10:43 科技观察

简介EPaxos(EgalitarianPaxos)作为备受业界关注的下一代分布式共识算法,具有广阔的应用前景。但是放眼业界,目前还没有EPaxos的工程化实现,更通俗的解释EPaxos的文章我还没有看到。EPaxos算法虽然理论很好,但由于难以理解,在工程实现上存在诸多挑战,实际应用还不成熟。本文旨在通俗易懂地介绍EPaxos算法,由浅入深,循序渐进,让只有Paxos或Raft等分布式共识算法基础的同学也能轻松理解EPaxos,真正让默默无闻的EPaxos变得平易近人,走进千家万户。在中,EPaxos由Paxos问题衍生而来,介绍了EPaxos的基本概念和直观理解。相信读者对EPaxos有一个整体的印象。本文将从比较Paxos和EPaxos的角度介绍EPaxos的核心协议流程。相信看完本文后,你能找到上一篇文章末尾留下的思考题的答案。阅读本文需要一些分布式共识算法(如Paxos或Raft)的背景知识。一、EPaxos的基本思想EPaxos是一种无领导者共识算法。不需要选举leader,任何副本都可以发起提案。Leaderless也可以看作是每个replica都是leader。从Multi-Paxos或者Raft的角度来看,如果使用多个group,每个leader分到不同的group。每个replica作为一个group的leader,同时作为所有其他group的leader。FollowerofGroup似乎可以达到类似Leaderless的效果。使用由多个组实现的Leaderless,每个组独立地同意一系列实例,每个组生成一个实例序列。不同组产生的实例相互独立,顺序无法确定。因此,跨组的一致性是一个大问题,无法在一致性层面解决,往往需要在上层使用分布式事务来解决。EPaxos解决了这个问题,实现了真正的Leaderless。EPaxos通过跟踪Instance之间的依赖关系来确定不同Group产生的Instance的相对顺序,然后通过排序将多个Group产生的多个Instance序列合并为一个全局Instance序列,实现跨Group的一致性,即真正的无领导者实现了。EPaxos首先运行共识协议,让每个副本对Instance的值和Instance依赖的相对顺序达成一致,然后运行排序算法,根据之前达成共识的Instance的相对顺序,对Instance进行全局排序,以及最终得到一个一致的全局Instance序列。以上是从Multi-Paxos或者Raft使用多组实现Leaderless的角度来看EPaxos的基本思路。实际组是共识算法以外的概念。为了方便介绍,这里介绍Group。EPaxos中没有Group的概念。但类似于Paxos或Raft,可以在EPaxos之上实现多个组。2.EPaxos的实例EPaxos的实例不同于Paxos。Paxos的实例是预先分配序号的,而EPaxos的实例是不预先分配序号的。每个副本可以乱序并发提交,但会跟踪和记录实例之间的依赖关系。最后根据依赖关系排序。这里简单总结一下区别:Paxos中EPaxosInstance和PaxosInstance的区别是通过全局不断递增的InstanceID来标识,也就是Instance的序号,全局唯一,不断递增。EPaxos的Instance空间是二维的,每个副本只有一行,所以用二维的R.i来标识,其中R是副本标识,i是副本中一个连续递增的整数,每递增一次新实例开始的时间。副本R拥有的Instance序列为R.1,R.2,R.3,...R.i,...EPaxosInstance相比Paxos有一些额外的属性:state标识当前InstanceStatus,可以预先-接受,接受,承诺。因为EPaxos的Instance有很多状态,所以需要一个特殊的状态字段标识。deps是依赖Instances的集合,存放所有依赖Instances的标识,也就是之前要执行的Instances。deps保存的是Instances之间的相对顺序,后面会根据deps对Instances进行排序。seq为Instance的序号,其值为deps中所有Instance的seq最大值加一,反映了Instanceproposals的顺序,用于后续排序。EPaxos的Instance的deps和seq属性和Instance的值是一样的,也需要replicas之间约定。后续的replicas会独立的根据deps和seq对Instance进行排序。因为EPaxos的排序算法是确定性的,每个副本根据相同的deps和seq对实例进行排序,最终得到一个全局一致的实例序列。将Instance视为图的顶点,deps是顶点的出边。图的顶点和边确定并在副本之间达成共识后,每个副本对图进行确定性排序,最终得到一致的Instance序列。三EPaxos共识协议Paxos需要两个阶段来提交一个值,EPaxos的Instance对setdeps和sequencenumberseq有更多的依赖。为了确定这些属性的值,EPaxos比Paxos多了一个stage。完整的EPaxos分为三个阶段,但并非每个阶段都是必需的。下表比较了Paxos和EPaxos的协议流程:Paxos和EPaxos的协议流程比较和Paxos相比,Prepare阶段和Accept阶段类似,但是EPaxos的PreAccept阶段的加入也是EPaxos最关键的阶段.正是因为EPaxos有更多的PreAccept阶段和更多的Instance状态,所以引入了特殊的状态属性来标识Instance的当前状态(pre-accepted、accepted、committed)。Prepare阶段的状态就不介绍了,因为Prepare阶段没有proposedvalue,可以通过是否有本地proposedvalue来区别于其他状态。通常情况下,EPaxos只运行PreAccept阶段,即Commit、Prepare、Accept阶段都可以跳过。EPaxos类似于Paxos。如果在任何阶段发现Instance被抢占,则需要回退到Prepare阶段重新开始。1Prepare阶段Prepare阶段的作用,EPaxos和Paxos类似,都是为了争取提议权,同时学习之前已经提议过的最新值。在EPaxos中,因为每个副本都有自己独立的Instance空间,所以在自己的Instance空间上提出,相当于Multi-Paxos的Leader,所以和Multi-Paxos类似,通常可以直接跳过Prepare阶段,直接Start与下一阶段。2PreAccept阶段PreAccept阶段是EPaxos独有的。它的作用是确定Instance的依赖集deps和序号seq,同时尽量使提议值、deps和seq在副本之间达成共识。如果PreAccept阶段已经达成一致,直接进入Commit阶段(FastPath),否则需要运行Accept阶段,然后进入Commit阶段(SlowPath)。PreAccept阶段如何确定Instance的依赖集deps和序号seq?其实比较简单。从副本的本地现有实例中,收集之前需要执行的实例,即本地deps集合,本地seq为本地deps中所有实例的seq的最大值加一。最终的依赖集deps取大部分replicas的localdepssets的并集,最终的序号seq取其localseq的最大值。每个replica并发提议时,不同replica的localdeps和localseq可能不一样,那么PreAccept阶段如何达成共识呢?如果足够多的副本(FastQuorum)具有相同的本地deps和本地seq,则已达成共识。否则,最终的依赖集deps取本地deps的大多数(SlowQuorum)副本的并集,最终序号seq取其本地seq的最大值,然后运行Accept阶段达成共识。PreAccept阶段的FastQuorum总是包括proposer,后面会讲到原因。FastQuorum的值不小于SlowQuorum。假设总副本数为N,可以容忍F个副本同时失败,N=2F+1,则FastQuorum=2F,优化后的EPaxos可以优化为F+[(F+1)/2]、SlowQuorum=F+1。FastQuorum的取值推导这里不再介绍,后续文章会详细讨论。SlowQuorum是replicas的多数,和Paxos的Accept阶段是一样的。3Accept阶段Accept阶段的作用与Paxos类似,但Paxos只是将提议的值同步给多数副本。EPaxos需要将提议的值、deps和seq同步到大多数副本。一旦形成多数,即达成决议。如果在PreAccept阶段已经达成决议,则可以跳过Accept阶段,直接进入Commit阶段。4Commit阶段Commit阶段的作用是,EPaxos和Paxos类似,将达成的决议异步发送给其他副本,以便其他副本学习该决议。不同的是EPaxos的resolution不仅包括resolutionvalue,还有deps和seq。4.EPaxos排序算法与Paxos不同。EPaxosInstances提交后,它们的顺序还没有确定,所以EPaxos需要一个额外的排序过程来对提交的Instances进行排序。当Instance被提交,其依赖集合deps中的所有Instance也都被提交时,就可以开始一个排序过程了。将EPaxos的Instance视为图的顶点,将Instance的依赖集deps视为顶点的出边。Instance的值和依赖集deps约定好后,图的顶点和边在副本之间约定,所以每个副本都会看到相同的依赖图。EPaxos对实例进行排序的过程类似于图的确定性拓扑排序。但是需要注意的是,EPaxos的Instances之间的依赖关系可能会形成一个循环,即图中可能存在循环,所以不是完全的拓扑排序。EPaxos的Instances排序算法为了处理循环依赖,需要先找到图的强连通分量,环路包含在强连通分量中。如果将一个强连通分量看作图整体的一个顶点,则所有强连通分量构造一个有向无环图(DAG),然后对所有强连通分量组成的有向无环图进行拓扑排序。EPaxos排序算法的流程如图1所示,其中背景色圈出的部分为强连通分量:EPaxos排序算法一般采用Tarjan算法求图的强连通分量,是一个递归算法。发现递归实现很容易爆栈,也给工程应用带来了一定的挑战。不同强连通分量中的实例根据确定的拓扑顺序进行排序。同一个强连通分量中的实例被并发提出,理论上可以按任何确定性规则进行排序。EPaxos为每个实例计算一个seq序号。seq的大小反映了实例提案的顺序。同一个强连通分量中的实例根据seq的大小进行排序。实际seq可能重复,不能保证全局唯一增量。EPaxos论文没有考虑到这一点。其实可以用seq加一个copyidentifier来排序。事实上,随着新Instance的不断运行,旧的Instance可能依赖于新的Instance,新的Instance也可能依赖于更新后的Instance。如此下去,依赖链可能会不断延伸,没有尽头,排序过程已经无法进行,形成Livelock。这也是EPaxos工程应用面临的一大挑战。由于Instance排序算法是确定性的,每个副本在根据一致的依赖图对Instance进行排序后,都会得到一个一致的Instance序列。五个EPaxos案例下面用一个具体的案例来介绍EPaxos的核心协议流程,如下图所示,系统由R1,R2,R3,R4,R5,5个副本组成,水平方向代表时间,取值分别为A、B、C提案流程如图所示。EPaxos共识协议案例中各个Instance的属性值如下表所示:EPaxos核心协议流程案例中Instance的属性1提议值A首先,R1运行PreAccept阶段发起提议值A。它首先获取自己的localdeps和localseq,此时,它没有任何localinstance,所以localdeps是一个空集,localseq为初始值1。它持久化了建议值A,localdeps和本地序列。然后R1向R2和R3广播PreAccept(A)消息。消息中携带建议值A、localdeps、localseq(图中未标注)。此时R1、R2、R3组成一个FastQuorum。PreAccept消息只能广播到FastQuorum中的副本。这种优化在EPaxos论文中被称为Thriftyoptimization。R2和R3收到PreAccept(A)消息后,分别获得自己的本地deps和本地seq。和R1类似,本地deps为空集,本地seq为1,持久化后回复R1。R1在FastQuorum中收到相同的localdeps和localseq副本,解决。最后deps为空集,seq为1,提交Commit阶段。2ProposedvalueB接下来,R5运行PreAccept阶段发起proposedvalueB,此时没有任何localinstance,所以localdeps为空集,localseq为初值1。local之后持久性,R5向R3和R4广播PreAccept(B)消息。R4回复的localdeps为空集,localseq为1,此时R3本地已经有一个值为A的Instance,所以R3回复的localdeps为{1.1},即{A}标记如图,localseq为2,即A的Instance的seq加一。FastQuorum中的replicas的localdeps和seq不都一样,所以需要运行Accept阶段,最后deps取大部分replicas的localdeps的并集为{1.1},即{A}图中标注,最终seq大部分replicas的本地seq最大值为2,通过Accept阶段,提议值B,最终deps,最终seq达到多数。最后,运行Commit阶段进行提交。3提议值C最后R1运行PreAccept阶段发起提议值C,此时R1本地已经有一个值为A的实例,所以本地deps为{1.1},也就是图中标注的{A},本地seq为3。本地持久化后,R1向R2和R3广播PreAccept(C)消息。此时R2和R3本地已经有值A和值B的Instance,所以R2和R3回复的本地deps为1.1,5.1},即图中标注的{A,B},本地seq为3,即B在Instance的seq上加一。FastQuorum中除proposerR1之外的其他replicas的localdeps和seq都是相同的,所以已经达成决议,最终deps为{1.1,5.1},即{A,B},seq为3,并提交Commit阶段。4个建议值A、B、C的实例按照依赖集deps排序。顺序(右)实例A的deps是空集,所以没有出边;实例B的deps是{A},所以有一条出边指向A;实例C的deps为{A,B},所以有两条出边分别指向A和B。依赖图中没有循环依赖,已经是有向无环图(DAG)。因此,顶点A、B、C均为强连通分量,经过确定性拓扑排序后得到它们的顺序:A<—B<—C,如图(右)所示。6EPaxos讨论1InstanceConflictEPaxos引入了InstanceConflict(Interfere)的概念(类似于ParallelRaft,并不是ConcurrencyConflict的概念)。如果两个Instance的值没有冲突(比如访问不同的key),它们的Sequence无所谓,甚至可以并行处理,所以EPaxos只处理冲突日志之间的依赖关系。EPaxos的Instance的依赖集deps存放了Instance之前需要执行的Instance。引入冲突后,将与Instance发生冲突的Instance存放在deps中。冲突是一个与具体应用相关的概念。引入冲突后,所有实例不再是全序,而是偏序,减少了依赖,降低了SlowPath的概率,提高了效率。2FastQuorumFastQuorum值的推导留待后续文章使用。这里先讨论为什么PreAccept阶段的FastQuorum总是包含proposer。在EPaxos的每个阶段,proposer总是先在本地持久化,然后再广播消息给其他replicas。也就是说,proposer一直在Quorum中,所以在判断是否达到Quorum时,proposer总可以算作一票。在PreAccept阶段,proposer将自己本地的deps和seq包含在PreAccept消息中,作为其他replicas计算自己本地deps和seq的依据,使得proposer本地的deps和seq始终包含在最终的deps和seq中,因此,PreAccept阶段的FastQuorum总是包含提议者。EPaxos总是先本地持久化成功再广播给其他副本,这样可以降低FastQuorum,但也会造成本地持久化和网络消息收发不兼容,降低一些效率,同时也会让proposer无法容忍本地磁盘的情况损坏,这些都是EPaxos工程应用必须面对的问题。为什么FastQuorum的值不小于SlowQuorum?FastQuorum的价值这里就不用推论了,这个结论可以直观得出。在Paxos中,一个副本提出一个值,所有的副本只能有两个结果,接受或者不接受这个值。在EPaxos中,每个副本可能给出不同的deps和seq,所以需要更多的副本给出相同的结果,以保证在一次副本失败后能够恢复正确的结果。7个EPaxos伪代码到这里,相信读者已经可以看懂EPaxos核心协议流程的伪代码了。EPaxos核心协议流程的伪代码如下图所示。为简单起见,省略了与ProposalID(ProposalID,或BallotNumber,投票编号)相关的部分,与Paxos相同。在伪代码中,日志被看作是一个命令(Command),每个Instance约定一个Command,每个副本用一个二维数组cmds保存接收到的Command。EPaxosCoreProtocol伪代码8总结EPaxos不仅通过显示和维护Instance之间的依赖关系,去除了对Leader的依赖,还允许Instance乱序并发提交,可以更好的优化Pipelining,显式维护依赖关系,同时也使得-可以按顺序执行。EPaxos支持乱序确认、乱序提交、乱序执行,理论上可以有更高的吞吐量。同时,我们也可以看到EPaxos工程应用中的一些挑战。这些都是EPaxos工程实施中需要解决的问题。本文从比较Paxos和EPaxos的角度介绍了EPaxos的核心协议流程,但EPaxos的内容并不局限于这些,尤其是故障转移场景下如何保证日志序列的顺序。思考结束,还剩下几个思考题。有兴趣的同学可以先思考一下:Instance的seq为什么会重复,什么情况下会重复?如何推导出FastQuorum的价值?如果一个Instance的共识协议过程还没有完成,它的proposer宕机了,其他的replicas应该如何处理这个Instance呢?