Paxos算法

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

Basic Paxos

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

P2b

注意,我们仍然需要满足要求P1,这样我们可以保证我们一定能接受一些proposal。
考虑下面的情况:

  1. 一个新的proposer提交了一个更高的number的proposal,但是具有不同的Value;
  2. 一个之前从来没有收到过任何proposal的acceptor收到了这个proposal;
  3. 根据要求P1,这个acceptor需要accept这个proposal;
  4. 根据要求P2a,这个acceptor不能accept这个proposal;

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

论证2

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

P2c

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

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

对于任意包含大多数acceptor的集合S必须包含C中的至少一个成员,因此我们可以得出我们需要满足下面的要求P2c。

考虑一个proposer发出了proposal(v,n),那么存在一个上述S,满足要求P2c:

  1. 要么S中的成员都没有accept过低于n的proposal;
  2. 要么accept的最大的小于n的proposal的Value是v

论证3

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

为了简化这个预测的流程,我们引入了一个提前的阶段,也就是proposer要求acceptor保证不会再去accept任何低于n的proposal了。

为此,我们得到下面的算法。

Proposer 算法 Step1

proposer选择一个新的number n,发送请求Prepare(n)给某个集合中的所有acceptor。此时acceptor应该返回:

  1. 保证不再接受小于n的proposal;
  2. 目前最大的小于n的accept的proposal。

Proposer 算法 Step2

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

  1. 如果没有人对v的值有proposal,那么这个proposer就可以任选v的值。这实际上对应了通常情况。
  2. 否则,就返回最大的小于n的proposal给出的v值。

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

Acceptor 算法 P1a

一个acceptor可以安全地忽略任何的请求。

acceptor可以回应Prepare请求。

acceptor可以回应accept请求,去accept某个proposal,当且仅当它没有保证不接受这个请求,即:
当且仅当一个acceptor没有回应大于n的Prepare请求,它可以接受一个n编号的accept请求。可以看出,P1是P1a的特例。

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

  1. 可以accept编号是n+1的accept请求;
  2. 不能accept编号是n的accept请求;
  3. 能不能promise编号是n的Prepare请求?
    文章中指出,没有理由去回应这样的请求。因为根据上一点,连编号为n的accept请求都不会被响应了,更何况Prepare请求呢?
    同理,如果一个请求已经被accept了,那么我们也不会再去回应对应的Prepare请求了。
    当然,这些只是优化点而已。

持久化要求

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

  1. 自己accept的最大的proposal number;
  2. 自己回复的最大的Prepare请求的number。

此外,一个proposer可以忘记或者放弃自己的proposal,只要它不会具有相同number的另一个请求。

算法

Phase 1

  1. Proposer
    选择n,发送Prepare(n)到majority个acceptor上。
  2. Acceptor
    对于Prepare(n),如果n高于已经响应过的其他Prepare请求,则:
    1. promise不会在accept任何小于n的请求;
    2. 发送最大的小于n的accept的proposal。

Phase 2

  1. Proposer
    如果收到了majority的acceptor对自己Prepare(n)的响应,则发送Accept(n,v)请求给所有这些acceptor。这里的v的选择参见Proposer 算法 Step2一节。
  2. Acceptor
    除非自己已经回复了Prepare(n+1)或者更高的,否则acceptor需要accept请求Accept(n,v)

Learner

容易发现,因为没有Leader,所以从单一的acceptor角度,并不能很方便地去发现某个proposal是否已经被chosen了。
一个平凡的方法就是每进行一次accept,就告知learner一次,不过这样的方法有很大的通信开销。考虑到learner也不会出现拜占庭错误,所以learner间可以相互通信以得到被accept的值,因此可以让每个acceptor只响应某一些learner。如果考虑到这一些learner可能失败,导致丢失acceptor信息,问题还会更复杂。此时,一个值被chosen了,但是没有learner发现。虽然learner可以再逐个询问acceptor,但只要有一个acceptor宕掉,就可能导致learner无法了解某个proposal是否得到多数同意。在这种情况下,只有当一个新的proposal被chosen的时候,learner才会再次发现。

对此,可以提出一个问题,对于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的作用。

实现

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,也就是可能变票。
接着,Ongaro提出一种实现Proposal Number的方案,也就是高位的Round Number和低位的Server ID。这些Round Number需要被持久化到磁盘上,以保证proposal number不会被重复使用。

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

需要注意的是,只有提出某个proposal的proposer才能知道是否已经被chosen;对于其他的proposer,必须用自己的proposal执行一遍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

如下图所示,当P 4.5到来时,值X已经被chosen了。

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

我们注意S3上的A 3.1 X请求已经被Accept了,所以当S5发出P 4.5后,它会知道值已经被Accept为X了,所以它不再坚持自己要Accept的值Y,而是转而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. 客户端协议以及状态机相关。

维护一个Log

首先我们考察,当一个proposer准备新增一个entry到log时,如下图所示,当client发送一个jmp给S1时,S1选择哪一个entry呢?这可能涉及一下的情况:

  1. 在Entry1和2中,mov和add被复制到了所有机器上,并且S1已经知道被chosen了。如下图所示,用粗框子框出来了。
  2. 在Entry3中,cmp实际上已经被chosen了,但是S1并不知道。这个可能是因为S3被分区了。

下面我们就考虑S3被分区的情况:

  1. 找到第一个没有被S1知道已经chosen的entry,即firstUnchosenIndex。也就是Entry3。
  2. 根据Basic Paxos算法,对这个entry去propose一个Value为jmp的proposal。显然,这个Value是不能被accept的,因为已经有一个Acceptor接受了cmp这个值了。所以这一个Basic Paxos Instance跑完,实际上会导致cmp在Entry3中被chosen。
  3. 接着,我们回到第1步,检查下一个尚未被发现已经chosen的entry,即Entry4,并尝试propose。显然,这次jmp还是不能被accept,因为sub已经被S2上的acceptor接受了。

通过这种方式,Server可以并发处理多条来自client的请求。演讲者提到,例如第一个请求用到了Entry3,那么下一个请求可能会尝试Entry4或者Entry5等等。在这一点上我还有点疑惑,就是我们能保证client的请求在Paxos log层面是in order的么?

但是最后这些命令需要按照log中的顺序来放到复制自动机中执行。

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

下面我们对这两点目的进行改进:

  1. 阻止具有旧的number的proposal
    我们可以让proposal number和整个log关联,而不是和某个entry关联。
  2. 发现可能存在的已经被chosen的Entry
    acceptor不仅要返回对于当前entry的最大的proposal number,还需要检查所有当前entry之后的所有entry,如果其中没有任何proposal被accept,那么就返回noMoreAccepted

如果一个acceptor返回了noMoreAccepted,那么后续就不再发送Prepare请求,直到某个Accept请求被拒绝。
如果一个Leader从多数的acceptor处都收到了noMoreAccepted,它就不再需要发送Prepare请求了。这个状态可能会被另一个当选的Leader打破,此时旧Leader会收到被拒绝的Accept请求。

Fully Replication

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

  1. 保证Entry最终在所有的机器上被复制,但目前我们只保证了majority。
  2. 保证所有的Server都能知道某个Entry是否被chosen,目前只有对应的proposer知道。

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

  1. Proposer需要不断地重复Accept请求(可以在后台完成),直到所有的acceptor都回复
    但这个策略是不充分的,原因是考虑当Proposer宕掉时,他未必能够将所有的Entry都进行复制。
  2. 跟踪所有被chosen的Entry
    每个Server对所有已经被chosen的Entry设置acceptedProposal[i]=INF,INF也是能够无缝适配协议的,因为不可能存在一个更大的proposal number了。
    每个Server维护一个firstUnchosenIndex(已经在前面介绍过了)。
  3. Proposer将自己的firstUnchosenIndex附加在Accept请求中发送
    这样,一个Accept请求会类似下面

    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

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

      现在,来自Leader Proposer的一个Accept请求告知firstUnchosenIndex=7,这也就意味着在这个Proposer上,Entry 1到6都被chosen了。此时,我们就可以将Entry 6标记为chosen。

      然后我们有几个疑问:

    • Entry 6为什么可以被标记为chosen?
      这是因为首先这个acceptor知道Entry 6也是来自于发送这个Accept的Proposer,并且它在这个Proposer上已经被chosen了。
      但这还不够,有没有可能这个Proposer后面发送了关于Entry 6的具有另外一个值的Accept请求呢?我想这样的话,proposal number一定会变得更大。但既然在3.4的时候,我们就知道Entry 6已经被chosen了,那么被chosen的这个值一定就是acceptor日志里面的这个值。
    • Entry 4为什么不能被标记为chosen?
      因为Entry 4的值来自于另外Round的另外一个Proposer,因此我们没办法像Entry 6一样确定这个不是一个陈旧的数据。也就是说,这个accpetor知道Entry 4被chosen了,但是并不知道这个被chosen的Value是不是自己Log里面的那个Value。因为很可能这个值又被改了。
    • 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

Leader缺少日志问题

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设置的。

配置切换

习题

官方习题

来自于Raft作者的博客。

1

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

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

2

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

这个问题并没有在问,如果在一个时间节点中存在majority都接受了一个proposal,是不是可以立刻认为这个proposal被chosen?因为accept另一个Value的机器只会在小分区中。

注意,这里的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
    因为5.1更大,所以S4/S5/S1会保证不会再accept小于5.1的请求。因为目前S4/S5/S1没有accept任何proposal,所以返回的“最大的小于n”的proposal为空。
  4. P2: Accept(5.1,X)
    发送到S4/S5/S1
  5. P1: Accept(3.4,Y)
    发送到S2/S3
    由于分区,所以S2/S3没有回复Prepare(5.1),更别说Accept(5.1,X)了。所以它能够接受请求Accept(3.4,Y)

不过如果S2/S3从分区中恢复后,会将自己的值改成5.1对应的值么?

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的slote的过程。

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设置minProposaln(即Accept请求中的proposal number)。描述一种场景,此时这个行为确实改变了minProposal的值,例如在这之前minProposal并不是n。描述如果没有这个操作,系统会出现问题的一个场景。

参考

  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