Paxos算法

发表于 |

本文介绍Paxos算法，包含Basic Paxos，以及Raft作者提出的一个Multi Paxos的工程化实现方案。此外，我们还就Raft作者给出的Paxos习题进行探讨。

Basic Paxos(Lamport)

Paxos允许消息被任意延迟、丢包、重复，但不允许消息被损坏。
Basic Paxos弱化了Leader的概念，而使用了Proposer的概念。
Basic Paxos只对一个Value决议。这个Value实际上类似于Raft里面的一个Log Entry，即x=1或者y=42之类的。根据原版论文The part-time parliament，这里的Value即法令，类似于禁止画画或者允许自由艺术等。
注意，一个 Value 被决定是 chosen 而不是 accepted，即决议的过程是

1
propose(issue) -> accept -> chosen

论证1

在论证1的部分，我们从原始要求倒推出需要维护的不变量 P2b。

P1

考虑没有丢包和机器故障，并且假设只有一个proposer。对于该平凡情况，可以得到下面的要求：
一个 acceptor 必须接受它收到的第一个 proposal。

显然这个方案存在一个问题，不同的 proposer 可能提出不同的value，这会导致每个 acceptor 收到了不同的 value，但其中没有一个 value 是占 majority 的。
这个问题导致我们需要让 acceptor 去 accept 多于一个 proposal。为了区分这些 proposal，就要引入 proposal number。
一个 Value 被 chosen，当具有这个 Value 的 proposal 已经被大部分的 acceptor accept 了。

P2

经过上面的论证，我们允许 choose 多个 proposal，前提是所有被 chosen 的 proposal 都有相同的 Value，因此提出下面的要求：
如果具有 Value v 的 proposal 被 chosen 了，那么对于任意更高的 number 的 proposal，如果它被 chosen，那么它就一定有 Value v。

P2a

就 P2 进一步推导，因为被 chosen 的前提是这个 proposal 要至少被一个 acceptor accept，可以通过满足下面条件来满足P2：
如果具有 Value v 的 proposal 被 chosen 了，那么对于任意更高的 number 的 proposal，如果它被任意的 accpetor accept，那么它就一定有 Value v。

这个条件更强，因为它从要求 chosen Value 变成要求 accept Value，相当于提前了。但前提还是已经有 proposal 被 chosen。

P2b

注意，仍然需要满足要求 P1，这样保证至少能 accpet 一个 proposal。因此可以构造出下面的情况：

  1. 一个新的 proposer propose 了一个更高的 number 的 proposal，但是具有不同的 Value v2；
  2. 一个之前从来没有收到过任何 proposal 的 acceptor 收到了这个 proposal；
  3. 根据 P1，这个 acceptor 需要 accept 这个 proposal；
  4. 根据 P2a，这个 acceptor 不能 accept 这个 proposal，因为它必须有之前的 Value v；

我们发现这里产生了矛盾，因此还需要继续强化要求P2a：
如果具有 Value v 的 proposal 被 chosen 了，那么对于任意更高的 number 的 proposal，在它被任意 proposer 发出时，就一定有 Value v。

这个条件更强，因为它从要求 accept Value 变成要求 propose Value，相当于更提前了。但前提还是已经有 proposal 被 chosen。

所以截止目前为止，我们还是不能得到一个完整的算法，因为缺少尚未 chosen 时的行为规则。

论证2

论证2紧接着论证1，讲述如何维护 P2b 性质。

P2c

首先要做的是，对 proposal 编号。

为了方便表示，规定 proposal(m,v) 表示具有 number n 和 Value v 的 proposal。下面查看 P2b 是如何保证自己一直成立的。

考虑 proposal(m,v) 被 chosen，那么要证明任何 number 大于 m 的 proposal(n) 也有 Value v。证明如下：
如果 m 被 chosen，那么一定有大多数 acceptor accept 了这个 proposal，这些 acceptor 属于集合 C。再结合 P2b，可以推出C中所有的 acceptor 都 accept 了从 m 到 n-1 的 proposal，并且这些被 accept 的 proposal 都具有 Value v。

因为任意包含大多数 acceptor 的集合 S 必须包含 C 中的至少一个成员，可以得出 P2c。也就是只要满足 P2c，就能维护 P2b 性质。

考虑一个 proposer 发出了 proposal(v,n)，那么存在一个上述的 acceptor 集合 S，满足要求 P2c：

  1. 要么 S 中的 acceptor 都没有 accept 过低于 n 的 proposal；
  2. 要么 accept 的最大的小于 n 的 proposal 的 Value 是 v。
    【Q】这种情况下，是否可能 accept 多个 Value 呢？

论证3

为了维护 P2c，我们发现一个 proposer 在发出 n 这个 proposal 之前，需要检查最大的小于 n 的 proposal，看它是否已经或者将要被某些 acceptor accept。前者容易，但是后者不容易，因为要预测某个 proposal 是否会被 accept。

为了简化掉这个预测，引入了一个提前的阶段。这个阶段中，proposer 要求 acceptor 保证不会再去 accept 任何低于 n 的 proposal 了。

现在，得到下面的算法，该算法指导如何 issue 一个 proposal。

Proposer 算法 Step1

在这里，我们引入了一个 Prepare 请求。需要注意 Prepare 请求和 proposal 的区别。
proposer 选择一个新的 number n，发送请求 Prepare(n) 给某个集合中的所有 acceptor。注意这个 Prepare 请求不同于 proposal，它不需要带上 Value。
此时每个 acceptor 应该返回：

  1. 保证不再接受小于 n 的 proposal；
  2. 自己目前 accept 了的最大的小于 n 的 proposal。如果没有的话，就不需要返回。

Proposer 算法 Step2

如果这个 proposer 收到了 majority 的 acceptor 的回复，那么就可以发送一个 Accept(n,v) 的请求。其中 n 是 Prepare 时候的 n，v 则遵循下面的规则选择：

  1. 如果没有人对 v 的值有 proposal，那么这个 proposer 就可以任选 v 的值。
  2. 否则，就返回最大的小于 n 的 proposal 给出的 v 值。

文章特别强调，Prepare 请求和 Accept 请求可以发送给不同的 acceptor。

Acceptor 算法

该算法又名 P1a 约束：

  1. 一个 acceptor 可以安全地忽略任何的请求。
  2. acceptor 可以回应 Prepare 请求。
  3. acceptor 可以回应 Accept 请求，并去 accept 某个 proposal，当且仅当它没有保证不接受这个请求，即：
    当且仅当一个 acceptor 没有回应大于 n 的 Prepare 请求，它可以接受一个 n 编号的 Accept 请求。可以看出，P1 是 P1a 的特例。

也就是说，如果回应了 n+1 的 Prepare 请求，那么：

  1. 可以忽略编号是任意的 Accept 请求；
  2. 可以 Accept 编号是 n+1 的 Accept 请求；
  3. 不能 Accept 编号是 n 的 Accept 请求；
  4. 能不能 promise 编号是 n 的 Prepare 请求？
    文章中指出，没有理由去回应这样的请求。因为根据上一点，连编号为 n 的 Accept 请求都不会被响应了，更何况 Prepare 请求呢？
    同理，如果一个请求已经被 accept 了，那么我们也不会再去回应对应的 Prepare 请求了。
    根据 Proposer 算法 Step 1，我是保证不会接受小于 n 的 proposal，但在这之前我已经保证不接受小于 n+1 的 proposal 了。但假如我们回应了 promise n，那么会返回之前的 proposal 给出的 v 值，我理解这样也不会出问题。所以这归根结底是个优化。

持久化要求

为了维护 P2c 这个不变量，一个 acceptor 需要持久化：

  1. 自己回复的最大的 Prepare 请求的 number；
  2. 自己 Accept 的最大的 proposal number；

此外，一个 proposer 可以忘记或者放弃自己的 proposal，只要它不会产生具有相同 number 的另一个请求。因此 proposer 需要持久化：

  1. 自己使用过的最大的 proposal number

算法

将 Proposer 和 Acceptor 组合起来，可以看到 Paxos 算法的全貌。

Phase 1：Prepare

  1. proposer
    选择 n，发送 Prepare(n) 到 majority 个 acceptor 上。
    注意 Prepare 阶段实际不要带上自己意向的 Value。
  2. acceptor
    对于 Prepare(n)，如果 n 高于已经响应过的其他 Prepare 请求，则：
    1. promise 不会再 accept 任何小于 n 的请求；
    2. 发送最大的小于 n 的 accept 的 proposal，这里面包含了 Value。

Phase 2：Accept

  1. proposer
    如果收到了 majority 的 acceptor 对自己 Prepare(n) 的响应，则发送 Accept(n,v) 请求给所有这些 acceptor。这里 v 的选择参见Proposer 算法 Step2一节。
  2. acceptor
    除非自己已经回复了 Prepare(n+1) 或者更高的 Prepare 请求，否则 acceptor 需要 accept 请求 Accept(n,v)。
    注意，如下文所述，一个 acceptor 可能 accept 不同的 Value，也就是可能变票。

Learner

容易发现，因为没有 Leader，所以从单一的 acceptor 角度，并不能很方便地去检查某个 proposal 是否已经被 chosen 了。

一个平凡的方法就是每进行一次 accept，就告知 Learner 一次，不过这有很大的通信开销。考虑到 Learner 也不会出现拜占庭错误，所以 Learner 间可以相互通信以得到被 accept 的值，因此可以让每个 acceptor 只响应某一些 Learner。

如果考虑到这一些 Learner 可能失败，导致丢失 acceptor 信息，问题还会更复杂。此时，一个值被 chosen 了，但是没有 Learner 发现。虽然 Learner 可以再逐个询问 acceptor，但只要有一个 acceptor 宕掉，就可能导致 Learner 无法了解某个 proposal 是否得到多数同意。在这种情况下，只有当一个新的 proposal 被 chosen Learner 才会再次发现。这就有点类似于 Raft 中新 Leader 不能提交旧 term 的日志的感觉。

【Q】对此，可以提出一个问题，对于 n>m，如果 n 被 chosen，那么 m 是不是一定被 chosen 呢？

活锁问题

上述的 Basic Paxos 算法存在活锁问题。考虑

  1. p 发送 Prepare(n1)；
  2. q 发送 Prepare(n2)，其中 n2>n1；
  3. 此时 p 不能成功地 Accept(n1) 了，因为 acceptor 保证了不会 accept 低于 n2 的请求；
  4. 于是 p 继续发送一个 Prepare(n3)，其中 n3>n2；
  5. 由此开始循环往复。

因此必须选出一个proposer，这个 proposer 起到 Leader 的作用，只有它可以发送 proposal。在论文后面提到，这个 Leader 实际上还起到首要的 Learner 的作用。

可以发现，Raft 之所以引入 Leader，一定程度上也是为了减少活锁的问题。

实现

acceptor 的回复需要带上对应的 proposal number。acceptor 需要先持久化自己的回复，再发送给对方。
下面讨论如何保证没有两个 proposal 的 number 是相同的。方法很简单，不同的 proposer 从不同的不相交集中取这些序号即可，比如模上自己的序号。每个 proposer 持久化自己所选取的最大的 proposal number。

实现状态机

使用多个服务器组成集群，每个服务器构成一个单独的状态机。因为状态机都是确定的，所以每个服务器对应的状态机的状态和输出始终是一致的。
为了保证每个状态机都能执行相同的状态机命令，实现了

Basic Paxos(Ongaro)

在 Ongaro 等的视频里面，进一步理清了 Basic Paxos 的相关概念。
首先是 Basic Paxos Instance、Server、Proposer 和 acceptor 的关系。一个 Instance 指的是 Basic Paxos 决定一个 Value 的过程。因此 Basic Paxos 被称为是 Single decree 的，因为它只决定一个值。

一般一个 Server 同时是一个 proposer 和 acceptor。一个 acceptor 完全被动地处理来自 proposer 的请求。一个 acceptor 可能 accept 不同的 Value，也就是可能变票。

特别地，只有提出某个 proposal 的 proposer 才能知道是否已经被 chosen；对于其他的 proposer，必须用自己的 proposal 执行一遍 basic paxos才行。

Basic Paxos 的图解

Split Votes讨论

这个章节论述 Paxos 算法是如何被得到的，所以有点往回讲。
如果 acceptor 每次只接受发给自己的第一个 proposal，那么就会出现下面的情况。为了避免，需要 acceptor 能够 accept 不同的 Value。

如果 acceptor 接受所有给它发来的 proposal，也不行。
第一个问题如下所示，可能导致有多个不同的 Value 被 chosen。为了解决这个问题，就有了 P2b，也就是一旦 chosen，那么后续 proposer 只能 propose 同样的 Value。这个由一个两阶段的协议来保证。

第二个问题如下所示。在这个场景下 S3 选择不同的策略可以导致不同的 Value 被 chosen。
如果我们秉持“接受所有发来的 Proposal”的策略，那么就会导致如下的情况：

  1. S5 并不需要 propose red 这个 Value，因为这个时候 red 还没有被 chosen。
    所以这个问题和第一个问题不同，因为这个时候 proposal 还没有被 chosen，所以 P2b 发挥不了作用。但 acceptor 还是不能来者不拒。
    所以这就是为什么 P2b 时还没引入 proposal number，到了 P2c 时就要引入了。
  2. 但是 S3 必须要 reject 掉 Accept(S1, red)，因为在收到这个 Accept 请求的时候 blue 已经 chosen 了。

Ongaro 说要引入 order，也就是新的 proposal 要比老的 proposal 更优先。当然，如果老的 proposal 已经被 chosen 了，那就按照 P2b 规则来。不然又退化成接受所有给它发来的 proposal 了。

所以为了解决问题二，实际上规则是：

  1. 一旦 chosen，就只能 propose 和 accept 同一个 proposal
  2. 否则，永远 accept 最新的 proposal

Proposal Number

接着，Ongaro 提出一种实现 Proposal Number 的方案，也就是高位的 Round Number 和低位的 Server ID。这些 Round Number 需要被持久化到磁盘上，以保证 proposal number 不会被重复使用。

Round Number 是全局递增的，而不是自己实现一个 Local 的计数器。每个 Server 基于自己看到的最大的 Round Number 来选取新的 Rounder Number：

  1. 自增自己维护的 maxRound
  2. 将自己的 Server ID 贴在后面

Paxos 算法

下面的图表示了 Basic Paxos 的消息通信过程

三种Prepare顺序讨论

下面讨论 Paxos 中三种常见的 Prepare 顺序和对应的结果。
框框中的 P 3.1 表示收到来自 Server1 的 Round Number 为 3 的 proposal，A 3.1 X 表示收到而不是接受这个 proposal，它的值为 X。
在这些场景中，有两个 proposer 试图 propose，分别是 S1 要 propose 值 X，且 S5 要 propose 值 Y。

1. 当值X已经被chosen

如下图所示，当来自 S5 的 proposal P 4.5 到来时，值 X 已经被 chosen 了。那 S3 会在 Prepare 的时候就告诉它自己已经 accept X 这个值了。后续 S5 的 proposal 也只好去 propose 这个值，也就是发送 Accept(3.1, X)。

2. 当值X没有被chosen，但新的proposer能够看到

注意 S3 已经 accept 了 A 3.1 X，所以当 S5 发出 P 4.5 后，它会告诉 S5 值已经被自己 accept 为 X 了。所以后续 S5 就发送 Accept(X)。

3. 当值X没有被chosen，新的proposer也看不到

此时 S3 上的 A 3.1 X 请求实际上不会被 accept，因为 Prepare(4.5) 已经捷足先登了。

Multi Paxos(Ongaro)

主要讲了几件事情：

  1. 如何维护一个 Log 也就是一系列 Entry，而不是某一个 Entry。
  2. 性能优化，包括两方面，但主要是借助于 Leader：
    1. 去掉 proposer 之间存在的活锁
      如果在任何一个时刻，保证只有一个 proposer 发请求的话，那么就不会存在活锁。
    2. 去掉冗余的 Prepare 请求
      即对每个 log 而不是每个 entry 进行一次 Prepare，这样话大部分 entry 可以在一轮 RPC 中被 chosen，即执行一轮 accept。
  3. 如何实现所谓的 Fully Replication，即让大家都知道某个 Entry 已经被 chosen 了。
  4. 客户端协议以及状态机相关。

可以看到，这些事情也正是 Raft 相比 Basic Paxos 增加的大部分内容，也是 Raft 容易理解和实现的原因。

维护一个Log

如下图所示，粗线框表示这个 Entry 我们知道已经被 chosen 了。而没加粗线框的 Entry，只是说明 accept 了这个值。

现在准备新增一个 entry 到 log。client 发送一个 jmp 给 S1，S1 选择哪一个 entry 呢？这可能涉及以下的情况：

  1. 在 Entry1 和 Entry2 中，mov 和 add 被复制到了所有机器上，并且 S1 已经知道被 chosen 了。如下图所示，用粗框子框出来了。
  2. 在 Entry3 中，cmp 被 S1 和 S3 accept 了，所以实际上已经被 chosen 了。但是 S1 并不知道，这个可能是因为 S3 的 acceptor 被分区了。其实我觉得还有可能是因为这个 proposal 不是 S1 提出来的，所以 S1 不知道。

下面考虑 S3 被分区的情况：

  1. S1 找到第一个自己不知道被是否 chosen 的 entry，即后面提到的 firstUnchosenIndex。也就是下图中的 Entry3。
  2. 根据 Basic Paxos 算法，对这个 entry 去 propose 一个 Value 为 jmp 的 proposal。显然，这个 Value 是不能被 accept 的，并且会在 Prepare 阶段就被要求使用 cmp 去发送 Accept 请求。因为已经有一个 acceptor 接受了 cmp 这个值了。所以这个 Basic Paxos Instance 跑完，实际上还是导致 cmp 在 Entry3 中被 chosen。并且 S1 知道了这个结果。
  3. 接着回到第1步，检查下一个尚未被发现已经 chosen 的 entry，即 Entry4，并尝试 propose。显然，这次 jmp 还是不能被成功 propose，因为 sub 已经被 S2 上的 acceptor accept 了。

上面实际上就是所谓“补空洞”的过程。可以发现，由新 proposer 来帮助老 proposal 实现 chosen，类似于 raft 中由新 Leader 帮助老 Leader 完成 commit 的过程。但我觉得实际上 Paxos 更加灵活，因为可以有多个 proposer 同时做这个工作。

通过这种方式，Server 可以并发处理多条来自 client 的请求。演讲者提到，例如第一个请求用到了 Entry3，那么下一个请求可能会尝试 Entry4 或者 Entry5 等等。

注意 Entry5 上原来的 cmp 命令，它只出现在 S3 上。但可能因为它被分区了，所以最终被 chosen 的是 jmp，并且 S3 上最终是个 shl。如果在这里有疑惑，如果 cmp 被 S3 accept 了，为啥还能先后 accept 不同的值？需要回过头去看 Split Votes 这一章节。或者看下习题2。

【Q】我们能保证 client 的请求在 Paxos log 层面是 in order 的么？也就是说 client 可能找一个 proposer 要求写入 cmp，另一个 proposer 要求写入 shl。然后它们实际的写入顺序是不一致的？

提升性能的办法

解决方案：

  1. 引入 Leader
    这样只有一个 Server 能 propose，减少冲突的可能性。
  2. 消除大部分 Prepare
    每个 log Prepare 一次，而不是每个 entry Prepare 一次。
    减少 choose 一个 Value 需要的 RPC 轮数。

Leader

选举

需要注意的是，Paxos 在有多个 Leader 的时候依旧能够正常运作，只是效率会受到影响；但是 Raft 等就必须要求有唯一的 Leader。
Lamport 提出一种简单的办法，就是令具有最大的 Server ID 的 proposer 为 Leader。接着所有的 Server 互相向其他 Server 以间隔 T 发送心跳包，心跳包中包含自己的 Server ID。如果一个 Server 在 2T 的时间内没有收到一个具有更高的 Server ID 的心跳包，那么它就以 Leader 的方式行动，即开始处理来自 client 的请求，且同时执行 proposer 和 acceptor 的角色。相对应地，如果一个 Server 不是 Leader，那么它不处理 client 的请求，并且只执行 acceptor 的角色。

演讲者后来指出，一般来说，并不会用这种方案。

减少Prepare

下面讨论如何减少 Prepare 请求。首先，为什么要有 Prepare 请求呢？

  1. 阻止具有旧的 number 的 proposal
  2. 发现可能存在的已经被 chosen 的 Entry
    因为 acceptor 处理 Prepare 请求时，如果自己已经 accept 了某个 proposal，会返回该 proposal。 即 Proposer 算法 Step1。

下面对这两点目的进行改进：

  1. 阻止具有旧的 number 的 proposal
    让 proposal number 和整个 log 关联，而不是和某个 entry 关联。
  2. 发现可能存在的已经被 chosen 的 Entry
    在处理 Prepare 请求时，acceptor 不仅要返回对于当前 entry 的最大的 proposal number，还要检查当前 entry 之后的所有 entry。如果这些 entry 里面没有任何 proposal 被 accept，那么就返回 noMoreAccepted。

如果一个 acceptor 返回了 noMoreAccepted，那么后续就不再发送 Prepare 请求，直到某个 Accept 请求被拒绝。【Q】根据 Basic Paxos 算法，acceptor 只有在已经响应了更高的 proposal number 的情况下，才会拒绝 Accept 请求。所以好奇什么情况下会拒绝呢？应该是当某一个新的 Leader 出现后，它会发起一个更高的 Prepare，从而导致某个 acceptor 会开始拒绝 Accept 请求。
如果一个 Leader 从多数的 acceptor 处都收到了 noMoreAccepted，它就不再需要发送 Prepare 请求了。这个状态可能会被另一个当选的 Leader 打破，此时旧 Leader 会收到被拒绝的 Accept 请求。

Fully Replication

因为最终所有的 Log Entry 都需要过 RSM，所以要保证最终每个 Server 上的 Log 都是全的，并且他们知道哪些已经被 chosen 了。这通常包括两个目标：

  1. 保证 Entry 最终在所有的机器上被复制，但目前只保证了 majority。
  2. 保证所有的 Server 都能知道某个 Entry 是否被 chosen。这样所有的 Server 才能及时跟进 Leader 的状态机。
    目前只有对应的 proposer 知道。因为 proposer 需要向 majority 个 acceptor 发送 Accept。

下面是解决方案，一共有四个措施，但其实大部分措施都是为了处理就 Leader 宕机的情况。

措施1：Proposer 需要不断地重复 Accept 请求，直到所有的 acceptor 都回复

当已经复制玩 majority 后，这个操作就可以在后台完成了。
这个策略保证了在这个 Server 上创建的大部分新 entry 都能给复制到其他 Server 上。但还是不充分的，原因是考虑当 Proposer 宕掉时，他未必能够将所有的 Entry 都进行复制。其实我还认为就算复制过去，但对方还是不知道这个 entry 是否可以 chosen 啊。

措施2：跟踪所有被 chosen 的 Entry

每个 Server 对自己知道的，已经被 chosen 的 Entry 设置 acceptedProposal[i]=INF，INF 也是能够无缝适配协议的，因为不可能存在一个更大的 proposal number 来 overwrite 掉这个 proposal 了。
每个 Server 维护一个 firstUnchosenIndex，也就是在“维护一个Log”中介绍的那个。

措施3： Proposer 将自己的 firstUnchosenIndex 附加在 Accept 请求中发送

这样，一个 Accept 请求具有下面的结构。表示 3.4 这个 proposal，设置 index = 8 处的 Value 为 v，并且 proposer 处第一个没标记为 chosen 的是 index = 7。

1
request = Accept(proposal=3.4, index=8, value=v, firstUnchosenIndex=7)

而 acceptor 会对每个 Entry[i] 进行如下的检查，如果下面两个条件被满足，那么就将 Entry[i] 标记为 chosen。

  • i < request.firstUnchosenIndex
  • acceptedProposal[i] == request.proposal

下面说的 Leader 指的是当前唯一能发送 proposal 的 proposer。在前面章节，我们论述了为什么要引入 Leader，以及如何选出一个 Leader。

为了解释这种情况，我们查看下面的这个例子。下图中，每个格子里面的数字指的是 proposal number。容易看到，在处理 Accept 请求前，这台 Server 上的 Entry 1/2/3/5 已经被 chosen 了。

现在，来自 Leader 的一个 Accept 请求告知 firstUnchosenIndex=7，意味着在 Leader 上，Entry1 到 Entry6 都被 chosen 了。此时 acceptor 扫描自己上面所有的 unchosen entry，如果发现这些 entry 具有和 Leader 发来的 proposal number，这里即 3.4 一样的 proposal number，则将对应 entry 设置为 chosen。对应下图中，就是将 Entry6 设置为 chosen。

然后我们有几个疑问：

  1. Entry 6 为什么可以被标记为 chosen？
    首先这个 acceptor 知道 Entry 6 也是来自于发送这个 Accept 的 Leader，即是这个 Leader 写入的。
    但这还不够，有关于 Entry 6 的具有另外一个值的 Accept 请求呢？我想这样的话，proposal number 一定会变得更大。但既然能 accept 这个 3.4 的请求，说明 3.4 这个 proposal number 是最新的。
    那么，既然这个 entry 是当前 Leader 写入的，并且 Leader 说它已经被 chosen 了，而这个 Leader 又是最新的，那被 chosen 的这个值一定就是 acceptor 日志里面的这个值。
    【Q】同一个 Leader 会发送 Entry 6 上具有另外一个值的 Accept 请求么？我觉得应该不会，新的写入应该对应新的 Entry 啊。
  2. Entry 4 为什么不能被标记为 chosen？
    因为 Entry 4 具有不同于 3.4 的 proposal number，也就是说来自于另外一个 Leader。所以没办法像 Entry 6 一样确定这不是一个陈旧的数据。也就是说，这个 accpetor 知道 Entry 4 被 chosen 了，但是并不知道这个被 chosen 的 Value 是不是自己 Log 里面的那个 Value。因为在 “Split Votes” 中提到，acceptor 可以 accept 不同的 value，所以很可能这个值又被改了。
    那么后续这个 Entry 怎么办呢？往后看。
  3. Entry 7 是怎么回事？为什么我们收到的 Accept 请求是写 Entry 8 而不是空的 Entry 7 的呢？

措施4：Success RPC

acceptor 会在对 Accept 消息的返回中附带上自己的 firstUnchosenIndex，当 Proposer 收到该 acceptor 返回后会将该值和自己的 firstUnchosenIndex 进行比较。如果 acceptor 的 firstUnchosenIndex 小于自己的，说明这个 acceptor 落后了，此时需要在后台发送 Success RPC。
这个 RPC 需要包含 index 以告知是那个 Entry 被 chosen 了，并且附带上一个 v 表示被 chosen 的值。当 acceptor 收到这个消息后，将：

  1. acceptedValue[index]=v
  2. acceptedProposal[index]=INF
  3. 返回新的 firstUnchosenIndex 给 Proposer，Proposer 会根据这个值判断是否需要再次发送 Success RPC

发送的 firstUnchosenIndex 有点类似于 Raft 中的 leaderCommit。

Leader 缺少日志问题

Paxos 和 Raft 的比较

Raft 可以被视为去掉 propose 阶段的 Multi Paxos。这是因为：

  1. Raft 借助于日志选主，而不需要 propose 环节来竞争一个 propose number 了。
  2. Paxos 中可以 accept 不同的值，这也对应了 Raft 中新的 Leader 会把老 Leader 复制的日志覆盖掉的情况。
  3. Raft 中会拒绝来自更低的 term 的 Leader 日志。这对应 acceptor 会拒绝掉更低的 Propose Number。
  4. Success RPC 类似于 leaderCommit 和对应的日志的 AppendEntries

Client协议

这一部分和 Raft 一样，非 Leader 的 Server 会把请求转发给 Leader。同样的，Leader 也会在 Client 提交的命令被 chosen 以及被 RSM 执行之后，才会返回。
如果请求超时，例如 Leader 宕机了，那么 Client 会将命令发送给其他 Server，在最终发现新Leader后，重试命令。

如何保证Exact once语义

这个问题通常发生在当老 Leader 在执行完自己的状态机后、返回给 Client 前宕机。根据上面的论述，Client 实际上会通过另一个 Leader 重试，在这种情况下，可能同样的命令就会被执行两次。其实这种情况在我实现 Raft 协议的时候也遇到过。

对此，演讲者建议 Client 对每个命令设置一个唯一的 ID。每个 Server 上的 RSM 都会自己记录一下自己执行过的最新的ID。那么当 RSM 在执行每个命令的时候，会首先检查它是否已经被执行过，如果被执行过了就忽略，并且返回当时的结果。这种策略的要求是 Client 不挂，因为 ID 是由 Client 设置的。

配置变更

包含：

  1. 每个 server 的 ID、addr
  2. 定义什么组成一个 majority，例如节点的上下线等

Conf Change 的难点是它会改变 majority。

Paxos 的配置变更的思路是：

  1. 配置被作为 log entry 来存储，并按照 log entry 来复制
  2. 用来 choose Entry i 的配置由 i-α 决定

因此：

  1. α 控制了并发度。i+α 只有在 i 被 chosen 之后才会被 chosen。

一些讨论

幽灵日志

第三态

超时就是分布式系统中除了“成功”和“失败”之外的第三态，对于客户端而言，我们并不知道到底是成功还是失败：

  1. 如果是在处理过程中，因为分区、宕机等因素导致的没有 Commit 成功，这个也许是失败；
  2. 如果是在 Commit 和 Apply 成功之后，返回客户端时宕机或者分区了，这个应当认为是成功。

一个case

  1. A被选为Leader，写日志1-10，其中1-5已经Commit和Apply，并返回给客户端。
  2. A宕机，但6-10没有被Commit和Apply，因此客户端会超时。
  3. B选为Leader。B应当从6开始写新的日志，此时客户端无法查到6-10号日志，因为它们还没提交。
  4. B提交了6和20号日志，并返回给客户端，但随后又宕机了。
  5. 此时A又被选为Leader。

此时，A如果想要Propose，肯定会发现自己得先补空洞，这就是类似“维护一个Log”章节中的操作：

  1. 针对日志6，A去跑一遍Basic Paxos，因为实际上这条日志已经被Chosen了，所以A也会接受被多数派认可的日志。
  2. 针对日志7-10，A是有本地日志的，但并没有被chosen，于是A会尝试提交本地日志。
  3. 针对日志11-19，A没有本地日志，所以这边就都是Noop。
  4. 针对日志20，也是接受被多数派认可的日志。

现在从时间的角度考虑日志7-10。在A宕机后，客户端超时了，实际上是陷入了第三态。这有什么问题呢？我们考虑这是个转账场景，客户发现第一次超时了，可能就会重试。此时A从宕机恢复过来，又把7-10给补上了，这就很可能导致用户重复转了两次账。

那么如何解决这个问题呢？朴素的想法就是“前任Leader留下的烂摊子，如果我不确定是不是可以Commit的，那么我就不能直接Commit它”。回过头来会发现，这个和Raft中新Leader不能直接提交来自较旧Leader的日志一样。

对于MultiPaxos而言，yubai老师的方案其实是类似的，也就是给每个Leader赋一个term，因为MultiPaxos的Leader不进行Propose，所以这个term就可以用proposal number。在补漏洞的过程中，要忽略掉term比自己小的日志。

习题

官方习题

来自于Raft作者的博客。

1

下面哪些日志是可能存在的？

  1. 这个应该是个标准情况，肯定是可以的。
  2. 也是可以的
  3. 也是可以的，Paxos容许日志缺失
  4. 也是可以的

2

在 Basic Paxos 中，考虑在一个5节点的集群中，有三个 acceptor 接受了 proposal(5.1, X) ，在此之后，是否可能有某些机器去 accept 另一个 Value Y 呢？

这个问题并没有挑战，如果在一个时间节点中存在 majority 个节点都 accept 了一个 proposal，是不是可以立刻认为这个 proposal 被 chosen？因为 accept 另一个 Value 的机器只会在小分区中。所以存在这个情况，并不和判定 chosen 的规则矛盾。

注意，这里的proposal number由round_number.server_id这样的方式构成。

答案是可能的。

我们知道，只要一个 acceptor 回复了 Prepare(5.1)，那么他就不可能去 Accept(3.4,Y) 或者 Prepare(3.4,Y) 了。所以如果这个可能发生，那么 Prepare(3.4) 一定要在 Prepare(5.1) 之前。
于是，我们尝试下面的顺序：

  1. P4: Prepare(3.4)
    发送到 S1/S2/S3/S4/S5。
  2. S4/S5/S1 和 S2/S3 发生分区
  3. P1: Prepare(5.1)
    发送到 S4/S5/S1。因为分区，没给 S2/S3。
    因为 5.1 更大，所以 S4/S5/S1 会保证不会再 accept 小于 5.1 的请求。因为目前 S4/S5/S1 没有 accept 任何 proposal，所以返回的“最大的小于 n ”的 proposal 为空。
  4. P2: Accept(5.1,X)
    发送到 S4/S5/S1。因为分区，没给 S2/S3。
  5. P1: Accept(3.4,Y)
    发送到 S2/S3。
    由于分区，所以 S2/S3 没有回复 Prepare(5.1)，更别说 Accept(5.1,X) 了。所以它能够接受请求 Accept(3.4,Y)。

官方答案：

Yes. If it’s S1, S2, and S3 that have accepted <5.1, X>, other servers could still accept Y if it has a stale proposal number.
For example, S4 could prepare 3.4 and discover no values. Then S1 could prepare 5.1 on just S1, S2, S3. Then S1 could
complete accepts on just S1, S2, S3. And S4 can still complete accepts on S4 and S5 with <3.4, Y>.

【Q】不过如果 S2/S3 从分区中恢复后，会将自己的值改成5.1对应的值么？不然是不是不能从这些节点 LocalRead 了？

3

在 MultiPaxos 中，如果一个 Server 刚变成 Leader，并且此时没有其他 Server 是 Leader。进一步地，假设这个 Server 继续是 Leader 一段时间，其中 chosen 了一系列 Entry，并且在这段时间中没有其他 Server 成为 Leader。

  1. 这个 Server 最少需要发送几轮 Prepare？
    我觉得最少只要一轮，在这一轮中大家都 Accept了，并且返回 noMoreAccepted。
  2. 这个 Server 最多需要发送几轮 Prepare？
    这个我没啥 idea，答案说统计 Leader 上面所有满足下面条件的 Entry，那么就需要一条 Prepare
    1. 还没有被 Leader 标记为 chosen；
    2. 曾经被某个 acceptor 接受。
      这个过程通常是这样的，Leader 向该这个 Entry 发送一个 Prepare，然后发现这个 Entry 已经被某个 acceptor 接受了，因此它去促使这个 Entry 最终被 chosen，并且在这之后去尝试去 Prepare 下一个 Entry。这个也对应了不断递增 firstUnchosenIndex，找到合适的可添加 Entry 的 slot 的过程。

4

如果一个 acceptor 通过来自 proposer 的 firstUnchosenIndex 知道了某个 Entry 被 chosen 了，它必须先比较自己 Entry 里面的 proposal number 是不是和这个 proposer 匹配。说明这个比较是不是必要的，并解释。

这个肯定是必要的，原因在“Entry 4为什么不能被标记为chosen”里面解释过了。

5

考虑 proposal number 的两个部分被对调了，即现在变成server_id.round_number，那么：

  1. 是否会影响算法的 Safety
    我觉得是有影响的，每个 proposer 会维护单独的 server_id，那么对于1号机器，它的 proposal number 始终是小于2号机器的，无论它如何自增 id。
    但答案是说没有影响的，因为在 MultiPaxos 中只要求 proposal number 是唯一的，这时候因为 server_id 是唯一的而 round_number 是自增的，所以 proposal number 是唯一的。
  2. 是否会影响算法的 Liveness
    看答案，是会的。例如具有较大 server_id 的 proposer 会发送一个 Prepare 请求给每个 acceptor，然后永远地宕机了。此时其他的 proposer 就无法再行动了，因为 acceptor 上的 minProposal 值对这些 proposer 来说太高了。

6

假定一个 proposer 打算执行 Accept(n,v1)，但在某个时间点宕掉了，如果这个 proposer 重启并且打算执行 Accept(n,v2)，这个是否安全呢？

这个在Paxos made simple中就明确指出是不可以的。

7

在一个成功的Accept请求中，acceptor设置minProposal为n（即Accept请求中的proposal number）。描述一种场景，此时这个行为确实改变了minProposal的值，例如在这之前minProposal并不是n。描述如果没有这个操作，系统会出现问题的一个场景。

8

Consider a configuration change in Multi-Paxos, where the old configuration consists of servers 1, 2, and 3, and the new configuration consists of servers 3, 4, and 5. Suppose that the new configuration has been chosen for entry N in the log, and entries N through N+α (inclusive) have also been chosen. Suppose that at this point the old servers 1 and 2 are shut down because they are not part of the new configuration. Describe a problem that this could cause in the system.

参考

  1. Paxos Made Simple
  2. Paxos Summary
  3. The part-time parliament
  4. https://zhuanlan.zhihu.com/p/278054304
  5. https://www.bilibili.com/video/BV1WW411a77S/?spm_id_from=333.788.videocard.13
  6. http://oceanbase.org.cn/?p=90
    yubai大佬的日志，描述了如何基于Basic Paxos去维护多个Log Entry
  7. http://oceanbase.org.cn/?p=111
    yubai大佬的日志，描述了Multi Paxos
  8. https://ongardie.net/static/raft/userstudy/quizzes.html
    paxos习题
  9. https://ongardie.net/static/raft/userstudy/rubric.pdf
    习题解答