Paxos

Paxos 达成一个决议至少需要两个阶段（Prepare 阶段和 Accept 阶段）。

• Prepare 阶段的作用：争取提议权，争取到了提议权才能在 Accept 阶段发起提议，否则需要重新争取；学习之前已经提议的值。
• Accept 阶段使提议形成多数派，提议一旦形成多数派则决议达成，可以开始学习达成的决议。Accept 阶段若被拒绝需要重新走 Prepare 阶段。

Multi-Paxos

Basic Paxos 达成一次决议至少需要两次网络来回，并发情况下可能需要更多，极端情况下甚至可能形成活锁，效率低下，Multi-Paxos 正是为解决此问题而提出。

Multi-Paxos 选举一个 Leader，提议由 Leader 发起，没有竞争，解决了活锁问题。提议都由 Leader 发起的情况下，Prepare 阶段可以跳过，将两阶段变为一阶段，提高效率。Multi-Paxos 并不假设唯一 Leader，它允许多 Leader 并发提议，不影响安全性，极端情况下退化为 Basic Paxos。

Multi-Paxos 与 Basic Paxos 的区别并不在于 Multi（Basic Paxos 也可以 Multi），只是在同一 Proposer 连续提议时可以优化跳过 Prepare 直接进入 Accept 阶段，仅此而已。

Raft

不同于 Paxos 直接从分布式一致性问题出发推导出来，Raft 则是从多副本状态机的角度提出，使用更强的假设来减少需要考虑的状态，使之变的易于理解和实现。复制状态机的想法是将服务器看成一个状态机，而一致性算法的目的是让多台服务器/状态机能够计算得到相同的状态，同时，如果有部分机器宕机，集群作为一个整体依然能继续工作。复制状态机一般通过复制日志（replicated log）来实现，如下图：

服务器会将客户端发来的命令存成日志，日志是有序的。而服务器状态机执行命令的结果是确定的，这样如果每台服务器的状态机执行的命令是相同的，状态机最终的状态也会是相同的，输出的结果也会是相同的。而如何保证不同服务器间的日志是一样的呢？这就是其中的“一致性模块”的工作了。一致性模块（consensus module）在收到客户端的命令时（②），一方面要将命令添加到自己的日志队列中，同时需要与其它服务器的一致性模块沟通，确保所有的服务器将最终拥有相同的日志，即使有些服务器可能挂了。实践中至少需要“大多数(大于一半)”服务器同步了命令才认为同步成功了。

Raft vs Paxos

Paxos, 我们首先要限制必须是 Basic Paxos, 否则没有争论的意义. Basic Paxos 本身是赤裸裸的, 限制少, 灵活, 因为它是基础中的基础. 也正因为太基础了, 所以脱离群众, 离真正实用太远. 这也是为什么这么多年, 业界没有一个真正意义上的开源的 Paxos 编程语言库。

Raft 是这么多年, 对 Paxos 工程实践的总结和提炼, 以学术研究(论文)的方式加以证明, 并提供了工程指导. 所以, 这才是为什么有那么多的 Raft 开源库, 而大家的代码结构又大同小异的原因. 因为, 幸福的家庭都是相似的, 不幸的家庭各有各的不同。

我总结一下, Paxos 和 Raft 的争议点在有哪些, 这些争议点是职责划分的问题, 你很快就会发现.

1. 单主还是多主

“多主"是很多人不选择 Raft 的原因(没什么所谓选择不选择 Paxos, Paxos 就是基础). 一是多写入点, 客户端可以随机选取任何一台服务器来接收请求, 所以, 客户端的代码非常简单, 配置服务器的 ip:port 列表, 用随机算法或者 round robin 算法选一台创建 socket 连接即可. 二是故障恢复时间, Paxos 把故障恢复隐含到了每一次请求当中, 不像 Raft 那样明确的划分职责, 独立出一个选主过程. 独立的选主过程占用独立的时间片, 阻塞正常请求, 所以理论上要增加故障时间.

但是, Raft 当然可以优化成在每一次请求都选主, 工程实践上没问题, 但是, 这不就成了 Basic Paxos 了吗? 所以, 没人这么做. 大多数情况下就是这样的, Paxos 加了限制就成了 Raft, 而 Raft 做了优化就变成了 Paxos. 向谁靠拢的选择而已.

2. 顺序提交还是乱序提交

这是争论最多的地方. 事实上, 一个系统必然有乱序(并发)的地方, 同时也会存在顺序(串行)的地方, 没有任何一个大型的系统只包含并发或者只包含串行, 不可能, 我在工程上没遇见过这样的系统. 问题就在于, 你想把并发(岔路口)开在哪?

举一个例子, 网络编程中, 你可以在 accept 之后就启动线程, 每个线程处理一个 socket, 也就是你把并发的岔路口开在了这里. 你当然也可以用 IO 多路复用(如 epoll), 在一个线程中顺序地(但不阻塞)地读取 socket, 然后在读完请求之后, 启动线程处理请求, 也就是, 你把并发的岔路开在了那里.

Paxos vs Raft 就是这样的例子, Raft 认为把串行的部分交给我, 然后你(状态机)再并发. 但是用 Paxos 的人认为, 关于是串行还并行, 应该由我(状态机)来决定, 共识算法没必要加这个限制. 孰优孰劣? 任何一个理性和聪明的人都能得出答案.

用 Paxos 的人, 希望自己把控更多的东西, 所以 Paxos 非常薄, 薄得几乎不存在, 也就没有所谓的 Paxos 库了, 因为它的职责太少, 以致于根本不值得独立成一个库. 用 Raft 的人相反, 把更多的职责加给 Raft, 不重新发明轮子.

EPaxos

EPaxos（Egalitarian Paxos）于 SOSP'13 提出，比 Raft 还稍早一些，但 Raft 在工业界大行其道的时间里，EPaxos 却长期无人问津，直到最近，EPaxos 开始被工业界所关注。EPaxos 是一个 Leaderless 的一致性算法，任意副本均可提交日志，通常情况下，一次日志提交需要一次或两次网络来回。EPaxos 无 Leader 选举开销，一个副本不可用可立即访问其他副本，具有更高的可用性。各副本负载均衡，无 Leader 瓶颈，具有更高的吞吐量。客户端可选择最近的副本提供服务，在跨 AZ 跨地域场景下具有更小的延迟。

不同于 Paxos 和 Raft，事先对所有 Instance 编号排序，然后再对每个 Instance 的值达成一致。EPaxos 不事先规定 Instance 的顺序，而是在运行时动态决定各 Instance 之间的顺序。EPaxos 不仅对每个 Instance 的值达成一致，还对 Instance 之间的相对顺序达成一致。EPaxos 将不同 Instance 之间的相对顺序也做为一致性问题，在各个副本之间达成一致，因此各个副本可并发地在各自的 Instance 中发起提议，在这些 Instance 的值和相对顺序达成一致后，再对它们按照相对顺序重新排序，最后按顺序应用到状态机。

从图论的角度看，日志是图的结点，日志之间的顺序是图的边，EPaxos 对结点和边分别达成一致，然后使用拓扑排序，决定日志的顺序。图中也可能形成环路，EPaxos 需要处理循环依赖的问题。EPaxos 引入日志冲突的概念（与 Parallel Raft 类似，与并发冲突不是一个概念），若两条日志之间没有冲突（例如访问不同的 key），则它们的相对顺序无关紧要，因此 EPaxos 只处理有冲突的日志之间的相对顺序。

若并发提议的日志之间没有冲突，EPaxos 只需要运行 PreAccept 阶段即可提交（Fast Path），否则需要运行 Accept 阶段才能提交（Slow Path）。

PreAccept 阶段尝试将日志以及与其它日志之间的相对顺序达成一致，同时维护该日志与其它日志之间的冲突关系，如果运行完 PreAccept 阶段，没有发现该日志与其它并发提议的日志之间有冲突，则该日志以及与其它日志之间的相对顺序已经达成一致，直接发送异步的 Commit 消息提交；否则如果发现该日志与其它并发提议的日志之间有冲突，则日志之间的相对顺序还未达成一致，需要运行 Accept 阶段将冲突依赖关系达成多数派，再发送 Commit 消息提交。

EPaxos 的 Fast Path Quorum 为 2F，可优化至 F + [ (F + 1) / 2 ]，在 3 副本和 5 副本时，与 Paxos、Raft 一致。Slow Path 为 Paxos Accept 阶段，Quorum 固定为 F + 1。EPaxos 还有一个主动 Learn 的算法，在恢复的时候可用来追赶日志，这里就不做具体的介绍了，感兴趣的可以看论文。

算法对比

可理解性

众所周知，Paxos 是出了名的晦涩难懂，不仅难以理解，更难以实现。而 Raft 则以可理解性和易于实现为目标，Raft 的提出大大降低了使用分布式一致性的门槛，将分布式一致性变的大众化、平民化，因此当 Raft 提出之后，迅速得到青睐，极大地推动了分布式一致性的工程应用。

EPaxos 的提出比 Raft 还早，但却长期无人问津，很大一个原因就是 EPaxos 实在是难以理解。EPaxos 基于 Paxos，但却比 Paxos 更难以理解，大大地阻碍了 EPaxos 的工程应用。不过，是金子总会发光的，EPaxos 因着它独特的优势，终于被人们发现，具有广阔的前景。

效率

从 Paxos 到 Raft 再到 EPaxos，效率有没有提升呢？我们主要从负载均衡、消息复杂度、Pipeline 以及并发处理几个方面来对比 Multi-Paxos、Raft 和 EPaxos。

负载均衡

Multi-Paxos 和 Raft 的 Leader 负载更高，各副本之间负载不均衡，Leader 容易成为瓶颈，而 EPaxos 无需 Leader，各副本之间负载完全均衡。

消息复杂度

Multi-Paxos 和 Raft 选举出 Leader 之后，正常只需要一次网络来回就可以提交一条日志，但 Multi-Paxos 需要额外的异步 Commit 消息提交，Raft 只需要推进本地的 commit index，不使用额外的消息，EPaxos 根据日志冲突情况需要一次或两次网络来回。因此消息复杂度，Raft 最低，Paxos 其次，EPaxos 最高。

Pipeline

我们将 Pipeline 分为顺序 Pipeline 和乱序 Pipeline。Multi-Paxos 和 EPaxos 支持乱序 Pipeline，Raft 因为日志连续性假设，只支持顺序 Pipeline。但 Raft 也可以实现乱序 Pipeline，只需要在 Leader 上给每个 Follower 维护一个类似于 TCP 的滑动窗口，对应每个 Follower 上维护一个接收窗口，允许窗口里面的日志不连续，窗口外面是已经连续的日志，日志一旦连续则向前滑动窗口，窗口里面可乱序 Pipeline。

并发处理

Multi-Paxos 沿用 Paxos 的策略，一旦发现并发冲突则回退重试，直到成功；Raft 则使用强 Leader 来避免并发冲突，Follwer 不与 Leader 竞争，避免了并发冲突；EPaxos 则直面并发冲突问题，将冲突依赖也做为一致性问题对待，解决并发冲突。Paxos 是冲突回退，Raft 是冲突避免，EPaxos 是冲突解决。Paxos 和 Raft 的日志都是线性的，而 EPaxos 的日志是图状的，因此 EPaxos 的并行性更好，吞吐量也更高。

可用性

EPaxos 任意副本均可提供服务，某个副本不可用了可立即切换到其它副本，副本失效对可用性的影响微乎其微；而 Multi-Paxos 和 Raft 均依赖 Leader，Leader 不可用了需要重新选举 Leader，在新 Leader 未选举出来之前服务不可用。显然 EPaxos 的可用性比 Multi-Paxos 和 Raft 更好，但 Multi-Paxos 和 Raft 比谁的可用性更好呢。

Raft 是强 Leader，Follower 必须等旧 Leader 的 Lease 到期后才能发起选举，Multi-Paxos 是弱 Leader，Follwer 可以随时竞选 Leader，虽然会对效率造成一定影响，但在 Leader 失效的时候能更快的恢复服务，因此 Multi-Paxos 比 Raft 可用性更好。

适用场景

EPaxos 更适用于跨 AZ 跨地域场景，对可用性要求极高的场景，Leader 容易形成瓶颈的场景。Multi-Paxos 和 Raft 本身非常相似，适用场景也类似，适用于内网场景，一般的高可用场景，Leader 不容易形成瓶颈的场景。