简介： EPaxos（Egalitarian Paxos）作为工业界备受瞩目的下一代分布式一致性算法，具备广大的利用前景。但纵观业内，至今仍未呈现一个EPaxos的工程实现，甚至都没看到一篇能把EPaxos讲得艰深一点的文章。EPaxos算法实践虽好，但因为其实在艰涩难懂，工程实现上也有很多挑战，理论利用落地尚未成熟。本文将用通俗易懂的语言介绍EPaxos算法，由浅入深、一步一步的让只有Paxos或Raft等分布式一致性算法根底的同学都能轻易看懂EPaxos，真正将艰涩难懂的EPaxos，变的平易近人，带入千万家。
作者 | 祥光（严祥光）
起源 | 阿里技术公众号
引言
EPaxos（Egalitarian Paxos）作为工业界备受瞩目的下一代分布式一致性算法，具备广大的利用前景。但纵观业内，至今仍未呈现一个EPaxos的工程实现，甚至都没看到一篇能把EPaxos讲得艰深一点的文章。EPaxos算法实践虽好，但因为其实在艰涩难懂，工程实现上也有很多挑战，理论利用落地尚未成熟。
本文旨在通俗易懂地介绍EPaxos算法，由浅入深、一步一步的让只有Paxos或Raft等分布式一致性算法根底的同学都能轻易看懂EPaxos，真正将艰涩难懂的EPaxos，变的平易近人，带入千万家。
在《一文理解分布式一致性算法EPaxos》中，从Paxos的问题引出EPaxos，介绍了EPaxos的基本概念与直观了解，置信读者曾经对EPaxos有了整体的印象。
本文将从Paxos与EPaxos比照的角度，介绍EPaxos外围协定流程。上一篇文章最初留下的思考题，置信在浏览完本文后，都能找到答案。浏览本文须要一些Paxos或Raft等分布式一致性算法背景。
一 EPaxos根本思维
EPaxos是一个Leaderless的一致性算法，无需选举Leader，任意正本均可发动提议。
Leaderless也能够看作每个正本都是Leader，从Multi-Paxos或Raft的角度看，如果应用多Group，将每个Leader划分到不同的Group，每个正本负责一个Group的Leader，同时负责其它所有Group的Follower，如同也能够做到相似Leaderless的成果。
应用多Group实现的Leaderless，每个Group独立的对一系列Instance达成统一，每个Group产生一条Instance序列，不同Group产生的Instance彼此独立，不能确定先后顺序。因而跨Group的一致性是一大问题，在一致性层面无奈解决，往往须要在下层应用分布式事务来解决。
EPaxos解决了这个问题，实现了真正的Leaderless。EPaxos通过跟踪Instance之间的依赖关系，确定不同Group产生的Instance的绝对程序，而后通过排序将多Group产生的多条Instance序列合并成一条全局的Instance序列，实现了跨Group的一致性，也即实现了真正的Leaderless。
EPaxos先运行共识协定，使各正本对Instance的值和Instance依赖的绝对程序达成统一，随后运行排序算法，基于后面曾经达成共识的Instance的绝对程序，对Instance进行全局排序，最终失去统一的全局Instance序列。
以上是站在Multi-Paxos或Raft应用多Group实现Leaderless的角度引出EPaxos的根本思维，理论Group是一致性算法之外的概念，这里引入Group只是为了不便介绍，理论EPaxos中并没有Group的概念，但与Paxos或Raft相似，能够在EPaxos之上实现多Group。
二 EPaxos的Instance
EPaxos的Instance与Paxos有所不同，Paxos的Instance当时调配序号，但EPaxos的Instance不当时调配序号，各正本能够并发的乱序提交，但跟踪记录Instance之间的依赖关系，最初依据依赖关系排序。这里先总结一下不同点：
EPaxos的Instance与Paxos的不同点
Paxos的Instance由全局间断递增的InstanceID标识，InstanceID也是Instance的序号，全局惟一，间断递增。
EPaxos的Instance空间是二维的，每个正本领有其中一行，因而由二维的R.i标识，其中R为正本标识，i为正本内间断递增的整数，每开始一个新的Instance就加一。正本R领有的Instance序列为R.1，R.2，R.3，...... R.i，......
EPaxos的Instance绝对Paxos还有一些额定的属性：
- state标识Instance以后的状态，可取值pre-accepted、accepted、committed。因为EPaxos的Instance的状态比拟多，所以须要专门的state字段标识。
- deps为依赖的Instance汇合，寄存所有依赖的Instance的标识，即要在后面执行的Instance。deps保留了Instance之间的绝对程序，后续将基于deps对Instance进行排序。
- seq为Instance的序列号，其值为deps中所有Instance的seq的最大值加一，反映Instance提议的程序，后续排序的时候应用。
EPaxos的Instance的deps和seq属性与Instance的值一样，也须要在各正本之间达成统一，后续各正本将独立的基于deps和seq对Instance进行排序。因为EPaxos的排序算法是确定性的，各正本基于雷同的deps和seq对Instance进行排序，最终会失去统一的全局Instance序列。
将Instance看作图的顶点，deps就是顶点的出边，图的顶点和边都确定并在各正本之间达成统一之后，各正本对图进行确定性的排序，最终失去统一的Instance序列。
三 EPaxos共识协定
Paxos提交一个值须要两阶段，而EPaxos的Instance多了依赖汇合deps和序列号seq，为了确定这些属性的值，EPaxos比Paxos多了一个阶段。残缺的EPaxos有三阶段，但并非每个阶段都是必须的，下表将Paxos与EPaxos的协定流程进行比照：
Paxos与EPaxos的协定流程比照
EPaxos与Paxos相比，Prepare阶段和Accept阶段相似，但EPaxos多了PreAccept阶段，也是EPaxos最要害的一个阶段。正因为EPaxos多了PreAccept阶段，Instance的状态更多了，所以引入专门的state属性来标识Instance以后所处的状态（pre-accepted、accepted、committed）。没有引入Prepare阶段的状态，是因为Prepare阶段没有提议值，能够通过本地有无提议值来与其它状态辨别。通常状况下，EPaxos只运行PreAccept阶段，即可Commit，Prepare阶段和Accept阶段都能跳过。
EPaxos与Paxos相似，在任意阶段如果发现Instance被抢占，都须要回退到Prepare阶段从新开始。
1 Prepare阶段
Prepare阶段的作用，EPaxos与Paxos相似，都是为了争取提议权，同时学习之前曾经提议的最新值。在EPaxos中，因为每个正本都领有各自独立的Instance空间，在本人的Instance空间上提议，相当于Multi-Paxos的Leader，所以与Multi-Paxos相似，通常状况下可间接跳过Prepare阶段，间接从下一阶段开始。
2 PreAccept阶段
PreAccept阶段是EPaxos特有的，其作用是确定Instance的依赖汇合deps和序列号seq，同时尽量让提议值、deps和seq在各正本间达成统一。若PreAccept阶段曾经达成统一，则间接到Commit阶段（Fast Path），否则须要运行Accept阶段，而后才到Commit阶段（Slow Path）。
PreAccept阶段是如何确定Instance的依赖汇合deps和序列号seq的呢？其实比较简单，从正本本地已存在的Instance中，收集须要在后面执行的Instance，即本地deps汇合，本地seq即本地deps中的所有Instance的seq的最大值加一。最终的依赖汇合deps取大多数正本的本地deps汇合的并集，最终的序列号seq则取他们的本地seq的最大值。
各正本并发提议的时候，不同正本的本地deps和本地seq都可能不一样，那么PreAccept阶段如何能力达成统一呢？如果有足够多的正本（Fast Quorum）的本地deps和本地seq都雷同，则曾经达成了统一。否则，最终的依赖汇合deps取大多数（Slow Quorum）正本的本地deps的并集，最终的序列号seq取它们的本地seq的最大值，而后运行Accept阶段达成统一。
PreAccept阶段的Fast Quorum始终蕴含提议者，会在前面探讨起因。Fast Quorum的值不小于Slow Quorum。假如正本总数为N，可容忍F个正本同时生效，N = 2F + 1，则Fast Quorum = 2F，优化后的EPaxos可优化至F + [ (F + 1) / 2 ]，Slow Quorum = F + 1。Fast Quorum取值的推导这里先不做介绍，会在后续文章中具体探讨，Slow Quorum即大多数正本，与Paxos的Accept阶段雷同。
3 Accept阶段
Accept阶段的作用，EPaxos与Paxos相似，但Paxos只将提议值同步到大多数正本，EPaxos须要将提议值、deps和seq都同步到大多数正本，一旦造成多数派则决定达成。若在PreAccept阶段曾经达成决定，则可跳过Accept阶段，间接进入Commit阶段。
4 Commit阶段
Commit阶段的作用，EPaxos与Paxos相似，都是将达成的决定异步发送给其它正本，让其它正本学习到决定，不同的是EPaxos的决定不仅包含决定值，还包含deps和seq。
四 EPaxos排序算法
与Paxos不同，EPaxos的Instance提交后，它们的程序还没有确定，因而EPaxos须要一个额定的排序过程，对已提交的Instance进行排序。当Instance被提交，并且其依赖汇合deps中的所有Instance也都提交后，就能够开始一次排序过程。
将EPaxos的Instance看作图的顶点，Instance的依赖汇合deps看作顶点的出边，Instance的值和依赖汇合deps达成统一后，图的顶点和边就在各正本之间达成统一，因而各正本会看到雷同的依赖图。
EPaxos对Instance排序的过程，相似于对图进行确定性的拓扑排序。但须要留神的是EPaxos的Instance之间的依赖可能造成环，即图中可能会有环路，因而不齐全是拓扑排序。
为了解决循环依赖，EPaxos对Instance排序的算法须要先寻找图的强连通重量，环路都蕴含在了强连通重量中，如果把一个强连通重量整体看作图的一个顶点，则所有强连通重量形成一个有向无环图（DAG），而后对所有的强连通重量形成的有向无环图进行拓扑排序。
EPaxos排序算法的流程如图1所示，其中由背景色圈起来的局部是强连通重量：
EPaxos排序算法
寻找图的强连通重量个别应用Tarjan算法，它是一个递归算法，实测发现递归实现很容易爆栈，也给工程利用带来了肯定的挑战。
不同强连通重量中的Instance依照确定性的拓扑程序排序，同一强连通重量中的Instance是并发提议的，实践上能够按任意确定性规定排序。EPaxos为每个Instance计算了一个seq序列号，seq的大小反映了Instance提议的程序，同一强连通重量外面的Instance依照seq大小排序。理论seq可能反复，并不能保障全局惟一递增，EPaxos论文并未思考到这一点，理论能够应用seq加正本标识排序。
事实上，随着新的Instance一直的运行，旧的Instance可能依赖新的Instance，新的Instance又可能依赖更新的Instance，如此上来可能导致依赖链一直延长，没有终结，排序过程始终无奈进行，造成活锁。这也是EPaxos工程利用的一大挑战。
因为Instance排序算法是确定性的，各正本基于统一的依赖图对Instance排序后，将失去统一的Instance序列。
五 EPaxos案例
上面应用一个具体的案例，介绍EPaxos的外围协定流程，如下图所示，零碎由R1、R2、R3、R4、R5，5个正本组成，程度方向代表工夫，值A、B、C的提议流程如图所示。
EPaxos共识协定
案例中各Instance的属性取值如下表所示：
EPaxos外围协定流程案例中Instance的属性
1 提议值A
首先R1运行PreAccept阶段发动提议值A，它首先获取本人的本地deps和本地seq，此时它本地还没有任何Instance，所以本地deps为空集，本地seq为初始值1，它长久化提议值A、本地deps和本地seq。
而后R1向R2、R3播送PreAccept(A)音讯，音讯携带提议值A、本地deps、以及本地seq（图中未标示），此时R1、R2、R3组成Fast Quorum。PreAccept音讯能够只播送给Fast Quorum中的正本，EPaxos论文中将这种优化称为Thrifty优化。
R2、R3收到PreAccept(A)音讯后，别离获取本人的本地deps和本地seq，与R1相似，本地deps为空集，本地seq为1，长久化后回复R1。
R1收到Fast Quorum中的正本的本地deps和本地seq都雷同，决定达成，最终的deps为空集，seq为1，运行Commit阶段提交。
2 提议值B
接下来R5运行PreAccept阶段发动提议值B，此时它本地也还没有任何Instance，所以本地deps为空集，本地seq为初始值1。R5本地长久化后，向R3、R4播送PreAccept(B)音讯。
R4回复的本地deps为空集，本地seq为1，R3此时本地曾经有了值A的Instance，因而R3回复的本地deps为{1.1}，也即图上标示的{A}，本地seq为2，即A的Instance的seq加一。
Fast Quorum中的正本的本地deps和seq不都雷同，因而须要运行Accept阶段，最终的deps取大多数正本的本地deps的并集为{1.1}，也即图上标的{A}，最终的seq取大多数正本的本地seq的最大值为2，通过Accept阶段，将提议值B、最终的deps、最终的seq达成多数派。最初运行Commit阶段提交。
3 提议值C
最初R1运行PreAccept阶段发动提议值C，此时R1本地曾经有了值A的Instance，因而本地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加一。
Fast Quorum中除了提议者R1以外的其它正本的本地deps和seq都雷同，因而决定曾经达成，最终的deps为{1.1，5.1}，也即{A，B}，seq为3，运行Commit阶段提交。
4 排序
提议值A、B、C的Instance依照它们的依赖汇合deps画出的依赖关系如下图（左）所示：
提议值A、B、C的Instance之间的依赖关系（左），排序之后的程序（右）
A的Instance的deps为空集，因而没有出边；B的Instance的deps为{A}，因而有一条出边指向A；C的Instance的deps为{A，B}，因而有两条出边，别离指向A和B。
依赖关系图中没有循环依赖，曾经是一个有向无环图（DAG）。因而顶点A、B、C各自是一个强连通重量，进行确定性的拓扑排序后失去它们的程序：A <— B <— C，如图如图（右）所示。
六 EPaxos探讨
1 Instance抵触
EPaxos引入Instance抵触（Interfere）的概念（与Parallel Raft相似，与并发抵触不是一个概念），若两个Instance的值之间没有抵触（例如拜访不同的key），则它们的先后顺序无关紧要，甚至能够并行处理，因而EPaxos只解决有抵触的日志之间的依赖关系。
EPaxos的Instance的依赖汇合deps，寄存的是须要在该Instance之前执行的Instance。引入抵触之后，deps中寄存的是与该Instance抵触的Instance。
抵触是一个与具体利用相干的概念，引入抵触之后，所有Instance不再是全序的，变成了偏序的，缩小了依赖，升高了Slow Path的概率，进步了效率。
2 Fast Quorum
对于Fast Quorum取值的推导，留待后续文章介绍，这里先探讨下，为什么PreAccept阶段的Fast Quorum始终蕴含提议者。
EPaxos在每个阶段，提议者总是本地先长久化胜利之后，再播送音讯给其它正本。也就是说提议者总是在Quorum中，因而判断是否达成Quorum时，提议者总是能够算一票。
在PreAccept阶段，提议者将其本地deps和seq蕴含在了PreAccept音讯中，作为其它正本计算它们本地deps和seq的根底，使得提议者的本地deps和seq总是蕴含在最终的deps和seq中，因而PreAccept阶段的Fast Quorum始终蕴含提议者。
EPaxos总是先本地长久化胜利之后再播送给其它正本，这样能够减小Fast Quorum，但也导致本地长久化与网络音讯收发不能并行进行，升高了一些效率，同时也使得提议者不能容忍本地磁盘损坏的状况，这些都是EPaxos工程利用必须面对的问题。
Fast Quorum的值为什么不会小于Slow Quorum呢？这里无需推导Fast Quorum的取值，从直观上就能够得出这个论断。在Paxos中一个正本提议一个值，所有正本只会有两种后果，承受或者不承受这个值。而在EPaxos中每个正本都可能给出不同的deps和seq，因而须要更多的正本给出雷同的后果能力保障在有正本生效后能复原出正确的后果。
七 EPaxos伪代码
到这里，置信读者曾经能够看懂EPaxos外围协定流程的伪代码了。EPaxos外围协定流程伪代码如下图所示，为了简略，省略了提议ID（Proposal ID，或者叫Ballot Number，投票编号）相干的局部，这部分与Paxos雷同。
伪代码中将日志视为命令（Command），每个Instance对一条Command达成统一，每个正本应用一个二维数组cmds保留收到的Command。
EPaxos外围协定流程伪代码
八 总结
EPaxos通过显示保护Instance之间的依赖关系，不仅去除了对Leader的依赖，还使得Instance能够并发的乱序提交，能够更好的进行Pipelining优化，同时显式保护依赖也使得乱序执行成为可能。EPaxos反对乱序确认、乱序提交、乱序执行，实践上能够有更高的吞吐量。同时也能够看到一些EPaxos工程利用的挑战，这些都是EPaxos工程落地要解决的问题。
本文从Paxos与EPaxos比照的角度，介绍了EPaxos外围协定流程，但EPaxos的内容决不仅仅只有这些，特地是Failover场景下，如何保障日志序列的程序性。
思考
最初留下几个思考题，感兴趣的同学能够先思考思考：
- Instance的seq为什么会反复，什么状况下会反复？
- Fast Quorum的取值如何推导？
- 如果一个Instance的共识协定流程还未实现，其提议者就宕机了，其它副本该怎么解决这个Instance？
原文链接
本文为阿里云原创内容，未经容许不得转载。