我要投搞

标签云

收藏小站

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

当前位置:百万心水论坛 > 段提交协议 >

微信分布式数据存储协议对比——Paxos和Quorum

归档日期:06-16       文本归类:段提交协议      文章编辑:爱尚语录

  作者:莫晓东,微信支付高级DBA,拥有丰富的数据架构和运维实战经验,擅长大规模MySQL数据库集群的架构、优化和高可用。2010年起在腾讯从事DBA工作,目前专注于微信社交支付的存储层运维和架构优化。

  责编:仲培艺,关注数据库领域,寻求报道或者投稿请发邮件,或微信zhongpy_0921。

  本文为《程序员》原创文章,未经允许不得转载,更多精彩文章请订阅2017年《程序员》

  分布式系统是网络化的计算机系统,海量数据的互联网应用只能通过分布式系统协调大量计算机来支撑。微信后台存储大量使用了分布式数据存储方式的NoSQL集群,比如核心业务:账号、支付单据、关系链、朋友圈等。存储设备出现异常是必然,分布式系统通过多节点分布及冗余,避免个别异常节点影响到系统的正常服务,同时提供平行扩展能力。微信自研的分布式存储在发展的不同阶段,分别依赖过Paxos和Quorum两种方案维护一致性。Paxos和Quorum也是互联网企业主要使用的分布式协议,这里向有兴趣的读者做些分布式算法的粗略介绍,以及为什么需要它们。

  为什么需要Paxos或Quorum算法?分布式系统实现数据存储,是通过多份数据副本来保证可靠,假设部分节点访问数据失败,还有其他节点提供一致的数据返回给用户。对数据存储而言,怎样保证副本数据的一致性当属分布式存储最重要的问题。 一致性是分布式理论中的根本性问题,近半个世纪以来,科学家们围绕着一致性问题提出了很多理论模型,依据这些理论模型,业界也出现了很多工程实践投影。何为一致性问题?简而言之,一致性问题就是相互独立的节点之间,在可控的时间范围内如何达成一项决议的问题。

  解决这个问题最简单的方法 ,就是强一致写。在用户提交写请求后,完成所有副本更新再返回用户,读请求任意选择某个节点。数据修改少节点少时,方案看起来很好,但操作频繁则有写操作延时问题,也无法处理节点宕机。

  既然实际系统中很难保证强一致,便只能通过两段式提交分成两个阶段,先由Proposer(提议者)发起事物并收集Acceptor(接受者)的返回,再根据反馈决定提交或中止事务。

  第一阶段:Proposer发起一个提议,询问所有Acceptor是否接受;

  第二阶段:Proposer根据Acceptor的返回结果,提交或中止事务。如果Acceptor全部同意则提交,否则全部终止。

  两阶段提交方案是实现分布式事务的关键;但是这个方案针对无反馈的情况,除了“死等”,缺乏合理的解决方案。 Proposer在发起提议后宕机,阶段二的Acceptor资源将锁定死等。如果部分参与者接受请求后异常,还可能存在数据不一致的脑裂问题。

  为了解决2PC的死等问题,3PC在提交前增加一次准备提交(prepare commit)的阶段,使得系统不会因为提议者宕机不知所措。接受者接到准备提交指令后可以锁资源,但要求相关操作必须可回滚。

  但3PC并没有被用在我们的工程实现上,因为3PC无法避免脑裂,同时有其他协议可以做到更多的特性又解决了死等的问题。

  图1 三段式提交,在二段式提交基础上增加prepare commit阶段

  微信后台近期开始主要推广Paxos算法用于内部分布式存储。Paxos是Leslie Lamport提出的基于消息传递的一致性算法,解决了分布式存储中多个副本响应读写请求的一致性,Paxos在目前的分布式领域几乎是一致性的代名词(据传Google Chubby的作者Mike Burrows曾说过这个世界上只有一种一致性算法, 那就是Paxos,其他算法都是残次品)。Paxos算法在可能宕机或网络异常的分布式环境中,快速且正确地在集群内部对某个数据的值达成一致,并且保证只要任意多数节点存活,都不会破坏整个系统的一致性。Paxos的核心能力就是多个节点确认一个值,少数服从多数,获得可用性和一致性的均衡。

  Paxos可以说是多节点交互的二段提交算法,Basic Paxos内的角色有Proposer(提议者)、Acceptor(接受提议者)、Learner(学习提议者),以提出Proposal(提议)的方式寻求确定一致的值。

  第一阶段(Prepare):Proposer对所有Acceptor广播自己的Proposal(值+编号)。Acceptor如果收到的Proposal编号是最大的就接受,否则Acceptor必须拒绝。如果Proposer之前已经接受过某个Proposal,就把这个Proposal返回给Proposer。在Prepare阶段Acceptor始终接受编号最大的Proposal,多个Proposer为了尽快达成一致,收到Acceptor返回的Proposal编号比自己的大,就修改为自己的Proposal。因此为了唯一标识每个Proposal,编号必须唯一。如果Proposer收到过半数的Acceptor返回的结果是接受,算法进入第二阶段。

  第二阶段(Accept):Proposer收到的答复中,如果过半数的Acceptor已经接受,Proposer把第一阶段的Proposal广播给所有Acceptor。而大多Acceptor已经接受了其他编号更大的Proposal时,Proposer把这个Proposal作为自己的Proposal提交。Acceptor接到请求后,如果Proposal编号最大则确认并返回结果给所有Proposer,如果Proposer得到多数派回复,则认为最终一致的值已经确定(Chosen)。Learner不参与提议,完成后学习这个最终Proposal。

  严格证明是通过数学归纳法,本文只做了直观判断。Paxos确认这个值利用的是“抽屉原理”,固定数量的节点选取任意两次过半数的节点集合,两次集合交集必定有节点是重复的。所以第一阶段任何已经接受的提议,在第二阶段任意节点宕机或失联,都有某节点已经接受提议,而编号最大的提议和确定的值是一致的。递增的编号还能减少消息交互次数,允许消息乱序的情况下正常运行。就一个值达成一致的方式(Basic Paxos)已经明确了,但实际环境中并不是达成一次一致,而是持续寻求一致,读者可以自己思考和推导,想深入研究建议阅读Leslie Lamport的三篇论文《Paxos made simple》、《The Part-Time Parliament》、《Fast Paxos》。实现多值方式(原文为Multi Paxos),通过增加Leader角色统一发起提议Proposal,还能节约多次网络交互的消耗。Paxos协议本身不复杂,难点在如何将Paxos协议工程化。

  我们实现Paxos存储做了一些改进,使用了无租约版Paxos分布式协议,参考Google MegaStore做了写优化,并通过限制单次Paxos写触发Prepare的次数避免活锁问题。虽然Paxos算法下只要多数派存在,就可以在分布式环境下达到严格的一致性。但是牺牲的性能代价可观,在大部分应用场景中,对一致性的要求并不是那么严格,这个时候有不少简化的一致性算法,比如Quorum。

  Quorum借鉴了Paxos的思想,实现上更加简洁,同样解决了在多个节点并发写入时的数据一致性问题。比如Amazon的Dynamo云存储系统中,就应用NWR来控制一致性。微信也有大量分布式存储使用这个协议保证一致性。Quorum最初的思路来自“鸽巢原理”,同一份数据虽然在多个节点拥有多份副本,但是同一时刻这些副本只能用于读或者只能用于写。

  Quorum控制同一份数据不会同时读写,写请求需要的副本数要求超过半数,写操作时就没有足够的副本给读操作;

  Quorum控制同一份数据的串行化修改,因为副本数要求,同一份数据不会被两个写请求同时修改。

  Quorum又被称为NWR协议:R表示读取副本的数量;W表示写入副本的数量;N表示总的节点数量。

  假设N=2,R=1,W=1,R+W=N=2,在节点1写入,节点2读取,无法得到一致性的数据;

  假设N=2,R=2,W=1,R+WN,任意写入某个节点,则必须同时读取所有节点;

  假设N=2,W=2,R=1,R+WN,同时写入所有节点,则读取任意节点就可以得到结果。

  要满足一致性,必须满足R+WN。NWR值的不同组合有不同效果,当W+RN时能实现强一致性。所以工程实现上需要N=3,因为冗余数据是保证可靠性的手段,如果N=2,损失一个节点就退化为单节点。写操作必须更新所有副本数据才能操作完成,对于写频繁的系统,少数节点被写入的数据副本可以异步同步,但是只更新部分节点,读取则需要访问多个节点,读写总和超过总节点数才能保证读到最新数据。可以根据请求类型调整BWR,需要可靠性则加大NR,需要平衡读写性能则调整RW。

  微信有大量分布式存储(QuorumKV)使用这个算法保证一致性,我们对这个算法做了改进,创造性地把数据副本分离出版本编号和数据存到不同设备,其中N=3(数据只有2份,版本编号有3份),在R=W=2时仍然可以保证强一致性。因为版本编号存放3份,对版本编号使用Quorum方式,通过版本编号协商,只有版本序号达成一致的情况下读写单机数据,从而在保证强一致性的同时实现高读写性能。实际数据只写入一台数据节点,使用流水日志的方式进行同步,并更新版本编号。但是我们的分布式存储(QuorumKV)仍存在数据可靠性比Paxos低的问题,因为数据只写一份副本,依靠异步同步。如果数据节点故障,故障节点上没有同步到另一个节点,数据将无法访问。版本节点故障时,如果Quorum协议没有设置W=3,也可能无法访问正确的数据节点副本。

  分布式存储选用不同的一致性算法,和业务的具体情况相关。我们的分布式存储在发展的不同阶段,使用过不同的算法:业务的发展初期使用Quorum算法,成本压力减少而业务稳定需求变大后,就开始使用Paxos算法。如果业务模型对数据一致性要求不高,使用Quorum则具有一定的成本和开发资源优势。

  分布式系统原理Quorum机制Quorum机制是一种简单有效的副本管理机制。本节首先讨论一种最简单的副本控制规则write-all-read-one,在此基础上,放松约束,讨论quorum机制。 1. 约定 为了简化讨论,本节先做这样的约定:更新操作(write)是一系列顺序的过程,通过其他机制确定更新操作的顺序(例如 primary-secondary 架构中由 prim...

  今天没写完,有点困,明天补上Quorum机制是一种简单有效的副本管理机制(1)约定假设:更新操作(write)是一系列顺序的过程,通过其他机制确定更新操作的顺序(例如由primary决定顺序),每个更新操作记为wi,i为更新操作单调递增的序号,每个wi执行成功后副本数据都发生变化,成为不同的数据版本,记作vi。假设每个副本都保存了历史上所有版本的数据(2)Write-all-read-onel  ...

  什么是paxos协议?Paxos用于解决分布式系统中一致性问题。分布式一致性算法(Consensus Algorithm)是一个分布式计算领域的基础性问题,其最基本的功能是为了在多个进程之间对某个(某些)值达成一致(强一致);简单来说就是确定一个值,一旦被写入就不可改变。paxos用来实现多节点写入来完成一件事情,例如mysql主从也是一种方案,但这种方案有个致命的缺陷,如果主库挂了会直接

  在《分布式系统之中心副本控制协议(Primary-secondary协议)》 中略微提及到了Quorum,但没有进行详细的阐述,这篇文章将带你走进Quorum. 1.Quorum介绍 首先,先认识发音和基本含义,英[ˈkwɔ:rəm], 美[ˈkwɔrəm, ˈkwor-],n. 法定人数. 在介绍Quorum之前,先对一些概念进行定义:系统中的更新操作定义为wiwiw_i,iii ...

  本文较为粗略地讲述了一致性协议与两种一致性算法,更加系统的理论可以参考后面的分布式系统理论专题文章。   2PC 由于BASE理论需要在一致性和可用性方面做出权衡,因此涌现了很多关于一致性的算法和协议。其中比较著名的有二阶提交协议(2 Phase Commitment Protocol),三阶提交协议(3 Phase Commitment Protocol)和Paxos算法。 本文要介绍的...

  关于一致性协议,分布式锁以及如何使用分布式锁 最近看antirez 和 Martin 关于redlock 的分布式锁是否安全的问题的争吵, 非常有意思

  Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? : Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。 : 理解了这两个分布式协议之后(Paxos/2PC),学习其他分布式协议会变得相当容易。 学习Paxos算法有两部分:a) 算法的原理/证明;b) 算法的理解/运作。 理

  分布式事务与Paxos协议的关系?  在数据库领域,提到分布式系统,就会提到分布式事务。Paxos协议与分布式事务并不是同一层面的东西。分布式事务的作用是保证跨节点事务的原子性,涉及事务的节点要么都提交(执行成功),要么都不提交(回滚)。分布式事务的一致性通常通过2PC来保证(Two-Phase Commit, 2PC),这里面涉及到一个协调者和若干个参与者。第一阶段,协调者询问参与者事

  本文介绍了分布式系统维护数据一致性中非常重要且基础的技术Paxos协议的基本原理。

  背景 在一个分布式系统中,如何保证集群中所有节点中的数据完全相同并且能够对某个提案(Proposal)达成一致是分布式系统正常工作的核心问题,而共识算法就是用来保证分布式系统一致性的方法。 然而分布式系统由于引入了多个节点,所以系统中会出现各种非常复杂的情况;随着节点数量的增加,节点失效、故障或者宕机就变成了一件非常常见的事情,解决分布式系统中的各种边界条件和意外情况也增加了解决分布式一致...

  分布式系统中的一致性协议之两阶段提交协议(2PC)         两阶段提交协议是很常见的解决分布式事务的方式,他可以保证分布式事务中,要么所有参与的进程都提交事务成功,要么都取消事务,这样做可以在分布式环境中保持ACID中A(原子性)。      在两阶段提交协议中,包含了两种角色:协调者与参与者。参与者就是实际处理事务的机器,而协调者就是其中一台单独的处理分布式事务的机器。

  转自:paxos算法 背景Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的”La”,此人现在在微软研究院)于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视,使Lamport在八年后重新发表到...

  分布式系统中的读写模型分布式系统是由多个节点(指代一台服务器、存储设备等)构成,由于网络异常、宕机等节点并不能保证正常工作,特别是在节点数量很大的时候,出现异常状况的节点几乎是肯定的。为了保证系统的正常运行,能够提供可靠的服务,分布式系统中对于数据的存储采用多份数据副本(注:这里的副本并非只用来备份,它可参与提供系统服务)来保证可靠性,也就是其中一个节点上读取数据失败了那么可以转向另外

  分布式系统研究简介:随着计算及技术的发展,如今几乎所有实际应用的计算机系统都是分布式的。分布式系统的理论研究其实是从Leslie Lamport在1989年提出关于Paxos算法的论文开始的。这篇论文企图用一个寓言的方式来描述Paxos算法;但由于其理论过于超前,阐述方式非常奇特,导致其很长一段时间不被学术界接受和认可。从1996年开始,学术界才开始大量的分布式计算的理论研究,2001年Lamps...

  Paxos算法1.CAP定理:一个分布式系统不可能同时满足一致性(C),可用性(A)和分区容错性(P)这三个基本需求,最多只能同时满足其中的两项。2.2PC: Prepare(投票);Commit(事务提交),中断Rollback(事务回滚) 优点:原理简单,实现方便 缺点:同步阻塞,单点问题,脑裂(主从数据不一致)、保守(协调者超时机制判断是否要中断事务)等3.3PC:事务询问(CanCom

  ZookeeperPaxos算法一致性协议前言Paxos一致性协议可以说是一致性协议研究的起点,也以难以理解闻名。其实协议本身并没有多难理解,它的难理解性主要体现在:为何如此设计协议以及如何证明其正确性。本文尝试通过流程图来说明协议的内容以及基本应用过程,不涉及如何证明其正确性。基本概念Paxos可以分为两种:Single-DecreePaxos:决策单个 Value Multi-...

本文链接:http://maps-enzymes.com/duantijiaoxieyi/579.html