分布式系统之Paxos算法

什么是Paxos算法

• Paxos 算法是 基于消息传递 且具有 高效容错特性 的一致性算法，目前公认的解决 分布式一致性问题最有效的算法之一.（要剖析啊，头疼）
• 背景：在常见的 分布式系统 中，总会发生 节点宕机 或 网络异常 (包括消息的 重复、丢失、延迟、乱序、网络分区) 等情况，Paxos 算法主要就是解决如何在一个 发生如上故障 的分布式系统中，快速正确的在集群内对某个值达成一致，并且保证整个系统的一致性。
  
  注：Paxos 的目标：保证最终有一个提案会被选定，当提案被选定后，其他议员最终也能获取到被选定的提案。
  Paxos 协议用来解决的问题可以用一句话来简化： 将所有节点都写入同一个值，且被写入后不再更改。

Basic Paxos

• 角色 & 提案
  提案 (Proposal)

注意：提案的范围>value.后面会讲到，[提案=编号+Value].也可表示为[M,V]. 以下描述中暂定: 提案=P，Value=V.

角色

1. Proposer : Proposer 可以 提出提案 (Proposal)。
2. Accecptor : Acceptor 可以 接受提案。一旦接受提案，提案 里面的 value 值就被选定了。
3. Learner : Acceptor 告诉 Learner 哪个提案被选定了，那么 Learner 就学习这个被选择的 value。
   

在具体的实现中，一个进程即可能是Proposer,也可能是Acceptor，也可能是Learner。

Paxos先把节点分成两类，发起提议(proposal)的一方为proposer，参与决议的一方为acceptor。假如只有一个proposer发起提议，并且节点不宕机、消息不丢包，那么acceptor做到以下这点就可以确定一个值：

P1. 一个acceptor接受它收到的第一项提议

当然上面要求的前提条件有些严苛，节点不能宕机、消息不能丢包，还只能由一个proposer发起提议。我们尝试放宽条件，假设多个proposer可以同时发起提议，又怎样才能做到确定并只确定一个值呢？

首先proposer和acceptor需要满足以下两个条件：

1. proposer发起的每项提议分别用一个ID标识，提议的组成因此变为(ID, value)

2. acceptor可以接受(accept)不止一项提议，当多数(quorum) acceptor接受一项提议时该提议被确定(chosen)

(注: 注意以上“接受”和“确定”的区别）

我们约定后面发起的提议的ID比前面提议的ID大，并假设可以有多项提议被确定，为做到确定并只确定一个值acceptor要做到以下这点：

P2. 如果一项值为v的提议被确定，那么后续只确定值为v的提议（确定并只确定一个值）

由于一项提议被确定(chosen)前必须先被多数派acceptor接受(accepted)，为实现P2，实质上acceptor需要做到：

P2a. 如果一项值为v的提议被确定，那么acceptor后续只接受值为v的提议

满足P2a则P2成立 (P2a => P2)。

目前在多个proposer可以同时发起提议的情况下，满足P1、P2a即能做到确定并只确定一个值。如果再加上节点宕机恢复、消息丢包的考量呢？

假设acceptor c 宕机一段时间后恢复，c 宕机期间其他acceptor已经确定了一项值为v的决议但c 因为宕机并不知晓；c 恢复后如果有proposer马上发起一项值不是v的提议，由于条件P1，c 会接受该提议，这与P2a矛盾。为了避免这样的情况出现，进一步地我们对proposer作约束：

P2b. 如果一项值为v的提议被确定，那么proposer后续只发起值为v的提议

满足P2b则P2a成立 (P2b => P2a => P2)。

P2b约束的是提议被确定(chosen)后proposer的行为，我们更关心提议被确定前proposer应该怎么做：

P2c. 对于提议(n,v)，acceptor的多数派S中，如果存在acceptor最近一次(即ID值最大)接受的提议的值为v’，那么要求v
= v’；否则v可为任意值

满足P2c则P2b成立 (P2c => P2b => P2a => P2)。

条件P2c是Basic Paxos的核心，光看P2c的描述可能会觉得一头雾水，我们通过 The Part-Time Parliament 中的例子加深理解：

假设有A~E 5个acceptor，- 表示acceptor因宕机等原因缺席当次决议，x 表示acceptor不接受提议，o 表示接受提议；多数派acceptor接受提议后提议被确定，以上表格对应的决议过程如下：

1. ID为2的提议最早提出，根据P2c其提议值可为任意值，这里假设为a
2. acceptor A/B/C/E 在之前的决议中没有接受(accept)任何提议，因而ID为5的提议的值也可以为任意值，这里假设为b
3. acceptor B/D/E，其中D曾接受ID为2的提议，根据P2c，该轮ID为14的提议的值必须与ID为2的提议的值相同，为a
4. acceptor A/C/D，其中D曾接受ID为2的提议、C曾接受ID为5的提议，相比之下ID 5较ID 2大，根据P2c，该轮ID为27的提议的值必须与ID为5的提议的值相同，为b；该轮决议被多数派acceptor接受，因此该轮决议得以确定
5. acceptor B/C/D，3个acceptor之前都接受过提议，相比之下C、D曾接受的ID 27的ID号最大，该轮ID为29的提议的值必须与ID为27的提议的值相同，为b

以上提到的各项约束条件可以归纳为3点，如果proposer/acceptor满足下面3点，那么在少数节点宕机、网络分化隔离的情况下，在“确定并只确定一个值”这件事情上可以保证一致性(consistency)：

1. B1(ß): ß中每一轮决议都有唯一的ID标识
2. B2(ß): 如果决议B被acceptor多数派接受，则确定决议B
3. B3(ß): 对于ß中的任意提议B(n,v)，acceptor的多数派中如果存在acceptor最近一次(即ID值最大)接受的提议的值为v’，那么要求v = v’；否则v可为任意值
   (注: 希腊字母ß表示多轮决议的集合，字母B表示一轮决议)

另外为保证P2c，我们对acceptor作两个要求：

1. 记录曾接受的ID最大的提议，因proposer需要问询该信息以决定提议值

2. 在回应提议ID为n的proposer自己曾接受过ID最大的提议时，acceptor同时保证(promise)不再接受ID小于n的提议

至此，proposer/acceptor完成一轮决议可归纳为prepare和accept两个阶段。prepare阶段proposer发起提议问询提议值、acceptor回应问询并进行promise；accept阶段完成决议，图示如下：

还有一个问题需要考量，假如proposer A发起ID为n的提议，在提议未完成前proposer B又发起ID为n+1的提议，在n+1提议未完成前proposer C又发起ID为n+2的提议…… 如此acceptor不能完成决议、形成活锁(livelock)，虽然这不影响一致性，但我们一般不想让这样的情况发生。解决的方法是从proposer中选出一个leader，提议统一由leader发起。

最后我们再引入一个新的角色：learner，learner依附于acceptor，用于习得已确定的决议。以上决议过程都只要求acceptor多数派参与，而我们希望尽量所有acceptor的状态一致。如果部分acceptor因宕机等原因未知晓已确定决议，宕机恢复后可经本机learner采用pull的方式从其他acceptor习得。

Multi Paxos

其实不断地进行“确定一个值”的过程、再为每个过程编上序号，就能得到具有全序关系(total order)的系列值，进而能应用在数据库副本存储等很多场景。我们把单次“确定一个值”的过程称为实例(instance)，它由proposer/acceptor/learner组成，下图说明了A/B/C三机上的实例：

不同序号的实例之间互相不影响，A/B/C三机输入相同、过程实质等同于执行相同序列的状态机(state machine)指令 ，因而将得到一致的结果。

proposer leader在Multi Paxos中还有助于提升性能，常态下统一由leader发起提议，可节省prepare步骤(leader不用问询acceptor曾接受过的ID最大的提议、只有leader提议也不需要acceptor进行promise)直至发生leader宕机、重新选主。

Paxos算法流程

（1）Proposer提出提案
总体思路如下：
(一). 学习阶段：Prepare请求
Proposer 选择一个新的提案 P[MN,?] 向 Acceptor 集合 S（数目在半数以上）发送请求，要求 S 中的每一个 Acceptor 做出如下响应：
a. 如果 Acceptor 没有接受过提案，则向 Proposer 保证 不再接受编号小于N的提案。
b. 如果 Acceptor 接受过请求，则向 Proposer 返回 已经接受过的编号小于N的编号最大的提案。

(二). 接受阶段：Acceptor请求
如果 Proposer 收到 半数以上 的 Acceptor 响应，则 生成编号为 N，value 为 V 的提案 [MN,V]，V 为所有响应中 编号最大 的提案的 value。
如果 Proposer 收到的响应中 没有提案，那么 value 由 Proposer 自己生成，生成后将此提案发给 S，并期望 Acceptor 能接受此提案。

(2) . Acceptor接受提案
Acceptor 可以忽略任何请求（包括 Prepare 请求和 Accept 请求）而不用担心破坏 算法的安全性。因此，我们这里要讨论的是什么时候 Acceptor 可以响应一个请求。
对 Acceptor 接受提案给出如下约束：

P1b . 一个 Acceptor 只要尚未响应过任何编号大于 N 的 Prepare 请求，那么就可以接受这个编号为 N 的提案。

如果 Acceptor 收到一个编号为 N 的 Prepare 请求，在此之前它已经 响应过 编号大于 N 的 Prepare 请求。根据 P1b，该 Acceptor 不可能接受编号为 N 的提案。因此，该 Acceptor 可以 忽略 编号为 N 的 Prepare 请求。当然，也可以回复一个 error，让 Proposer 尽早知道自己的提案 不会被接受。
因此，一个 Acceptor 只需记住：

1. 已接受的编号最大的提案；
2. 已响应的请求的最大编号。

附（算法描述）