Paxos分布式一致性算法

本节内容:Paxos算法是莱斯利·兰伯特(英语:Leslie Lamport,LaTeX中的“La”)于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。

基本模型

环境假设

异步(执行时间和消息传递时间不确定)的没有拜占庭式错误(即:消息可能重复传输或丢失,但不会被篡改)。

基本问题

在分布式系统中经常会发生机器宕机以及网络异常,需要快速正确的在集群内部实现对某个数据的值达成一致,并且保证上述异常不会破坏整个系统的一致性。

一致性问题是分布式系统中的经典问题。

一致性基本要求

  • 在这些被提出的提案中,只有一个会被选中
  • 如果没有提案被提出,那么就不会有被选定的提案
  • 当一个提案被选定后,进程可以获取被选定的提案的信息。

同时,基于安全性考虑,一致性需要满足:

  • 只有被提出的提案才能被选定
  • 只能有一个值被选定
  • 如果某个进程认为某个提案被选定了,那么这个提案必须是真的被选定的那个。

基本假设

在Paxos一致性算法中,有三种参与角色:Proposer(提案提出者)、Acceptor(提案批准者)、Learner(提案学习者),另外为了防止死锁问题,可以引入一个主Proposer:Leader,规定只有主Proposer才可以提出提案,提案编号$M_n$,提案内容为$v_n$。

假设参与者充当上述角色,那么基本假设如下:

  • 参与者: 每个参与者可以以任意的速度执行,可能会因为出错而停止,也可能会重启, 同时,即使一个提案被选定后,所有的参与者也可能失败或重启,因此除非那些失败或重启的参与者可以记录某些信息,否则将无法确定最终的值。
  • 消息:消息在传输的过程中可能会出现不可预知的延迟,也有可能会重复或丢失,但是消息不会被篡改。

具体算法

提案批准

Paxos协议流程划分为两个阶段,第一阶段是准备阶段,Proposer学习提案最新的状态;第二阶段是提交阶段,根据学习到的状态组成正确提案,完整的协议过程如下:

  • Prepare阶段

    • 选择一个提案编号$M_n$,并向半数以上的Acceptor发送编号为$M_n$的Prepare请求;
    • 如果一个Acceptor收到一个编号为$M_n$的Prepare请求,并且$M_n$大于它已经响应的所有Prepare请求的编号,那么它就会保证不会再批准(Accept)任何编号小于$M_n$的提案,同时将它已经通过的最大编号的提案(如果存在的话)作为响应。
  • Accept阶段

    • 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求(编号为$M_n$)的响应,那么它就会发送一个针对编号为$M_n$,value值为$v_n$的提案的Accept请求给Acceptor,在这里$v_n$是收到的响应中编号最大的提案的值,如果响应中不包含提案,那么它可以是任意值;
      • 如果Acceptor收到一个针对编号$v_n$的提案的Accept请求,只要它还未对编号大于$v_n$的Prepare请求作出响应,它就可以通过这个提案。

提案学习

为了减少通信开销以及防止单点故障问题,将主Learner的范围扩大,Acceptor可以将已经批准的提案发送给一个指定的Learner的集合,该集合中的每一个Learner都可以在一个提案被通过后通知其他的Learner。

活锁问题

如果两个Proposer依次交叉提出一系列编号递增的提案,但是最终都没有被选定通过,则会陷入死循环状态。因此必须选择一个主Proposer,只有主Proposer才能提出提案,即选举出一个Proposer作为Leader,所有的Proposal都通过Leader来提交,当Leader宕机时马上再选举其他的Leader。

推导过程

分析:

  • 单个Acceptor: 所有的Proposal都发给这个Acceptor,它接受最先收到的Proposal,若这个Acceptor发生故障,则整个系统都将无法工作,因此不可取(单点问题)。

  • 多个Acceptor: 可以解决单点问题, 某个Acceptor故障不会影响到提案批准,如果超半数的Acceptor批准某个具有编号$M_n$的值$v_n$,则该值被选择。

Acceptor只能Accept一个Proposal. 并为了保证当只有一个value的情况下也会被choose,在没有失败和消息丢失的情况下,可将上述多个Acceptor加强为:

P1:Acceptor必须批准它接收到的第一个决议。

上面这个要求导致如下问题:如果多个提案被不同的Proposer同时提出,这可能导致每个Acceptor都批准了它收到的第一个提案,但没有一个提案是由多数人选择批准的;或者即使只有两个提案被提出,每个提案都差不多被一半的Acceptor批准,此时当一个Acceptor出错,都导致无法选择任意一个提案。

因此,在P1的基础上,需要避免多个value被选择批准,即允许多个提案被选定,但必须保证所有被选定的提案都有相同的值value,引出如下定义:

P2: 如果一个提案{n, v}被选择,那么所有被选择的提案(编号更高)包含的决议都是v。

得到P2后关键是如何保持P2成立,需要进一步的具体和细化。

因为提案的编号是全序的,条件P2保证了只有一个value值被选定,同时一个提案被选定,首先必须被至少一个Acceptor批准,因而可以通过如下条件满足P2:

$P2^a$: 如果一个提案{n, v}被选择,那么任何acceptor批准的提案(编号更高)包含的决议都是v。

同时,我们仍然需要P1来保证提案被选定,同时因为通信是异步的,一个提案可能会在某个Acceptor还没有收到任何提案时就被选定了,因此,如果要同时满足P1和$P2^a$,需要对$P2^a$进行如下强化:

$P2^b$:如果一个提案{n, v}被选择,那么此后,任何proposer提出的提案(编号更高)包含的决议都是v。

因为一个提案必须在被Proposer提出后才能被Acceptor批准,因此$P2^b$包含了$P2^a$,进而包含了$P2$, 于是,下一步就是证明$P2^b$成立。为此,我们使用第二是数学归纳法证明如下结论:

假设编号为M0到Mn的提案已经被选定,其值都是v,证明编号为Mn的提案的值也为v。

因为编号为M0的提案已经被选定了,这就意味着肯定存在一个由半数以上的Acceptor组成的集合C,C中的每个Acceptor都批准了这个提案,由归纳假设知,“编号为M0的提案被选定”意味着:C中的每一个Acceptor都批准了一个编号在M0到Mn-1范围内的提案,并且每个编号在M0到Mn-1范围内的被批准的提案,它的值也是v。

因为任何包含半数以上的Acceptor的集合都至少包含C中的一个成员,因此如果一下$P2^c$保持不变,那么编号为Mn的提案的值也为v:

$P2^c$: 对于任意的v和n,如果提案{n, v}被提出,那么存在一个由acceptor的多数派组成的集合S,满足如下两个条件中的任意一个

  • S中没有acceptor批准过编号小于n的提案
  • 在S的任何acceptor批准的所有提案(编号小于n)中,v是编号最大的提案的决议。}

$P2^c$包含$P2^b$是显而易见的,因此,如果能保证$P2^c$,就满足了$P2^b$。

为了保持$P2^c$的不变性,准备提出议案(编号为Mn)的Proposer必须知道所有编号小于Mn的议案中编号最大的那个,如果存在的话,它已经或将要被Acceptor的某个多数派批准。获取已经批准的议案是简单的,但是预知将来可能批准的议案是困难的。Proposer并不做预测,而是假定不会有这样的情况。也就是说,Proposer要求Acceptor不能批准任何编号小于Mn的议案。这引出了下面提出议案的两阶段算法:

  • 第一步:准备阶段: Proposer选择一个新编号Mn,向某个Acceptor集合中的所有成员发送请求,并要求Acceptor集合回应:
    • 向Proposer承诺永不批准编号小于Mn的议案
    • 如果Acceptor已经批准过任何提案,那么其就向Acceptor反馈当前已经批准的编号小于Mn的编号最大的议案。
  • 第二步:接收请求: 如果Proposer收到了多数Acceptor的回应,那么它就可以提出议案{Mn, v},其中v是所有回应中编号最高的议案的决议,或者是如果Acceptor回应说还没有批准过议案,Proposer则回应任意值。

在确定提案后,Proposer就会将该提案再次发送给某个Acceptor集合,并期望获得它们的批准,我们称此请求为Accept请求。

对于Acceptor,其批准提案如下:

一个Acceptor可能会收到来自Proposer的两种请求,分别是Prepare和Accept,对这两类请求做出的响应条件分别如下:

  • Prepare: Acceptor可以在任何时候响应一个Prepare请求
  • Accept: 在不违背Accept现有承诺的前提下,可以任意响应Accept请求

因此,对于Acceptor处理的约束条件为:

$P1^a$: acceptor可以批准一个编号为n的提案,当且仅当它没有回应过一个编号大于n的prepare请求。

主要贡献与存在问题

贡献

Paxos算法解决的问题是在一个可能发生异常(进程可能会慢、被杀死或者重启,消息可能会延迟、丢失、重复,不考虑消息篡改即拜占庭错误的情况)的分布式系统中如何就某个值达成一致,保证不论发生以上任何异常,都不会破坏决议的一致性。

Paxos协议提出只要系统中2f+1个节点中的f+1个节点可用,那么系统整体就可用并且能保证数据的强一致性,它对于可用性的提升是极大的。

Paxos算法是分布式计算领域的一个开创性算法,后面有很多算法都是在其基础上改进演化的。

存在问题

  • 如何保证全局编号问题

在分布式环境下, 编号无法直接确定, 只能根据自身知道的最大number先提一个Proposal, 如果被拒绝, 那么拒绝的Acceptor应该通知他知道的最大的number是多少.

  • 活锁问题

如前文所述,需要Proposer Leader,而这个问题又引入Leader选举问题,存在称之为PaxosLease的Paxos算法简化版可以完成leader的选举.

  • 持久存储问题 在算法执行的过程中会产生很多的异常情况, 各种角色都可能失败,为了保证paxos算法的正确性,需要各个节点都做持久存储,以便重启后还能恢复,典型的有:
    • Proposer存储已提交的最大Proposal编号
    • Learner存储已学习过的Proposal被Accepted情况