精华内容
下载资源
问答
  • 2021-02-11 15:48:26

    简介

    Paxos 其实是一类能够解决分布式一致性问题的协议,它能够让分布式网络中的节点在出现错误时仍然保持一致;Leslie Lamport 提出的 Paxos 可以在没有恶意节点的前提下保证系统中节点的一致性,也是第一个被证明完备的共识算法,目前的完备的共识算法包括 Raft 本质上都是 Paxos 的变种。

    作为一类协议,Paxos 中包含 Basic Paxos、Multi-Paxos、Cheap Paxos 和其他的变种

    Basic Paxos

    Basic Paxos 是 Paxos 中最为基础的协议,每一个 Basic Paxos 的协议实例最终都会选择唯一一个结果;使用 Paxos 作为共识算法的分布式系统中,节点都会有三种身份,分别是 ProposerAcceptorLearner
    在这里插入图片描述

    我们在这里会忽略最后一种身份 Learner 简化协议的运行过程,便于读者理解;Paxos 的运行过程分为两个阶段,分别是准备阶段(Prepare)和接受阶段(Accept),当 Proposer 接收到来自客户端的请求时,就会进入如下流程:
    在这里插入图片描述

    在整个共识算法运行的过程中,Proposer 负责提出提案并向 Acceptor 分别发出两次 RPC 请求,Prepare 和 Accept;Acceptor 会根据其持有的信息 minProposal、acceptedProposal 和 acceptedValue 选择接受或者拒绝当前的提案,当某一个提案被过半数的 Acceptor 接受之后,我们就认为当前提案被整个集群接受了。
    在这里插入图片描述

    我们简单举一个例子介绍 Paxos 是如何在多个提案下保证最终能够达到一致性的,上述图片中 S1 和 S5 分别收到了来自客户端的请求 X 和 Y,S1 首先向 S2 和 S3 发出 Prepare RPC 和 Accept RPC,三个服务器都接受了 S1 的提案 X;在这之后,S5 向 S3 和 S4 服务器发出 Prepare(2.5) 的请求,S3 由于已经接受了 X,所以它会返回接受的提案和值 (1.1, X),这时服务器使用接收到的提案代替自己的提案 Y,重新向其他服务器发送 Accept(2.5, X) 的 RPC,最终所有的服务器会达成一致并选择相同的值。

    Multi-Paxos

    由于大多数的分布式集群都需要接受一系列的值,如果使用 Basic Paxos 来处理数据流,那么就会导致非常明显的性能损失(所有的用户要两两交互),而 Multi-Paxos 是前者的加强版,如果集群中的 Leader 是非常稳定的,那么我们往往不需要准备阶段的工作,这样就能够将 RPC 的数量减少一半。
    在这里插入图片描述

    上述图片中描述的就是稳定阶段 Multi-Paxos 的处理过程,S1 是整个集群的 Leader,当其他的服务器接收到来自客户端的请求时,都会将请求转发给 Leader 进行处理。
    当然,Leader 角色的出现自然会带来另一个问题,也就是 Leader 究竟应该如何选举,在 Paxos Made Simple 一文中并没有给出 Multi-Paxos 的具体实现方法和细节,所以不同 Multi-Paxos 的实现上总有各种各样细微的差别。
    在这里插入图片描述

    Paxos算法的解决的问题描述

    假设有一组可以提出(propose)value(value在提案Proposal里)的进程集合。一个一致性算法需要保证提出的这么多value中,只有一个value被选定(chosen)。如果没有value被提出,就不应该有value被选定。如果一个value被选定,那么所有进程都应该能学习(learn)到这个被选定的value。对于一致性算法,安全性(safaty)要求如下:
    • 只有被提出的value才能被选定。

    • 只有一个value被选定,并且如果某个进程认为某个value被选定了,那么这个value必 须是真的被选定的那个。

    • Paxos的目标:保证最终有一个value会被选定,当value被选定后,进程最终也能获取到被选定的value

    Paxos算法的过程

    第一阶段-prepare阶段

    • proposer选择一个提案编号(N),然后想半数以上的acceptor发送编号为N的提案。prepare(N)。这里的编号N只是一个数字,用于标记作用。真正的内容是里面的value。

    • 如果一个Acceptor收到一个编号为N的Prepare请求,如果小于它已经响应过的请求,则拒绝,不回应或回复error。若N大于该Acceptor已经响应过的所有Prepare请求的编号(maxN),那么它就会将它已经接受过(已经经过第二阶段accept的提案)的编号最大的提案(如果有的话,如果还没有的accept提案的话返回{pok,null,null})作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案。

    第二阶段-accept阶段

    • 如果一个Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。
    注意:V就是收到的响应中编号最大的提案的value,如果响应中不包含任何提案(就是propose人接收到的都是{pok,null,null}),那么V就由Proposer自己决定。

    • 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案。如果N小于Acceptor以及响应的prepare请求,则拒绝,不回应或回复error(当proposer没有收到过半的回应,那么他会重新进入第一阶段,递增提案号,重新提出prepare请求)。

    • 在上面的运行过程中,每一个Proposer都有可能会产生多个提案。但只要每个Proposer都遵循如上述算法运行,就一定能保证算法执行的正确性。
    在这里插入图片描述

    learner的学习方式

    在这里插入图片描述

    活锁问题

    在这里插入图片描述
    参考:
    https://draveness.me/consensus/

    https://blog.csdn.net/wolf_love666/article/details/92832811

    更多相关内容
  • zab协议不像paxos是一种通用的分布式一致性算法,它是一种特别为zookeeper设计的崩溃可恢复的原子消息广播算法! paxos算法概述 poxos算法是莱斯利兰伯特(Leslie Lamport)于1990提出的一种基于消息传递且具有高度...
  • https://zh.wikipedia.org/zh/Paxos算法#.E5.AE.9E.E4.BE.8B 其中A1能和A2 A3通信,A5能和A2 A3通信 A1(Proposer),想把v修改成A1 A2(Acceptor) A3(Acceptor) A4(Acceptor) A5(Prop
  • java笔初级试题基本的Paxos 汤姆·科卡涅 <> v2.0,2013 年 1 月 介绍性说明 这个存储库包含我第一次尝试提供有用且具有教育意义的 Paxos 实现的结果。 存储库的状态非常好,仍然可以发挥其预期的作用,但设计...
  • 一、paxos算法的背景 Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一,其解决的问题就是在分布式系统中如何就某个值...
  • 分布式理论Paxos, Raft

    2021-01-20 13:47:21
    一、Paxos算法 世界上只有一种一致性算法,就是 Paxos,其它的算法都是残次品,但Paxos非常复杂难懂。 算法原理参考:Paxos的通俗解释 Paxos共识算法详解 算法例子参考:如何浅显易懂地解说 Paxos 的算法? Paxos...
  • paxos:Paxos的实现

    2021-06-14 17:18:07
    帕克索斯 使用 Akka 实现单实例 Paxos
  • 简单的 Paxos 算法模拟 该项目在 Go 中实现了 Paxos 算法的基本版本。 代码根本没有优化,但理解协议本身可能很有用。 该项目是基于以下项目的“概念验证”工作: :
  • 服务发现工具的主要目标是用来服务查找和相互对话,为此该工具需要知道每个服务,这不是一个新概念,在Docker之前就已经存在很多类似的工具了,然而,容器带给了这些工具一个全新水平的需求。
  • Paxos算法虽然可以容忍已经申请到访问权的“提案委员”故障,可以容忍少数派“审批委员”故障;但在出现竞争的情况下,其收敛速度很慢,甚至可能出现活锁的情况,例如当有等于或多于审批委员会数量的“提案委员”在同时...
  • Paxos implementation

    2019-03-02 22:29:12
    raft simplify Paxos algorithm you deserved it since it so powful
  • FireFly提供了三种同步的paxos方式,包括paxos管道以优化不同机房中的rt,路由计算将在使用成本最低的节点链之前进行。 在一个tcp中为一类PaxosOperator提供强而一致的读取。 可以在运行时更改节点的规模,但不会...
  • 在github上找到的paxos算法实现,具体是运行和实现方法可以看README文件,注意acceptor、proposer、以及learner的数量根据打开进程的数量变化,不是局限于.c文件的数量。
  • 什么是Paxos共识算法 最初的服务往往都是通过单体架构对外提供的,即单Server-单Database模式。随着业务的不断扩展,用户和请求数都在不断上升,如何应对大量的请求就成了每个服务都需要解决的问题,这也就是我们常...
  • 主要介绍了基于python的Paxos算法实现,理解一个算法最快,最深刻的做法,我觉着可能是自己手动实现,虽然项目中不用自己实现,有已经封装好的算法库,供我们调用,我觉着还是有必要自己亲自实践一下,需要的朋友可以...
  • Lamport Paxos 的这两篇论文真的很难懂,小编也是竭尽全力的推敲每一句话的意思,尽量的将Lamport的意思完整的呈现出来。希望大家支持一下。两篇论文大概码了3万多字,每一个公式都是手敲的… 为什么会研究Paxos?...
  • paxos simple

    2018-06-18 10:41:44
    paxos简单版论文,好东西,分布式必看
  • 作者:郑勰,腾讯 CSIG 网络产品部后台开发工程师 什么是 CAP 关于 CAP 理论的背景介绍已经很多,这里不过多介绍,我们谈谈如何理解它的问题。 用通俗易懂的话解释三个名词: 一致性 如果刚刚向一个节点写入,那么...
  • Paxos到Zookeeper++分布式一致性原理与实践-文字可复制, 完整版 基于80M的完整版文件,用ABBYY文字识别处理并压缩后的文件。
  • Paxos到ZooKeeper分布式一致性原理与实践.pdf 从Paxos到ZooKeeper分布式一致性原理与实践.pdf
  • Paxos到Zookeeper++分布式一致性原理与实践.pdf从Paxos到Zookeeper++分布式一致性原理与实践.pdf
  • Paxos到Zookeeper:分布式一致性原理与实践,适合分布式系统各阶段学习,并对分布式架构有深入的理解与提高
  • Paxos到Zookeeper分布式一致性原理与实践 + ZooKeeper-分布式过程协同技术详解
  • Paxos到Zookeeper分布式一致性原理与实践包括源码推荐给需要学习的童鞋
  • zookeeper实际上是yahoo开发的,用于分布式中一致性处理的框架。(PS:为方便自己后期查找而上传,侵删.)
  • 先讲PAXOS算法,然后逐步进入时间zookeeper,从分布式一致性原理到实践,全盘讲解,带书签。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,056
精华内容 12,422
关键字:

paxos

友情链接: rtspclient.zip