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不容易形成瓶颈的场景。