Paxos Made Simple

注：Pn 是原论文中明确给出的 constraint，Cn 是推导过程中，临时的 constraint。

推导步骤：

1. 多个 Proposer, 一个 Acceptor

• C1. 谁的 proposal 先到，就 accept 谁的 proposal，即 choose 这个 proposal
  存在的问题：Acceptor 存在 SPOF

2. 多个 Proposer, 多个 Acceptor

• C2. 被超过半数的 acceptor accept 的 proposal 才能被 choose
  因为如果 choose 两个 value，就存在两个 超过半数的 acceptor 集合，那这样的话，必然有至少一个 acceptor 同时属于两个集合。如果一个 acceptor 只允许 accept 一个 proposal，那么就能保证最多只选出一个 proposal。
• C3. 一个 Acceptor 最多只能 accept 一个 proposal
  但是我们希望，如果只有一个 Proposer 提出了一个 proposal，这个 proposal 必定会通过，也就是说 acceptor 不会拒绝掉这个唯一的 proposal，因为 Proposer 不清楚会有多少个 proposal，所以必须在接收到第一个它收到的 proposal 时 accept。
• P1. Acceptor 必须接受它第一个收到的 proposal
  这个会带来新的问题：一个简单的例子，如果每个 Acceptor 都 accept 不同的 proposal，就无法形成过半数。为了解决这个问题，我们去掉 C3 的约束。
• C4. 一个 Acceptor 可以接受多个 proposal
  可是这样一来，就可能会有多个 proposal 都获得过半的 accept。看似陷入了死循环，实际不然：我们想要的是唯一选出 proposal 里的内容，只要多个 proposal 对应同一个内容，就可能达到这个要求。自然而然，想到可以用 (key, value) 对来表示一个 proposal。当一个 proposal 被 accept 的时候，我们认为这个 value 被 accept 了。key 部分，我们称之为 proposal number, 不同的 proposal 拥有不同的 proposal number, 以唯一区分; 并且严格单调递增，表示提出的顺序。
  虽然允许 accept 多个 proposal，这些 proposal 的 value 必须相同，也就是说，还是得保证只选择一个唯一的 value.
• P2. 一个值为 V 的 proposal 被 chosen，那么编号比这个 proposal 大的 proposal 如果被 chosen 了，值也是 V
  因为 proposal number 是有序的，这个约束保证了被选中的 value 的唯一性。
  choose 一个 proposal 首先得有至少一个 Acceptor 来 accept 它。所以 P2 可以由 P2a 来满足。
• P2a. 一个值为 V 的 proposal 被 chosen，那么编号比这个 proposal 大的 proposal 如果被 Acceptor accept 了，值也是 V
  注意， P2a 不与 P2 等价，P2a 的约束更强。P2 的情况下，如果编号比这个 proposal 大的 proposal 被 Aceeptor accept 了，值不是 V，那么只要满足过半数的 accept 的 proposal 的值是 V，最后 chosen 的仍然是 V。但是 P2a 要求 accept 的都必须值为 V。
  但是，一个 proposal 可能被一些特定的，没有接受过任何 proposal 的 Acceptro accept 掉。考虑如下的情况：
  假设有 5 个 Acceptor。Proposer1 提出 [N1, V1]，Acceptor1, 2, 3 accept 这个 proposal，Accetpor 4 此时处于宕机状态，那么 V1 就被 chosen 了。然后 Acceptor 4 恢复工作，这个时候 Acceptor 4 不知道 V1 被选中了，如果 Proposer 2 提出 [N2, V2], N2 > N1, V1 != V2, Aceeptor 4 按照 P1，必须 accept 掉这个 proposal，从而出现了不一致。与 P2a 相矛盾。
• P2b. 一个值为 V 的 proposal 被 chosen，那么编号比这个 proposal 大的 proposal 的值也必须是 V
  对应上面的例子，也就是说，Proposer 2 得以某种方式知道当前已经被 chosen 的 proposal，[N1, V1]，自己在提新的 proposal 的时候，必须是 [N2, V1]。P2a 是对 Acceptor 的约束，P2b 把这个约束转移到了 Proposer 上。P2b 可以保证 P2a, P2a 可以保证 P2.
  如何确包 P2b 呢？
• P2c. 提出一个 [N,V] proposal 必须满足：对于某个由过半的 Acceptor 组成的集合，
  -- 要么他们都没有 accept 过编号小于 N 的任何 proposal，
  -- 要么他们 accept 过，但这些 proposal 中 proposal number 最大的这个 proposal, 其值也为 V
  P2c 可以保证 P2b。这里需要用 数学归纳法来证明 。假设具有值 v 的提案 m 获得通过，当 n=m+1 时，根据 P2c，由于任何一个多数派中至少有一个批准了 m，因此提案n具有值 v；若 (m+1)..(n-1) 所有提案都具有值v，根据 P2c，若反设新提案 n 不具有值v 则存在一个多数派，他们没有批准过 m..(n-1) 中的任何提案。但是我们知道，他们中至少有一个人批准了 m。于是我们导出了矛盾，获得了证明。也就是说，只要满足 P2c，那么 P2b 就得到满足。
  保证 P2c 的关键，是要保证 如果一个 Proposer 想要提出 [N, V]，那么它必须先知那么它必须要获取 已经或者将要被 chosen 的一个 proposal [M, U]，M 小于 N。如果没有 [M, U] 不存在，[N, V] 才能被提出；否则只能提出 [N, U]。获取已经被 chosen 的 proposal 比较简单，但是对未来的情况进行预测就非常困难了。为了不产生这种情况，Proposer 请求 Acceptor 在收到 [N,V] 后不要再接受任何 proposal number 小于 N 的 proposal。解决这个问题需要 Proposer 和 Acceptor 各有个算法，即 Paxos。
  Proposer 算法：
  1.Proposer 提出一个 [N, NULL]，发给某个 Acceptor 集合（半数以上），并希望它们回复：
  -- 承诺不再接受 小于 N 的 proposal
  -- 如果已接受了 小于 N 的 proposal，返回该 proposal
  这个请求称为 编号为 N 的 prepare request
  2.如果 Proposer 收到过半数的回复，那么就可以生成一个 proposal [N, X], X 是返回结果中最大的 proposal number 对应的 X 或者 Proposer 自己决定的值。Proposer 再把 [N, X] 发给某个 Acceptor 集合（半数以上），这里可以不与 1 中的集合一致，请求它们接受。
  这个请求称为 accept request
  Acceptor 算法：
  Acceptor 可以忽略任何请求（包括 prepare 和 accept 请求）而不用担心破环算法的安全性。因此，只考虑 Acceptor 响应一个请求的情况。
  P1a. 当且仅当一个 Acceptor 尚未响应过任何编号大于 N 的 prepare 请求，它可以接受这个编号为 N 的提案
  P1a 满足 P1，如果 Acceptor 收到一个编号为 N 的 prepare请求，在此之前它已经响应过编号大于 N 的 prepare请求。根据 P1a，该 Acceptor 不可能接受编号为 N 的提案。因此，该 Acceptor 可以忽略编号为 N 的 prepare请求。一个 Acceptor 只需要记住两个东西（即使故障，意味着必须持久化）:
  -- 已接受的编号最大的提案
  -- 已响应的请求的最大编号

Paxos 算法描述

上面的推导过程已经描述了算法需要满足哪些要求，即执行过程中如何处理分布式环境下的问题，下面总结 Paxos 算法的流程。
Paxos 算法分为两个阶段：

• 阶段一：
  (a) Proposer选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的prepare请求。
  (b) 如果一个 Acceptor 收到一个编号为 N 的 prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话，否则直接忽略这个消息）作为响应反馈给 Proposer，如果没有接受过，论文没有说明这种情况下的操作，估计这部分返回为空；同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。
• 阶段二：
  (a) 如果 Proposer收到半数以上 Acceptor对其发出的编号为 N 的 prepare请求的响应，那么它就会发送一个针对 [N,V] 提案的 accept 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么 V 就由 Proposer自己决定。
  (b) 如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor没有对编号大于 N 的 prepare 请求做出过响应，它就接受该提案。

Paxos 算法的一个无错情况下的流程

Learner 学习被 chosen 的 value

Learner 学习被 chosen 的 value 有如下三种方案：

如何保证 Paxos 算法的活性

通过选取主 Proposer，proposal 由它来发，就可以保证 Paxos 算法的活性。选择主 Proposer 必须要么使用随机数，要么依照当前物理时间。至此，我们得到一个既能保证安全性，又能保证活性的分布式一致性算法——Paxos 算法。

实现

实现部分略，等以后（或许永远也不）再填坑吧。

参考：
分布式一致性算法——Paxos原理与推导过程
《Paxos Made Simple》翻译
Paxos Made Simple [原文解释版][转载]