分布式一致性(1):Paxos真的很简单!

Leslie Lamport老爷子说,Paxos很简单,简单的不能再简单🐶 我敢说,简单到全世界搞计算机起码有90%的人都得怀疑自己的智商。

"The Paxos algorithm, when presented in plain English, is very simple."
—— Leslie Lamport

为了让自己保持在自己的10%之内,最近几天又重新来学习一下Paxos。回头来看,Paxos made simple的确很简单地描述了Paxos算法。本文即记录理解此文的一些思考。

Paxos共识算法

共识问题

共识问题就是一组程序需要能够为选择某个值达成共识。首先来说,需要有至少一个提议(proposal),然后各程序通过类似投票的方式进行选举,达成共识后,这个提议的值被称为选中(chosen)。为了保证这个过程是完备的,需要遵循几个安全性要求(safety requirements):

  • 只有被提议的值才可能被选中,也就是说不能平白无故随便选一个值出来
  • 有且仅有一个值会被选中
  • 只有一个值真正被选中之后,程序才能获悉(learn)选中了此值。这个条件稍微有点奇怪,换句话表述就显得自然一些:程序必须要获悉真正被选中的值

FLP不可能原理(FLP Impossibility)已经证明,在异步的网络模型(即无超时边界)下,不存在一种共识算法能够完全满足下面三个条件:

  • 可终止 (Liveness): 所有的节点(只要没有挂掉)最后必须要决定一个值
  • 达成一致 (Safety): 即上述的安全性要求
  • 容错性(Fault Tolerance):当存在节点失败的情况下依然能够奏效

但是如果牺牲掉一些特性(比如3选2)或者使用同步的情况下,是可以实现一致性算法的。Paxos中假定遵循异步、非拜占庭容错(non-Byzantine)的网络模型:

  • 节点可以奔溃、失败、重启,可以以任意的速度响应
  • 消息可以经过任意长的时间投递;可以重复;可以丢失;但不会被篡改(如果是拜占庭容错,那么可以假定节点可能发出一些篡改的消息,例如被恶意攻击)

Paxos中,将参与者区分为提议者(proposers)、接受者(acceptors)、学习者(learners)。简单来说,提议者可以提出待选择的提议;接受者决定选择哪一个提议;学习者能够获悉被选中的值。

一般情况下为了简化这个过程,通常让一个分布式节点即是提议者、又是接受者。学习者不是必须的。

确定选取的提议

Paxos made simple文中,作者通过一步一步从简单到复杂的推理过程,来得出一个最终的算法,让人印象深刻。

从最简单的情况开始。最简单的情况是,只有一个接受者,并且选择接受到的第一个提议。这样肯定可以达成一致,但是一旦这个接受者挂掉,那么就不可能会选取一个值。因此,在分布式共识算法中,需要有多个接受者,只有其中的大多数接受者都选取了一个值,才认为其被选中(chosen)。为了达成“大多数”的情况,节点总数必须为奇数\(n = 2k + 1\)

这种方式下,接受者如果最多只能接受一个值,那么可以形成一个多数派,从而达成共识。考虑到消息可能丢失或者节点失败,节点是无法预测是否会有第二个消息到来,那么假设只有一个提议者,提交了一个提议,这个提议一定需要被接受。否则这种情况下,无法达成共识。这种方式被归纳为:

\(P1\): 接受者必须接受其第一次接收到的提议。 An acceptor must accept the first proposal that it receives.

这种方式存在的问题是,有可能会有多个提议者几乎同时发起了提议,而接受者分别接受到了不同的提议,假定有5个接受者、三个提议:

  • A,B首先接受到1,按照\(P2\)接受了1
  • C,D首先收到2,接受了2
  • E首先收到3,接受了3

这种情况下,提议1、2、3没有一个形成多数派(至少3个接受者接受),因此无法达成一致。即便只有2个提议者1、2,一旦E挂掉,提议1、2也无法达成一致。因此,可以推论出,接受者必须要允许接受多个提议。

为了方便表示,将提议进行编号(以自然数正序),以\(<n, v>\)代表编号为\(n\)的提议值为\(v\)。没一个不同的提议其编号是不一样的(即便是两个提议值相同,也是不同的提议,其编号一定不相同)。在这种方式表示的情况下,一个值\(v\)被选中的条件是,有一个值为\(v\)的提议被多数派接受。

为了满足\(P1\),同时又能够支持接受者多次接受,那么推导出\(P2\):

\(P2\): 如果一个值为v的提议被选中,那么其他被选中的更高序号的提议值必然为v。 If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

这个推论看起来没什么问题,但却困扰了我一段时间:既然v已经选中,又何来再选中之说呢?我们这可是basic paxos阿!选中一个值,不就结束了么?

应该这么来看待:选中首先是要站在事实的角度来看(即以上帝视角来审视),如果超过半数的接受者接受了某个提议,那么它事实上已经被选中。这是从所有接受者的角度来看的,但对于观察者(提议者)而言,是不能保证他们一定能够获悉这个结论的。提议者通过将自己的提议发送给所有的接受者,并从结果中判断是否有超过半数的接受者接受,来判断自己的提议是否被接受。

    比如两个提议者(A,B)分别提议了1,2,acceptor一定只能接受一个,
    比如1被多数接受者接受,那么<1, v1>就被选中了。
    但是假设返回给提议者的消息丢失了,对于提议者A无法确定自己的提议是否被接受;
    从而需要再发起一次投票
    但是此时,B已经获悉自己的提议被接受。
            (Acceptor 1)  (Acceptor 2)  (Acceptor 3)
   ________ ___________  ____________  _______________
   <1, v1>  | accept      | accept      |   reject 
   <2, v2>  |   reject    |   reject    | accept

因为消息可能丢失,或者节点挂掉重启。因此,当这样的情况发生时,观察者需要重新发起提议,向所有的接受者重新发起提议,然后再判断是否选中。

因此,“选中”这个事件,不论是在观察者角度、还是接受者角度,都可能发生多次;只有保证他们全部是一致的,才能满足安全性需求。所以说,即使有多个提议被事实上选中,那么他们的值必然要一致,才能保证对于所有的观察者而言,选中了一个唯一的值。

那么如何才能保证\(P2\)呢?\(P2\)说,如果\(v\)被选中,那么更高编号的提议被选中必然值为\(v\);本来“选中”只需要超过半数的接受者接受即可,但是我们可以用一个更严格的条件来满足它:如果\(v\)被选中,后续所有接受者接受的更高编号的提议必然值为\(v\)。这个约束比\(P2\)更加严格,也能够保证\(v\)被选中,因此得到:

\(P2^{a}\): 如果一个值为\(v\)的提议被选中,那么其他被任意接受者接受的的更高序号的提议值都为\(v\)。 If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

P2a必须跟P1一起才能保证正确,因为\(P2^{a}\)无法适用只有一次提议的场景。而因为是异步模型,可能存在一种场景是,某个接受者接受到的第一次提议,对于其他接受者而言不是第一次了(比如一个接受者挂掉,进行第二轮投票的时候才恢复)。对于其他接受者,可以只接受自己曾经接受过的值;但是对于这个接受者,按照\(P1\),它必需要接受这个提议,无论其值是什么。这样就可能出现与\(P2^{a}\)冲突的情况。解决的办法也很简单,既然值是由提议者决定的,那么我们要求一旦值被选中后,提议者提出的更高序号的提议的值必须为\(v\)

\(P2^{b}\): 如果一个值为v的提议被选中,那么任意提议者提出的任意更高序号的提议值都为v。 If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v

\(P2^{b}\)是比\(P2^{a}\)更严格的条件,因此\(P2^{b}\)可以满足\(P2^{a}\),当然也满足\(P2\)。那么如何做才能满足\(P2^{b}\)这个条件呢?通过数学归纳法,可以证明:假设提议\(<m, v>\)被选中,那么对于任意提议\(<n, v_{n}>(n> m)\)必定有\(v_{n}=v\)

数学归纳法分为两步:

  • 基础步骤:验证\(P(n)\)\(n=1\)时成立
  • 归纳步骤:假设\(P(k)\)为真,证明\(P(k + 1)\)为真

那么,如果应用到上述的条件,可以有:

基础步骤: 为m的时候,\(<m, v>\)被选中是预设的前提,无需证明 归纳假设:假设提议\(m..(n-1)\)的值都为\(v\)。 证明目标:现在要证明对于提议\(n\),其值也为\(v\)

为了完成这一目标,还需要先增加一个提议的条件\(P2^{c}\)

\(P2^{c}\): 对于任意的提议\(<n, v>\)被提出的条件是,存在一个多数派集合\(S\)要么满足(a):这个集合中没有一个接受者接受过任意小于\(n\)的提议(也就是说第一次接受提议);要么满足(b):所有接受者中,其接受的小于\(n\)的最大编号提议的值为\(v\)

因为\(<m, v>\)已经选中,所以一定存在一个多数派\(C\),其中所有的接受者都接受了提议\(m\)。从而推断出:

\(C\)中的所有接受者都接受了一个\(m..(n-1)\)的提议(至少接受了\(m\)),且其中所有提议的值均为\(v\)(从假设可以得出)。

对于任意一个多数派集合\(S\),一定与\(C\)至少有一个交集,因此条件(a)不可能成立;而根据上面的推论,条件(b)是满足的。从而,一个新的提议(\(n\))的值必然也为\(v\)

从而,证明了\(P2^{b}\)

要满足\(P2^{c}\),提议者在提议\(n\)之前,必须要获悉当前小于\(n\)的最高提议的值,为了能够得到确定的结果,要求接受者不能再接受任何小于\(n\)的提议,并得到如下的一个算法:

  1. 提议者准备提交\(n\),首先发送一个准备请求(\(prepare(n)\))给接受者,要求其: = (a) 承诺不再接受任何小于n的提议
      1. 返回其接受的小于\(n\)的最大提议(如果有的话)
  2. 如果提议者从多数接受者获得的提议值为\(v\),那么提议者可以提议\(<n, v>\);或者没有从接受者获悉已经接受的提议,那么提议者可以提议任意的值\(<n, Any>\)。这个过程被称为接受请求(\(accept(n)\))

对于接受者而言,可以响应任意的\(prepare\)请求,而对于\(accept\)请求,必须要保证:

\(P1^{a}\): 接受者当且仅当在没有响应大于\(n\)\(prepare\)请求的时候,才可以接受\(n\)。 An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n

很明显,\(P1^{a}\)是包含\(P1\)的。最后,加入了一个小的优化。如果接受者已经响应了\(prepare\)的请求且大于\(n\),那么接受者无论如何也不会再接受提议\(n\)了,因此不需要响应\(prepare(n)\)\(accept(n)\);同样对于已经接受的提议的\(prepare\)请求也不需要响应。

最终,完整的算法如下:

  • 准备阶段: 提议者向多数派接受者发送\(prepare(n)\)请求。如果接受者收到请求时\(n\)大于其响应过的任意\(prepare\)请求序号,那么它返回给提议者一个不再接受任何小于\(n\)的提议的承诺,以及其已经接受的最大的提议(如果存在的话)
  • 提交阶段:如果从多数派接受者收到的响应

是不是真的很简单?

Ref: