我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019年全年资料内部公开36码 > 强一致性 >

分布式中的一致性算法:Paxos和Raft比较

归档日期:08-18       文本归类:强一致性      文章编辑:爱尚语录

  分布式中的一致性可以被描述为在协作解决问题的一组操作之间达成一致的行为。随着开源分布式计算和存储平台的兴起,一致性算法已成为复制的基本工具。其中Paxos和Raft是最受欢迎的一致性算法,通过消除单点故障来提高系统的弹性。

  虽然Paxos在分布式一致性方面主导着学术和商业话语,但协议本身太复杂而无法推理,因此需要更易理解的算法。研究人员对Paxos进行了广泛的研究,而Raft在工程师中非常受欢迎。Raft的受欢迎程度来自这样一个事实:尽管研究人员对Paxos感兴趣,但工程师仍然需要阅读几篇论文,以便能够理解并创建解决实际问题的解决方案,并在通信步骤方面提供良好的性能。此外,他们仍然需要填补自定义实施的一些空白,这些实施有时会变得非常脆弱。

  为了克服这个障碍,Diego Ongaro和John Ousterhout创建了一个名为Raft的新一致性算法,它被设计为更容易理解,并为构建实用系统提供了比Paxos更好的基础。虽然Raft为分布式系统的复杂世界带来了一些新鲜血液,但它仍然与Paxos有许多共同之处。例如,两者都要选出一位负责决定协商一致的领导者。

  在这篇博文中,我们将简要介绍Paxos和Raft之间的相同点和不同点。首先,我们将描述一致的算法是什么。其次,我们将描述如何使用一致性算法的实例来构建复制解决方案。然后我们将描述如何在算法和一些安全和活跃属性中选出领导者。

  分布式系统的特征在于一组安全性和活跃性或两者的混合。简单地讲,安全是一种财产,规定在执行程序期间不会发生任何不良事件。另一方面,活跃性规定最终会发生一些好事。

  一致性的目标是使一组服务器在一个值上达成一致,所以活跃的特征在于最终每个服务器都可以决定一个值。安全性表明没有两台服务器来设定值。

  不幸的是,服务器执行算法步骤可能比其他服务器花费更长时间,并且可能崩溃并停止处理一致性算法。邮件可能会延迟,无序传递或丢失。这些方面使得一致性算法的实施变得非常困难,并迫使它们在“不稳定”期间降低标准并保持安全。确切地说,当系统变得“稳定”时虽然未知,但最终它将保持足够长的“稳定”,以便一致性算法能够做出决定达成最终的一致性。

  领导者向所有服务器发送它想要达成协议的值,并且每个服务器回复给领导者,通知他已经接受了请求。因此,当领导者从法定数量(n/2+1节点)的服务器接收消息时,就达成了协议。

  请注意,我们在此分析中省略了两条消息:将服务器希望与领导者达成协议的值转发给服务器的消息以及通知服务器已达到该值协议的消息。如果服务器将接受消息发送到所有服务器,或者在领导者发送给服务器的下一条消息中捎带信息,则后一条消息可能不是必需的。

  为了实现复制,运行一致性算法的几个实例,并且每个实例都被限制在复制日志中的一个槽条目中,该条目可能会持久存储在磁盘上。领导者可以并行运行多个实例以填充不同的插槽,从而提高性能。但是,并行度高度依赖于硬件、使用的网络和应用程序。

  Paxos和Raft都认为最终会有一个领导者,所有稳定的服务器都会信任,而一个领导者负责一个周期(Term)。如果怀疑现任领导人有问题,新领导人将提出一个新任期,必须大于前一任期。

  在Raft中,服务器向其他服务器发送“领导请求”,并且在认为自己是领导者之前期望大多数服务器的回复。如果它没有得到大多数服务器的回复或者接收到另一个服务器已成为领导者的消息,它将超时并重新开始新的选举过程。服务器每个Term只能投票给一个领导者请求。

  但是,Paxos并没有真正定义服务器如何成为领导者。为简单起见,研究人员利用服务器id(整数)等进程之间的先后排名。因此,没有被怀疑的排名最高或最低的服务器成为新的领导者。虽然这是一个简单直观的解决方案,但它需要在服务器之间划分术语空间:新术语=旧术语+ N,其中N是服务器的最大数量。

  Raft对领导者选举过程施加限制:只有最新的服务器才能成为领导者。基本上,它保证领导者拥有以前周期中的所有已提交条目,并且不需要了解它不知道的复制日志中的旧条目。因此,在成为领导者之后,服务器可以简单地在其他服务器上“强加”其“愿望”。

  然而,Paxos允许任何服务器成为领导者。因此,服务器必须在开始在其他服务器上“强加”其“愿望”之前了解过去,提高了灵活性但也伴随着额外的复杂性。

  在Raft中,服务器1或服务器2可以成为领导者。而在Paxos中,任何一个都可以。

  由于系统的异步性质,服务器可能在不同时间感知故障和选举。这意味着服务器可能会以不同的方式临时运行,但最终所有服务器都会收敛到一个Term。

  在任何情况下,如果服务器从比其当前版本更早的Term获得消息,则这意味着发送者要么是领导者,要么试图成为旧Term中的一个,并且接收者必须拒绝该消息并通知发送者。

  如果服务器从一个大于当前的Term获得消息,这意味着有一个新Term和一个新的领导者,并且接收者必须开始接受领导者的“愿望”。

  但是,两种算法都必须小心避免覆盖旧领导做出的决定,从而违反安全规定。这就是Raft和Paxos分歧的地方,我们可以看到Raft使用了简单而优雅的方法。

  如上所述,Raft对领导者选举算法施加限制,只有最新的服务器才能成为领导者:

  Raft通过比较日志中最后一个条目的索引和术语来确定两个日志中哪一个更新。如果日志包含具有不同术语的最后一个条目,则具有较晚术语的日志将更新。如果日志以相同的术语结束,则更长的日志更新是最新的。

  然后,领导者只需要确保服务器中的复制日志最终收敛,这是通过施加以下限制来完成的:如果服务器之前没有接受插槽的值,“n服务器不能接受插槽的值n - 1”。领导者包括当前请求中的先前日志条目的术语,并且如果其先前请求的术语与领导者发送的术语匹配,则服务器仅接受该请求。否则,它要求领导者首先发送先前失踪的请求,如此反复n - 2和 n - 3等。

  在Paxos中,任何服务器都可以成为领导者,因此避免决策不被覆盖的任务变得有点复杂,因为新的领导者必须在开始“强加”它之前找出其他服务器已处理的内容。希望“在别人身上。这是Paxos算法的准备阶段,必须在选出新领导者后运行一次。准备消息包含新术语和插槽号,“n通过该插槽号可以达到所有先前条目的协议。服务器回复有关大于的插槽的信息n”,此信息用于限制新领导者为这些插槽建议的值。

  背景在一个分布式系统中,如何保证集群中所有节点中的数据完全相同并且能够对某个提案(Proposal)达成一致是分布式系统正常工作的核心问题,而共识算法就是用来保证分布式系统一致性的方法。然而分布式系统...博文来自:niyuelin1990的博客

  分布式一致性算法paxosamp;raft1paxos算法paxos算法通过多个监督者来增强可靠性通过监督者投票表决状态变化保证所有数据访问都遵从这种表决多数派写客户端写入Wgt;...博文来自:fanc的博客

  聊聊Zookeeper-快速开始什么是ZookeeperZookeeper是一个高性能的分布式应用协调服务的框架。Zookeeper=Zoo+keeper,中文直译是动物园的看守者。为什么要使用Zoo...博文来自:黄小斜

  本文较为粗略地讲述了一致性协议与两种一致性算法,更加系统的理论可以参考后面的分布式系统理论专题文章。 2PC由于BASE理论需要在一致性和可用性方面做出权衡,因此涌现了很多关于一致性的算法和协议。其中...博文来自:gangsijay888的博客

  协议比paxos的优点是容易理解,容易实现。它强化了leader的地位,把整个协议...博文来自:xxxcyzyy的博客

  ZOOKEEPER系列Paxos、Raft、ZABPaxos算法莱斯利·兰伯特(LeslieLamport)这位大牛在1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。如果你不知道这个人...博文来自:Old Wang的博客

  说明:以下内容总结自网络1.CAP原理要想数据高可用,就得写多份数据写多分数据就会导致数据一致性问题数据一致性问题会引起性能问题2.一致性模型弱一致性最终一致性(一段时间达到一致性)强一致1、2异步冗...博文来自:followMyInclinations的专栏

  因为要写个demo出来,所以在网上找了很多资料,文章都是站在各个博主巨人肩上拼凑出来的。一、Raft协议的易理解性描述在一个由Raft协议组织的集群中有三类角色:Leader(领袖)Follower(...博文来自:u011466728的博客

  我们知道Raft来源与Paxos,Paxos最早是由莱斯利·兰伯特于1990提出。Paxos的大规模应用是在Google的广告系统中。Raft可以看做是简化版本的Paxos。Raft动画演示:(真心推...博文来自:迎风的舵手

  一致性问题可以算是分布式领域的一个圣殿级问题了,关于它的研究可以回溯到几十年前。拜占庭将军问题LeslieLamport在三十多年前发表的论文《拜占庭将军问题》(参考[1])。拜占庭位于如今的土耳其的...博文来自:weixin_30348519的博客

  1.Paxos算法Paxos算法是一个经典的分布式算法,它引入了提议者,接受者,学习者三种角色,generalize了二阶段提交模型。大致思想是,提议者通过竞争获得提议资格(超过半数认可),提议被多数...博文来自:Think++

  晒昔日的“散片”记我们已经在上面的分析中,我们已经看到observer模型在多机场景下的问题,所以,paxos模型的目标就是解决这个问题,他解决这个问题的方法就是quorum模型。我的目标是让大家能弄...博文来自:zhang_shuai_2011的专栏

  写在前面一直以来,对Raft协议的理解感觉都没有非常到位,本着眼过千遍,不如手过一遍的原则,利用空闲时间,就自己把Raft翻译一遍,加深自己的理解,也方便其他同学参考。Raft协议英文版参考资料:ht...博文来自:baijiwei的博客

  什么是raft?Raft论文中都做了详细的描述,语言清晰,我这里仅做下认为非常重要的点的记录:数据流向是由leader流向follower的,follower和leader不一致,以leader为准修...博文来自:yinn

  最近工作中用到了Consul,在学习过程中,发现它是基于Raft来做分布式一致性的。正巧以前学习过Raft,那么就正好借此机会复习一下吧!...博文来自:沈鸿斌的博客

  Paxos算法:Paxos一直是分布式协议的标准,但是Paxos难于理解,更难以实现,Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。阶段一:1、Proposer选择一个提案...博文来自:A_zhenzhen的专栏

  本篇介绍分布式一致性算法:Paxos算法Paxos算法是莱斯利·兰伯特(LeslieLamport,就是 LaTeX 中的La,此人现在在微软研究院)于1990年提出的一种基于...博文来自:彪锅锅来啦

  共识算法区块链中最重要的便是共识算法,比特币使用的是POS(Proof ofWork,工作量证明),以太币使用的是POS(ProofofStake,股权证明)使得算理便的不怎么重要了,而今POS的变体...博文来自:新手村

  数据库高可用性难题数据库的数据一致和持续可用对电子商务和互联网金融的意义不言而喻,而这些业务在使用数据库时,无论MySQL还是Oracle,都会面临一个艰难的取舍,就是如何处理主备库之间的数据同步。对...博文来自:kobejayandy的专栏

  Proposer:提议发起者Acceptor:提议批准者ProposalID:每个提议都有一个编号,编号越高优先级越高PaxosInstance:Paxos用来在多个节点之间对同一个值达成一致的过程a...博文来自:k_cnoize的博客

  Raft简介Raft替代了paxos(太复杂),并提供了一种在计算系统集群中分布状态机的通用方法,确保集群中的每个节点都同意一系列相同的状态转换,也就是说,它在提供的计算机集群分布状态机时,有个别或者...博文来自:The_Reader的博客

  核心问题:在复杂的网络环境中保证各个节点的数据一致步骤:初始:每个机器投自己投票:每个机器接收到其他机器的投票,与自己保存的票(myId,zxid)比较先比较ZXID大的获胜 再比较myId大的获胜统...博文来自:大道至简

  Paxos写在前面GoogleChubby的作者MikeBurrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。Paxos算法也因为晦涩难懂而臭名昭著。不仅理解它的执行...博文来自:TheLudlows的博客

  Paxos背景paxos是现代分布式系统中的一项重要的基础性技术,整个发展过程大概可以分为3类:第一阶段,萌芽期。大概是1988-1996年。先是Liskov等人提出的本质上与paxos基本一致的主从...博文来自:snail hack的脚步

  Paxos比较难理解,这篇文章从头推导出了协议,推荐阅读。在这里我简单的拾一下牙慧。首先分两种角色,提议者和接受者(可以...博文来自:ddxd0406的博客

  Raft是一个管理日志副本一致性的算法。相比Paxos结果一样,并且一样高效,但是理解起来更加的容易。Raft将一致性的主要元素分离开来,比如leader选举,log复制,安全等。同时,也提供了一个新...博文来自:KDF5000的专栏

  Raft是分布式环境下的一致性算法,它通过少数服从多数的选举来维持集群内数据的一致性。它与RBFT算法名称有点像,然而Raft算法里不能存在拜占庭节点,而RBFT则能容忍BFT节点的存在。Raft非常...博文来自:陶辉:聚焦分布式系统的程序员

  在分布式系统中,有很多复杂的理论,从CAP理论到BASE理论,我们不断的在可用性以及一致性之间做出抉择,每一部分都相当复杂,就分布式一致性而言,又有许多协议,从2PC到3PC再到paxos算法,到ZA...博文来自:不清不慎的博客

  Paxos问题[1]是指分布式的系统中存在故障(crashfault),但不存在恶意(corrupt)节点的场景(即可能消息丢失或重复,但无错误消息)下的共识达成问题。这也是分布式共识领域最为常见的问...博文

  《分布式》:paxos算法和一致性Hash算法相关记录今天无意之间看到了这个关于分布式的协调一致的算法:paxos,于是找了一些相关博文看了下,说没有弄懂吧,感觉还懂点,说懂了吧,但是又感觉差点。哎,...博文来自:wojiushimogui的博客

  百度描述Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点执行相同的操作序列,那么他们最后能得到一个一...博文来自:乐扣老师lekkoliu——区块链、量子计算

  Raft一致性算法今天和明天都得值班,基本主要是看监控,趁着空闲时候大概看了会raft算法,以前比较粗略的了解了一下,今天仔细的学习了会,在这里做个笔记吧。在分布式系统中,一致性是个很棘手的问题,单节...博文来自:sryan的专栏

  这里写自定义目录标题什么是分布式一致性Leader选举日志复制流程在分布式系统中,分布式一致性是一个非常重要的概念,它是指分布式系统的各个服务器都保持一个统一的状态(数据)。但是在分布式系统中,通常由...博文来自:flydean的专栏

  理解分布式一致性:Paxos协议之BasicPaxos角色在理解分布式一致性:Raft协议中,我们详细分析了什么是分布式一致性和实现分布式一致性的Raft协议,本文我们主要讲一下分布式一致性的Paxo...博文来自:flydean的专栏

  :[reply]b452608[/reply] 两个月了 学会了吗》学会了教教我吧,我急用!!!!

本文链接:http://ravynhart.com/qiangyizhixing/510.html