精华内容
下载资源
问答
  • paxos算法概念入门

    2016-12-11 11:44:45
    看了paxos算法一些文章,特别是复杂数据计算的一些,越看越不懂了。后来找到几个通俗故事来介绍原理的,理解了很多。记录下来,后面再找实际的例子试试。 故事1 在通过一则故事来学习paxos的算法的...

    看了paxos算法一些文章,特别是复杂数据计算的一些,越看越不懂了。后来找到几个通俗故事来介绍原理的,理解了很多。记录下来,后面再找实际的例子试试。


    故事1


    在通过一则故事来学习paxos的算法的流程(2阶段提交),有2个Client(老板,老板之间是竞争关系)和3个Acceptor(政府官员):

    1. 现在需要对一项议题来进行paxos过程,议题是“A项目我要中标!”,这里的“我”指每个带着他的秘书Proposer的Client老板。
    2. Proposer当然听老板的话了,赶紧带着议题和现金去找Acceptor政府官员。
    3. 作为政府官员,当然想谁给的钱多就把项目给谁。
    4. Proposer-1小姐带着现金同时找到了Acceptor-1~Acceptor-3官员,1与2号官员分别收取了10比特币,找到第3号官员时,没想到遭到了3号官员的鄙视,3号官员告诉她,Proposer-2给了11比特币。不过没关系,Proposer-1已经得到了1,2两个官员的认可,形成了多数派(如果没有形成多数派,Proposer-1会去银行提款在来找官员们给每人20比特币,这个过程一直重复每次+10比特币,直到多数派的形成),满意的找老板复命去了,但是此时Proposer-2保镖找到了1,2号官员,分别给了他们11比特币,1,2号官员的态度立刻转变,都说Proposer-2的老板懂事,这下子Proposer-2放心了,搞定了3个官员,找老板复命去了,当然这个过程是第一阶段提交,只是官员们初步接受贿赂而已。故事中的比特币是编号,议题是value。

        这个过程保证了在某一时刻,某一个proposer的议题会形成一个多数派进行初步支持;

     ===============华丽的分割线,第一阶段结束================

      5. 现在进入第二阶段提交,现在proposer-1小姐使用分身术(多线程并发)分了3个自己分别去找3位官员,最先找到了1号官员签合同,遭到了1号官员的鄙视,1号官员告诉他proposer-2先生给了他11比特币,因为上一条规则的性质proposer-1小姐知道proposer-2第一阶段在她之后又形成了多数派(至少有2位官员的赃款被更新了);此时她赶紧去提款准备重新贿赂这3个官员(重新进入第一阶段),每人20比特币。刚给1号官员20比特币, 1号官员很高兴初步接受了议题,还没来得及见到2,3号官员的时候

    这时proposer-2先生也使用分身术分别找3位官员(注意这里是proposer-2的第二阶段),被第1号官员拒绝了告诉他收到了20比特币,第2,3号官员顺利签了合同,这时2,3号官员记录client-2老板用了11比特币中标,因为形成了多数派,所以最终接受了Client2老板中标这个议题,对于proposer-2先生已经出色的完成了工作;

    这时proposer-1小姐找到了2号官员,官员告诉她合同已经签了,将合同给她看,proposer-1小姐是一个没有什么职业操守的聪明人,觉得跟Client1老板混没什么前途,所以将自己的议题修改为“Client2老板中标”,并且给了2号官员20比特币,这样形成了一个多数派。顺利的再次进入第二阶段。由于此时没有人竞争了,顺利的找3位官员签合同,3位官员看到议题与上次一次的合同是一致的,所以最终接受了,形成了多数派,proposer-1小姐跳槽到Client2老板的公司去了。

    ===============华丽的分割线,第二阶段结束===============

      Paxos过程结束了,这样,一致性得到了保证,算法运行到最后所有的proposer都投“client2中标”所有的acceptor都接受这个议题,也就是说在最初的第二阶段,议题是先入为主的,谁先占了先机,后面的proposer在第一阶段就会学习到这个议题而修改自己本身的议题,因为这样没职业操守,才能让一致性得到保证,这就是paxos算法的一个过程。原来paxos算法里的角色都是这样的不靠谱,不过没关系,结果靠谱就可以了。该算法就是为了追求结果的一致性。





    展开全文
  • Paxos算法

    2020-10-02 22:50:25
    文章目录paxos算法历史paxos算法介绍1.错误模型2. paxos名词3. basic paxos4. mutil paxos5. paxos有其它变种paxos算法实现1.引入库 paxos算法历史 paxos算法是lamport大佬在1998年第一次发布在ACM上的论文,期间...

    paxos算法历史

    paxos算法是lamport大佬在1989年第一次发布在ACM上的论文,期间经过了7年时间。然后因为原文大家觉得有点不太好理解,于是在2001年总结上一篇论文,以精简和计算机术语发布出来。

    paxos算法介绍

    Paxos常被误称为“一致性算法”。但是“一致性(consistency)”和“共识(consensus)”并不是同一个概念。Paxos是一个共识(consensus)算法。

    1.错误模型

    不可靠网络、非拜占庭错误

    2. safety and liveness

    safety:
    a. 只有一个被提议的值被chosen
    b. 单一值被chosen
    c. 一个进程不会知道某个被chosen的值,直到它被chosen

    liveness:
    a. 最终一定有个值被chosen
    b. 如果一个值被chosen,则某个进程最终一定会知道这个值

    3. FLP

    validity:只能被提议的值被accepted
    agreement:只能有一个值被accepted
    termination:不保证能中止(多proposer的情况)

    4. paxos名词

    1. proposer:发起一个提案
    2. acceptor:接收proposer的提案,通过多数表决通过提案
    3. learner:接收acceptor通过的提案

    5. basic paxos

    一次paxos run是对一个值达成共识

    6. mutil paxos

    当需要对多个值达成共识时需要执行多次paxos run

    7. paxos有其它变种

    fast-paxos、cheap-paxos、generalized-paxos、byzantine-paxos

    paxos算法详解

    1. basic paxos两阶段

    paxos本质是一个两阶段协议

    阶段一:
    phase1a:prepare
    proposer接收客户端的请求,处理成proposal提交给acceptor,每个proposal包含一个唯一递增的id

    phase1b:promise
    在acceptor收到proposal后,检查是否收到比当前id大的proposal,如果没有则回复proposer成功promised,否则失败

    阶段二:
    phase2a:accept
    当proposer收到大多数的acceptor成功回复的请求,proposer再发起一个accept(id, value)

    phase2b:accepted
    acceptor再比较此accept(id, value),如果是当前phase1确认的最大id,则回复accepted成功,否则失败

    此两阶段是实现对一个值达成共识,如果要继续对其他值达成共识则就需要mutil paxos

    2. mutil paxos介绍

    当需要连续对多个值达成共识时则需要mutil paxos,此算法最简单的就是将basic paxos的两阶段对每个需要达成共识的值执行一次,但是这样发送消息的代价太大,因此衍生出如果proposer不变则执行了一次阶段以后,后续不再执行阶段二,并且为了达到算法的中止,proposer也变成了一个。

    目前所有paxos的实现都是基于mutil paxos,并且其他很多共识算法都是参考mutil paxos,比如raft、zab、vs等

    paxos推导

    满足安全性的条件:

    1. B1:Each ballot in B(Beta) has a unique ballot number.
    2. B2:The quorums of any two ballots in B(Beta) have at least one priest in common.
    3. B3:For every ballot B in B(Beta), if any priest in B’s quorum voted in an earlier ballot in B(Beta), then the decree of B equals the decree of the latest of those earlier ballots

    以上条件推出两条定理

    1. If B1(B),B2(B),andB3(B) hold, then((Bqrm⊆Bvot)∧(B′bal>Bbal))⇒(B′dec=Bdec) for any B,B′ in B.
    2. Let b be a ballot number and Q a set of priests such that b>Bbal and Q ∩ Bqrm=∅ for all B∈B.If B1(B),B2(B),and B3(B) hold, then there is a ballot B′ with B′bal = b and B′qrm=B′vot=Q such that B1(B∪{B′}),B2(B∪{B′}), and B3(B∪{B′}) hold

    设计满足以上B1,B2,B3条件的流程(step 1,2,3,4,5,6)
    The Preliminary Protocol -> The Basic Protocol -> The Complete Synod Protocol -> The Multi-Decree Parliament

    展开全文
  • Paxos 算法

    2021-08-09 08:40:02
    所谓的 Paxos 算法,是为了解决来自客户端的值被发送到集群中的任意一点,而后集群中的所有节点为该值达成共识的一种协调算法。同时这个值伴随一个版本号,可以保证消息是有顺序的,该顺序在集群中任何一点都是一致...

    所谓的 Paxos 算法,是为了解决来自客户端的值被发送到集群中的任意一点,而后集群中的所有节点为该值达成共识的一种协调算法。同时这个值伴随一个版本号,可以保证消息是有顺序的,该顺序在集群中任何一点都是一致的。

    基本的 Paxos 算法非常简单,它由三个角色组成。

    ProposerProposer 可以有多个,Proposer 提出议案(value)。所谓 value,可以是任何操作,比如“设置某个变量的值为 value”。不同的 Proposer 可以提出不同的 value。但对同一轮 Paxos 过程,最多只有一个 value 被批准。

    AcceptorAcceptor 有 N 个,Proposer 提出的 value 必须获得 Quorum 的 Acceptor 批准后才能通过。Acceptor 之间完全对等独立。

    Learner:上面提到只要 Quorum 的 Accpetor 通过即可获得通过,那么 Learner 角色的目的就是把通过的确定性取值同步给其他未确定的 Acceptor。

    这三个角色其实已经描述了一个值被提交的整个过程。其实基本的 Paxos 只是理论模型,因为在真实场景下,我们需要处理许多连续的值,并且这些值都是并发的。如果完全执行上面描述的过程,那性能消耗是任何生产系统都无法承受的,因此我们一般使用的是 Multi-Paxos。

    Multi-Paxos 可以并发执行多个 Paxos 协议,它优化的重点是把 Propose 阶段进行了合并,这就引入了一个 Leader 的角色,也就是领导节点。而后读写全部由 Leader 处理,同时这里与 ZAB 类似,Leader 也有任期的概念,Leader 与其他节点之间也用心跳进行互相探活。是不是感觉有那个味道了?后面我就会比较两者的异同。

    另外 Multi-Paxos 引入了两个重要的概念:replicated log 和 state snapshot

    replicated log:值被提交后写入到日志中。这种日志结构除了提供持久化存储外,更重要的是保证了消息保存的顺序性。而 Paxos 算法的目标是保证每个节点该日志内容的强一致性。

    state snapshot:由于日志结构保存了所有值,随着时间推移,日志会越来越大。故算法实现了一种状态快照,可以保存最新的日志消息。当快照生成后,我们就可以安全删除快照之前的日志了。

    总结

    Paxos 算法解决来自客户端的值被发送到集群中的任意一点,而后集群中的所有节点为该值达成共识的一种协调算法

    展开全文
  • Paxos算法推导

    2020-06-26 00:33:12
    文章目录Paxos算法推导Paxos定义Paxos算法出现所解决的问题Basic Paxos的需求Basic Paxos的组件推导过程单Acceptor多个AcceptorProposer生成提案Acceptor接受提案Basic Paxos算法描述如果保证Basic Paxos算法的...

    Paxos算法推导


    关于一致性算法,看大家的文章基本上都是认为Raft比Paxos要好理解很多,事实上在学习的过程中也的确是这样。Raft学习理解完毕后我也来学习一下Paxos算法。毕竟如果这个世界上只有一种一致性算法,那么一定是Paxos。Paxos算法在分布式领域具有无可撼动的地位,缺点就是难以理解,工程实现也很难。

    为了描述Paxos,Lamport虚拟了一个叫做Paxos的希腊城邦,这个岛按照议会民主制的政治模式制定法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员、议长或者是传递纸条的服务员都不能承诺别人在需要时一定会及时出现,也无法承诺批准决议或传递消息的时间。Paxos算法的场景中,我们假设不出现拜占庭将军问题,但是会出现网络丢失消息,或者存在消息延迟的情况,就是说可能会存在到达顺序和发送顺序不一样的情况。但是只要等待足够的时间,消息就会被传到。另外,Paxos岛上的议员不会反对其他议员提出的决议,也就是说大家的意愿是尽快形成一致的决议,而不是执着于让自己提出的决议通过。

    Paxos定义

    Paxos算法是基于消息传递且具有高度容错特性的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一

    下面我就把推导的一步步过程通过这篇文章记录下来,也是为了加深自己的理解,有问题的地方大家可以随时指正。

    Paxos算法出现所解决的问题

    在常见的分布式系统中,总会发生机器宕机或者网络异常等情况,对应到消息传递上就是会导致消息的延迟、丢失、重复、乱序,网络分区等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常,都不会破坏系统的一致性。

    Paxos可以拆分为两个问题:Basic Paxos、Multi Paxos,其中Basic Paxos就是我们经常提到的Paxos。假设有一组服务器,其中有些服务器会提议特定的值。Basic Paxos的目的是挑选这些值中唯一的一个,这个被选定的值成为chosen。Basic Paxos只挑选一个唯一值,它不会挑选第二个值,也不会更改它的选择。

    而对于日志,会存在很多条日志记录,所以就需要为多条日志创建多个Basic Paxos实例,一条日志对应一个Basic Paxos实例,这就是Multi Paxos。

    这篇文章主要是对Basic Paxos的推导过程记录。

    Basic Paxos的需求

    假设有一组可以提出提案(proposal)的进程集合。Basic Paxos需要保证提出的这么多proposal中,最终只有一个value被选定(value在提案proposal中)。如果没有proposal提出,就不该有value被选定。如果一个value被选定,那么所有进程都应该能learn到这个被选定的value。对于Basic Paxos,有如下两个需求:

    1. 安全性(Safety):
      • 只有被提出的value才能被选定
      • 只有一个value被选定
      • 如果某个进程认为某个value被选定了,那么这个value必须是真的被选定的那个
    2. 可用性(Liveness):
      • 最终一个会选定某个提议的值
      • 服务器通过学习,最终会知道value已经被选定
      • 可用性的前提是大多数的服务器是活着的,并能在合理的时间内通讯。

    Basic Paxos的组件

    1. Proposer:提议者是主动性的,它们会主动做一些事情,通常它们会接收来自客户端的请求,获得特定的选定值,然后它会传递这个值,并让集群里的其他服务器也达成一致选择这个值。
    2. Acceptor:接受者是被动的,它们简单地接收来自于Proposer的请求并作出响应,可以把这种响应当成投票,Proposer会尝试获得Acceptor所投的多数票,Acceptor会存储多个状态,比如可能被选定或者未被选定的值,以及响应的投票结果。
    3. Learners:称为学习者,这些节点想要知道被选定的值。Learner是处于Acceptor内的

    在具体的实现中,一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。还有一个很重要的概念叫Proposal提案,最终要达成一致的value就在提案里。

    Proposer、Acceptor、Learner分别在什么情况下才认为某个value被选定呢?

    • Proposer:只要Proposer发出的提案被Acceptor接受(半数以上的Acceptor同意才行),Proposer就认为该提案里的value被选定了。
    • Acceptor:只要Acceptor接受了某个提案,Acceptor就认为该提案里的value被选定了。
    • Learner:Acceptor告诉Learner哪个value被选定,Learner就认为那个value被选定。

    推导过程

    我们先假设不同组件之间可以通过发送消息来进行通信,那么:

    • 每个组件以任意的速度执行,可能因出错而停止,也可能会重启。一个value被选定后,所有的组件可能失败然后重启,除非那些失败后重启的组件能记录某些信息,否则等他们重启后无法确定被选定的value
    • 消息在传递过程中可能出现任意时长的延迟,可能会重复,也可能丢失,但是消息不会被篡改

    我们先从最简单的方案开始探讨:

    单Acceptor

    假设只有一个Acceptor,多个Proposer,只要Acceptor接受它收到的第一个提案,则该提案被选定,该提案里的value就是被选定的value。这样就可以保证只有一个value会被选定。但是这样的系统可用性很低,一旦唯一的Acceptor宕机,整个系统就不可用。因此Acceptor必须要有多个。

    多个Acceptor

    如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢?

    如果我们希望即使只有一个Proposer提出了一个value,该value也最终被选定。那么就可以得到下面的约束:

    P1:一个Acceptor必须接受它收到的第一个提案Proposal

    但是这会导致出现新的问题:如果每个Proposer分别提出不同的value,发给不同的Acceptor。根据P1,Acceptor分别接受自己收到的value,就会导致不同的value被选定,出现不一致的情况。

    这是因为一个提案只要被一个Acceptor接受,则该提案的value就被选定了,这就导致了上面不一致现象的发生。因此我们添加一个规定:

    一个提案被选定需要被半数以上的Acceptor接受

    这个规定又暗示了“一个Acceptor必须能够接受不止一个提案”,不然可能导致最终没有value被选定。比如像下图的情况,就会很尴尬了。v1、v2、v3都没有被选定,因为它们都只被一个Acceptor接受。

    在这里插入图片描述

    那么提案中不能仅仅包含value,于是重新设计提案,给每个提案加上一个提案编号,表示提案被提出的顺序。令提案=提案编号+value。

    虽然允许多个提案被选定,但是必须保证所有被选定的提案都具有相同的value值,否则又会出现不一致的情况。于是新的约束如下:

    P2:如果某个value为v的提案被选定了,那么每个编号更高的被选定提案的value也必须是v。

    而一个提案只有被Acceptor接受才可能被选定,所以我们可以进一步加强P2的约束条件,形成P2a。

    P2a:如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value也必须是v。

    只要满足了P2a,就能满足P2.

    但是目前的约束条件还不够强,考虑下面的情况:

    假设总共有5个Acceptor,Proposer2提出[M1,V1]的提案,Acceptor2-5(已达majority)均接受了该提案,于是对于Acceptor2-5和Proposer2来说,它们都认为V1被选定了。Acceptor1刚从宕机状态恢复且Acceptor1没有收到过任何提案,此时Proposer1向Acceptor1发送了[M2,V2]的提案(V2!=V1且M2>M1),对于Acceptor1来讲,这是它收到的第一个提案,根据P1,Acceptor1必须接受该提案,这样Acceptor1就成功接受了Proposer1的提案[M2,V2],Acceptor1也认为V2被选定。这里出现了两个问题:

    • Acceptor1认为V2被选定,Acceptor2-5和Proposer2认为V1被选定,这里出现不一致情况。
    • V1被选定了,但是编号更高的被Acceptor1接受的提案[M2,V2]的value是V2,V2!=V1。这就是和P2a矛盾。

    因此我们还要在P2a的条件上进一步强化约束,P2a是对Acceptor接受的提案约束,但是提案是Proposer提出的,所以我们对Proposer提出的提案进行约束,得到P2b:

    P2b:如果某个value为v的提案被选定了,那么之后任何Proposer提出的编号更高的提案的value也必须是v。

    那我们如何保证Proposer提出的编号更高的提案中的value都是v呢?我们再进行约束:

    P2c:对于任意的M和V,如果提案[M,V]被提出,那么存在一个半数以上的Acceptor组成的集合S,满足以下两个条件中的任意一个:

    • S中每个Acceptor都没有接受过编号小于M的提案
    • S中Acceptor接受过的最大编号的提案的value为V

    Proposer生成提案

    为了满足P2b,这里涉及到一个重要的问题:Proposer生成提案之前,应该先去学习已经被选定或者可能被选定的value,然后以该value作为自己提出的提案的value。如果没有value被选定,Proposer才可以自己决定value的值,这样才能满足一致性。这个学习阶段在Basic Paxos算法中是通过Prepare请求实现的。

    提案生成算法如下:

    1. Proposer选择一个新的提案编号M,然后向某个Acceptor集合(半数以上)发送请求,要求该集合中的每个Acceptor做出如下响应:
      • 向Proposer承诺保证不再接受任何编号小于M的提案
      • 如果Acceptor已经接受过提案,那么就向Proposer响应已经接受过的编号小于M的最大编号的提案

    我们将该请求称为编号M的Prepare请求。如果Proposer收到了半数以上Acceptor的响应,那么它就可以生成编号为M,value为V的提案[M,V]。这里的V是所有的响应中编号最大的提案的value。如果所有的响应中都没有提案,那么此时V就可以由Proposer自己选择。在生成提案后,Proposer将该提案发送给半数以上的Acceptor集合,并期望这些Acceptor集合能接受该提案,我们称为Accept请求(此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合)

    Acceptor接受提案

    Acceptor可以忽略任何请求(包括Prepare和Accept请求)而不用担心破坏算法的安全性。因此,我们这里要讨论的是什么时候Acceptor可以响应一个请求。

    我们对Acceptor接受提案做出如下约束:

    P1a:一个Acceptor只要尚未响应过任何编号大于M的Prepare请求,那么它就可以接受这个编号为M的提案。

    如果Acceptor收到一个编号为M的Prepare请求,在此之前它已经响应过编号大于M的Prepare请求。根据P1a,该Acceptor不可能接受编号为M的提案。因此该Acceptor可以忽略编号为M的Prepare请求。

    因此一个Acceptor需要保存两个信息:

    1. 已接受的编号最大的提案
    2. 已响应的请求的最大编号

    Basic Paxos算法描述

    1. Basics

      • 提案编号(n)=(轮次round number,服务器ID)
      • T:在领导者选举算法中使用的固定超时时间
      • α:Multi-Paxos中的并发限制

      1.1 领导选举算法

      • 每隔T毫秒向其他服务器发送空的心跳消息。
      • 如果一个服务器在最近的2T毫秒内没有收到某一具有更高ID的服务器的心跳消息,则它充当领导者。

      上面的几条有些内容我们可能还没涉及到,这里面都是Multi-Paxos的内容。下一篇文章我对Multi-Paxos做个推导记录。

    2. Basic Paxos

      2.1 每台服务器的持久状态

      • minProposal:此服务器将接受的最小提案的编号,如果从未收到Prepare请求,则为0
      • acceptedProposal:服务器已接受的最后一个提议的编号,如果从未接受任何提案,则为0
      • acceptedValue:服务器已接受的最新提案中的值,如果从未接受提案,则为null
      • maxRound:服务器已知的最大轮数

      2.2 Messages

      2.2.1 Prepare阶段

      请求字段:

      • n:新的提案编号

      Acceptor在收到Prepare请求后, 如果n>=minproposal,Acceptor将minProposal设置为n。该响应构成了拒绝将来提案编号小于n的Accept消息的承诺,即承诺不会再接受一个提案编号小于n的请求。

      响应字段:

      • acceptedProposal:Acceptor的acceptedProposal(当前接受的具有最高编号的提案的编号)
      • acceptedValue:Acceptor的acceptedValue(当前接受的具有最高编号的提案的值)

      2.2.2 Accept

      请求字段:

      • n:与Prepare阶段中使用的提案编号相同
      • v:一个值,可以是Prepare阶段所有响应中编号最大的值,如果没有,则来自客户端请求

      Acceptor收到Accept请求后,如果n>=minProposal,则:

      • 设置acceptedProposal=n
      • 设置acceptedValue=v
      • 设置minProposal=n

      响应字段:

      • n:Acceptor的minProposal

      2.3 Proposer提议者算法

      1. 设n为新的提案编号(增加并持久化maxRound)
      2. 广播Prepare(n)请求给所有Acceptor
      3. 当收到来自大多数Acceptor的Prepare响应(reply.acceptedProposal,reply.acceptedValue):
        • 按如下方式设置v:如果这些reponse中的最大reply.acceptedProposal不为0,则使用其对应的reply.acceptedValue。否则使用inputValue
      4. 广播Accept(n,v)请求
      5. 当收到Accept的response(reply.n):
        • 如果reply.n>n,则设置maxRound从n开始,并从步骤1重新执行
      6. 等待直到接收到来自大多数接受者的n的响应
      7. 最终选定v

    如果保证Basic Paxos算法的Liveness

    竞争提案时可能会导致死锁

    在这里插入图片描述

    假设服务器S1成功接收到请求,并处于Prepare阶段(P 3.1)。在接受值X之前(A 3.1X),另外一个服务器S5正处于它的Prepare阶段(P 3.5),这会阻止前序值的接受(A 3.1X)。然后S1会重新选择提案编号并再次开始提案过程(P 4.1),假设它正进入了第二轮的Prepare阶段,在接受值之前,服务器S5正试图完成接受值的选定Y(A 3.5 Y),不过此时因为(P 4.1)的编号高于(A 3.5 Y),所以它阻止了(A 3.5 Y)的Accept,这样S5的提议就失败了,然后S5又重新开始下一轮的提案,如此往复,这个过程无限循环就造成了死锁。

    为了不发生死锁,Basic Paxos需要通过某种补充机制来保证它可以正确运行。一个简单的方式是让服务器等待一个random time,如果发生接受失败的情况,必须返回重新开始。在重新开始之前等待一会,让提案有机会完成。话说这个机制真的很像Raft leader election阶段的选举失败再Re-election的机制,都是随机等待一段时间。可以让集群下服务器随机的延迟,从而避免所有服务器都处于相同的等待时间下。在Multi-Paxos下,会有些不同,会采取一种leader election的机制,保证在同一时间下只有一个Proposer在工作。

    展开全文
  • 图解 Paxos 算法

    2021-02-11 10:14:48
    Paxos 算法由 Leslie Lamport 在 1989 年提出的一个分布式共识算法Paxos 算法较难理解,本文尝试以图形化方案解释 Paxos 算法。 本文在很大篇幅参考了韩健极客时间的课程《分布式协议与算法》,有兴趣了解韩老师...
  • Paxos算法和Raft算法

    千次阅读 2020-09-30 15:31:10
    一、 Paxos算法 Paxos算法达成共识过程: 准备阶段: 接受阶段: 二、Raft算法 选举领导者的过程 本文是参考腾讯课堂fox老师的课程而写的笔记 一、 Paxos算法 Paxos算法是莱斯利·兰伯特(英语:Leslie ...
  • Paxos算法原理和过程解析

    万次阅读 多人点赞 2019-06-19 15:27:50
    我们了解了2PC和3PC之后,我们可以发现,无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题...Paxos算法是公认的晦涩,很难可能能将清楚,但是工程上也很难实现,所以有很多Paxos算法的工程实现,如...
  • Paxos算法介绍

    2017-03-05 22:01:54
    最近研究paxos算法,看了许多相关的文章,概念还是很模糊,觉得还是没有掌握paxos算法的精髓,所以花了3天时间分析了libpaxos3的所有代码,此代码可以从https://bitbucket.org/sciascid/libpaxos 下载。对paxos算法...
  • paxos算法

    千次阅读 2013-09-08 22:45:56
    Paxos算法1-算法形成理论 分类: 分布式算法2011-01-27 15:11 7862人阅读 评论(1) 收藏 举报 算法servernosqllessinsertc  Paxos算法的难理解与算法的知名度一样令人敬仰,从我个人的经历而言...
  • Paxos算法详解

    2016-10-14 17:02:44
    最近研究paxos算法,看了许多相关的文章,概念还是很模糊,觉得还是没有掌握paxos算法的精髓,所以花了3天时间分析了libpaxos3的所有代码,此代码可以从https://bitbucket.org/sciascid/libpaxos 下载。对paxos算法...
  • Paxos算法(一)- Basic Paxos

    千次阅读 2020-06-01 17:16:14
    抄的极客时间上的,因为我觉得他写的好,没必要再写一遍提到分布式算法,就不得不提 Paxos 算法,在过去几十年里,它基本上是分布式共识的代名词,因为当前最常用的一批共识算法都是基于它改进的。比如,Fast Paxos ...
  • Paxos算法 Paxos Made Simple

    千次阅读 2013-10-07 20:53:30
    Paxos算法 Paxos Made Simple Leslie Lamport 2001.11.1 简介 Paxos算法,纯文本方式描述,非常简单。 1 介绍 为 实现具有容错能力的分布式系统而提出的Paxos算法,曾被认为难以理解,可能因为对于大部分读者而言...
  • Paxos 算法详解(一)

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

    2019-02-26 14:13:38
    Paxos Paxos 这个算法是Leslie Lamport在1990年提出的一种基于... part-time parliament Paxos Made Simple里这样描述Paxos算法执行过程: prepare 阶段: proposer【申请人】 选择一个提案编号 n 并将 prepa...
  • 经典Paxos算法笔记

    2017-09-06 00:06:00
    现在将经典Paxos算法相关内容整理到博客上。 经典Paxos算法本身也并不是太难理解,Lamport从期望的结果出发,通过增强条件一步步反推,最终发掘出可以保证了系统一致性的Paxos算法。如果能仔细体会到这其中一步步的...
  • Paxos 算法浅析

    2016-07-19 17:28:20
    讲解 Paxos 算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,416
精华内容 4,166
关键字:

paxos算法相关概念