分布式一致性算法 -- Paxos

看之前可以先了解一下 paxos-simple，这里面讲述了 Paxos 的基本原理
paxos-simple

什么是 Paxos

Paxos 是具有高度容错特性的分布式一致性算法，其核心是共识算法中的 synod 算法。主要用来解决当一个集群内节点通讯失败或者节点宕机时，保证整个集群内能够快速的对某个值达成一致，即确定一个大家公认的决策值，从而保证整个系统的一致性。

Paxos的三种角色

proposers
发送 prepare 请求和 accept 请求
acceptors
处理 prepare 请求和 accept 请求
learners
学习决策，获取 Paxos 算法实例决定的结果

Paxos原理

该算法能够实现协商一致的安全前提要求如下：

• 只有值被作为提案提出的时候，才有可能被选择为决策值
• 在所有的提案中，只有一个值被选择为决策值
• 只有当决策值被确定时，所有的学习者才会去学习（同步）这个值

选择决策值的最简单方法是选择一个领导者。提议人向领导者发送提议，领导者接受第一个提议值，然后将值更新的消息发送给所有的学习者。
但是这会出现一个问题，如果 领导者节点发生了异常，那么所有的后续操作都将不能进行。
所以，Paxos 尝试了另一种选择值的方法， 决策者不是一个单一节点，而是一组节点。

选值约束（大部分为Paxos Made Simple的翻译内容）

P1：每个接收者 acceptor 需要接受接收到的第一个提案值。

但这可能会出现一种情况，即每个接受者接收到的都是不一样的提案，则每个提案中的值都不能满足大多数原则，因此需要我们允许多个提案被接受。
因为需要确保决策值的唯一性，所以所有被选中的提案中的值必须保持一致，就需要增加 P2 约束：

P2：如果一个带有某个值的提案被选中，那么所有的带有较高编号的提案中的值必须也是这个值

如果提案编号 n 的值 v 被选中，那么任何提案编号 n‘ ，如果 n’ > n 那么 ，v’ = v，因为在 Paxos 算法中，提案编号 n 是全局唯一的，那么 P2 就可以保证算法的安全性，当在 acceptor 接受某个提案之后，仍然有 proposer 提出更高版本的提案请求，那么这个 proposer 就必须遵循 P2 原则，以保证值的唯一性，满足 P2 必然满足 P2a

P2a：如果一个带有某个值的提案被选中，那么所有被acceptor接受的带有较高编号的提案中的值必须也是这个值。

为了同时满足 P2 和 P2a ，进一步提出了约束条件：

P2b：如果一个带有某个值的提案被选中，那么所有proposer提出的带有较高编号的提案中的值必须也是这个值。

即 acceptor 接收到的提案满足 P2 原则，才能保证 acceptor 最终接受的提案满足 P2 原则，同时也满足了 P2a‘。
同时 acceptor 需要满足一些条件：

P2c：对于任意的值v和提案编号n，如果某个proposer发出带有n和v构成的提案，那么形成一个有大多数acceptor组成的集合S需要满足以下其一：1. 没有接受方接受了编号小于n的任何提案，2. S中的acceptor接受过的编号小于n的提案中编号最高的那个提案值为v
为了实现 P2c ，需要进行以下操作：
（1）一个proposer提出一个新的提案编号并发送给每一个acceptor，并要求acceptor承诺以下两件事：
    （a）不再接受编号小于n的其它的提案
    （b）如果acceptor已经接受或承诺过其他提案，那么将这个acceptor已经接受或承诺过的编号小于n的提案中编号最大的那个提案放在回复消息中，否则返回空。
我们将这个步骤称为 prepare(n) 阶段。
（2）如果proposer收到了大多数的acceptor的满足上述承诺的回复消息，那么这个proposer就可以发送一个编号为n，且带有值v的提案给所有acceptor。

Paxos实现过程

变量说明：
n ：Proposer 提案编号
v’ ：Proposer 决定要提案的值
n_ : Acceptor 已经承诺过或接受过的最大提案号；
nm，nmv: Acceptor 接受过的最大提案编号和对应的值

先简单了解下各个角色的工作内容：

Proposer进程

变量说明：

1. proposer 提出一个提案号，该提案号是唯一的，并且比以往的编号都要大，然后将 prepare(n) 预准备请求发送给所有的 acceptors (包含当前节点的 acceptor )。
2. 若该 proposer 从大多数的 acceptors 中获取到了 prepare ok 的响应，表示预准备阶段成功，返回的预准备成功的响应中带有以下信息：
   当前proposer的提案号
   当前acceptor所有已接受的提案号
   当前acceptor所有已接受的提案号中对应的值
3. proposer 获取到大多数的 prepare ok 响应之后，选择自认为最新的值 v’ 。即从返回 prepare ok 的响应中，获取提案编号最高的提案对应的值 nmv，若所有的响应中都没有提案值，则自己确定一个值。
4. 将带有提案编号和提案值的请求 accpct(n,v’) 发送给所有的 acceptor 。
5. 当集群内大多数的 acceptor 返回 accpct ok 的响应时，表示当前提案已经成功，然后 proposer 发送 decide(n) 消息通知集群内所有的节点。

在 proposer 工作过程中，有任何一步出现问题，例如发送 prepare(n) 的过程中出现网络中断等，将从步骤一重新执行，直到决定了决策值为止。

Acceptor进程

1. 首先，当 acceptor 接收到来自 proposer 的 prepare(n) 请求的时候，他会判断请求中的提案编号 n 和自己已经承诺过或接受过的最大提案号 n_ 谁更大，如果 n > n_ ，那么就更新 n_ 为 n ,表示该 acceptor 已经承诺考虑当前提案，并返回给proposer prepare ok 的响应，否则返回 prepare reject 的响应。
2. 当接收到 proposer 的 accept(n,v’) 请求的时候，判断请求中的 n 是不是比自己已经承诺过或接受过的最大提案号 n_ 大，如果 n > n_，那么当前 acceptor 就会接受当前提案 ，更新 n_ 为 n ，并更新接受的最大提案号和值 nm=n ，nmv=v‘，返回 accept ok 的响应，否则返回 accept reject 的响应。

时序图