1. 概述
大家在讨论分布式系统的时候，一个经常要碰到的问题就是分布式系统里的一致性问题，也就是CAP理论中的C (Consistency)。让网络中各个节点达成一致性的一种方法，就是上一遍博客中提到的状态机复制 (State Machine Replication)，状态机复制的基础协议就是所谓的共识协议，而Paxos算法，就是为了让多个节点达成共识而发明出来的算法。
虽然我们经常说Paxos算法，但是严格说来，Paxos是一整个协议族，里面包含：基础Paxos，Multi-Paxos，Fast Paxos和Egalitarian Paxos。而我们今天要讨论的，就是其中的基本Paxos（Basic Paxos）算法。
2. 基础Paxos算法特性
基础Paxos算法具有以下特性：
- 最后达成共识的值只能从被提议的候选值中产生；
- 仲裁节点（Quorum）一旦就某个值达成共识，后面就不能就另外的值达成共识；
- 仲裁节点（quorum）一旦就某个值达成共识，那么最终所有的节点都将学习到这个值；
- 算法保证了安全性，但是理论上并不能保证活性；
- 算法能在不可靠的消息传输协议下（消息可以被丢失，重传，乱序）正常工作，但是消息要保证正确和完整；
- 如果有2N+1个节点参与算法，那么算法可以在N个节点失效的情况下依旧保证正常工作；
3. 基础Paxos算法流程
3.1 算法目的
基础Paxos算法要解决的问题是：如果有2N+1个节点都有一个寄存器文件，并且针对这个寄存器文件提交了m个候选值，那么这2N+1个节点需要最终决定这个寄存器文件需要写入哪一个候选值，并且一旦至少N+1个节点对这个决定达成了共识，那么此决定将不可再更改。
3.2 前提假设
- 系统不存在拜占庭将军问题，即所有的节点不存在欺骗，消息在传输过程中要保证内容的正确和完整；
- 任意一个节点都可以发送消息到另外一个节点；
- 任何一个节点都可能失效；
- 网络协议本身并不可靠。
3.3 角色
基础Paxos算法定义了如下角色：
- 客户端（Client）：向分布式集群系统发起请求（对值作出提议），并且等待集群系统的响应结果；
- 提议者（Proposer）：也可以叫做协调者（coordinator），提议者负责接受客户端发起的提议，然后尝试让接受者接受该提议，同时保证即使多个提议者的提议之间产生了冲突，那么算法都能进行下去；
- 接受者（Acceptor）：也可以叫做投票员（voter），负责对提议者的提议投票，同时需要记住自己的投票历史；
- 学习者（Learner）：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。
这里给出的角色定义是算法层面的逻辑定义。在实际应用中，往往一个系统具有一个或者多个角色的功能。下图给出了各个角色的逻辑关系图：
注1：图中给出的示例有两个客户同时提交了请求，但是基础Paxos算法保证只有其中一个客户端的请求会被共识系统接受，而另一个客户端的请求将会被拒绝。
3.4 算法流程
基础Paxos算法的核心思想是：多轮选举；超半数节点响应；响应结果传递。
在基础Paxos算法中，任何一个Proposer都能发起新一轮的选举，即使上一轮的选举还没有完成。而且一旦Acceptor收到了新一轮选举的消息，那么它就要拒绝所有之前选举的消息。为了实现这个目的，Proposer在开始新一轮选举的时候都要给这轮选举付一个全局唯一的ID（Pro poseNum），而且此ID必须比之前所有进行过的选举的ID都要大。那么问题来了，要让所有的节点都能生成一个全局唯一ID，这本身就是一个共识问题，就变成了用一个共识问题去解决另一个共识问题。怎么办？一个比较简单的方法就是使用分布式ID生成算法：我们让Proposer所在的节点都有一个唯一的Server ID，然后每一个节点都维持一个本地的最大选举轮数计数器maxLocalRound，当我们需要ProposeNum的时候，我们可以通过如下算法生成它：
1 | localRoundNum = ++maxLocalRound |
我们可以重复执行以上算法直到ProposeNum大于当前正在进行的选举的ProposeNum。
每一轮的选举都分为两个阶段：
- 阶段一(Phase 1)：准备/承诺 (Prepare/Promise)
目的：
1. 停止所有之前还没有完成的选举；
2. 尝试发现是否已经有提议被接受。
流程：
Prepare（Phase 1a）: proposer生成一个比它之间见到过的ProposeNum都要大的新ProposeNum，然后把这个新的ProposeNum通过prepare消息发送给所有的acceptor。
Promise（Phase 1b）: acceptor内部维护着一个变量minProposeNum，当acceptor收到了一个prepare消息，并且消息包含的ProposeNum > minProposeNum, 则让minProposeNum = ProposeNum，并向proposer返回包含minProposeNum和<acceptedProposeNum, acceptedValue>的确认消息（如果acceptor在之前没有接受过任何proposal，则acdeptedProposeNum/acceptedValue可以设置为null）。然后，acceptor对于后面收到的任何消息，只要消息里的ProposeNum <= minProposeNum, 则将返回reject或者忽略。
- 阶段二(Phase 2)：接受请求/请求被接受（Accepting/Accpeted)
目的：
1. 让acceptor接受某个提议。
流程：
Accepting（Phase 2a）: 当proposer在Phase 1b里收到了超过半数acceptor返回的确认消息，它将扫描所有返回的<acceptedProposeNum, acceptedValue>, 如果所有的acceptedValue都为null，则proposer可以自行决定接下来将要发送的value，否则，它必须将最大的acceptedProposeNum对应的acceptedValue作为接下来将要发送的value的值。然后proposer将向所有的acceptors发送附带有<ProposeNum, value>的accepting消息；
Accepted（Phase 2b）: 当acceptor收到了带有<ProposeNum, value>的accepting消息后，如果ProposeNum < minProposeNum, 则返回reject消息或者忽略，否则，设置minProposeNum = acceptedProposeNum = ProposeNum, accptedValue = value. 然后向proposer和learner发送附带有minProposeNum的accepted消息。
当learner收到了超过半数acceptor针对于某个ProposeNum的accepted消息后，认为共识已经达成，它可以开始执行提议并向client返回最终结果。
4. 使用场景
Paxos算法可以使用到一下场景里面：
- Leader选举，proposer把server id作为提议运行paxos算法，最后就哪个server id达成了共识，对应的server就能成为leader；
- 分布式锁，请求分布式锁的client把自己的client id作为提议发送给proposer运行paxos算法，最后就哪个server id达成了共识，对应的client就能获得分布式锁。
- 就状态机复制中节点replication log中的log entry达成一致。
5. 活锁
基础Paxos算法存在活锁的场景，如下图所示：
6. 注意事项
- 基础Paxos是一个Leaderless算法，也就是说，它的运行不依赖于系统选举出一个leader （基础Paxos本身就可以拿来做leader选举）；
- 虽然对于整个系统来说，一旦系统就某个提议达成共识，那么这个提议就是最终结果并且不能再改变，但是对于每一个acceptor来说，它们能在不同的选举轮中接受不同的值；
- Acceptor只负责投票和记录投票历史，它并不实际执行达成共识的提议，实际的执行操作是由learner来完成，其实我本人不是很赞成使用接受者(Acceptor)这个名词，因为给人的第一感觉就好像一旦接受了就可以开始执行提议了，但实际上它仅仅起到一个投票的作用，所以我觉得叫voter更好一些。
