paxos协议

前边微服务框架选择中,反复看到一致性的协议,这一阶段就来对这些一些进行研究,包括:Paxos协议、Raft协议、Gossip协议,本文是这一系列第一篇:Paxos协议

1. 概述

网上关于Paxos协议的介绍有很多,概览一番之后,觉得参差不齐、深浅不一,有些还相互矛盾,不看原论文估计是不行了,本文是Lamport2001年的Paxos Made Simple论文的摘要以及一点思考。

作者
本节是写raft时发现把作者的图片贴出来以表尊敬。
Leslie_Lamport

2. 背景

一致性要求

  • 一个值只有被提出来之后才可能被选中
  • 只有一个值被选中
  • 只有当一个值被选中后,process才能learn它

基本概念

Paxos的基本术语是Proposql,proposal = proposql Number(提议编号) + proposql value(提议值)

根据角色不同,分成3种agent:

  • proposers:提议发起者
  • acceptors:提议接收者
  • learners :提议学习者

一个进程可以扮演多个agent

通信模型

使用异步、非拜占庭模型:

  • agents 以随意的速度运行,它可能宕机、重启。

    由于在一个值被选中后,任意一个agents都可能宕机、重启,一个solution只有在某些信息被agent记住才可能有效 ;

  • 消息传输可能不稳定、重复、丢失,但不会冲突

3. 协议详情

协议过程

简单来说,Proposor发起提案,向acceptor审批所用proposal number,超过半数acceptor通过后,proposor再将proposal value写进提案,与proposal number一起提交给acceptor。这样就分成了2个阶段,准备阶段(Prepare)与提交阶段(Accept)。

下边来详细看看整个过程。

  • P1

    image-20220921170233789

    • A阶段

      Proposer选择一个提议编号n,向所有的Acceptor广播Prepare(n)请求。

    • B阶段

      Acceptor接收到Prepare(n)请求,若提议编号n比之前接收的Prepare请求都要大,则承诺将不会接收提议编号比n小的提议,并且带上之前Accept的提议中编号小于n的最大的提议(包括n、v),否则不予理会。

  • P2

image-20220921170430468

  • A阶段

    如果未超过半数accpetor响应,直接转为提议失败;

    如果超过多数Acceptor的承诺,又分为不同情况:

    • 如果所有Acceptor都未接收过值(都为null),那么向所有的Acceptor发起自己的值和提议编号n;
    • 如果有部分Acceptor接收过值,那么从所有接受过的值中选择对应的提议编号最大的作为提议的值,提议编号仍然为n。但此时Proposer就不能提议自己的值,只能信任Acceptor通过的值,维护一但获得确定性取值就不能更改原则;
  • B阶段

    Acceptor接收到提议后,如果该提议版本号不等于自身保存记录的版本号(第一阶段记录的),不接受该请求,相等则写入本地。

协议推论

  • P1: acceptor必须接收它收到的第一份议案
    => 当多个proposer同时提出自己的提案时,各acceptor各自接收自己value,而达不到多数胜出
    => 为了区分这些同时提出的议案,自然就需要对它们进行编号,这样一个议案就包括2个属性:编号number与值value
    => 当有多数acceptor接收一个议案时,这个议案才能被选中

  • P2: 如果值为v的议案被选中,那么所有被选中的更高编号的议案值都是v
    允许多个议案被选中,但必须保证所有被选中的议案有相同的number。

  • P2a: 如果值为v的议案被选中,那么所有被acceptor接收的更高编号的议案值都是v

  • P2b: 如果值为v的议案被选中,那么所有被proposer提出的更高编号的议案值都是v

  • P2c: 对于任意 v与n,如果一个值为v、编号为n的议案被提出,那么有一个由多数acceptors组成的集合S,使得(a)没有接收过编号小于n的议案,或者(b)v是被acceptors接收的编号小于n的议案中最高编号的议案对应的值

    => 为了维持P2c 不变,如果proposer想提出编号为n的议案,必须学习过上一个被大多数acceptor接收的议案。

    可以这样来思考,如果在值为v被选中,而这个v提出时议案的编号为m,在这个m后,proposer又提出了几个议案,一致到编号n(n>m),那么propser在[m+1, n]这几个议案的值都需要是v。proposer在提出这几个议案的时候,只需要参考上一个议案(如在提m+1时,参考m议案)的值即可。那这样会不会有问题?当然有,上一个议案如果发生变化怎么办?为了防止这种可能,就需要accptor做出承诺,上一个议案保证不变。怎么能保证不变呢?保证上次议案与本次议案之间不会再有新的插队议案就可以。

    这样一直在说的都是都是在m已经达成一致的情况,如何让在编号为m上达成一致?自然就需要进行一次投票,决定出m与v。

  • P1a 如果acceptor在prepare阶段没有响应过大于n的议案,那么它能够接收编号为n的议案。

小结:

  1. 对于learner来说,目的是最后的value一致

  2. 既然为了区分不同的议案,给它们做了编号,那么 1. 只要编号一致,就能保证value一致; 2. 如果编号不一致,那么只要保证不同编号的值是一致的

  3. paxos本着少数服从多数的原则

  4. 编号n的单调递增性对一致性的价值
    在现实中,通过一起开会的方式(同步)对某个议案进行表决,最终少数服从多数得出一致性

    但计算机没有同步的条件,只能通过异步的方式,单调递增是给异步定了一个方向。像极了时间的概念。

4. 演变

  • 杰出learner

    为了学习被选中的值,learner需要找到被选中的议案,最简单的方式是,每个acceptor选则一个议案后,都向每一个learner汇报自己的选择,但这样就会有 Number(learners) * Number(acceptors) 次通信。

    由于假设了非拜占庭的模式,learner可以从另外一个learner中获取答案。这样只要找到一个杰出的learner,所有的acceptors都向它汇报自己的选择,然后这个杰出的learner再通知其他learner,这样通信的次数就减少到Number(learners) + Number(acceptors)。

    也可以有多个杰出的learner,这样以更高一点的通信复杂度换取更高一点的可靠性。

    由于信息丢失,以及acceptor宕机,可能让learner不知道议案是否被大多数acceptors选中,这样只有等到一个新的议案被选中时才能知道,当然learner也可以发起一个询问议案。

  • 杰出proposer

    想象一个有2个proposer交互持续提出议案的情景,proposer p以编号n1结束phase 1,另一个proposer q以编号n2(n2> n1)完成phase 1,这时候当p以n1提出phase 2时,它的议案就被忽略。然后p接着以n3(n3>n2)完成phase 1,而q以n2提出phase 2时,也遇到p相同的情况...,依次循环,这样就永远不会有值被选中。

    这样就需要一个杰出的proposer,只有它可以提出议案,它可以与大多数acceptors通信,就可以保证提出更高编号的议案。

5. 应用场景

实现分布式系统的一种简单方式是一组clients向中心server提交指令。当server以一定的顺序执行指令时,它的状态就是确定的。这个状态机有一个当前的状态,执行每一个指令都会产生一个新的状态。比如银行系统的出纳是分布式系统的client,状态机包括所有账户的盈余。对于一个取钱指令,当账户余额大于取钱数的时,就会执行减少账户余额操作从而产生新的状态。

如果只用单一的中心server,当它宕机时,操作就会失败。所以引入多台sever,每个server都是一个状态机。因为它们状态是确定的,当执行相同的指令序列后,它们最后的结果是一致的。

为了保证所有机器执行相同序列的指令,使用Paxos的一系列单独实例,第i个实例选择的值就是指令序列中第i个指令。在所有的实例中,每一个server扮演所有的角色(proposer、acceptor、learner)。假定server的集合是固定的,那么在一致性算法的所有实例,使用的都是相同的agents。

通常,一个server被选成为leader,在所有一致性算法的实例中扮演杰出的proposer的角色。client向leader发送指令,leader决定每个指令的次序。如果leader决定某一个指令是第135号,它尝试使这个指令成为第135号一致性算法的实例。一般都会成功,也会由于错误或者另外一个觉得是leader的server提出一个不同的第135号指令而失败。但一致性算法保证了至多只有一个指令是第135号指令。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×