基础Paxos算法

1. 概述

    大家在讨论分布式系统的时候,一个经常要碰到的问题就是分布式系统里的一致性问题,也就是CAP理论中的C (Consistency)。让网络中各个节点达成一致性的一种方法,就是上一遍博客中提到的状态机复制 (State Machine Replication),状态机复制的基础协议就是所谓的共识协议,而Paxos算法,就是为了让多个节点达成共识而发明出来的算法。
    虽然我们经常说Paxos算法,但是严格说来,Paxos是一整个协议族,里面包含:基础Paxos,Multi-Paxos,Fast Paxos和Egalitarian Paxos。而我们今天要讨论的,就是其中的基本Paxos(Basic Paxos)算法。

2. 基础Paxos算法特性

    基础Paxos算法具有以下特性:

  1. 最后达成共识的值只能从被提议的候选值中产生;
  2. 仲裁节点(Quorum)一旦就某个值达成共识,后面就不能就另外的值达成共识;
  3. 仲裁节点(quorum)一旦就某个值达成共识,那么最终所有的节点都将学习到这个值;
  4. 算法保证了安全性,但是理论上并不能保证活性;
  5. 算法能在不可靠的消息传输协议下(消息可以被丢失,重传,乱序)正常工作,但是消息要保证正确和完整;
  6. 如果有2N+1个节点参与算法,那么算法可以在N个节点失效的情况下依旧保证正常工作;

3. 基础Paxos算法流程

3.1 算法目的

    基础Paxos算法要解决的问题是:如果有2N+1个节点都有一个寄存器文件,并且针对这个寄存器文件提交了m个候选值,那么这2N+1个节点需要最终决定这个寄存器文件需要写入哪一个候选值,并且一旦至少N+1个节点对这个决定达成了共识,那么此决定将不可再更改。

3.2 前提假设

  1. 系统不存在拜占庭将军问题,即所有的节点不存在欺骗,消息在传输过程中要保证内容的正确和完整;
  2. 任意一个节点都可以发送消息到另外一个节点;
  3. 任何一个节点都可能失效;
  4. 网络协议本身并不可靠。

3.3 角色

    基础Paxos算法定义了如下角色:

  1. 客户端(Client):向分布式集群系统发起请求(对值作出提议),并且等待集群系统的响应结果;
  2. 提议者(Proposer):也可以叫做协调者(coordinator),提议者负责接受客户端发起的提议,然后尝试让接受者接受该提议,同时保证即使多个提议者的提议之间产生了冲突,那么算法都能进行下去;
  3. 接受者(Acceptor):也可以叫做投票员(voter),负责对提议者的提议投票,同时需要记住自己的投票历史;
  4. 学习者(Learner):如果有超过半数接受者就某个提议达成了共识,那么学习者就需要接受这个提议,并就该提议作出运算,然后将运算结果返回给客户端。

    这里给出的角色定义是算法层面的逻辑定义。在实际应用中,往往一个系统具有一个或者多个角色的功能。下图给出了各个角色的逻辑关系图:
角色关系图
注1:图中给出的示例有两个客户同时提交了请求,但是基础Paxos算法保证只有其中一个客户端的请求会被共识系统接受,而另一个客户端的请求将会被拒绝。

3.4 算法流程

    基础Paxos算法的核心思想是:多轮选举;超半数节点响应;响应结果传递。

    在基础Paxos算法中,任何一个Proposer都能发起新一轮的选举,即使上一轮的选举还没有完成。而且一旦Acceptor收到了新一轮选举的消息,那么它就要拒绝所有之前选举的消息。为了实现这个目的,Proposer在开始新一轮选举的时候都要给这轮选举付一个全局唯一的ID(Pro poseNum),而且此ID必须比之前所有进行过的选举的ID都要大。那么问题来了,要让所有的节点都能生成一个全局唯一ID,这本身就是一个共识问题,就变成了用一个共识问题去解决另一个共识问题。怎么办?一个比较简单的方法就是使用分布式ID生成算法:我们让Proposer所在的节点都有一个唯一的Server ID,然后每一个节点都维持一个本地的最大选举轮数计数器maxLocalRound,当我们需要ProposeNum的时候,我们可以通过如下算法生成它:

1
2
localRoundNum = ++maxLocalRound
ProposeNum = (localRoundNum << (bits of serverID)) | serverID

    我们可以重复执行以上算法直到ProposeNum大于当前正在进行的选举的ProposeNum。

    每一轮的选举都分为两个阶段:

  • 阶段一(Phase 1):准备/承诺 (Prepare/Promise)

        目的
        1. 停止所有之前还没有完成的选举;
        2. 尝试发现是否已经有提议被接受。

        流程
        Prepare(Phase 1a): proposer生成一个比它之间见到过的ProposeNum都要大的新ProposeNum,然后把这个新的ProposeNum通过prepare消息发送给所有的acceptor。
        Promise(Phase 1b): acceptor内部维护着一个变量minProposeNum,当acceptor收到了一个prepare消息,并且消息包含的ProposeNum > minProposeNum, 则让minProposeNum = ProposeNum,并向proposer返回包含minProposeNum和<acceptedProposeNum, acceptedValue>的确认消息(如果acceptor在之前没有接受过任何proposal,则acdeptedProposeNum/acceptedValue可以设置为null)。然后,acceptor对于后面收到的任何消息,只要消息里的ProposeNum <= minProposeNum, 则将返回reject或者忽略。

  • 阶段二(Phase 2):接受请求/请求被接受(Accepting/Accpeted)

        目的
        1. 让acceptor接受某个提议。

        流程
        Accepting(Phase 2a): 当proposer在Phase 1b里收到了超过半数acceptor返回的确认消息,它将扫描所有返回的<acceptedProposeNum, acceptedValue>, 如果所有的acceptedValue都为null,则proposer可以自行决定接下来将要发送的value,否则,它必须将最大的acceptedProposeNum对应的acceptedValue作为接下来将要发送的value的值。然后proposer将向所有的acceptors发送附带有<ProposeNum, value>的accepting消息;
        Accepted(Phase 2b): 当acceptor收到了带有<ProposeNum, value>的accepting消息后,如果ProposeNum < minProposeNum, 则返回reject消息或者忽略,否则,设置minProposeNum = acceptedProposeNum = ProposeNum, accptedValue = value. 然后向proposer和learner发送附带有minProposeNum的accepted消息。

当learner收到了超过半数acceptor针对于某个ProposeNum的accepted消息后,认为共识已经达成,它可以开始执行提议并向client返回最终结果。

4. 使用场景

     Paxos算法可以使用到一下场景里面:

  1. Leader选举,proposer把server id作为提议运行paxos算法,最后就哪个server id达成了共识,对应的server就能成为leader;
  2. 分布式锁,请求分布式锁的client把自己的client id作为提议发送给proposer运行paxos算法,最后就哪个server id达成了共识,对应的client就能获得分布式锁。
  3. 就状态机复制中节点replication log中的log entry达成一致。

5. 活锁

基础Paxos算法存在活锁的场景,如下图所示:
基础Paxos活锁

6. 注意事项

  1. 基础Paxos是一个Leaderless算法,也就是说,它的运行不依赖于系统选举出一个leader (基础Paxos本身就可以拿来做leader选举);
  2. 虽然对于整个系统来说,一旦系统就某个提议达成共识,那么这个提议就是最终结果并且不能再改变,但是对于每一个acceptor来说,它们能在不同的选举轮中接受不同的值;
  3. Acceptor只负责投票和记录投票历史,它并不实际执行达成共识的提议,实际的执行操作是由learner来完成,其实我本人不是很赞成使用接受者(Acceptor)这个名词,因为给人的第一感觉就好像一旦接受了就可以开始执行提议了,但实际上它仅仅起到一个投票的作用,所以我觉得叫voter更好一些。