精华内容
下载资源
问答
  • Paxos开源实现

    千次阅读 2017-01-13 15:15:12
    腾讯微信开源实现 https://github.com/tencent-wechat/phxpaxos/blob/master/README.zh_CN.md

    腾讯微信开源实现

    https://github.com/tencent-wechat/phxpaxos/blob/master/README.zh_CN.md

    展开全文
  • paxos开源实现

    2013-10-29 17:42:29
    paxos开源实现,可以代替zookeeper
  • libhalog Libhalog是使用多个paxos开源高可用性重做日志库。
  • Paxos和FastPaxos算法的实现集合,用于解决不可靠处理器网络中的共识。 访问http://libpaxos.sourceforge.net/了解更多信息
  • 项目地址 [url]https://github.com/tencent-wechat/phxpaxos[/url] 实现原理 [url=...4UUbO0Hjwfrl8Qpg622IhXpRXk6RLojit4d8ysqJyJk=]微信自研生产级paxos类库PhxPaxos实现原理介绍[/url]
    项目地址
    
    [url]https://github.com/tencent-wechat/phxpaxos[/url]

    实现原理
    [url=http://mp.weixin.qq.com/s?src=3&timestamp=1468151143&ver=1&signature=fGdg5ZDJyTsvVWFx2n7xyEAyTbkYU8CsFsBAQHNCjw4ASHXjqafTygJOzKJLKKM12yC6ONJ*uccxu8PVBvRfxZ2AfKDMSYPlMB95SyIDpZIsfMDXgzkWbZe3VFUSLKE-4UUbO0Hjwfrl8Qpg622IhXpRXk6RLojit4d8ysqJyJk=]微信自研生产级paxos类库PhxPaxos实现原理介绍[/url]
    展开全文
  • 腾讯开源Paxos库 PhxPaxos 代码解读---Accept阶段(一) 在看Accept阶段代码之前, 我们再回想一下 Basic Paxos算法; 1. Basic Paxos 算法是为了使集群中的Acceptor们达成一个最终的值, 或者不能达成一个最终...

    腾讯开源的 Paxos库 PhxPaxos 代码解读---Accept阶段(一)

     

    在看Accept阶段代码之前, 我们再回想一下 Basic Paxos算法;

     

        1.  Basic Paxos 算法是为了使集群中的Acceptor们达成一个最终的值, 或者不能达成一个最终的值;

     

            就是说, 要么达成一个最终的值, 某个时间点上, 多数派节点都是一个一致的值, 这个值就是最终的值;

     

            否则, 没有多数派在某个时间点达成一个一致的值, 这个值不断被新的提议(Proposal)刷新, 无法达成最终值;

            这种情况一般意味着发生了活锁;

     

        2.  一个最终的值一旦被确定, 不能再有Proposor发出提议进行修改, 为了确保这点, 有了针对Proposor的约束:

            Proposor必须收到多数派的响应, 才能进行Accept提议; 原因如下:

               

                Proposor只有收到多数派响应消息, 才能确定是否已经有多数派接受过提议(Proposal),

                如果多数派响应消息里面已经携带了接受过的提议, 则有两种可能:

     

                    1. 多数派已经已经达成了一致, 必然会有某些Acceptor的响应携带了这个值;

     

                    2. 多数派还没有达成一致, 但是Proposor正好收到了某个已经接受过提议的Acceptor的响应;

     

                上述情况不论是哪种, Proposor都需要用已有的提议发起Accept请求, 选择最大ProposolID的那个;

                这样是为了促使Acceptor们尽快的达成一致;

     

        3.  对于Acceptor的约束, 则是必须要大于等于当前已经接受过的最大ProposalID, 才能刷新这个值,;

            我们给出一个典型的场景来说明, 以3个Acceptor为例:

           

            第1个时间片段:

                Proposor1发起Prepare请求(1, null), 成功到达 Acceptor1和Acceptor2, Acceptor的状态如下:

                    Acceptor1(1, null); Acceptor2(1, null); Acceptor3(null, null)

            第2个时间片段:

                Proposor2发起Prepare请求(2, null), 成功到达 Acceptor1和Acceptor2, Acceptor的状态如下:

                    Acceptor1(2, null); Acceptor2(2, null); Acceptor3(null, null)

            第3个时间片段:

                Proposor1发起Accept请求(1, 100), 1 < 2, 被Acceptor拒绝, Acceptor的状态如下:

                    Acceptor1(2, null); Acceptor2(2, null); Acceptor3(null, null)

            第4个时间片段:

                Proposor2发起Accept请求(2, 100), 2=2, 被Acceptor接受, Acceptor的状态如下:

                    Acceptor1(2, 100); Acceptor2(2, 100); Acceptor3(null, null)

            第5个时间片段:

                Proposor1重新发起Prepare请求(3, null), 到达Acceptor2和Acceptor3,

                收到响应之后, 用Acceptor2接受的值发起Accept请求(2,100),成功到达Acceptor2和Acceptor3,

                状态变为如下:

                    Acceptor1(2, 100); Acceptor2(2, 100); Acceptor3(2, 100)

     

    在处理Prepare和Accept请求时, 我们不仅要考虑网络中的异步情况, 还要考虑在接受一个提议时代码执行的异步情况;

     

    前面一篇博客已经简单介绍过phxpaxos中Prepare阶段的代码, 下面简单的介绍一下Accept阶段的代码;

     

    phxpaxos\src\algorithm\proposer.cpp

    这里的代码是Proposor的逻辑

     

    phxpaxos\src\algorithm\acceptor.cpp

    这里的代码是Acceptor的逻辑

     

    下面的图是Proposor发起Accept请求的操作:

     

     

     

    下面的图是Acceptor收到Accept请求的操作:

     

     

    下面的图是Propsor收到Acceptor返回响应的操作:

     

     

     

    结束:
    微信开源的Paxos库有很多照顾性能的实现, 后面慢慢讲吧;

     

    转载于:https://www.cnblogs.com/lijingshanxi/p/10250878.html

    展开全文
  • 共识算法是实现自主产权区块链的必不可少的关键环节,本文列出社区中相对成熟的区块链共识算法开源实现,包括BFT共识、Raft共识、Paxos共识、PoW共识等,可供希望开发自主产权区块链的团队参考学习。 相关推荐:...
  • Multi Paxos

    2021-08-13 23:36:35
    Multi Paxos是什么 Basic Paxos 只能对一个值形成决议,决议的形成至少需要两次网络来回,在高并发情况下可能需要更多的网络来回,极端情况下甚至可能形成活锁 实际应用中我们常常需要连续确定多个值,而且希望能有...

    Multi Paxos是什么

    • Basic Paxos 只能对一个值形成决议,决议的形成至少需要两次网络来回,在高并发情况下可能需要更多的网络来回,极端情况下甚至可能形成活锁
    • 实际应用中我们常常需要连续确定多个值,而且希望能有更高的效率。

    补充

    • 分布式一致性协议,来源于我们对系统可用性,容错性的追求。 为了避免单机失效导致整个系统不可用的问题, 我们会很自然地希望复制数据多结点部署。 但数据一旦出现了多份, 就需要解决一致性的问题。
    • 为了解决多份数据的一致性问题, 我们常常将其简化为多份状态机的一致性问题,即复制状态机。 对于客户端发来的一系列指令, 只要我们能确保将指令以唯一确定的顺序发送给所有结点, 那么只要各个状态机的初始状态相同, 执行完所有指令后 (指令对状态机的影响必须是唯一确定的结果), 必然也会到达相同的状态, 实现一致性目标。 在多状态机一致性问题中, 共识算法( Consensus Algorithm) 的作用就是确保多份 log 中包含顺序和内容完全一致的指令。
    • Paxos 算法最开始是定义了一种算法, 能够使多个结点针对单个决议/单个数据项 达成共识。 Raft 将该算法称为 single-decree Paxos(单决议 Paxos)。 在实践中, 我们希望达成一致的数据, 显然不会是个单项孤立的数据, 在单决议 Paxos (single-decree Paxos)的算法基础上实现多决议/多数据一致性的算法被称之为multi-Paxos( 多决议 Paxos)。

    要点

    • 针对每一个要确定的值,运行一次Paxos算法实例(Instance),形成决议。每一个Paxos实例使用唯一的Instance ID标识。第i个实例中的内容就是第i条状态机指令。
    • Paxos实例中的每个服务器同时具有所有的角色:proposer、acceptor和learner。
    • 在所有服务器中选举一个Leader,由Leader唯一地提交Proposal给Acceptors进行表决。leader会决定客户端发送的指令在序列中出现的位置。
    • 这样没有Proposer竞争,解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下,Prepare阶段就可以跳过,从而将两阶段变为一阶段,提高效率。

    总结

    • Paxos描述了三个阶段,prepare、accept和learn。
    • 在前两个阶段中,proposer和acceptor通过通信来决定一个提案是否通过,提案的内容一般是对分布式系统中的数据进行操作。
    • 当一个提案通过时,learner会学习这个提案,表示为分布式系统的learner将提案的内容应用到自己的状态机模型上。
    • 论文中没有描述leader具体怎么选举
    • leader身兼3个角色,作为proposer唯一提出提案,作为learner将通过提案发送给其他的learner
    • 缺少必要具体实现的描述

    优点

    安全性 safety

    • 在集群内结点可能宕机, 通信消息可能丢失,延迟的情况下(消息不会被篡改),客户端发往集群的请求不会返回错误的结果
    • 所谓错误的结果是指违反 Linearizability 的结果, Linearability 的定义后续有详细说明

    存活性 liveness

    • 当集群半数以上结点正常运转且可以相互正常通信的情况下, 整个系统可以正常对外提供服务。
    • 注意上述存活性的定义中, 半数以上结点能够相互通信非常重要, 缺失了这一前提后, 再想实现同时满足 livess 和 safety 的系统就是一个不可能达成的目标, 这是被学界大佬证明过的, 类似于 CAP 定理

    在正常的情况下,效率不差

    缺点

    难以理解

    • Paxos 原始论文《The part-time parliament》
    • 简化论文《Paxos made simple》
    • 《How to Build a Highly Available System Using Consensusr》
    • 《The ABCD’s of Paxos》

    缺失了工程化的细节信息

    • Lamport 本人的论文描述主要集中于 single-decree Paxos, 他描述了几种实现 multi-Paxos 的可行方法, 但缺失了细节。
    • 有一些论文试图更完整地描述 multi-Paxos 的实现方式, 但是这些论文描述的方案各不相同, 并且与Lamport 本人描述的 multi-Paxos 实现思路也有差异。Google 实现的 Chubby 系统论文中声称基于 Paxos 的算法, Chubbty 也有很多细节信息没有发表在论文里,Chubbty并不开源。

    参考

    https://www.zhihu.com/collection/149098870

    展开全文
  • Zookeeper与Paxos

    2017-05-14 21:26:25
     在学习了Paxos在Chubby中的应用后,接下来学习Paxos开源软件Zookeeper中的应用。 二、Zookeeper  Zookeeper是一个开源的分布式协调服务,其设计目标是将那些复杂的且容易出错的分布式一致性服务封装起来...
  • Paxos Made Easy: The Geometric Meaning and Geometric Proof of Paxos Algorithm Paxos Made Easy: Paxos算法的几何意义与证明 ...本文是开源项目的一个子项目。Turing Cell Model是一个运行于分布式一
  • Paxos算法

    2021-08-20 14:50:16
    Paxos算法 paxos-simple.pdf 1. Paxos算法基本概念 1.1 拜占庭问题 拜占庭将军问题:是指拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的,只能依靠通讯员进行...
  • PhxQueue是微信开源的一款基于Paxos协议实现的高可用、高吞吐和高可靠的分布式队列,保证At-Least-Once Delivery。在微信内部广泛支持微信支付、公众平台等多个重要业务。
  • 简单的画了一下PhxPaxos在Prepare阶段的逻辑,主要是正常的逻辑,异常逻辑和超时后面再写了; 熟悉PhxPaxos代码最好的方法是编译运行sample目录下的三个例子,编译方法在另一篇博客已经写了,这里忽略;...
  • paxos协议学习

    2021-01-02 19:18:12
    paxos算法历史拾遗2. 从分布式算法开始1. 分布式算法是做什么用的2. 分布式数据一致性的类型1. backup2. 主从异步复制3. 主从同步复制4. 半同步复制5. 分布式一致性协议paxos协议简介paxos的假设1. 节点层面2. ...
  • 与其他免费提供的开源实现相比,此实现的显着特征是该库独立于应用程序域和网络基础设施。 尽管大多数 Paxos 实现都深深且不可分割地嵌入到特定于应用程序的逻辑中,但该实现侧重于将 Paxos 算法封装在不透明且易于...
  • Paxos算法详解

    千次阅读 2018-03-23 12:24:14
    Paxos、Raft分布式一致性算法应用场景一文讲述了分布式一致性问题与分布式一致性算法的典型应用场景。作为分布式一致性代名词的Paxos算法号称是最难理解的算法。本文试图用通俗易懂的语言讲述Paxos算法。一、Paxos...
  • Paxos协议

    2015-10-08 13:49:26
    Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。...
  • Paxos历史回顾

    千次阅读 2014-09-28 22:54:23
    Paxos提出,迄今已有20多年了,围绕着该算法曾经发生过一些非常有趣的事情,这些也已成为人们津津乐道的一段轶事,故事的主角自然是Paxos的提出者Lamport,当然Lamport的特立独行也是很早就出了名的。首先来讲述下...
  • 一致性算法 Paxos

    多人点赞 热门讨论 2021-06-08 20:31:37
    一致性算法 Paxos 什么是Paxos算法 Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开,最初的描述使用希腊的一个小岛 Paxos作为比喻,描述了Paxos小岛中通过决议的流程,并以此命名这个算法,...
  • Paxos algorithm

    2011-03-22 22:12:27
    Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becom...
  • Paxos小议

    2017-11-23 15:33:00
     ,paxos开源实现 [4]  http://zh.wikipedia.org/zh-cn/Paxos算法  ,wikipedia上的中文说明 [5]  http://en.wikipedia.org/wiki/Paxos_algorithm  ,wikipedia上的英文说明 [6]  ...
  • 在朴素Paxos算法中, 各个节点经过 Prepare 和 Accept 阶段, 会达成一个值, 这个值一旦达成, 就不能被修改, 如下例子: 图示1 上面的操作几乎没有任何实用价值, 于是演变成下面这种操作, 多个"实例(Instance)", ...
  • Paxos 由著名图灵奖获得者Leslie Lamport提出,该算法是分布式一致性算法中的奠基之作,今天初读此文仅将相关学习心得予以记录。 1.Paxos 是什么?主要用来解决什么问题? Paxos是一个用于实现可容错的分布式系统的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,634
精华内容 3,853
关键字:

paxos开源