前言

目前主流分布式共识算法有 etcd 使用的 raft ， zookeeper 使用的 zab ，其思想或多或少受到 paxos 启发。 paxos 算法由 Leslie Lamport 在《The part-time parliament》论文中首次提出。
为描述该算法， Lamport 虚构出一个 paxos 小岛，利用类比的手法提出共识算法，本文旨在理解该论文后并结合相关经验对该算法进行重新描述。

文章整体结构与论文相同：
(1) 首先阐述Lamport提出的三条约束，由这三条约束推导出一致性。
(2) 在保证约束条件情况下，导出算法。

术语

• 一致性：一致性是一种状态。
• 活性：共识算法能够保证最终达成一致性。
• 共识：共识是过程（节点通过何种共识算法达成一致）。
• 决议：分布式系统想要达成一致的值、操作等。
• 提议：提出决议的过程。
• 投票：对决议表示赞同。
• 未决决议：已投票的决议，能否达成一致性未知。
• 已决决议：通过共识算法达成一致性的决议。
• 节点：参与共识算法的进程。
• 投票节点集：对当前决议进行投票的节点。
• 法定投票节点集：若法定投票节点集中所有节点对当前提议进行投票，则当前决议成为已决决议。

一个浅显的例子：
存在一个 256 节点的集群，需要对集群管理密码进行统一配置，即所有节点密码与集群密码相同，存放在变量password中。
一致性：任意一台功能正常节点密码相同；
活性：修改密码过程能够完成，中止或者成功；
共识过程：客户端进行密码修改，令set password xxx，发送给集群中主节点，主节点进行提议，提议后当前决议成为未决决议，集群其他节点进行投票，经过共识过程使决议成为已决决议，密码修改生效。

条件

1. 非拜占庭环境，节点不会伪造信息，都尽力完成任务。
2. 消息在信道中可能存在丢失、重复、乱序。
3. 节点可能会发生故障（掉电，磁盘损坏等）。

约束

所有轮次提议构成的集合需要满足下列三条约束：

约束Ⅰ 决议的每一轮提议都有唯一提议号。
约束Ⅱ 任意两次提议的法定投票节点集都存在至少一个公共节点。
约束Ⅲ 任意一次提议的决议与该提议法定投票节点集中所有节点已投票决议中具有最大提议号的决议一致。

注意：提议号可以进行大小比较，但是一般不反应时间先后顺序。

如上是一个满足约束条件的提议集：提议号唯一，任意两次提议法定节点集都有至少一个公共节点。
002 和 005 号提议中法定投票节点之前都没有进行投票，所以决议可以为任意值；
114 号提议中， 03 节点在 002 号提议中进行投票， 01 和 04 节点未进行投票，所以该轮提议的决议需与 002 号提议中的决议一致；
127 号提议中， 02 和 03 节点在之前提议中进行投票，且最大提议号为 005 ，所以该轮提议的决议需与 005 号提议中的决议一致；
229 号提议中， 01 、 02 和 03 节点均在之前提议中进行投票，且最大提议号为 114 ，所以该轮提议的决议需与 114 号提议中的决议一致。
127 号提议中，法定投票节点集中所有节点进行了投票，这本次决议达成一致，成为已决决议，最终值达成一致为abc（01和04节点可能并不知晓该次决议，但是不影响最终对外一致性）。

一致性

当提议形成的提议集，满足上述约束，能够保证一致性。

若某轮提议达成一致，成为已决决议，则任意提议号大于该提议的决议都与其相同

证明（反证法）：

1. 假设在已决决议提议之后存在提议的决议与已决决议不同，取这些提议中提议号最小的提议，记为提议甲。
2. 提议甲中的法定节点集一定与已决决议投票节点集有交集（约束Ⅱ保证法定节点集之间有交集，已决决议保证法定节点集是投票节点集的子集）。
3. 提议甲的法定节点集中一定存在节点，在大于等于已决决议提议号，小于提议甲提议号之间进行了投票（由2推出至少存在一个节点，即在已决决议提议中进行投票的节点）。取这些投票所对应的提议号距提议甲最近的一次决议，记为决议乙。
4. 由约束Ⅲ的存在，决议甲的法定节点集在决议乙中进行了投票，则决议甲等于决议乙，两者与已决决议不等。
5. 违法决议甲是不同于已决决议中拥有最小提议号的假设。

算法导出

保证约束Ⅰ，即提议号是唯一是简单的，可以采用多种策略：随机数，特殊编码格式（节点号 + 递增值）等。

保证约束Ⅱ，同样简单，只需要每次提议的法定投票节点集满足大多数（一半以上节点），就能保证每次提议中必定含有至少一个公共节点。

保证约束Ⅲ，在生成决议前，需要收集法定投票节点集（大多数节点）已投票决议中具有最大提议号的决议作为本轮提议的决议。如果决议为空，则本轮决议可以为任意值。

原初算法

1. 提议节点初始化新提议号，发送给其他节点（包括提议节点）。
2. 节点接收到新提议号，在已投票的提议中，选取小于新提议号且提议号最大的一次提议，记该提议为提议甲，将提议甲发送回提议节点。节点在发送该消息之后，为确保对于该新提议号，每次发回的提议都为提议甲，节点必须承诺在提议甲和新提议之间不在对其他提议进行投票。
3. 提议节点在接收到法定投票节点集中所有节点（大多数节点）发回的提议中，选择其中提议号最大的决议作为新提议中的决议。如果收集到的决议为空，则可生成任意的决议。然后提议节点将新提议发送给步骤 2 中响应的节点。
4. 节点在接收到新提议时，决定是否为该提议进行投票。如果该节点对该提议进行投票，则该节点记录下投票信息后，发送投票消息给提议节点。节点可能为保证步骤 2 中的承诺，不对新提议进行投票。
5. 提议节点接收到法定投票节点集中所有节点（大多数节点，与步骤 3 中节点相同）发回的投票消息时，决议成为已决决议，发送成功消息通知步骤 2 中响应的节点。
6. 节点接收到决议成为已决决议的成功消息时，持久化该决议。

上述算法任意节点都可以同时执行，算法仅能保证一致性，不能保证共识流程能够完成（例如不停有新节点进行提议）。

有上述算法可知，每个节点必须维护的信息包括：步骤 1 中所有发起的提议号；步骤 4 中所有投票信息；步骤 2 中每次响应提议节点的信息（“承诺信息”）。

基础算法

原初算法要求节点记录的信息太多，可精简为：步骤 1 中节点最后发起的提议号；步骤 4 中节点最后投票的提议；步骤 2 中承诺的最大提议号。在此基础上进一步增强承诺，构成基础算法。

1. 提议节点初始化新提议号，该提议号大于最后发起的提议号，并更新最后发起提议号的值，发送给其他节点（包括提议节点）。
2. 节点接收到新提议号，且该提议号大于承诺提议号，发送最后投票的提议回提议节点，并更新最新承诺提议号为该协议号。
3. 提议节点在接收到法定投票节点集中所有节点（大多数节点）发回的提议中，选择其中提议号最大的决议作为新提议中的决议。然后提议节点将新提议发送给步骤 2 中响应的节点。
4. 节点接收到新提议时，若提议号和承诺提议号相同，发送投票消息给提议节点，并更新最后投票的提议为当前提议。
5. 提议节点接收到法定投票节点集中所有节点（大多数节点，与步骤 3 中节点相同）发回的投票消息时，决议成为已决决议，发送成功消息通知步骤 2 中响应的节点。
6. 节点接收到决议成为已决决议的成功消息时，持久化该决议。

完整算法

基础协议对原初协议做出了更加严格的承诺，但是仍然不能满足可进展性（每个节点仍然会不停的进行提议），不发起提议或者发起提议过快都会阻止进展性（即无法使决议成为已决决议）。最好的方式是选择一个主节点来进行提议。完整算法如图：（存在故障节点 3 ，时延较大节点 2 ，忽略提议节点到自己的时延）

参考

• Leslie, Lamport. "The part-time parliament." ACM Trans. on Computer Systems 16 (1998): 133-169.
• Lamport, Leslie. "Paxos made simple." ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (2001): 51-58.