理解 Paxos 分布式共识算法
什么？Paxos 号称是最难理解的算法？虽然有些夸张，那也得看一下！
直接入正题，在分布式系统中存在多个主机节点，这些主机之间的通信机制一般分为 共享内存 和 消息传递 两种。这两种方式各有优劣，而 paxos 算法主要用来解决基于消息机制的分布式一致性问题。
在分布式系统中，网络一般被认为是不可靠的，所以传递的消息可能会存在延迟、丢失、重复等问题，发送消息的进程也可能出现运行缓慢、重启，甚至被杀死等情况。Paxos 算法解决的问题是在一个可能发生这些异常（不包括消息可能被篡改的情况）的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决策一致性的问题。
算法陈述
在 paxos 算法中定义了三种角色，包括 提案者（Proposer） 、决策者（Acceptor） ，以及 学习者（Learner） 。其中 proposer 和 acceptor 是整个算法的核心角色，paxos 描述的就是在一个由多个 proposer 和多个 acceptor 构成的系统中，如何让多个 acceptor 针对 proposer 提出的多种提案达成一致的过程，而 learner 只是“学习”最终被批准的提案。
需要注意的是这里的角色不是相互独立的，也就是说一个进程可以充当多种角色，并且为了防止单点故障，在一个分布式系统中往往存在多个 acceptor，其个数一般都是大于 2 的奇数，以实现协议所依赖的少数服从多数原则。
我们先来对整个算法进行描述，暂时先不考虑算法如何保证一致性。假设现在有若干 proposer 和 acceptor，每个 proposer 都可以提出一个或多个提案，而每个 acceptor 也可以批准一个或多个提案，我们最终的目标就是希望在这些被提出的提案中选择唯一一个进行批准，而所有的 proposer 都需要认可这个被批准的提案。我们令提案的格式为 [m, v]，其中 m 表示提案的编号（ 全局唯一 ），而 v 表示提案的内容（提案值），整个算法分为两个阶段：
- 第一阶段
- Proposer 选择一个编号为 m 的提案，然后向 acceptor 的某个超过半数的子集发送编号为 m 的 prepare 请求。
- 当 acceptor 收到一个编号为 m 的 prepare 请求，且编号 m 大于该 acceptor 已经响应的最大编号的 prepare 请求，则将其批准过的最大编号的提案作为响应发送给 proposer，同时承诺不再批准任何编号小于 m 的提案。
- 第二阶段
- 如果 proposer 收到来自半数以上 acceptor 的 prepare 响应，则会发送一个内容为
[m, v]的 accept 请求，这里的 v 是之前 prepare 请求收到的最大编号提案对应的提案值，如果 prepare 响应不包含任何提案，则可以是任意值。 - 当 acceptor 收到 accept 请求，只要该 acceptor 尚未对编号大于 m 的提案做出过响应，就可以批准该提案。
由上面的执行过程我们可以看到，其实 paxos 算法并不是很复杂，甚至可以说其执行过程还是很简单的，而真正让大家感觉其难以理解的关键在于如何证明这么简单的两个阶段执行过程能够保证在分布式系统下达成一致。
算法推导
在这一节中，将借鉴作者的思路，逐步来推导出整个算法。首先我们需要明白整个算法是建立在 “少数服从多数” 的选举原则之上的，这里的少数和多数指的是批准提案的 acceptor 的数目，然后我们需要清楚目前所面临的限制性条件，实际上主要有两点：
- 提案只有被 proposer 提出后，才可以被 acceptor 批准。
- 在一次算法的执行过程中，仅有一个提案被批准。
注意：这里说的只有一个提案被批准，更准确的说是只有一个提案值被批准，因为我们会对每个提案都附加一个全局唯一的提案编号，不同的编号可以对应同一个提案值，在算法的执行过程中，可以批准多个不同编号的提案，但这些提案必须持有相同的提案值。
为了保证当只有一个提案被提出时也能被正确选举，算法首先做了如下约束：
P1: 一个 acceptor 必须批准它收到的第一个提案
但是仅有上述条件是不够的，可以设想极端条件下每个 proposer 都将其提出的提案提交给了不同的 acceptor，这个时候按照 P1 原则，每个 acceptor 都需要接受它所收到的第一个提案，这样就无法满足 “少数服从多数” 原则，也就意味着一个 acceptor 可以批准多个提案，于是引出第二个约束（依然按照第一节中我们对于提案的格式定义）：
P2: 如果提案
[m, v]被选定了，那么所有比编号 m 更高，且被选定的提案，其提案值必须是 v
如果在一个分布式系统中能够同时满足 P1 和 P2，那么一致性就能够保证。其中 P1 可以保证算法能够正常的向前推进，而 P2 能够保证最终仅有一个提案值被批准，这并不难理解，实际上 P2 可以简单理解为对于一致性的描述。
那么如何才能做到这两点呢？我们可以对 P2 做如下增强：
P2a: 如果提案
[m, v]被选定了，那么所有比编号 m 更高，且被任何 acceptor 批准的提案，其提案值必须是 v
但是 P2a 和 P1 是矛盾的，因为各个 acceptor 之间可以看作是独立的，彼此之间通过消息机制进行通信，所以无法做到各个 acceptor 关于其它已批准提案值的实时同步，如果其中某个未批准过任何提案的 acceptor 还不知道当前已经被批准的提案值，而此时正好有一个 proposer 发送了一个更大编号的新提案，按照 P1 的规则是要接受这个新提案的，但此时就违背了 P2a。
既然 acceptor 无法保证一致性，那么我们就换个角度从 proposer 出发：
P2b: 如果提案
[m, v]被选定了，那么之后任何 proposer 产生的编号更高的提案，其提案值都为 v
由于 acceptor 收到的提案来源于 proposer，所以 p2b 也算是从源头上对 p2a 进行保证，是更强的约束。那么如何实现呢？如果要实现到这一层面，似乎 proposer 之间需要具备某种协商通信的机制，但是既然 proposer 都能从源头上保证提出提案的一致性了，还需要 paxos 干啥？似乎饶了一大圈又回到了原点。
我们需要换个角度思考 P2b，假设提案 [m, v] 已经被批准了，那么什么情况下，对于编号 n (n > m) 来说都有提案值 v 呢？
P2c：如果一个编号为 n 的提案具有提案值 v，那么存在一个过半数集合满足如下两个条件之一：
- 集合中所有 acceptor 都没有接受编号小于 n 的任何提案
- 集合中 acceptor 已经接受的所有编号小于 n 的提案中编号最大的那个提案的值为 v
现在我们的问题变成了如何证明 P2c 蕴含 P2b，我们暂时把证明过程搁置一下，先看看如何满足 P2c。
要满足 P2c 的约束，即当一个 [m, v] 的提案被批准之后，proposer 新提出的提案 [n, w] (n > m) 要满足 w = v，那么 proposer 必定在提出新的提案之前需要与 acceptor 进行通信，以约束新的新提出的提案值。所以就有了第 1 节中两个阶段的算法执行过程。
我们最后再来整理一下 proposer 生成提案，以及 acceptor 批准提案的过程。
Proposer 生成提案
Proposer 在产生一个编号为 m 的提案时，必须要知道当前某一个将要或已经被半数以上 acceptor 批准的编号小于 m 的最大编号提案，并要求所有的 acceptor 不再批准任何编号小于 m 的提案。
- prepare 请求
Proposer 选择一个新的提案编号 m，并向某个半数以上 acceptor 集合发送提案请求，要求集合中的 acceptor 做如下回应：
- 向 proposer 承诺不再批准任何编号小于 m 的提案
- 如果 acceptor 已经批准过任何提案，那么就向 proposer 反馈已经批准的编号小于 m 的最大编号对应的提案值
- accept 请求
当 proposer 收到半数以上 acceptor 响应结果之后，就可以产生 [m, v] 的提案，这里的 v 是所有响应中编号最大的提案值。如果之前半数以上的 acceptor 未批准过任何提案，那么响应中也就不会包含任何提案值，此时提案值可以由 proposer 自己决定。一旦确定提案，proposer 就可以向某个 acceptor 集合（注意这时候的集合不一定是 prepare 请求时候的集合）发送提案，并希望该提案被批准。
Acceptor 批准提案
Proposer 提案请求包括 prepare 和 accept 两类请求，acceptor 针对这两类请求的响应策略分别为：
针对 __prepare 请求__，acceptor 可以在任何时间响应一个 prepare 请求。针对 __accept 请求__，在不违背 acceptor 现有承诺的前提下，可以任意响应 accept 请求。
到这里整个算法就推导完了，慢着，似乎还有一件事情没有做，我们需要证明 P2c 蕴含 P2b，我们先来回忆一下我们已有的条件是什么，以及我们希望得到什么。
已有的条件（P2c）：
假设提案
[m, v]已经被批准了，如果寄希望对于编号 n (n > m) 的提案来说也有提案值 v，则需要满足如下两个条件之一：
- 集合中所有 acceptor 都没有接受过任何编号小于 n 的提案
- 集合中 acceptor 已经接受的所有编号小于 n 的提案中编号最大的那个提案的值为 v
希望得到的结论（P2b）:
如果提案
[m, v]被选定了，那么之后任何 proposer 产生的编号更高的提案，其提案值都为 v
这里我们采用 数学归纳法 进行证明：
假设提案 [m, v] 已经被批准，
当 n=m+1 时，采用反证法，假设有提案 [n, w] (w ≠ v) 被批准，则说明至少有一个过半数 acceptor 集合满足如下两个条件之一：
- 这个集合中的 acceptor 未批准过任何提案
- 这个集合中的 acceptor 所接受的所有编号小于 n 的提案中最大编号的提案值是 w
由于两个过半数集合之间必定有交集，且由条件可知其中一个集合已经批准了 [m, v] 提案，所以这两个条件均不能满足，所以当 n=m+1 时，w 必定等于 v。
当编号为 (m+1)...(N-1) 的所有提案的提案值都为 v，采用反证法，假设有提案 [N, w] (w ≠ v) 被批准，则说明至少存在一个过半数 acceptor 集合满足如下两个条件之一：
- 这个集合中的 acceptor 未批准过任何提案
- 这个集合中的 acceptor 所接受的所有编号小于 n 的提案中最大编号的提案值是 w
由于两个过半数集合之间必定存在交集，且由条件可知其中一个集合已经批准了 [m, v] 提案，所以这两个条件均不能满足，所以当 n=N 时，w 必定等于 v。
由此我们可以得出 P2c 蕴含 P2b，而整个算法的推导过程也是条件逐渐增强的过程，而算法最终能够满足 P1 和 P2c，再加上 P2c -> P2b -> P2a -> P2，所以间接可以得出算法能够满足 P1 和 P2，而由 P1 和 P2 显然可以保证分布式一致性，所以 paxos 算法得证。
图解算法
最后我们用一张图演示一次简单的 paxos 执行过程。这里我们设置了 2 个 proposer 和 5 个 acceptor。
算法的执行过程如下：
- proposer_1 选择提案编号 1，并向 acceptor_1~3 发送 prepare 请求；
- 因为 acceptor_1~3 之前未响应过任何提案，所以响应 null 值（这里以 N/A 代替）；
- proposer_1 在收到响应之后，因为响应值都为 null，所以自己可以决定发送的提案值，假设这里发送了提案 (1, x)；
- 服务器批准了该提案，并承诺不再接受编号小于 1 的提案；
- 于此同时 proposer_2 选择提案编号 2，并向 acceptor_3~5 发送 prepare 请求；
- acceptor_4 和 5 因为之前未响应过任何提案，所以响应 null 值，但是 acceptor_3 因为之前已经响应过 proposer_1 的请求，所以此时应该响应 (1, x)；
- proposer_2 收到响应之后应该选择编号最大的提案值，而不能自己任意决定，所以 proposer_2 只能发送提案 (2, x)；
- 因为 proposer_2 的提案编号更大，同时提案值与之前批准的提案值相同，所以可以批准该提案；
- 最终在本次算法执行结束，提案值 x 被唯一确定，各个主机之前没有争议，接下去可以交由 learner 去学习。