Paxos 算法

2018-06-18

概述

首先定义共识算法解决的问题,我们只考虑单个值(single value)。在分布式环境中,多个进程可以发起提议(propose),每个提议包含一个值,共识算法确保所有值中只有一个值被选中(chosen)。共识算法需要满足以下安全性:

  • 只有被提议的值才有可能被选中,如果没有值被提议,那么就没有值被选中
  • 只能有一个值被选中
  • 只有当值被选中后,其他进程可以学到被选中的值

FLP 证明了异步网络中无法解决共识问题,而 Paxos 只能解决特定环境中非拜占庭模型的共识问题,在这样的环境中:

  • 进程可能会崩溃,可能会重启,但是进程运行时总是正常的,不会发出错误消息
  • 消息可能经过任意长的时间才会到达,有可能冗余,还有可能丢失,但是消息内容总是正确的

Paxos 中主要有三类角色:

  • proposers,负责提议需要被选中的值
  • acceptor,负责决定要选择的值
  • learner,不参与选值的过程,存储被选中后的值

每个进程都可以担任不止一种角色。

推导

最简单的情况是只有一个 acceptor,其他 proposer 向该 acceptor 发起提议,由该 acceptor 选择第一个收到的值:

这样的模型虽然简单,但是却有单点故障的问题:acceptor 可能会在选中值后宕机,那么系统就丢失了选中的值。

所以我们需要有多个 acceptor,每个 acceptor 都可以接受值,并且只有多数派(majority)的 acceptor 都选择了同一个值,才能认为该值被选中(多数派原理)。那么多个 acceptor 如何选择某个值呢?在不考虑消息丢失或者进程失败的情况下,我们希望即使只有一个 proposer 提议了一个值,那么这个值也会被选中。这样的要求表明算法必须满足以下条件:

$P1.$ 一个 acceptor 必须接受它收到的第一个提议

但是如果每个 acceptor 只接受收到的第一个提议,就会出现多个 proposer 同时发起提议,但是没有值被选中的情况,如下:

$S_1$、$S_3$ 和 $S_5$ 同时发起提议,$S_2$ 接受了 $S_1$ 的提议,$S_4$ 接受了 $S_3$ 的提议,但是没有值被选中,而且这样的过程可能会一直重复。这要求 acceptors 必须能多次接受不同的提议。

为了区分不同的提议,我们为每个提议加上一个提议号,使用 $(n, v)$表示一个提议,其中 $n$ 是提议号,$v$ 是值,不同的提议有不同的提议号。如果一个提议被多数派 acceptor 接受,那么我们说该提议(以及提议包含的值)被选中。

既然 acceptors 可以接受不同的提议,那么 acceptors 可以每次都接受收到的提议吗?答案也是不可以,因为这会导致不同的值被选中,违反了安全性。如下图:

$S_1$ 首先发起提议,但是由于延迟,其他进程还没有收到消息;这时 $S_5$ 发起了另一个提议,然后 $S_3$ 和 $S_4$ 接受了 $S_5$ 的值;但是稍后 $S_1$ 的提议到达了 $S_3$,这时 $S_3$ 也接受了这个值,这样就导致了不同的值被选中。

这说明提议号应该是全局有序的,新提议的提议号大于旧提议的提议号,并且 acceptor 要拒绝旧提议。另外共识算法的安全性要求只能有一个值被选中,同时我们现在又允许可以有多个提议被选中,那么我们需要保证所有被选中的提议都包含同样的值,即以下条件必须满足:

$P2.$ 如果提议 $(n, v)$ 被选中,那么后面任何被选中的提议 $(m, u), m \ge n$ 都满足 $u = v$

因为提议号是全局有序的,那么条件 $P2$ 保证了共识算法的安全性。如果一个提议要被选中,那么至少有一个 acceptor 接受了该提议。所以,我们可以通过满足下面的条件满足 $P2$:

$P2^a.$ 如果提议 $(n, v)$ 被选中,那么后面被任何 acceptor 接受的提议 $(m, u), m \ge n$ 都满足 $u = v$

但是仅有 $P2^a$ 无法满足系统约束。我们需要 $P1$ 确保总是有提议被选中,这是因为系统的通信模型是异步的,即使某些 acceptor 没有接受任何提议,依然可以有提议被选中。那么假设一个新的 proposer “突然醒来”,发起了一个更大提议号的提议,并且值不同与当前被选中的值,$P1$ 要求 acceptor 接受这个请求,这样就违反了 $P2^a$,如下图:

$S_1$ 提议的值被选中,但是后续 $S_5$ 提议不同的值也被选中。所以要维持 $P1$ 和 $P2^a$,我们需要将 $P2^a$ 加强为:

$P2^b.$ 如果提议 $(n, v)$ 被选中,那么后面任何 proposer 发起的提议 $(m, u), m \ge n$ 都满足 $u = v$

可以通过归纳法证明 $P2^b$ 成立。$P2^b$ 等价于:

$P2^c.$ 对于一个提议 $(n, v)$ 和任意一个包含了多数派的 acceptor 集合 $S$,只有可能存在两种情况:(a) $S$ 中的所有 acceptor 都没有接受任何小于 n 的提议,或者(b)存在提议 $(m,u)$,其中 $m$ 是 $S$ 中所有 acceptor 接受提议的最大提议号,并且 $m < n$,那么有 $u = v$。

简单地说就是对于一个新的提议 $(n, v)$,要么没有值被选中,要么 $v$ 就是已经被选中的值。

所以当 proposer 要发起提议时,首先需要了解是否存在已经被多数派 acceptor 选中的提议。如果存在,那么就不能提议新的值;但是难点在于如果不存在值被选中时,新提议的值不会与将要被选中的值冲突。Paxos 通过引入额外的约束保证这样的冲突不存在:当 proposer 发起了一个提议 $(n,v)$,要求 acceptor 不再接受小于 $n$ 的提议。

算法描述

Paxos 分为两个阶段:

Prepare 阶段

  1. proposer 选择一个提议号 $n$,然后向每个 acceptor 发送 $prepare(n)$ 请求
  2. acceptor 收到 $prepare(n)$ 后,如果 $n$ 大于其他的 $prepare$ 请求,那么 acceptor 回复保证不再接受任何小于 $n$ 的提议

Accept 阶段

如果 proposer 收到多数派 acceptor 的保证后,就可以进入 accept 阶段:

  1. proposer 使用提议 $(n,v)$ 向所有 acceptor 发出 $accept(n,v)$ 请求,其中 $v$ 是 prepare 阶段 acceptor 回复中最高提议号对应的值;如果没有提议被接受,那么 $v$ 可以是任意值
  2. acceptor 收到 $accept(n,v)$ 后,并且没有收到更大提议号的 prepare 请求,那么就接受这次提议

算法优化

伪代码描述

这一节使用伪代码描述 Paxos 算法。

每个进程需要持久存储以下变量:

  1. $\mathcal {minProposal}$:进程会接受提议的最小提议号,初始值为 0
  2. $\mathcal {acceptedProposal}$:进程最近一次接受提议的提议号,初始值为 0
  3. $\mathcal {acceptedValue}$:进程最近一次接受提议的值,初始值为 null

流程描述:

      Proposer                          |        Acceptor 
1. choose a new proposal number n       |
2. for acceptor in acceptors:           |
       acceptor.send(prepare(n))        |
                                       -->
                                        | 3. on receiving prepare(n);
                                        |     if n > minProposal:
                                        |        minProposal = n
                                        |     if acceptedProposal != nil:
                                        |        return (acceptedProposal, 
                                        |                acceptedValue)
                                        |     else:
                                        |        return (nil, nil)
                                       <--         
4. receiving from majority of acceptors:| 
       if any acceptedValue returned,   |
       replace v with acceptedValue     |
       for highest acceptedProposal     | 
       for acceptor in acceptors.       |
           acceptor.send(accept(n,v))   |
                                       -->                                                    
                                        | 5. on receiving accept(n, value):
                                        |     if n >= minProposal: 
                                        |        acceptedProposal = n
                                        |        minProposal = n 
                                        |        acceptedValue = value
                                        |     return minProposal
                                       <--
6. receiving from majority of acceptors:|
       if minProposal > n:              |
          goto 1                        |
       else:                            |
          success                       |

参考

  1. Paxos made simple
  2. Paxos user study