Paxos 算法在分布式领域具有非常重要的地位，它是能够基于一大堆完全不可靠的网络条件下却能可靠确定地实现共识一致性的算法。也就是说：它允许一组不一定可靠的处理器（服务器）在某些条件得到满足情况下就能达成确定的安全的共识，如果条件不能满足也确保这组处理器（服务器）保持一致。

1. Quorum选举算法

在了解Paxos 算法之前，我们先来看分布式系统中的 Quorum 选举算法。在各种一致性算法中都可以看到Quorum 机制的身影，主要数学思想来源于抽屉原理

抽屉原理，用一句话解释那就是，在 N 个副本中，一次更新成功的如果有 W 个，那么我在读取数据时是要从大于 N－W 个副本中读取，这样就能至少读到一个更新的数据了。

和Quorum机制对应的是WARO，也就是WriteAllReadone，是一种简单的副本控制协议，当Client请求向某副本写数据时（更新数据），只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。

WARO优先保证读服务，因为所有的副本更新成功，才能视为更新成功，从而保证了所有的副本一致，这样的话，只需要读任何一个副本上的数据即可。写服务的可用性较低，因为只要有一个副本更新失败，此次写操作就视为失败了。假设有 N 个副本，N－1 个都宕机了，剩下的那个副本仍能提供读服务；但是只要有一个副本宕机了，写服务就不会成功。

WARO 牺牲了更新服务的可用性，最大程度地增强了读服务的可用性，而 Quorum 就是在更新服务和读服务之间进行的一个折衷。

1.1. Quorum 定义

Quorum的定义如下：假设有N个副本，更新操作wi在W个副本中更新成功之后，才认为此次更新操作wi成功，把这次成功提交的更新操作对应的数据叫做：“成功提交的数据”。对于读操作而言，至少需要读 R 个副本才能读到此次更新的数据，其中，W+R>N ，即 W 和 R 有重叠，一般，W+R=N+1。

• N = 存储数据副本的数量
• W = 更新成功所需的副本
• R = 一次数据对象读取要访问的副本的数量

Quorum就是限定了一次需要读取至少N+1-w的副本数据,听起来有些抽象，举个例子，我们维护了10个副本，一次成功更新了三个，那么至少需要读取八个副本的数据，可以保证我们读到了最新的数据。

这三个因素决定了可用性，一致性和分区容错性。W+R>N可以保证数据的一致性(C)，W越大数据一致性越高。这个NWR模型把CAP的选择权交给了用户，让用户自己在功能，性能和成本效益之间进行权衡。

对于一个分布式系统来说，N通常都大于3，也就说同一份数据需要保存在三个以上不同的节点上，以防止单点故障。W是成功写操作的最小节点数，这里的写成功可以理解为“同步”写，比如N=3，W=1，那么只要写成功一个节点就可以了，另外的两份数据是通过异步的方式复制的。R是成功读操作的最小节点数，读操作为什么要读多份数据呢？在分布式系统中，数据在不同的节点上可能存在着不一致的情况，我们可以选择读取多个节点上的不同版本，来达到增强一致性的目的。

NWR模型的一些设置会造成脏数据和版本冲突问题，所以一般要引入vector clock算法来解决这个问题。

1.2. Quorum 的应用

Quorum 机制无法保证强一致性，也就是无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。

Quorum 机制的使用需要配合一个获取最新成功提交的版本号的 metadata 服务，这样可以确定最新已经成功提交的版本号，然后从已经读到的数据中就可以确认最新写入的数据。

Quorum 是分布式系统中常用的一种机制，用来保证数据冗余和最终一致性的投票算法，在 Paxos、Raft 和 ZooKeeper 的 Zab 等算法中，都可以看到 Quorum 机制的应用。

2. Paxos 算法

2.1. Paxos 的节点角色

在Paxos算法中，主要有3种角色：

• Proposer：提议者
• Acceptor：决策者
• Learner：最终决策学习者

另外还有一个 Client，作为产生议题者。

上述三类角色只是逻辑上的划分，在工作实践中，一个节点可以同时充当这三类角色。

Proposer 提案者

Proposer可以有多个，在流程开始时，Proposer提出议案，也就是value，所谓value，在工程中可以是任何操作，比如“修改某个变量的值为某个新值”，Paxos 协议中统一将这些操作抽象为 value。

不同的Proposer可以提出不同的甚至矛盾的value，比如某个Proposer提议“将变量X设置为1”，另一个Proposer提议“将变量X设置为2”，但对同一轮 Paxos 过程，最多只有一个 value 被批准。

Acceptor 批准者

在集群中，Acceptor 有 N 个，Acceptor 之间完全对等独立，Proposer 提出的 value 必须获得超过半数（N/2+1）的 Acceptor 批准后才能通过。

Learner 学习者

Learner 不参与选举，而是学习被批准的 value，在Paxos中，Learner主要参与相关的状态机同步流程。

这里Leaner的流程就参考了Quorum议会机制，某个value需要获得W=N/2+1的Acceptor批准，Learner需要至少读取N/2+1个Accpetor，最多读取 N 个 Acceptor 的结果后，才能学习到一个通过的 value。

Client 产生议题者

Client 角色，作为产生议题者，实际不参与选举过程，比如发起修改请求的来源等。

2.2. Proposer 与 Acceptor 之间的交互

Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：

1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

Paxos中，Proposer和Acceptor是算法核心角色，Paxos描述的就是在一个由多个Proposer和多个Acceptor构成的系统中，如何让多个 Acceptor 针对 Proposer 提出的多种提案达成一致的过程，而 Learner 只是“学习”最终被批准的提案。

Proposer 与 Acceptor 之间的交互主要有 4 类消息通信，如下图：

这 4 类消息对应于 Paxos 算法的两个阶段 4 个过程，下面在分析选举过程时会讲到。

• Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID)，向所有 Acceptors 发送 Prepare 请求，这里无需携带提案内容，只携带 Proposal ID 即可。
• Promise: Acceptors 收到 Prepare 请求后，做出“两个承诺，一个应答”。
  • 两个承诺：
    • 不再接受 Proposal ID 小于等于当前请求的 Prepare 请求。
    • 不再接受 Proposal ID 小于当前请求的 Propose 请求。
  • 一个应答：
    • 不违背以前作出的承诺下，回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID，没有则返回空值。
• Propose: Proposer 收到多数 Acceptors 的 Promise 应答后，从应答中选择 Proposal ID 最大的提案的 Value，作为本次要发起的提案。如果所有应答的提案 Value 均为空值，则可以自己随意决定提案 Value。然后携带当前 Proposal ID，向所有 Acceptors 发送 Propose 请求。
• Accept: Acceptor 收到 Propose 请求后，在不违背自己之前作出的承诺下，接受并持久化当前 Proposal ID 和提案 Value。
• Learn: Proposer 收到多数 Acceptors 的 Accept 后，决议形成，将形成的决议发送给所有 Learners。

2.3. Paxos 选举过程

选举过程可以分为两个部分，准备阶段和选举阶段，可以查看下面的时序图：

2.3.1. 准备阶段

Proposer 生成全局唯一且递增的 ProposalID，向 Paxos 集群的所有机器发送 Prepare 请求，这里不携带 value，只携带 N 即 ProposalID。

Acceptor收到Prepare请求后，判断收到的ProposalID是否比之前已响应的所有提案的N大，如果是，则：

• 在本地持久化N，可记为Max_N；
• 回复请求，并带上已经Accept的提案中N最大的value，如果此时还没有已经Accept的提案，则返回value为空；
• 做出承诺，不会 Accept 任何小于 Max_N 的提案。

如果否，则不回复或者回复 Error。

2.3.2. 选举阶段

为了方便描述，我们把 Phase 2 选举阶段继续拆分为3个阶段。

a：Proposer发送Accept

经过一段时间后，Proposer收集到一些Prepare回复，有下列几种情况：

• 若回复数量 > 一半的 Acceptor 数量，且所有回复的 value 都为空时，则 Porposer 发出 accept 请求，并带上自己指定的 value。

• 若回复数量>一半的Acceptor数量，且有的回复value不为空时，则Porposer发出accept请求，并带上回复中ProposalID最大的value，作为自己的提案内容。

• 若回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，再转到准备阶段执行。

b：Acceptor 应答 Accept

Accpetor 收到 Accpet 请求 后，判断：

• 若收到的 N >= Max_N（一般情况下是等于），则回复提交成功，并持久化 N 和 value；
• 若收到的 N < Max_N，则不回复或者回复提交失败。

c: Proposer 统计投票

经过一段时间后，Proposer 会收集到一些 Accept 回复提交成功的情况，比如：

• 当回复数量 > 一半的 Acceptor 数量时，则表示提交 value 成功，此时可以发一个广播给所有的 Proposer、Learner，通知它们已 commit 的 value；
• 当回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，转到准备阶段执行。
• 当收到一条提交失败的回复时，则尝试更新生成更大的 ProposalID，也会转到准备阶段执行。

网上找的伪代码

3. 三种情况

Basic Paxos共识过程一共有三种可能的情况。下面分别进行介绍。

3.1. 情况1：提案已接受

如下图所示。X、Y代表客户端，S1到S5是服务端，既代表Proposer又代表Acceptor。为了防止重复，Proposer提出的编号由两部分组成：

序列号.Server ID

例如S1提出的提案编号，就是1.1、2.1、3.1……

这个过程表示，S1收到客户端的提案X，于是S1作为Proposer，给S1-S3发送Prepare(3.1)请求，由于Acceptor S1-S3没有接受过任何提案，所以接受该提案。然后Proposer S1-S3发送Accept(3.1, X)请求，提案X成功被接受。

在提案X被接受后，S5收到客户端的提案Y，S5给S3-S5发送Prepare(4.5)请求。对S3来说，4.5比3.1大，且已经接受了X，它会回复这个提案 (3.1, X)。S5收到S3-S5的回复后，使用X替换自己的Y，于是发送Accept(4.5, X)请求。S3-S5接受提案。最终所有Acceptor达成一致，都拥有相同的值X。

这种情况的结果是：新Proposer会使用已接受的提案

3.2. 情况2：提案未接受，新Proposer可见

S3接受了提案(3.1, X)，但S1-S2还没有收到请求。此时S3-S5收到Prepare(4.5)，S3会回复已经接受的提案(3.1, X)，S5将提案值Y替换成X，发送Accept(4.5, X)给S3-S5，对S3来说，编号4.5大于3.1，所以会接受这个提案。

然后S1-S2接受Accept(3.1, X)，最终所有Acceptor达成一致。

这种情况的结果是：新Proposer会使用已提交的值，两个提案都能成功

3.3. 情况3：提案未接受，新Proposer不可见

S1接受了提案(3.1, X)，S3先收到Prepare(4.5)，后收到Accept(3.1, X)，由于3.1小于4.5，会直接拒绝这个提案。所以提案X无法收到超过半数的回复，这个提案就被阻止了。提案Y可以顺利通过。

这种情况的结果是：新Proposer使用自己的提案，旧提案被阻止

3.4. 活锁 (livelock)

活锁发生的几率很小，但是会严重影响性能。就是两个或者多个Proposer在Prepare阶段发生互相抢占的情形。

解决方案是Proposer失败之后给一个随机的等待时间，这样就减少同时请求的可能。

4. Multi-Paxos算法

原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。

实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Basic Paxos做了两点改进：

1. 针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。
2. 在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Multi-Paxos首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos实例来选举出一个Leader。选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过。

Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。

Multi-Paxos需要解决几个问题，我们逐个来看。

4.1. Leader选举

一个最简单的选举方法，就是Server ID最大的当Leader。

每个Server间隔T时间向其他Server发送心跳包，如果一个Server在2T时间内没有收到来自更高ID的心跳，那么它就成为Leader。其他Proposer，必须拒绝客户端的请求，或将请求转发给Leader。

当然，还可以使用其他更复杂的选举方法，这里不再详述。

4.2. 省略Prepare阶段

Prepare的作用是阻止旧的提案，以及检查是否有已接受的提案值。

当只有一个Leader发送提案的时候，Prepare是不会产生冲突的，可以省略Prepare阶段，这样就可以减少一半RPC请求。

Prepare请求的逻辑修改为：

• Acceptor记录一个全局的最大提案编号
• 回复最大提案编号，如果当前entry以及之后的所有entry都没有接受任何提案，回复noMoreAccepted

当Leader收到超过半数的noMoreAccepted回复，之后就不需要Prepare阶段了，只需要发送Accept请求。直到Accept被拒绝，就重新需要Prepare阶段。

4.3. 完整信息流

目前为止信息是不完整的。

• Basic Paxos只需超过半数的节点达成一致。但是在Multi-Paxos中，这种方式可能会使一些节点无法得到完整的entry信息。我们希望每个节点都拥有全部的信息。
• 只有Proposer知道一个提案是否被接受了（根据收到的回复），而Acceptor无法得知此信息。

第1个问题的解决方案很简单，就是Proposer给全部节点发送Accept请求。

第2个问题稍微复杂一些。首先，我们可以增加一个Success RPC，让Proposer显式地告诉Acceptor，哪个提案已经被接受了，这个是完全可行的，只不过还可以优化一下，减少请求次数。

我们在Accept请求中，增加一个firstUnchosenIndex参数，表示Proposer的第一个未接受的Index，这个参数隐含的意思是，对该Proposer来说，小于Index的提案都已经被接受了。因此Acceptor可以利用这个信息，把小于Index的提案标记为已接受。另外要注意的是，只能标记该Proposer的提案，因为如果发生Leader切换，不同的Proposer拥有的信息可能不同，不区分Proposer直接标记的话可能会不一致。

Proposer正在准备提交Index=2的Accept请求，0和1是已接受的提案，因此firstUnchosenIndex=2。当Acceptor收到请求后，比较Index，就可以将Dumplings提案标记为已接受。

由于之前提到的Leader切换的情况，仍然需要显式请求才能获得完整信息。在Acceptor回复Accept消息时，带上自己的firstUnchosenIndex。如果比Proposer的小，那么就需要发送Success(index, value)，Acceptor将收到的index标记为已接受，再回复新的firstUnchosenIndex，如此往复直到两者的index相等。

5. Paxos 常见的问题

关于Paxos协议，有几个常见的问题，简单介绍下。

1.如果半数以内的 Acceptor 失效，如何正常运行？

在Paxos流程中，如果出现半数以内的Acceptor失效，可以分为两种情况：

• 第一种，如果半数以内的Acceptor失效时还没确定最终的value，此时所有的Proposer会重新竞争提案，最终有一个提案会成功提交。

• 第二种，如果半数以内的 Acceptor 失效时已确定最终的 value，此时所有的 Proposer 提交前必须以最终的 value 提交，也就是Value实际已经生效，此值可以被获取，并不再修改。

Acceptor需要接受更大的N，也就是ProposalID有什么意义？

这种机制可以防止其中一个Proposer崩溃宕机产生阻塞问题，允许其他Proposer用更大ProposalID来抢占临时的访问权。

3. 如何产生唯一的编号，也就是 ProposalID？

在《Paxosmadesimple》论文中提到，唯一编号是让所有的Proposer都从不相交的数据集合中进行选择，需要保证在不同Proposer之间不重复，比如系统有5个Proposer，则可为每一个Proposer分配一个标识j(0~4)，那么每一个Proposer每次提出决议的编号可以为5*i+j，i可以用来表示提出议案的次数

6. 一个通俗的解释

摘自 https://mp.weixin.qq.com/s/g_F2YiptjUynoUzKFj8qNg

假设一群驴友决定端午去旅游，驴友遍布全国各地，一共10人，为了能达成一致，这10个人另外找5个作为队长。5个队长之间相互不通信，只跟10个驴友发短信。

第一阶段（申请阶段），驴友发短信给5个队长，申请与队长进行沟通。队长在任何时刻只能与一个驴友沟通。发送的每条短信都带有时间，队长采用的原则是同意与短信发送时间最新的驴友沟通，如果出现更新的短信，则与短信更新的驴友沟通。至少大多数队长同意沟通了，这个驴友才能进入第二阶段实质性沟通。

第二阶段（沟通阶段），获得沟通权的驴友A收到队长们给他发的旅游地，可能有几种情况。

第一种情况：沟通的队长们全部都还没有决定到底去哪里旅游，此刻驴友A会把自己想去的旅游地发给队长们（比如马尔代夫），结果可能大多数队长同意了，整个过程执行完毕，就是去马尔代夫旅游了，其他的驴友迟早会知道。除此之外就表明失败了，可能队长没有回复(跟女友打电话去了)，可能被其他驴友抢占沟通权了（上面说过队长只跟最新的短信的人进行沟通）。如果失败了，A需要重新开始第一阶段申请，重新给队长们发短信申请沟通权。

第二种情况：至少有一个队长已经决定旅游地了，这个时候A会收到不同队长决定的多个旅游地，这些旅游地是不同队长跟不同驴友在不同时间做的决定。A会先看看有的旅游地是不是被大多数（半数以上）队长同意了，如果有(这里假设3个队长决定去三亚，一个去拉萨，另外可能某种原因没搭理），那证明整个决定过程已经达成一致了，A收拾收拾去三亚吧，结束！

如果都没有达到半数（比如2个去三亚，1个去拉萨，1个去昆明，1个没搭理），这时候A可能想去马尔代夫，但也不按照自己意愿乱来了（这里是Paxos的关键所在，后者认可前者，否则整个过程无止境了），A会根据收到队长的所有旅游地中找到最新的那个决定地（比如去昆明是那个队长是1分钟前决定的，去拉萨的队长是半小时前决定的，去三亚的队长是1小时前决定的），于是A顶最新的决定，去昆明。这时候去昆明的决定又更新了，这样下一个抢到沟通权的驴友也很大可能会顶去昆明，这样决定去昆明的队长会越来越多。

一旦某个时刻大多数（半数以上）队长都同意了去某个地点，比如去昆明，后续获得沟通权的驴友B会发现大多数队长都决定去昆明了，它也会服从，最终所有的驴友都达成一致去昆明。

Paxos的基本思想大致就是上面过程，Paxos利用的是选举，少数服从多数的思想，只要N个(N为奇数，至少大于等于3)节点中，有[N/2]+1(这里N/2为向下取整)或以上个节点同意了某个决定，则认为系统达到了一致，这样的话，客户端不必与所有服务器通信，选择与大部分通信即可；也无需服务器都全部处于工作状态，有一些服务器挂掉，只有保证半数以上存活着，整个过程也能持续下去，容错性相当好。

7. 参考资料

https://zhuanlan.zhihu.com/p/31780743

https://segmentfault.com/a/1190000018844326

https://zhuanlan.zhihu.com/p/25664121

https://mp.weixin.qq.com/s/g_F2YiptjUynoUzKFj8qNg

《分布式技术原理与实战45讲》