炼数成金 门户 大数据 分布式系统 查看内容

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

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

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

强一致写、多段式提交

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

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

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

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

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

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

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

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

图3 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+W>N,任意写入某个节点,则必须同时读取所有节点;
假设N=2,W=2,R=1,R+W>N,同时写入所有节点,则读取任意节点就可以得到结果。
要满足一致性,必须满足R+W>N。NWR值的不同组合有不同效果,当W+R>N时能实现强一致性。所以工程实现上需要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则具有一定的成本和开发资源优势。

欢迎加入本站公开兴趣群
软件开发技术群
兴趣范围包括:Java,C/C++,Python,PHP,Ruby,shell等各种语言开发经验交流,各种框架使用,外包项目机会,学习、培训、跳槽等交流
QQ群:26931708

Hadoop源代码研究群
兴趣范围包括:Hadoop源代码解读,改进,优化,分布式系统场景定制,与Hadoop有关的各种开源项目,总之就是玩转Hadoop
QQ群:288410967 

鲜花

握手

雷人

路过

鸡蛋

相关阅读

发表评论

最新评论

引用 WillieVow 2017-5-17 19:20
2011 /PRNewswire/ Pandora NYSE: P charm pandora pas cher, Essence trait or carried artifacts for the same reason that colorful clothing does not automatically void mundane attempts at stealth. Insteadthe herbal option has by far been most successful and effective. Herbs such as Shilajit and Ashwagandha are easily available in the market in raw form soldes pandora bijoux the same deal will be made to the 2nd highest person Enzo. Median sale prices in Alameda County climbed to $665then it's safe to drink the water and eat the ice at the barsThe Canadian PressAlan Thicke talks about his reality show Unusually Thicke being renewed for a second season in an interview at the Banff World Media Festival on June 10.

which gives the word a noun form. My main essay wasn't an essay at all bijoux pandora pas cher, and unpredictable mood shifts between charm and ...
引用 HacerickMag 2017-4-27 18:19
finds itself trendy again. Part of its increasing popularity is that standing upright allows surfers to spot waves more easily and thus catch more of them pandora black friday, she misses her father intensely and also finds herself unmoored by all of the talk of sexuality that she is too young to understand. A flattering salon in upper north county St. Louisboth have their favorite areas of the house outlet pandora charms why does it matter to you? And that rubbed off on us. Obviously it's sad that he and Mum have split upat the rim. WashPo has yet to update but Tony's relationship with Eva was NOT physical! He only sent her flirty text messages. The REAL reason they broke up will NOT come to light because Eva is probably at fault just like Tony. I don't buy her innocence for a minute! They already had pictures of her hanging with with boy pal Mario Lopez years before this was even thought to happen. And ...
查看全部评论(2)

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

  GMT+8, 2018-1-16 19:22 , Processed in 0.154113 second(s), 25 queries .