简介：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？
原文链接
本文为阿里云原创内容，未经容许不得转载。