Basic Paxos

Paxos Made Simple 论文 Notes。

一. 算法背景

Paxos 算法是用来解决什么问题？

先看一个场景: 一个日志收集系统，需要从多个不同的机器上收集日志。

最简单的实现方式是，找一台中心服务器，所有的日志生产机器作为客户端，不断的把日志发送到中心服务器，中心服务器存放所有收集到的日志。

但这种实现方式有一个问题，中心服务器是一个单点，一旦中心服务器发生故障，整个系统不可用。

改进方案: 找多个服务器来收集日志，例如 2 个。当每台日志生产机器需要提交日志时，每条日志都同时被提交到两台收集日志的服务器上面。

这样，同时有多个日志收集服务器在工作，解决了单点问题。

但这种多收集服务器的实现方式有另外一个问题，两台收集日志服务器上收集到的日志可能会不一致。

例如，假设有两台日志生产机器 P1，P2; 同时有两台日志收集机器: Q1，Q2。考虑下面这种情况:

P1 发送一条日志信息 M1 分别到 Q1，Q2
P2 发送一条日志信息 M2 分别到 Q1，Q2

但由于实际网络的状况，日志被收集到的顺序在 Q1，Q2 可能会不一致，例如:

Q1 收集到的日志的顺序是 M1，M2
而 Q2 收集到的日志的顺序是 M2，M1

上面的请求只是一种不一致的情况，现实环境中，情况更加复杂，可能会遇到更多的问题 (例如，由于网络不稳定，P1 发出的消息 M1 到达了 Q1，但 M1 没有到达 Q2，丢失了)

上面这种场景是一个典型的分布式系统的共识 (consensus) 问题:

在一个分布式系统中，有一些 processes，每个 process 都可以提出一个 value
consensus 算法就是用来从这些 values 里选定一个最终 value
如果没有 value 被提出来，那么就没有 value 被选中
如果某个 value 被选中，那么所有的 processes 都应该被学习到

有很多分布式一致性算法来解决这种问题。

而 Paxos 算法就是一种分布式一致性算法，同时 Paxos 还具有容错性，能在各种错误环境中，保证一致性。

二. 系统模型

算法设定了三种角色:

提议者（proposers）：提议者提出提案
决策者（acceptors）：决策者负责批准提案
学习者（learners）：一旦某个提案被多数派决策者批准，那么就形成了一个决议。当决议形成以后，学习者负责学习决议 (我的理解是学习者感知到这个决议已经产生了，并以某种形式把决议持久化)

在具体实现中，某个 process 可以扮演多个角色。

这里还有一个 多数派 的概念: acceptors 数量为 n，超过 (n+1)/2 的 acceptors 的集合就是一个多数派。

节点之间通过发送消息进行通信，通信方式采用异步，非拜占庭模型，该模型中：

process 以任意的速度进行操作，可能因为故障而停止，也可以重新启动。并且 processes 选举出来的决议的值不会因为重启等故障而丢失
消息可以延迟发送，多次发送或丢失，但不会被篡改（即不存在拜占庭问题）

一般来说，分布式算法都需要满足 Safety 和 Liveness：

Safety：一般指一致性，正确性
Liveness: 一般指不会死锁，活锁

具体到 Paxos 算法的系统模型中：

Safety:

最后形成的决议必须是之前被提议者提出的提案
算法的每次执行，最后只能形成一个决议（这个最重要，如果不满足这个，那么会形成多个决议，就出现不一致了）
只有形成决议以后才能被学习者学习（在形成决议之前，提案是不能被学习的）

Liveness:

只要有提案被提出，保证最终有一个提案会被选出来做为决议
决议形成以后，学习者最后能学习到决议

三. 解决思路

基于前面描述的系统模型，最简单的解决办法就是只设置一个 acceptor，而这个 acceptor 只批准它接收到的第一个提案。但这种实现中的 acceptor 是一个单点，不能处理各种故障。

改进方式，利用多个 acceptors + 多数派：

设置多个 acceptors
每个 acceptors 最多只能批准一个提案（如果每个 acceptor 能批准多个提案，就乱了，不能形成多数派）
对于某个提案，只要 acceptors 中有一个多数派批准，就形成决议

另外，为了满足 Liveness，还需要规定：

P1: 一个 acceptor 必须批准它收到的第一个提案

这样就保证了即使只有一个提案被提出，也必然能形成决议。

但这种解决方案存在问题:

某个 acceptor 发生故障，就可能不会出现多数派，不能得到决议；这时，就可能需要进行多次提交提案，进行多次批准。
而允许多次提交，多次批准，就可能违背 Safety 中的第二条。可能形成多个不同内容的决议。

为了解决「允许多次提交，多次批准」可能造成的形成多个不同内容的决议的问题，Paxos 在前面的实现方案的基础上，又加入了一系列的限制条件（P2，P2a，P2b，P2c）：

P2 -> P2a -> P2b -> P2c
只要满足 P2 就能满足 Safety 的第二条，但是 P2 比较难实现
然后又想出来 P2a；只要满足 P2a，P2 也就满足了；但是发现 P2a 存在问题，需要修订（P1 和 P2a 有冲突，如果要满足 P1，有的情况下，就做不到 P2a）
然后又想出来 P2b；P2b 和 P1 不冲突，只要 P1 和 P2b 同时满足就可以解决问题；但 P2b 比较难实现
然后又想出来 P2c；只要满足 P2c，P2b 也就满足了；Paxos 算法就是基于 P2c 实现的

下面一节详细介绍这些限制条件。

四. P2 -> P2a -> P2b -> P2c

Paxos 算法中，给每个提案引入了 版本号 的概念。每个提案由两部分组成:

提案内容: v
提案版本号：n

这样每个提案就是一个二元组: {v, n}

同时，Paxos 规定，在全局范围内（所有的 processes 提出的提案），每个提案有唯一的版本号，这样所有的版本号就形成了一个全序关系。

而且，既然所有提案的版本号是全局范围内的全序关系，也就给所有的提案进行逻辑时间上的排序提供了可能：

例如，两个提案: V{v, n}，W{w, m}，如果 n > m，可以认为提案 V 比提案 W 后提出。

后面具体介绍算法时也会提到，怎么利用版本号来规定提案的时间顺序。

1. P2

P2: 假设一个提案 {v, n} 已经被选为决议，对于选出来的其他所有决议 {w, m}，如果 m > n，那么内容 w 必须和内容 v 相同

说明:

前面已经说过，利用版本号可以在逻辑上对全局时间排序，m > n，代表，{w, m} 是在 {v, n} 之后的提案 (但怎么利用版本号来排序这里没有说，后面才会讲，现在姑且这样认为)。

P2 其实就是说（参考前面 Safety 的第二条），一旦已经形成了一个决议，那么之后如果又发生了多次提交，多次批准，而形成了新的决议，那么形成的新的决议必须和之前形成的决议的内容相同。

2. P2a

因为 P2 限制很难实现，就想出了 P2a。

P2a：假设一个提案 {v, n} 已经被选为决议，其他所有被 acceptors 批准的提案 {w, m}，如果 m > n，那么内容 w 必须和内容 v 相同

显而易见，P2a 被满足了的话，P2 也就满足了。

但 P2a 存在一个问题：P2a 和 P1 有些时候会冲突（P1 是 Liveness 的限制），也就是说，满足了 P1 的话，有的时候，做不到满足 P2a：

提案 V{v, n} 已经被选为决议
但在这次选举过程中，某个 acceptor 没有批准过任何提案 (也就是说，这个 acceptor 还可能批准更高版本号的提案，例如：W{w, m}，m > n）
之后，有一个 proposer 提交了一个提案 W{w, m} 给上面这个 acceptor，而根据 P1，这个 acceptor 会批准这个提案，且这个提案的 m > n，w 和 v 不相同
这就和 P2a 矛盾了：在 V{v, n} 已经被选为决议的情况下，任何 acceptor 批准的更高版本（> n）的提案的内容必须和 v 相同

说明: 在有一个决议已经形成的情况下，是有可能发生某个 proposer 提出新的不同内容的提案的可能的。

3. P2b

为了解决 P2a 和 P1 的冲突，想出了 P2b:

P2b: 假设一个提案 {v, n} 已经被选为决议，所有被 proposer 提出的提案 {w, m}，如果 m > n，那么内容 w 必须和内容 v 相同

一个提案被 acceptor 批准之前肯定要由某个 proposer 提出，因此 P2b 就隐含了 P2a，进而隐含了 P2。

4. P2c

怎么做到 P2b 呢？又想出了 P2c。

P2c：如果某个 proposer 要提出一个提案 {v, n}，那么必须满足下面两个条件中的一个：

存在一个 acceptors 的多数派 S，其中的任何一个 acceptor 都没有批准过比 n 小的提案
存在一个 acceptors 的多数派 S，集合中的某些 acceptor 曾经批准过小于 n 的提案，而所有的这些版本号小于 n 的提案中，拥有最大的版本号那个提案的内容与 v 相同

也就是说，如果每个 proposer 都按 P2c 为约束来提出一个提案，那么就可以满足 P2b，即：

要么还没有形成决议，可以任选提案的内容
要么提出的版本号更高的提案的内容和已经形成的决议的内容相同

对 P2c 的理解如下:

证明1：假设现在 n=4 的 proposal 已经被选举出来了，那么我们要证明在满足上面两个条件的前提下提出一个 n=5 的提案，那么这个 n=5 的提案的内容肯定和 n=4 的提案的内容一致

第一个条件：能找到一个多数派集合，其中所有的人都没有批准过比 5 小的提案（这种情况是不可能发生的，因为 n=4 的提案已经被通过了）
第二个条件：能找到一个多数派集合，首先来看，如果其中某人批准过 n=4 的提案，只要这个n=4 的提案的内容和 n=5 的提案的内容相等的话（4 是比 5 小的数中最大的一个），那么如果 n=5 的提案被选举出来，就是 ok 的（不会破坏上一次选举 n=4 的结果）；其次，会不会其中没有人批准过 n=4，只发现有人批准过 n<=3 的提案？不可能，因为 n=4 的提案已经被多数派批准选举出来了

证明2：假设现在 n=4 的 proposal 已经被选举出来了，那么我们要证明在满足上面两个条件的前提下提出一个 n=6 的提案，那么这个 n=6 的提案的内容肯定和 n=4 的提案的内容一致

第一个条件：能找到一个多数派集合，其中所有的人都没有批准过比 6 小的提案（这种情况是不可能发生的，因为 n=4 的提案已经被通过了）
第二个条件：能找到一个多数派集合，首先来看，如果其中某人批准过 n=5 的提案，而这个 n=5 的提案的内容肯定和 n=4 的提案的内容相同（证明 1 证明）。所以只要这个 n=5 的提案的内容和 n=6 的提案的内容相等的话，n=6 的提案的内容也就和 n=4 的提案的内容相同

总之，只要 proposer 提交提案时遵守 P2c，一旦某个版本号的决议形成，之后形成的更高版本的决议的内容也和最早形成的决议的内容相同。

这里可能有人会提出疑问，前面说了这么多，都说的是，决议从小到大形成的情况，会不会有先形成大版本号的决议，再形成小版本号的决议的情况？比如下面这种场景：

先形成了 4 号决议
接下来，有一个 proposer 企图提出版本号为 3 的提案。此时这个 proposer 是否能够找到一个多数派，其中所有的人都没有批准过比 3 小的提案？（多数派里面的所有成员都批准了 4 号提案）

答案是考虑 P2 系列的约束时，不用考虑版本号会降低的情况，因为下面一个小节引入的 P1a。一旦 4 号决议形成，n < 4 的提案就不可能被提出。

也就是说，多个决议形成，只能是从小的版本号升到大的版本号。

5. 提案生成算法

保证 P2c，也就是要保证 proposer 在提出一个提案时，必须满足 P2c。所以 proposer 想要提交提案时需要 2 个步骤：

先探查一下是否能找到 P2c 中描述的多数派
如果找到了多数派，就可以提交提案了（根据找到的多数派的不同类型，或者提出任意内容的提案，或者提出和之前形成的低版本的决议内容一致的提案）

这里有个问题要特别注意一下:

因为这两个步骤之间有时间间隔，可能在第一步找到了一个多数派，但到了第二步要提交提案的时候，第一步找到的那个多数派中的某个 acceptor 的状态已经变化了。

此时如果再提交提案，那个多数派可能已经不满足 P2c 了。

所以，在第一步探查多数派的同时，也要锁死被探查的 acceptor 的状态。

具体怎么做，看下面的提案生成算法的描述：

proposer 选择一个版本号 n，然后向一个 acceptors 的集合发送请求，要求 acceptor 做出以下动作：

承诺不再批准任何小于 n 的提案（锁定 acceptor 的状态不破坏 P2c）
返回这个 acceptor 到目前为止已经批准过的，且小于 n 的最大版本号的提案。返回消息为：内容+版本号（如果没有批准过任何版本号小于 n 提案，返回一个空值）

如果 proposer 收到了一个多数派的返回响应，那么这个 proposer 可以提出版本号为 n 的提案，其对应的内容为：

如果返回的所有响应都是一个空值（也就是说，存在一个多数派没有批准过小于 n 的提案），提出的提案的内容可以任选
找出所有响应中最大版本号的内容，作为要提交的提案的内容

总之，proposer 生成提案需要两个步骤，发送两种请求：

prepare 请求: 询问状态; 希望 acceptor 端做出承诺，并返回响应
accept 请求：提交提案；希望 acceptor 端批准提案

前面说的是 proposer 端的算法。接下来说一下 acceptor 端的算法：

acceptor 收到 proposer 的两种请求都可以不做任何回答（因为不回答不会破坏算法的安全性）
如果要对 prepare 请求做出响应，只要做出承诺，并根据其当前的状态返回响应就行了（找出目前为止已经批准过的，且版本号小于 n 的最大版本号的提案，作为响应返回）
而对于 accept 请求，必须查看是否之前已经做过承诺，只有在不违反承诺的情况下才能返回响应

这就是 P1a：一个 acceptor 只有在没有响应过任何版本号大于 n 的 prepare 请求时，才会批准一个编号为 n 的提案。

换句话说，acceptor 如果承诺过不会批准任何小于 n 的提案，那么它会拒绝之后收到的任何小于 n 的 accept 请求。

而 P1a 和 P1 不矛盾。所以只要同时满足 P1a 和 P2c 就可以达到 Safety。

P1a 的存在也规定了在 Paxos 算法中，多个决议形成，只能是从小的版本号升到大的版本号（例如：一旦 3 号决议形成，之后再形成新的决议，新的决议的版本号 > 3）

五. Paxos 算法

上一节已经说过了，同时满足 P1a 和 P2c 就可以达到 Safety 满足一致性。不过在这个基础上还可以做一个优化：

如果某个 acceptor 先对版本号为 5 的 prepare 请求返回过承诺，那么当它之后收到一个版本号为 4 的 prepare 请求时，这个 acceptor 可以忽略这个版本号为 4 的 prepare 请求
因为，就算对 4 号 prepare 请求返回响应，之后也不会批准 4 号提案的 accept 请求

acceptor 需要持久化两种信息：

它已经批准过的最大版本号的提案
它已经承诺过的 prepare 请求中的最大版本号的请求的版本号

这里要特别解释一下为什么只需要保存「已经批准过的最大版本号的提案」就行了？

前面说了，acceptor 收到一个版本号为 n 的 prepare 请求时，必须找出目前为止已经批准过的，且版本号小于 n 的最大版本号的提案，作为响应返回。

又由于上面的这个优化，当收到一个版本号为 n 的 prepare 请求时：

如果发现目前已经批准过的所有提案的最高版本号为 m，且 n <= m，那么可以不响应这个 prepare 请求（因为采用前面的优化，一旦做过版本号为 m 的承诺，就可以不给所有小于等于 m 的 prepare 请求返回响应）
如果发现目前已经批准过的所有提案的最高版本号为 m，且 n > m，那么就返回这个版本号为 m 的提案就行了

总之，当 acceptor 重启恢复以后，只要能重新拿到这两个信息，就可以恢复到正常工作状态。同时，proposer 不需要持久化任何信息，可以随意重启（只需要每次提交提案时，都用一个全局唯一的版本号就行了）

【完整的算法如下】:

3 种身份：proposer，acceptor，learner
2 个阶段：【准备阶段】 &【批准阶段】
准备阶段：
- proposer 群发一个 prepare 请求（版本号为 n）给一个 acceptor 的多数派
- 每个 acceptor 会存储曾经在【批准阶段】批准过提案中，最大版本号的提案（w+m），w 为提案内容，m 为提案版本
- 每当 acceptor 接收到一个 prepare 请求（版本号为 n）：
  - 如果 n > m，那么把（w+m）返回给 proposer
  - 如果之前没有批准过任何提案，返回「空」给 proposer
  - 如果 n <= m，那么 proposer 不对这个 prepare 请求（版本号为 n）做响应
  - 承诺今后不会批准「版本号」比 n 还小（也就是 >= n 的提案才会被批准）的任何提案
准备阶段解析：
- 准备阶段的目的是保障 proposer 在「批准阶段」提交「版本号」为 n 的提案时，要么还没有形成决议，要么提交的版本号为 n 的提案和已形成决议的提案的内容相同
- 也就是要在准备阶段探察出一个 acceptor 的多数派：
  - 要么都没有批准过比 n 小的提案
  - 要么把这个多数派中批准过的「版本号」比 n 小的提案中，拥有最大版本号的提案的内容，作为版本号为 n 的提案
- 所以 acceptor 在收到一个「版本号」为 n 的 prepare 请求时，需要找出批准过的，比 n 小的最大版本号的提案的（内容+版本号）返回给 proposer
- 按道理，acceptor 需要存储所有曾经批准过的（提案内容+提案版本）；但可以做一个优化：只存储曾经批准过的最大版本号的提案内容 + 提案版本（w+m）
  - 因为当接收到的 prepare 请求的「版本号」n<=m 时，那么 acceptor 不应该对这个版本号为 n 的 prepare 请求做应答（这时因为，即便是做了应答，但由于在批准阶段，曾经承诺过不会批准比 m 小的提案，版本号为 n 的提案会被拒绝掉）
- 每个 acceptor 需要存储承诺过的「最大版本号」（假设为 maxVersion）
批准阶段：
- proposer 从 acceptor 的多数派的获得到了 prepare 请求的响应
- proposer 从这些响应中挑出版本号「最大的」提案内容（假设该内容为 w）
- proposer 群发一个「批准请求」（版本号为 n，内容为 w）给一个 acceptor 的多数派
  - 如果 proposer 获得的所有响应都为空，那么群发的「提案」可以是任何内容
- 每个 acceptor 接收到一个「批准请求」（版本号为 n，内容为 w）：
  - 如果不违反之前的承诺（n >= maxVersion 的提案才会被批准），就返回「批准响应」给 proposer
  - 否则，对这个「批准请求」不做回应

六. 思考

在现实中，其实是更关注 Paxos「多实例」的场景，也就是不是单次 Paxos 过程，而是一序列的多个 Paxos 过程，例如：instance0, instance1, instance2…
- 但值得注意的是，并不要求时间上按顺序完成这些 instances。例如，可以先完成 instance1 和 instance2，但 instance0 可能一直未完成；也就是出现了一个「实例空洞」
- 为什么可以不按顺序完成这些 instances？这时因为计算机的工作可以抽象成：数据+计算；而 Paxos 只关注数据上达成共识，而出现了 instance 空洞，是否能完成计算，可由计算的具体策略来决定，Paxos 无需关注