精华内容
下载资源
问答
  • Paxos算法详解

    2021-06-06 21:57:10
    兰伯特提出的Paxos算法包括2个部分: 一个是Basic Paxos算法,描述的是多节点之间如何就某个值(提案value)达成共识 另一个是Multi-Paxos思想,描述的是执行多个Basic Paxos实例,就一系列值达成共识 1、Basic ...

    兰伯特提出的Paxos算法包括2个部分:

    • 一个是Basic Paxos算法,描述的是多节点之间如何就某个值(提案value)达成共识
    • 另一个是Multi-Paxos思想,描述的是执行多个Basic Paxos实例,就一系列值达成共识

    1、Basic Paxos

    一个分布式集群由节点A、B、C组成,提供只读KV存储服务。创建只读变量的时候,必须要对它进行赋值,而且这个值后续没办法修改。因此一个节点创建只读变量后就不能再修改它了,所以所有节点必须要先对只读变量的值达成共识,然后所有节点再一起创建这个只读变量

    当有多个客户端访问这个系统,试图创建同一个只读变量,客户端1试图创建值为3的X,客户端2试图创建值为7的X,这样如何达成共识,实现各节点上X值的一致呢?

    在这里插入图片描述

    1)、Basic Paxos中的三种角色

    在Basic Paxos中,有提议者(Proposer)、接受者(Acceptor)、学习者(Learner)三种角色,他们之间的关系如下:

    在这里插入图片描述

    • 提议者(Proposer):提议一个值,用于投票表决。集群中收到客户端请求的节点是提议者
    • 接受者(Acceptor):对每个提议的值进行投票,并存储接受的值。集群中所有节点都在扮演接受者的角色,参与共识协商,并接受和存储数据

    一个节点可以身兼多个角色。如下图,一个3节点的集群,1个节点收到了请求,那么该节点将作为提议者发起二阶段提交,然后这个节点和另外2个节点一起作为接受者进行共识协商

    在这里插入图片描述

    • 学习者(Learner):被告知投票的结果,接受达成共识的值,存储保存,不参与投票的过程。一般来说,学习者是数据备份节点,比如Master-Slave模型中的Slave,被动地接受数据,容灾备份

    这3种角色在本质上代表的是3种功能:

    • 提议者代表的是接入和协调功能,收到客户端请求后,发起二阶段提交,进行共识协商
    • 接受者代表投票协商和存储数据,对提议的值进行投票,并接受达成共识的值,存储保存
    • 学习者代表存储数据,不参与共识协商,只接受达成共识的值,存储保存

    2)、如何达成共识

    在Basic Paxos中,兰伯特使用提案代表一个提议,提案中包含了提案编号和提议值。下面使用[n, v]代表一个提案,其中n为提案编号,v为提议值

    假设客户端1的提案编号为1,客户端2的提案编号为5,并假设节点A、B先收到来自客户端1的准备请求,节点C先收到来自客户端2的准备请求

    1)准备(Prepare)阶段

    首先客户端1、2作为提议者,分别向所有接受者发送包含提案编号的准备请求:

    在这里插入图片描述

    在准备请求中是不需要指定提议的值的,只需要携带提案编号就可以了

    接着,当节点A、B收到提案编号为1的准备请求,节点C收到提案编号为5的准备请求后:

    在这里插入图片描述

    • 由于之前没有通过任何提案,所以节点A、B将返回一个尚无提案的响应。也就是说节点A和B在告诉提议者,我之前没有通过任何提案,并承若以后不再响应提案编号小于等于1的准备请求,不会通过编号小于1的提案
    • 节点C将返回一个尚无提案的响应,并承诺以后不再响应提案编号小于等于5的准备请求,不会通过编号小于5的提案

    当节点A、B收到提案编号为5的准备请求,和节点C收到提案编号为1的准备请求的时候,将进行如下处理:

    在这里插入图片描述

    • 当节点A、B收到提案编号为5的准备请求的时候,因为提案编号5大于它们之前响应的准备请求的提案编号1,而且两个节点都没有通过任何提案,所以它将返回一个尚无提案的响应,并承诺以后不再响应提案编号小于等于5的准备请求,不会通过编号小于5的提案
    • 当节点C收到提案编号为1的准备请求的时候,由于提案编号1小于它之前响应的准备请求的提案编号5,所以丢弃该准备请求,不做响应

    2)接受(Accept)阶段

    第二个阶段也就是接受阶段,首先客户端1、2在收到大多数节点的准备响应之后,会分别发送接受请求:

    在这里插入图片描述

    • 当客户端1收到大多数的接受者(节点A、B)的准备响应后,根据响应中提案编号最大的提案的值,设置接受请求中的值。因为该值在来自节点A、B的准备响应中都为空(尚无提案),所以就把自己的提议值3作为提案的值,发送接受请求[1, 3]
    • 当客户端2收到大多数的接受者的准备响应后(节点A、B、C),根据响应中提案编号最大的提案的值,来设置接受请求中的值。因为该值在来自节点A、B、C的准备响应都为空(尚无提案),所以就把自己的提议值7作为提案的值,发送接受请求[5, 7]

    当3个节点收到2个客户端的提案请求时,会进行这样的处理:

    在这里插入图片描述

    • 当节点A、B、C收到接受请求[1, 3]的时候,由于提案的提案编号1小于3各节点承诺能通过的提案的最小提案编号5,所以提案[1, 3]将被拒绝
    • 当节点A、B、C收到接受请求[5, 7]的时候,由于提案的编号5不小于3个节点承诺能通过的提案的最小提案编号5,所以就通过提案[5, 7],也就是接受了值7,3个节点就X值为7达成了共识

    如果集群中有学习者,当接收者通过了一个提案时,就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案,那么它也通过该提案,接受该提案的值

    3)、小结

    Basic Paxos是通过二阶段提交的方式来达成共识的,而且还实现了容错,大多数节点都同意的原则赋予了Basic Paxos容错的能力,让它能够容忍少于一半的节点的故障

    本质上,提案编号的大小代表着优先级。根据提案编号的大小,接受者保证3个承诺:

    • 如果准备请求的提案编号,小于等于接受者已经响应的准备请求的提案编号,那么接受者将承诺不响应这个准备请求
    • 如果接受请求的提案编号,小于接受者已经响应的准备请求的提案编号,那么接受者将承诺不通过这个提案
    • 如果接受者之前有通过提案,那么接受者将承诺,会在准备请求的响应中,包含已经通过的最大编号的提案信息

    4)、思考题

    如果节点A、B已经通过了提案[5, 7],节点C未通过任何提案,那么当客户端3提案编号为9时,通过Basic Paxos执行SET X = 6,最终3个节点上X值是多少呢

    最终节点上的值应该是[9, 7],过程如下:

    1. 在准备阶段,节点C收到客户端3的准备请求[9, 6],因为节点C未收到任何提案,所以返回尚无提案的响应。这时如果节点C收到了之前客户端的准备请求[5, 7],根据提案编号5小于它之前响应的准备请求的提案编号9,会丢弃该准备请求
    2. 客户端3发送准备请求[9, 6]给节点A、B,这时因为节点A、B已经通过了提案[5, 7],根据“如果接受者之前有通过提案,那么接受者将承诺会在准备请求的响应中,包含已经通过的最大编号的提案信息”的原则,节点A、B会返回[5, 7]给客户端3
    3. 客户端3发送接受请求[9, 7]给节点A、B、C(这里使用的是准备阶段的最大提议编号和已经被通过的值),因为此时请求编号9不小于之前的请求编号,所以所有节点接受该请求[9, 7]

    2、Multi-Paxos

    Basic Paxos只能就单个值达成共识,一旦遇到为一系列的值实现共识的时候,它就不管用了

    兰伯特提到的Multi-Paxos是一种思想,不是算法。而Multi-Paxos算法是一个统称,它是指基于Multi-Paxos思想,通过多个Basic Paxos实例实现一系列值的共识的算法

    1)、兰伯特关于Multi-Paxos的思考

    Basic Paxos是通过二阶段提交来达成共识的。在第一阶段,也就是准备阶段,接收到大多数准备响应的提议者,才能发起接受请求进入第二阶段(接受阶段):

    在这里插入图片描述

    如果直接通过多次执行Basic Paxos实例,来实现一系列值的共识,就会存在这样几个问题:

    • 如果多个提议者同时提交提案,可能出现因为提案编号冲突,在准备阶段没有提议者接收到大多数准备响应,协商失败,需要重新协调。比如,一个5节点的集群,如果3个节点作为提议者同时提案,就可能发生因为没有提议者接受大多数响应(比如1个提议者接收1个准备响应,另外2个提议者分别接收到2个准备响应)而准备失败,需要重新协调
    • 2轮RPC通讯(准备阶段和接受阶段)往返消息多、耗性能、延迟大

    2)、领导者(Leader)

    通过引入领导者节点来解决多个提议者同时提交提案可能出现因为提案编号冲突的问题

    领导者节点作为唯一提议者,这样就不存在多个提议者同时提交提案的情况,也就不存在提案冲突的情况了:

    在这里插入图片描述

    在论文中,兰伯特没有说如何选举领导者,需要我们在实现Multi-Paxos算法的时候自己实现。 比如在Chubby中,主节点(也就是领导者节点)是通过执行Basic Paxos算法,进行投票选举产生的

    3)、优化Basic Paxos执行(2轮RPC通讯)

    可以采用当领导者处于稳定状态时,省掉准备阶段,直接进入接受阶段这个优化机制,优化Basic Paxos执行。也就是说,领导者节点上序列中的命令是最新的,不再需要通过准备请求来发现之前被大多数节点通过的提案,领导者可以独立指定提案中的值。这时,领导者在提交命令时,可以省掉准备阶段,直接进入接受阶段:

    准备阶段的意义,是发现接受者节点上,已经通过的提案的值。领导者节点上,序列中的命令是最新的,不再需要通过准备请求来发现之前被大多数节点通过的提案,领导者可以独立指定提案中的值

    在这里插入图片描述

    和重复执行Basic Paxos相比,Multi-Paxos引入领导者节点之后,因为只有领导者节点一个提议者,只有它说了算,所以就不存在提案冲突。另外,当主节点处于稳定状态时,就省掉准备阶段,直接进入接受阶段,所以在很大程度上减少了往返的消息数,提升了性能,降低了延迟

    4)、Chubby的Multi-Paxos实现

    Chubby中通过引入主节点,实现了兰伯特提到的领导者(Leader)节点的特性。也就是说,主节点作为唯一提议者,这样就不存在多个提议者同时提交提案的情况,也就不存在提交提案冲突的情况了

    在Chubby中,主节点是通过执行Basic Paxos算法,进行投票选举产生的,并且在运行过程中,主节点会通过不断续租的方式来延长租期。如果主节点故障了,那么其他的节点又会投票选举出最新的主节点,也就是说主节点是一直存在的,而且是唯一的

    在Chubby中实现了兰伯特提到的,当领导者处于稳定状态时,省掉准备状态,直接进入接受阶段这个优化机制

    在Chubby中页实现了成员变更,以此保证节点变更的时候集群的平稳运行

    最后,在Chubby中为了实现强一致性,读操作也只能在主节点上执行。也就是说,只要数据写入成功,之后所有的客户端督导的数据都是一致的(只能在主节点进行读操作,效果相当于单机,对吞吐量和性能有所影响)

    • 所有的读请求和写请求都由主节点来处理。当主节点从客户端接收到写请求后,作为提议者,执行Basic Paxos实例,将数据发送给所有的节点,并且在大多数的服务器接受了这个写请求之后,再响应给客户端成功

    在这里插入图片描述

    • 当主节点接收到读请求后,主节点只需要查询本地数据,然后返回给客户端就可以了

    在这里插入图片描述

    参考:

    05 | Paxos算法(一):如何在多个节点间确定某变量的值?

    06 | Paxos算法(二):Multi-Paxos不是一个算法,而是统称

    展开全文
  • paxos算法详解

    2019-10-28 16:15:05
    Paxos算法的目的是为了解决分布式环境下一致性的问题。 多个节点并发操纵数据,如何保证在读写过程中数据的一致性,并且解决方案要能适应分布式环境下的不可靠性(系统如何就一个值达到统一) paxos协议用来解决的...

    目的


    Paxos算法的目的是为了解决分布式环境下一致性的问题。
    多个节点并发操纵数据,如何保证在读写过程中数据的一致性,并且解决方案要能适应分布式环境下的不可靠性(系统如何就一个值达到统一)
    paxos协议用来解决的问题可以用一句话来简化:

        将所有节点都写入同一个值,且被写入后不再更改。

    基本概念


    两个操作

     1. Proposal Value:提议的值;
     2. Proposal Number:提议编号,可理解为提议版本号,要求不能冲突;

    三个角色

     1. Proposer:提议发起者。Proposer 可以有多个,Proposer 提出议案(value)。所谓 value,可以是任何操作,比如“设置某个变量的值为value”。不同的 Proposer 可以提出不同的 value,例如某个Proposer 提议“将变量 X 设置为 1”,另一个 Proposer 提议“将变量 X 设置为 2”,但对同一轮 Paxos过程,最多只有一个 value 被批准。
     2. Acceptor:提议接受者;Acceptor 有 N 个,Proposer 提出的 value 必须获得超过半数(N/2+1)的 Acceptor批准后才能通过。Acceptor 之间完全对等独立。
     3. Learner:提议学习者。上面提到只要超过半数accpetor通过即可获得通过,那么learner角色的目的就是把通过的确定性取值同步给其他未确定的Acceptor。
     

    角色分工参与决策
    Proposer提出提案,提案:[编号Id,提议的Value]
    Acceptor接收提案,批准/拒绝提案,当提案被大多数的Acceptor(Quorum)批准后即为被选定的提案(Chosen)
    Learner学习(Learn)最新被选定的提案×

     
    流程


    一句话说明是:

        proposer将发起提案(value)给所有accpetor,超过半数accpetor获得批准后,proposer将提案写入accpetor内,最终所有accpetor获得一致性的确定性取值,且后续不允许再修改。

     1. 准备阶段(占坑阶段)
     1.第一阶段A:Proposer选择一个提议编号n,向所有的Acceptor广播Prepare(n)请求。
    2.第一阶段B:Acceptor接收到Prepare(n)请求,若提议编号n比之前接收的Prepare请求都要大,则承诺将不会接收提议编号比n小的提议,并且带上之前Accept的提议中编号小于n的最大的提议,否则不予理会。
     2. 接受阶段(提交阶段)
    1. 第二阶段A:整个协议最为关键的点:Proposer得到了Acceptor响应
     1.如果未超过半数accpetor响应,直接转为提议失败;
     2.如果超过多数Acceptor的承诺,又分为不同情况:
      - 如果所有Acceptor都未接收过值(都为null),那么向所有的Acceptor发起自己的值和提议编号n,记住,一定是所有Acceptor都没接受过值;
      - 如果有部分Acceptor接收过值,那么从所有接受过的值中选择对应的提议编号最大的作为提议的值,提议编号仍然为n。但此时Proposer就不能提议自己的值,只能信任Acceptor通过的值,维护一但获得确定性取值就不能更改原则;
    2. 第二阶段B:Acceptor接收到提议后,如果该提议版本号不等于自身保存记录的版本号(第一阶段记录的),不接受该请求,相等则写入本地。



    整个paxos协议过程看似复杂难懂,但只要把握和理解这两点就基本理解了paxos的精髓:
    -  理解第一阶段accpetor的处理流程:如果本地已经写入了,不再接受和同意后面的所有请求,并返回本地写入的值;如果本地未写入,则本地记录该请求的版本号,并不再接受其他版本号的请求,简单来说只信任最后一次提交的版本号的请求,使其他版本号写入失效;

    - 理解第二阶段proposer的处理流程:未超过半数accpetor响应,提议失败;超过半数的accpetor值都为空才提交自身要写入的值,否则选择非空值里版本号最大的值提交,最大的区别在于是提交的值是自身的还是使用以前提交的。

    例子



    看这个最简单的例子:1个processor,3个Acceptor,无learner。

    目标:proposer向3个aceptort 将name变量写为v1。

    - 第一阶段A:proposer发起prepare(name,n1),n1是递增提议版本号,发送给3个Acceptor,说,我现在要写name这个变量,我的版本号是n1
    - 第一阶段B:Acceptor收到proposer的消息,比对自己内部保存的内容,发现之前name变量(null,null)没有被写入且未收到过提议,都返回给proposer,并在内部记录name这个变量,已经有proposer申请提议了,提议版本号是n1;
    - 第二阶段A:proposer收到3个Acceptor的响应,响应内容都是:name变量现在还没有写入,你可以来写。proposer确认获得超过半数以上Acceptor同意,发起第二阶段写入操作:accept(v1,n1),告诉Acceptor我现在要把name变量协议v1,我的版本号是刚刚获得通过的n1;
    - 第二阶段B:accpetor收到accept(v1,n1),比对自身的版本号是一致的,保存成功,并响应accepted(v1,n1);
    结果阶段:proposer收到3个accepted响应都成功,超过半数响应成功,到此name变量被确定为v1。

    三军问题



    1. 参谋1发起提议,派通信兵带信给3个将军,内容为(编号1);
    2. 3个将军收到参谋1的提议,由于之前还没有保存任何编号,因此把(编号1)保存下来,避免遗忘;同时让通信兵带信回去,内容为(pok);
    3. 参谋1收到至少2个将军的回复,再次派通信兵带信给3个将军,内容为(编号1,进攻时间1);
    4. 3个将军收到参谋1的时间,把(编号1,进攻时间1)保存下来,避免遗忘;同时让通信兵带信回去,内容为(aok);
    5. 参谋1收到至少2个将军的(aok)内容,确认进攻时间已经被大家接收;
    6. 参谋2发起提议,派通信兵带信给3个将军,内容为(编号2);
    7. 3个将军收到参谋2的提议,由于(编号2)比(编号1)大,因此把(编号2)保存下来,避免遗忘;又由于之前已经接受参谋1的提议,因此让通信兵带信回去,内容为(pok,编号1,进攻时间1);
    8. 参谋2收到至少2个将军的回复,由于回复中带来了已接受的参谋1的提议内容,参谋2因此不再提出新的进攻时间,接受参谋1提出的时间;

    1. 参谋1发起提议,派通信兵带信给3个将军,内容为(编号1);
    2. 3个将军的情况如下
        a.将军1和将军2收到参谋1的提议,将军1和将军2把(编号1)记录下来,如果有其他参谋提出更小的编号,将被拒绝;同时让通信兵带信回去,内容为(pok);
        b.负责通知将军3的通信兵被抓,因此将军3没收到参谋1的提议;
    3. 参谋2在同一时间也发起了提议,派通信兵带信给3个将军,内容为(编号2);
    4. 3个将军的情况如下
        a.将军2和将军3收到参谋2的提议,将军2和将军3把(编号2)记录下来,如果有其他参谋提出更小的编号,将被拒绝;同时让通信兵带信回去,内容为(pok);
        b.负责通知将军1的通信兵被抓,因此将军1没收到参谋2的提议;
    5. 参谋1收到至少2个将军的回复,再次派通信兵带信给有答复的2个将军,内容为(编号1,进攻时间1);
    6. 2个将军的情况如下
        a.将军1收到了(编号1,进攻时间1),和自己保存的编号相同,因此把(编号1,进攻时间1)保存下来;同时让通信兵带信回去,内容为(aok);
        b.将军2收到了(编号1,进攻时间1),由于(编号1)小于已经保存的(编号2),因此让通信兵带信回去,内容为(ano);
    7. 参谋2收到至少2个将军的回复,再次派通信兵带信给有答复的2个将军,内容为(编号2,进攻时间2);
    8. 2个将军的情况如下 
        a.将军2收到了(编号2,进攻时间2),和自己保存的编号相同,因此把(编号2,进攻时间2)保存下来,同时让通信兵带信回去,内容为(aok);
        b.将军3收到了(编号2,进攻时间2),和自己保存的编号相同,因此把(编号2,进攻时间2)保存下来,同时让通信兵带信回去,内容为(aok);
    9. 参谋2收到至少2个将军的(aok)内容,确认进攻时间已经被多数派接受;
    10. 参谋1只收到了1个将军的(aok)内容,同时收到一个(ano);参谋1重新发起提议,派通信兵带信给3个将军,内容为(编号3);
    11. 3个将军的情况如下
        a.将军1收到参谋1的提议,由于(编号3)大于之前保存的(编号1),因此把(编号3)保存下来;由于将军1已经接受参谋1前一次的提议,因此让通信兵带信回去,内容为(pok,编号1,进攻时间1);
        b.将军2收到参谋1的提议,由于(编号3)大于之前保存的(编号2),因此把(编号3)保存下来;由于将军2已经接受参谋2的提议,因此让通信兵带信回去,内容为(pok,编号2,进攻时间2);
        c.负责通知将军3的通信兵被抓,因此将军3没收到参谋1的提议;
    12. 参谋1收到了至少2个将军的回复,比较两个回复的编号大小,选择大编号对应的进攻时间作为最新的提议;参谋1再次派通信兵带信给有答复的2个将军,内容为(编号3,进攻时间2);
    13. 2个将军的情况如下 
        a.将军1收到了(编号3,进攻时间2),和自己保存的编号相同,因此保存(编号3,进攻时间2),同时让通信兵带信回去,内容为(aok);
        b.将军2收到了(编号3,进攻时间2),和自己保存的编号相同,因此保存(编号3,进攻时间2),同时让通信兵带信回去,内容为(aok);
    14. 参谋1收到了至少2个将军的(aok)内容,确认进攻时间已经被多数派接受;

    总结


    第一种情况:Proposer提议正常,未超过accpetor失败情况


    问题:还是上面的例子,如果第二阶段B,只有2个accpetor响应接收提议成功,另外1个没有响应怎么处理呢?

    处理:proposer发现只有2个成功,已经超过半数,那么还是认为提议成功,并把消息传递给learner,由learner角色将确定的提议通知给所有accpetor,最终使最后未响应的accpetor也同步更新,通过learner角色使所有Acceptor达到最终一致性。

    第二种情况:Proposer提议正常,但超过accpetor失败情况


    问题:假设有2个accpetor失败,又该如何处理呢?

    处理:由于未达到超过半数同意条件,proposer要么直接提示失败,要么递增版本号重新发起提议,如果重新发起提议对于第一次写入成功的accpetor不会修改,另外两个accpetor会重新接受提议,达到最终成功。

    情况再复杂一点:还是一样有3个accpetor,但有两个proposer。


    情况一:proposer1和proposer2串行执行


    proposer1和最开始情况一样,把name设置为v1,并接受提议。
    proposer1提议结束后,proposer2发起提议流程:
    第一阶段A:proposer1发起prepare(name,n2)

    第一阶段B:Acceptor收到proposer的消息,发现内部name已经写入确定了,返回(name,v1,n1)

    第二阶段A:proposer收到3个Acceptor的响应,发现超过半数都是v1,说明name已经确定为v1,接受这个值,不在发起提议操作。


    情况二:proposer1和proposer2交错执行


    proposer1提议accpetor1成功,但写入accpetor2和accpetor3时,发现版本号已经小于accpetor内部记录的版本号(保存了proposer2的版本号),直接返回失败。

    proposer2写入accpetor2和accpetor3成功,写入accpetor1失败,但最终还是超过半数写入v2成功,name变量最终确定为v2;

    proposer1递增版本号再重试发现超过半数为v2,接受name变量为v2,也不再写入v1。name最终确定还是为v2


    情况三:proposer1和proposer2第一次都只写成功1个Acceptor怎么办


    都只写成功一个,未超过半数,那么Proposer会递增版本号重新发起提议,这里需要分多种情况:

    1. 3个Acceptor都响应提议,发现Acceptor1{v1,n1} ,Acceptor2{v2,n2},Acceptor{null,null},Processor选择最大的{v2,n2}发起第二阶段,成功后name值为v2;
    2. 2个Acceptor都响应提议,
    1.如果是Acceptor1{v1,n1} ,Acceptor2{v2,n2},那么选择最大的{v2,n2}发起第二阶段,成功后name值为v2;
    2.如果是Acceptor1{v1,n1} ,Acceptor3{null,null},那么选择最大的{v1,n1}发起第二阶段,成功后name值为v1;
    3.如果是Acceptor2{v2,n2} ,Acceptor3{null,null},那么选择最大的{v2,n2}发起第二阶段,成功后name值为v2;
    3. 只有1个Acceptor响应提议,未达到半数,放弃或者递增版本号重新发起提议

    可以看到,都未达到半数时,最终值是不确定的!


    其他问题


    Paxos议案ID生成算法

    在Google的Chubby论文中给出了这样一种方法:假设有n个proposer,每个编号为ir[0,n),proposal编号的任何值s都应该大于它已知的最大值,并且满足:

        s%n=ir =>  s=m*n+ir
        proposer已知的最大值来自两部分:proposer自己对编号自增后的值和接收到acceptor的拒绝后所得到的值。

    例:以3个proposer P1、P2、P3为例,开始m=0,编号分别为0,1,2。
    1. P1提交的时候发现了P2已经提交,P2编号为1 >P1的0,因此P1重新计算编号:new P1 = 1*3+1 = 4;
    2. P3以编号2提交,发现小于P1的4,因此P3重新编号:new P3 = 1*3+2 = 5。

    活锁


    当某一proposer提交的proposal被拒绝时,可能是因为acceptor承诺返回了更大编号的proposal,因此proposer提高编号继续提交。 如果2个proposer都发现自己的编号过低转而提出更高编号的proposal,会导致死循环,这种情况也称为活锁。

    比如说当此时的 proposer1提案是3,proposer2提案是4,但acceptor承诺的编号是5,那么此时proposer1,proposer2都将提高编号假设分别为6,7,并试图与accceptor连接,假设7被接受了,那么提案5和提案6就要重新编号提交,从而不断死循环。

    解决方案是Proposer失败之后给一个随机的等待时间,这样就减少同时请求的可能。/选取一个主Proposer,只有主Proposer才能提出提案


    Learner学习被选定的value

    序号方案优点缺点
    方案一Acceptor接受了一个提案,就将该方案发送给所有的LearnerLeader可以快速获取被选定的value通信次数过多
    方案二Acceptor接受了一个提案,就将该方案发送给主Learner,主Learner通信次数减少单点问题(主Learner出现问题)
    方案三Acceptor接受了一个提案,就将该方案发送给Learner集合,Learner集合再通知其他Learner集合中Learner个数越多,可靠性越高网络通信复杂度越高

     

    展开全文
  • 1 paxos算法详解 1.1 基本概念 角色: 提议者(proposer):提议的发起者。 批准者(acceptor):对提议进行批准。 学习者(learner):作为一致性协议的副本因子,对被超过半数的 acceptor 批准的方案进行学习。 ...

    0 paxos算法解决了什么问题

    现在有n个人组成提一个会议,这个会议的目的是为了确定今年的税率,那么每个人都会提出自己认为的今年的合理的税率,为了大家能够达成一致,有了paxos算法。实际里,这个会议就是一个集群。

    1 paxos算法详解

    1.1 基本概念

      1. 角色:
        提议者(proposer):提议的发起者。
        批准者(acceptor):对提议进行批准。
        学习者(learner):作为一致性协议的副本因子,对被超过半数的 acceptor
        批准的方案进行学习。
      1. 提议(propose):
        Proposer(提议者)可以提出提议,最终要达成一致的 value 就在提议里。Acceptor(接收者)根据提议的编号来选择是否接受(accept)提议。如果超过半数的cceptor 接收了一个提议,那么这个提议就被接受(accepted)了,提议里的 value 也就被选定了。
      1. 仲裁集合(Quorums): 是 Acceptor(假设有 N 个)的一个子集,任何两个 Quorums 至少有一个相同的成员,也就是说一个 quorums 是一个包含了超过 N/2+1 个 Acceptor 的一个集合。
      1. 提议序号(Proposal number)和批准值(agreed value):对于任意一个给定的提议者,其给定的提议对应的提议号必定全局唯一。每一个提议(n,v 代表的话)都有一个提议序号(n)和其想要通过的提议值(v),为了便于理解,设想一个权力机关去决定今年的税率,那么每个人会给自己的提议有一个全局唯一的序号(n),然后还包含对于想要决定的目标变量(税率)的值(n)也就是税率的大小。

    1.2 算法具体流程

    Paxos(这里主要说的是 Basic paxos 算法)的具体流程分为两阶段:

    Phase1

    • (1) Phase 1a - proposer 准备(Prepare):
      Proposer 创建一个条消息,我们将其称为“Prepare”,以数字 n 标识。请注意,n 不是要提议的值也不是可能会被同意的商定的值,而只是一个数字,该数字由提议者唯一标识此初始消息(发送给接收者)。数字 n 必须大于此提议者在先前的任何 Prepare 消息中使用的任何数字。然后,它将包含 n 的 Prepare消息发送到接受方的一个仲裁集合(超过一半以上的 Acceptor 的集合)。请注意,Prepare 消息仅包含数字 n(也就是说,它不必包含例如建议的值,通常用 v 表示)。提议者决定谁在仲裁集合。如果提议者不能与至少一个接受者的仲裁集合进行通信,则他不应启动 Paxos。
    • (2) Phase 1b - acceptor 承诺(Promise):
      任何接受者都在等待来自任何提议者的准备消息。如果接受方收到一条准备消息,则接受方必须查看刚刚收到的准备消息的标识符编号 n。有两种情况:
      1. 如果 n 高于接受者从任何提议者接收到的每个先前的提议编号,那么接受者必须向提议者返回一条消息,我们称其为“承诺”,以忽略所有将来的提议数量少的提议比 n。如果接受者在过去某个时候接受了提议者的提议(也就是第二阶段中批准的提议),则在对提议者的答复中必须包含先前接受的的提议编号(例如 m)和相应的接受(批准)值(例如 w)。
      1. 否则(即,n 小于或等于接受者从任何提议者收到的任何先前提议编号),接受者可以忽略收到的提议。在这种情况下,Paxos 不必工作。但是,为了优化起见,发送拒绝(Nack)响应将告诉提议者它停止以 n 作为提议的序号去建立共识(这是优化手段,因为即使不主动告诉,其提议的序号也会增长)。

    Phase2

    • (1) Phase 2a - proposer 发送 Accept 消息:
      • 1 如果提议者从接受者的一个仲裁集合中获得大部分承诺,则需要为其提议设置值 v。
      • 2 如果任何接受者先前已接受过一个提议,那么他们会将这个提议发送给提议者,提议者现在必须将其提议值 v 设置为与接受者报告的(与这些接受者最高提议编号关联的)提议值(也就是提议者之前接受过的提议),我们称之为 z。
      • 3 如果到目前为止,没有一个接受者接受提议,则提
        议者可以选择其最初想要提议的值,例如 x。在这个阶段,提议者会发送一个 Accept 信息:(n,v)给一个接受者个仲裁集合。(n 就是之前提议者发给接受者的准备信息里的提议里的提议序号。v=z 或 者 v=x (当所有接受者都没有接受过提议时。)),这个 accept 请求可以理解为一个请求:“请接受这个提议!”。
    • (2) Phase 2b - acceptor 发送 Accepted 消息:
      如果接受者从提议者接收到 Accept 信息(n,v),分为两种情况:
      • 1 如果:它尚未承诺(在 Paxos 协议的阶段 1b 中)仅考虑提议序号大于 n 的提议时,则它应该将(刚接收到的 Accept 消息的)值 v 注册为(协议)的接受值,并向提议者和每个学习者(通常是提议者本身)发送一条接受消息。
      • 2 否则:它可以忽略这个 Accept 消息。

    1.3 paxos算法的活锁问题

    livelock

    如上图,(从上图也可以看出集群里的一个机器可以有多重身份)首先 s1-3 给出 3 个 preparemeesage,然后 s1-3 是一个 quorum 得到了大多数支持,开始发送 phase2-a 的 accept 信息(A3.1),但是由于在发送phase2-a 的 accept 消息之前,s3-5 给出 3 个 prepare message,s3 又更新了自己主张的提议,那么之前发送的(accept 信息)A3.1 就不会被回应,之后 s1-2 发现由于超过半数(s3-5)拒绝了自己,然后就出了新的一轮 prepare message 为 P4.1,
    然后,就这样循环往复下去出现了活锁。

    其改进方法:

    • 解决方案1:出现冲突的时候,在重新开始执行prepare message流程之前,施加随机的延迟;让其他proposers有机会完成value的确认
    • 解决方案2:multi-paxos会使用leader来避免活锁;

    2 paxos算法实现

    2.1 paxos.cpp

    模拟paxos算法的主要流程

    #include <stdlib.h>
    #include <stdio.h>
    #include "Paxos/Acceptor.h"
    #include "Paxos/Proposer.h"
    #include "lib/Thread.h"
    #include "lib/Lock.h"
    #include "lib/mapi.h"
    #include "lib/atom.h"
    #include "lib/Logger.h"
    
    paxos::Proposer p[5];
    paxos::Acceptor a[11];
    mdk::Mutex l[11];
    int finishedCount = 0;
    int finalValue = -1;
    bool isFinished = false;
    mdk::uint64 g_start;
    mdk::Logger g_log;
    
    void* Proposer(void *id)
    {
    	mdk::Logger log;
    	char logName[256];
    	sprintf( logName, "Proposer%d", (long)id );
    	log.SetLogName(logName);
    	log.SetMaxLogSize(10);
    	log.SetMaxExistDay(30);
    	log.SetPrintLog(false);
    
    	paxos::Proposer &proposer = p[(long)id];
    	paxos::PROPOSAL value = proposer.GetProposal();
    	paxos::PROPOSAL lastValue;
    
    
    	int acceptorId[11];
    	int count = 0;
    
    	mdk::uint64 start = mdk::MillTime();
    	while ( true )
    	{
    		value = proposer.GetProposal();//拿到提议
    		log.Info("Info", "Proposer%d号开始(Propose阶段):提议=[编号:%d,提议:%d]\n", 
    			(long)id, value.serialNum, value.value);
    		count = 0;
    		int i = 0;
    		for (i = 0; i < 11; i++ )
    		{
    		/*
    			* 发送消息到第i个acceptor
    			* 经过一定时间达到acceptor,sleep(随机时间)模拟
    			* acceptor处理消息,mAcceptors[i].Propose()
    			* 回应proposer
    			* 经过一定时间proposer收到回应,sleep(随机时间)模拟
    			* proposer处理回应mProposer.proposed(ok, lastValue)
    		*/
    			mdk::m_sleep(rand()%500);//经过随机时间,消息到达了mAcceptors[i]
    			//处理消息
    			l[i].Lock();
    			bool ok = a[i].Propose(value.serialNum, lastValue);
    			l[i].Unlock();
    			mdk::m_sleep(rand()%500);//经过随机时间,消息到达Proposer
    			//处理Propose回应
    			if ( !proposer.Proposed(ok, lastValue) ) //重新开始Propose阶段
    			{
    				mdk::m_sleep(1000);//为了降低活锁,多等一会让别的proposer有机会完成自己的2阶段批准
    				break;
    			}
    			paxos::PROPOSAL curValue = proposer.GetProposal();//拿到提议
    			if ( curValue.value != value.value )//acceptor本次回应可能推荐了一个提议
    			{
    				log.Info("Info", "Proposer%d号修改了提议:提议=[编号:%d,提议:%d]\n", 
    					(long)id, curValue.serialNum, curValue.value);
    				break;
    			}
    			acceptorId[count++] = i;//记录愿意投票的acceptor
    			if ( proposer.StartAccept() ) break;
    		}
    		//检查有没有达到Accept开始条件,如果没有表示要重新开始Propose阶段
    		if ( !proposer.StartAccept() ) continue;
    
    		//开始Accept阶段
    		//发送Accept消息到所有愿意投票的acceptor
    		value = proposer.GetProposal();
    		log.Info("Info", "Proposer%d号开始(Accept阶段):提议=[编号:%d,提议:%d]\n", 
    			(long)id, value.serialNum, value.value);
    		for (i = 0; i < count; i++ )
    		{
    			//发送accept消息到acceptor
    			//减少accept阶段等待时间,加快收敛
    			mdk::m_sleep(rand()%200);//经过随机时间,accept消息到达acceptor
    			//处理accept消息
    			l[acceptorId[i]].Lock();
    			bool ok = a[acceptorId[i]].Accept(value);
    			l[acceptorId[i]].Unlock();
    			mdk::m_sleep(rand()%200);//经过随机时间,accept回应到达proposer
    			//处理accept回应
    			if ( !proposer.Accepted(ok) ) //重新开始Propose阶段
    			{
    				mdk::m_sleep(1000);//为了降低活锁,多等一会让别的proposer有机会完成自己的2阶段批准
    				break;
    			}
    			if ( proposer.IsAgree() )//成功批准了提议
    			{
    				start = mdk::MillTime() - start;
    				log.Info("Info", "Proposer%d号的提议被批准,用时%lluMS:最终提议 = [编号:%d,提议:%d]\n", (long)id, start, value.serialNum, value.value);
    				g_log.Info("Info", "Proposer%d号的提议被批准,用时%lluMS:最终提议 = [编号:%d,提议:%d]\n", (long)id, start, value.serialNum, value.value);
    				if(finalValue == -1) finalValue = value.value;
    				else if(finalValue != value.value) finalValue = 0;
    				if ( 4 == mdk::AtomAdd(&finishedCount, 1) )
    				{
    					isFinished = true;
    					g_start = mdk::MillTime() - g_start;
    					if(finalValue > 0){
    						g_log.Info("Info", "Paxos完成,用时%lluMS,最终通过提议值为:%d\n", g_start, finalValue);
    					}
    					else{
    						g_log.Info("Info", "Paxos完成,用时%lluMS,最终结果不一致!\n", g_start);
    					}
    				}
    				return NULL;
    			}
    		}
    	}
    	return NULL;
    }
    
    //Paxos过程模拟演示程序
    int main(int argc, char* argv[])
    {
    	int i = 0;
    	g_log.SetLogName("Paxos");
    	g_log.SetMaxLogSize(10);
    	g_log.SetMaxExistDay(30);
    	g_log.SetPrintLog(true);
    	g_log.Info("Info", "5个Proposer, 11个Acceptor准备进行Paxos\n"
    		"每个Proposer独立线程,Acceptor不需要线程\n"
    		"Proposer编号从0-10,编号为i的Proposer初始提议编号和提议值是(i+1, i+1)\n"
    		"Proposer每次重新提议会将提议编号增加5\n"
    		"Proposer被批准后结束线程,其它线程继续投票最终,全部批准相同的值,达成一致。\n");
    	g_start = mdk::MillTime();
    	g_log.Info("Info", "Paxos开始\n" );
    	paxos::PROPOSAL value;
    
    	for ( i = 0; i < 5; i++ ) 
    	{
    		p[i].SetPlayerCount(5, 11);
    		value.serialNum = value.value = i + 1;
    		p[i].StartPropose(value);
    	}
    
    	mdk::Thread t[5];
    	for ( i = 0; i < 5; i++ ) t[i].Run(Proposer, (void*)i);
    	//for ( i = 0; i < 5; i++ ) t[i].WaitStop();
    	while(true){
    		if(isFinished) break;
    		mdk::m_sleep(500);
    	}
    	return 0;
    }
    

    2.2 proposer.cpp

    模拟提议者的主要流程

    #include "Proposer.h"
    
    namespace paxos
    {
    
    Proposer::Proposer()
    {
    	SetPlayerCount(0, 0);
    }
    
    Proposer::Proposer(short proposerCount, short acceptorCount)
    {
    	SetPlayerCount(proposerCount, acceptorCount);
    }
    
    Proposer::~Proposer()
    {
    }
    
    void Proposer::SetPlayerCount(short proposerCount, short acceptorCount)
    {
    	m_proposerCount = proposerCount;
    	m_acceptorCount = acceptorCount;
    
    	return;
    }
    
    void Proposer::StartPropose(PROPOSAL &value)
    {
    	m_value = value;
    	m_proposeFinished = false;
    	m_isAgree = false;
    	m_maxAcceptedSerialNum = 0;
    	m_okCount = 0;
    	m_refuseCount = 0;
    	m_start = time(NULL);
    
    	return;
    }
    
    PROPOSAL& Proposer::GetProposal()
    {
    	return m_value;
    }
    /**
    //提议者
    class Proposer
    {
    public:
    	Proposer();
    	Proposer(short proposerCount, short acceptorCount);
    	virtual ~Proposer();
    	//设置参与者数量
    	void SetPlayerCount(short proposerCount, short acceptorCount);
    	//开始Propose阶段
    	void StartPropose(PROPOSAL &value);
    	//取得提议
    	PROPOSAL& GetProposal();
    	//提议被投票,Proposed失败则重新开始Propose阶段
    	bool Proposed(bool ok, PROPOSAL &lastAcceptValue);
    	//开始Accept阶段,满足条件成功开始accept阶段返回ture,不满足开始条件返回false
    	bool StartAccept();
    	//提议被接受,Accepted失败则重新开始Propose阶段
    	bool Accepted(bool ok);
    	//提议被批准
    	bool IsAgree();
    
    private:
    	short			m_proposerCount;///proposer数量
    	short			m_acceptorCount;//acceptor数量
    	PROPOSAL		m_value;//预备提议
    	bool			m_proposeFinished;//完成拉票,准备开始二阶段
    	bool			m_isAgree;//m_value被批准
    	unsigned int	m_maxAcceptedSerialNum;//已被接受的提议中流水号最大的
    	time_t			m_start;//阶段开始时间,阶段一,阶段二共用
    	short			m_okCount;//投票数量,阶段一,阶段二共用
    	short			m_refuseCount;//拒绝数量,阶段一,阶段二共用
    };
    
    
    	//提议数据结构
    	typedef struct PROPOSAL
    	{
    		unsigned int	serialNum;//流水号,1开始递增,保证全局唯一
    		unsigned int	value;//提议内容
    	}PROPOSAL;
    **/
    bool Proposer::Proposed(bool ok, PROPOSAL &lastAcceptValue)
    {
    	if ( m_proposeFinished ) return true;//可能是一阶段迟到的回应,直接忽略消息
    
    	if ( !ok ) 
    	{
    		m_refuseCount++;
    		//已有半数拒绝,不需要等待其它acceptor投票了,重新开始Propose阶段
    		//使用StartPropose(m_value)重置状态
    	
            //请完善下面逻辑
     		/**********Begin**********/
            if ( m_refuseCount > m_acceptorCount/2 ){
                // 重新开始投票阶段,将提案号自增
                m_value.serialNum += 5;
                StartPropose(m_value);
                return false;
            }
    	    /**********End**********/
    		//拒绝数不到一半
    		return true;
    	}
    
    	m_okCount++;
    	/*
    		没有必要检查分支:serialNum为null
    		因为serialNum>m_maxAcceptedSerialNum,与serialNum非0互为必要条件
    	*/
    	//如果已经有提议被接受,修改成已被接受的提议
    	//请完善下面逻辑
     	/**********Begin**********/
         
        if(lastAcceptValue.serialNum > m_maxAcceptedSerialNum){
            m_value.value = lastAcceptValue.value;
            m_maxAcceptedSerialNum = lastAcceptValue.serialNum;
            return true;
        }
    	/**********End**********/	
    
    
    
    
    
    	//如果自己的提议被接受
    	if ( m_okCount > m_acceptorCount / 2 ) 
    	{
    		m_okCount = 0;
    		m_proposeFinished = true;
    	}
    	return true;
    }
    
    bool Proposer::StartAccept()
    {
    	return m_proposeFinished;
    }
    
    bool Proposer::Accepted(bool ok)
    {
    	if ( !m_proposeFinished ) return true;//可能是上次第二阶段迟到的回应,直接忽略消息
    
    	if ( !ok ) 
    	{
    		m_refuseCount++;
    		//已有半数拒绝,不需要等待其它acceptor投票了,重新开始Propose阶段
    		//使用StartPropose(m_value)重置状态
    	    //请完善下面逻辑
            /**********Begin**********/
            if ( m_refuseCount > m_acceptorCount/2 ){
                // 重新开始投票阶段,将提案号自增
                m_value.serialNum += 5;
                StartPropose(m_value);
                return false;
            }
            /**********End**********/
     		
    		return true;
    	}
    
    	m_okCount++;
    	if ( m_okCount > m_acceptorCount / 2 ) m_isAgree = true;
    
    	return true;
    }
    
    bool Proposer::IsAgree()
    {
    	return m_isAgree;
    }
    
    }
    

    2.3 acceptor.cpp

    模拟接受者的主要流程

    #include "Acceptor.h"
    
    
    namespace paxos
    {
    
    
    Acceptor::Acceptor(void)
    {
    	m_maxSerialNum = 0;
    	m_lastAcceptValue.serialNum = 0;
    	m_lastAcceptValue.value = 0;
    }
    
    Acceptor::~Acceptor(void)
    {
    }
    /***
    //投票者
    class Acceptor
    {
    public:
    	Acceptor(void);
    	virtual ~Acceptor(void);
    
    	//同意投票
    	bool Propose(unsigned int serialNum, PROPOSAL &lastAcceptValue);
    	//接受提议
    	bool Accept(PROPOSAL &value);
    
    private:
    	PROPOSAL		m_lastAcceptValue;//最后接受的提议
    	unsigned int	m_maxSerialNum;//Propose提交的最大流水号
    };
    
    
    	//提议数据结构
    	typedef struct PROPOSAL
    	{
    		unsigned int	serialNum;//流水号,1开始递增,保证全局唯一
    		unsigned int	value;//提议内容
    	}PROPOSAL;
    
    ***/
    bool Acceptor::Propose(unsigned int serialNum, PROPOSAL &lastAcceptValue)
    {
    	if ( 0 == serialNum ) return false;
    	//提议不通过
    	if ( m_maxSerialNum > serialNum ) return false;
    	//接受提议
        //请完善下面逻辑
    
    	/**********Begin**********/
        //m_lastAcceptValue = lastAcceptValue;
        // If n is higher than every previous proposal number received, from any of the Proposers, by the Acceptor, 
        // then the Acceptor must return a message, which we call a "Promise", to the Proposer, to ignore all future 
        // proposals having a number less than n. If the Acceptor accepted a proposal at some point in the past, it 
        // must include the previous proposal number, say m, and the corresponding accepted value, say w, in its response to the Proposer.
        m_maxSerialNum = serialNum;
        
        lastAcceptValue = m_lastAcceptValue; // which contains m -> w
    	/**********End**********/
    
    	return true;
    }
    
    bool Acceptor::Accept(PROPOSAL &value)
    {
    	if ( 0 == value.serialNum ) return false;
    	//Acceptor又重新答应了其他提议
       //请完善下面逻辑
    	/**********Begin**********/
        if (m_maxSerialNum > value.serialNum ){
            return false;
        }
        // 然后接受新的提案
        m_lastAcceptValue = value;
    	/**********End**********/
    
        
    	//批准提议通过
        //请完善下面逻辑
        /**********Begin**********/
        m_maxSerialNum = value.serialNum;
    	/**********End**********/
    
    	return true;
    }
    
    }
    
    

    3 参考

    [1] https://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos
    [2] https://www.cs.rutgers.edu/~pxk/417/notes/paxos.html
    [3] https://github.com/HaHaJeff/Paxos/blob/master/basic_paxos.md

    展开全文
  • Paxos 算法详解(一)

    万次阅读 多人点赞 2020-05-24 13:52:59
    提到分布式算法,就不得不提 Paxos 算法,在过去几十年里,它基本上是分布式共识的代 名词,因为当前最常用的一批共识算法都是基于它改进的。比如,Fast Paxos 算法、 Cheap Paxos 算法、Raft 算法、ZAB 协议等等。 ...

    前言

    提到分布式算法,就不得不提 Paxos 算法,在过去几十年里,它基本上是分布式共识的代 名词,因为当前最常用的一批共识算法都是基于它改进的。比如,Fast Paxos 算法、 Cheap Paxos 算法、Raft 算法、ZAB 协议等等。

    兰伯特提出的 Paxos 算法包含 2 个部分:

    • 一个是 Basic Paxos 算法,描述的是多节点之间如何就某个值(提案 Value)达成共 识;
    • 另一个是 Multi-Paxos 思想,描述的是执行多个 Basic Paxos 实例,就一系列值达成共 识

    可因为兰伯特提到的 Multi-Paxos 思想,缺少代码实现的必要细节(比如怎么选举领导 者),所以在理解上比较难。

    Basic Paxos 是 Multi-Paxos 思想的核心,说白了,Multi-Paxos 就是多执行 几次 Basic Paxos

    思考题。

    假设我们要实现一个分布式集群,这个集群是由节点 A、B、C 组成,提供只读 KV 存储服 务。你应该知道,创建只读变量的时候,必须要对它进行赋值,而且这个值后续没办法修 改。因此一个节点创建只读变量后就不能再修改它了,所以所有节点必须要先对只读变量的 值达成共识,然后所有节点再一起创建这个只读变量。

    那么,当有多个客户端(比如客户端 1、2)访问这个系统,试图创建同一个只读变量(比 如 X),客户端 1 试图创建值为 3 的 X,客户端 2 试图创建值为 7 的 X,这样要如何达成 共识,实现各节点上 X 值的一致呢?带着这个问题,我们进入今天的学习。

    三种角色:

    为了帮助人们更好地理解 Basic Paxos 算法,兰伯特在 讲解时,也使用了一些独有而且比较重要的概念,提案、准备(Prepare)请求、接受 (Accept)请求、角色等等,其中最重要的就是“角色”。因为角色是对 Basic Paxos 中 最核心的三个功能的抽象,比如,由接受者(Acceptor)对提议的值进行投票,并存储接 受的值。

    他们之间的关系如下:
    在这里插入图片描述

    提议者(Proposer):提议一个值,用于投票表决。为了方便演示,你可以把图 1 中的 客户端 1 和 2 看作是提议者。但在绝大多数场景中,集群中收到客户端请求的节点,才 是提议者(图 1 这个架构,是为了方便演示算法原理)。这样做的好处是,对业务代码 没有入侵性,也就是说,我们不需要在业务代码中实现算法逻辑,就可以像使用数据库 一样访问后端的数据。
    接受者(Acceptor):对每个提议的值进行投票,并存储接受的值,比如 A、B、C 三 个节点。 一般来说,集群中的所有节点都在扮演接受者的角色,参与共识协商,并接受 和存储数据。

    讲到这儿,你可能会有疑惑:前面不是说接收客户端请求的节点是提议者吗?这里怎么又是 接受者呢?这是因为一个节点(或进程)可以身兼多个角色。想象一下,一个 3 节点的集 群,1 个节点收到了请求,那么该节点将作为提议者发起二阶段提交,然后这个节点和另外 2 个节点一起作为接受者进行共识协商,就像下图的样子:
    在这里插入图片描述

    学习者(Learner):被告知投票的结果,接受达成共识的值,存储保存,不参与投票的 过程。一般来说,学习者是数据备份节点,比如“Master-Slave”模型中的 Slave,被 动地接受数据,容灾备份。

    这三种角色,在本质上代表的是三种功能:

    • 提议者代表的是接入和协调功能,收到客户端请求后,发起二阶段提交,进行共识协 商;
    • 接受者代表投票协商和存储数据,对提议的值进行投票,并接受达成共识的值,存储保 存;
    • 学习者代表存储数据,不参与共识协商,只接受达成共识的值,存储保存。

    在 Basic Paxos 中,兰伯特也使用提案代表一个提议。不过在提案中, 除了提案编号,还包含了提议值。为了方便演示,我使用[n, v]表示一个提案,其中 n 为提 案编号,v 为提议值。

    我想强调一下,整个共识协商是分 2 个阶段进行的(也就是我在 03 讲提到的二阶段提 交)。那么具体要如何协商呢?

    我们假设客户端 1 的提案编号为 1,客户端 2 的提案编号为 5,并假设节点 A、B 先收到 来自客户端 1 的准备请求,节点 C 先收到来自客户端 2 的准备请求。

    准备(Prepare)阶段

    先来看第一个阶段,首先客户端 1、2 作为提议者,分别向所有接受者发送包含提案编号的 准备请求
    在这里插入图片描述
    你要注意,在准备请求中是不需要指定提议的值的,只需要携带提案编号就可以了,这是很 多同学容易产生误解的地方。

    接着,当节点 A、B 收到提案编号为 1 的准备请求,节点 C 收到提案编号为 5 的准备请求 后,将进行这样的处理:
    在这里插入图片描述
    由于之前没有通过任何提案,所以节点 A、B 将返回一个 “尚无提案”的响应。也就是 说节点 A 和 B 在告诉提议者,我之前没有通过任何提案呢,并承诺以后不再响应提案编 号小于等于 1 的准备请求,不会通过编号小于 1 的提案。

    节点 C 也是如此,它将返回一个 “尚无提案”的响应,并承诺以后不再响应提案编号小 于等于 5 的准备请求,不会通过编号小于 5 的提案。

    另外,当节点 A、B 收到提案编号为 5 的准备请求,和节点 C 收到提案编号为 1 的准备请 求的时候,将进行这样的处理过程:
    在这里插入图片描述
    当节点 A、B 收到提案编号为 5 的准备请求的时候,因为提案编号 5 大于它们之前响应 的准备请求的提案编号 1,而且两个节点都没有通过任何提案,所以它将返回一个 “尚 无提案”的响应,并承诺以后不再响应提案编号小于等于 5 的准备请求,不会通过编号 小于 5 的提案。

    当节点 C 收到提案编号为 1 的准备请求的时候,由于提案编号 1 小于它之前响应的准备 请求的提案编号 5,所以丢弃该准备请求,不做响应。

    接受(Accept)阶段

    第二个阶段也就是接受阶段,首先客户端 1、2 在收到大多数节点的准备响应之后,会分别 发送接受请求:
    在这里插入图片描述
    当客户端 1 收到大多数的接受者(节点 A、B)的准备响应后,根据响应中提案编号最大 的提案的值,设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空 (也就是图 5 中的“尚无提案”),所以就把自己的提议值 3 作为提案的值,发送接受 请求[1, 3]。

    当客户端 2 收到大多数的接受者的准备响应后(节点 A、B 和节点 C),根据响应中提 案编号最大的提案的值,来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备 响应中都为空(也就是图 5 和图 6 中的“尚无提案”),所以就把自己的提议值 7 作为 提案的值,发送接受请求[5, 7]。

    当三个节点收到 2 个客户端的接受请求时,会进行这样的处理:

    在这里插入图片描述
    当节点 A、B、C 收到接受请求[1, 3]的时候,由于提案的提案编号 1 小于三个节点承诺 能通过的提案的最小提案编号 5,所以提案[1, 3]将被拒绝。

    当节点 A、B、C 收到接受请求[5, 7]的时候,由于提案的提案编号 5 不小于三个节点承 诺能通过的提案的最小提案编号 5,所以就通过提案[5, 7],也就是接受了值 7,三个节 点就 X 值为 7 达成了共识。

    通过上面的演示过程,你可以看到,最终各节点就 X 的值达成了共识。那么在这里我还想 强调一下,Basic Paxos 的容错能力,源自“大多数”的约定,你可以这么理解:当少于一半的节点出现故障的时候,共识协商仍然在正常工作

    展开全文
  • 本篇文章将开启对分布式协调服务zk的学习,目前规划是从理论基础开始逐步到源码解析,深入学习...Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的、具有高 容错性的一致性算法。Google ...
  • Paxos算法详解与Zookeeper分析

    千次阅读 2016-09-06 20:53:54
    Paxos算法 1.1 基本定义 算法中的参与者主要分为三个角色,同时每个参与者又可兼领多个角色: ⑴proposer 提出提案,提案信息包括提案编号和提议的value; ⑵acceptor 收到提案后可以接受(accept)提案; ⑶...
  • [译] Paxos算法详解

    2015-06-11 13:49:00
    Paxos算法被用来实现一个容错的分布式系统,一直以来以晦涩难懂著称。这可能是因为该算法最开始使用希腊文表述的。事实上,它是所有分布式算法中最简单易懂的。Paxos算法的本质其实就是一个共识算法(我不太同意国内...
  • 提到分布式算法,就不得不提 Paxos 算法,在过去几十年里,它基本上是分布式共识的代 名词,因为当前最常用的一批共识算法都是基于它改进的。比如,Fast Paxos 算法、 Cheap Paxos 算法、Raft 算法、ZAB 协议等等。 ...
  • PAXOS算法详解2

    2014-02-11 11:31:40
    Paxos算法描述的过程是发生在“一次选举”的过程中,这个在前面也提到过,实际Paxos算法执行是一轮接一轮,每轮还有个专有称呼:instance(翻译成中文有点怪),每instance都选出一个唯一的value。   在...
  • Paxos算法细节详解--通过现实世界描述算法
  • 详解Paxos算法

    2020-02-23 14:09:43
    Paxos算法是什么? Paxos算法是莱斯利.兰伯特1990年提出的一种基于消息传递的、具有高容错性的一致性算法。 算法描述 算法角色描述 Paxos算法中有三种角色,分别具有三种不同的行为,一个进程可能同时充当多个角色。...
  • 文章为本人对paxos算法(basic paxos)的理解,水平有限难免有理解不到位的地方,欢迎批评。   一、简介 1.1Paxos算法处理的问题  Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。...
  • Paxos算法细节详解(一)

    2019-01-03 14:46:00
    最近研究paxos算法,看了许多相关的文章,概念还是很模糊,觉得还是没有掌握paxos算法的精髓,所以花了3天时间分析了libpaxos3的所有代码,此代码可以从https://bitbucket.org/sciascid/libpaxos下载。对paxos算法有...
  • 文章为本人对paxos算法(basic paxos)的理解,水平有限难免有理解不到位的地方,欢迎批评。   一、简介 1.1Paxos算法处理的问题  Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型...
  • 最近研究paxos算法,看了许多相关的文章,概念还是很模糊,觉得还是没有掌握paxos算法的精髓,所以花了3天时间分析了libpaxos3的所有代码,此代码可以从https://bitbucket.org/sciascid/libpaxos 下载。对paxos算法...
  • Paxos算法细节详解(一)--通过现实世界描述算法 Paxos分析 最近研究paxos算法,看了许多相关的文章,概念还是很模糊,觉得还是没有掌握paxos算法的精髓,所以花了3天时间分析了libpaxos3的所有代码,此代码...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,559
精华内容 1,023
关键字:

paxos算法详解