《可靠分布式系统基础-paxos的直观解释》由会员分享，可在线阅读，更多相关《可靠分布式系统基础-paxos的直观解释（44页珍藏版）》请在金锄头文库上搜索。
1、Paxos可靠分布式系统基础：paxos的直观解释2015-07-02drdrxp背景背景多个节点一起完成一件事情.分布式中唯一的一个问题：对某事达成一致.Paxos:分布式系统的核心算法.目目录录1.问题2.复制策略3.Paxos算法4.Paxos优化问题问题对系统的需求:持久性要达到：99.99999999%我们可以用的基础设置:磁盘:4%年损坏率服务器宕机时间:0.1%或更长IDC间丢包率:5%30%解决方案解决方案(可能可能)多副本xNR=N2+1容忍最多(N-1)2个节点损坏.TimeNode.1ClientNode.2Node.3多数派写多数派写.后写入后写入优胜优胜最后1次写入覆
2、盖先前写入.所有写入操作需要有1个全局顺序：时间戳TimeNode.1ClientNode.2Node.3:高可靠性.:高可用性.:数据完整性有保证.够了吗？多数派写多数派写.多数派写多数派写.W+RN一致性:最终一致性事务性:非原子更新脏读更新丢失问题http:en.wikipedia.orgwikiConcurrency_control一个假想存一个假想存储储服服务务一个有3个存储节点的存储服务集群.使用多数派读写的策略.只存储1个变量“i”.“i”的每次更新对应有多个版本:i1i2i3这个存储系统支持3个命令:get读最新的“i”set设置下个版本的i的值为inc对“i”加，也生成1个新
3、版本我们将用这个存储系统来演示多数派读写策略的不足，以及如何用paxos解决这些问题.一个假想存一个假想存储储服服务务.实现实现命令实现：set直接对应多数派写.inc(最简单的事务型操作):1.通过多数派读，读取最新的“i”:i12.Leti2=i1+n3.seti2Xseti2=3Xgeti212100322132Xgeti1=2i2=i1+1322132seti2=3OKseti2=4一个假想存一个假想存储储服服务务.并并发问题发问题XXgeti212100322132532153Xgeti1=2i2=i1+1我们期待最终X可以读到i3=5这需要Y能知道X已经写入了i2。如何实现这个机制
4、？Ygeti1=2Yi2=i1+2322132此时为了保证正确，Y必须重新运行多数派读，然后再进行一次多数派写这这1步步Y必必须须失失败败。否否则则X写入的写入的值值会会丢丢失。失。一个假想存一个假想存储储服服务务.在X和Y的2次“inc”操作后，为了得到正确的i3：整个系统里对i的某个版本(i2)，只能有1次成功写入.推广为:在存储系统中，一个值(1个变量的1个版本)在被认为确定(客户端接到OK)之后，就不允许被修改().如何定义“被确定的”如何避免修改“被确定的”值如何确定一个如何确定一个值值XYAnyvaluesetXNoXX-Anyvalueset-YYesYgivesupXXX-XX
5、-方案:每次写入一个值前，先运行一次多数派读，来确认是否这个值（可能）已经被写过了.如何确定一个如何确定一个值值.并并发问题发问题XYAnyvaluesetXNoYYXYXX-Anyvalueset-YNoX但是，X和Y可能同时以为还没有值被写入过，然后同时开始写。更新丢失如何确定一个如何确定一个值值.XAnyvaluesetXNoYYXY-XY-Anyvalueset多数派读的同时写入：X是最后读的。-YNo多数派读的同时写入：Y是最后读的X-方案改进:让存储节点记住谁最后1次做过“写前读取”，并拒绝之前其他的“写前读取”的写入操作。现在节点1、2只接受X的写入现在节点2、3只接受Y的写入如
6、何确定一个如何确定一个值值.使用这个策略，一个值(i的每个版本)可以被安全的存储.LeslieLamport写了个这个算法的paper.PaxosPaxos是什么是什么一个可靠的存储系统:基于多数派读写.每个paxos实例用来存储一个值.用2轮RPC来确定一个值.一个值确定后不能被修改.确定指被多数派接受写入.强一致性.PaxosClassicPaxos1个实例(确定1个值)写入需要2轮RPC.MultiPaxos约为1轮RPC，确定1个值(第1次RPC做了合并).FastPaxos没冲突：1轮RPC确定一个值.有冲突：2轮RPC确定一个值.Paxos:执执行的条件行的条件存储必须是可靠的:没
7、有数据丢失和错误否则需要用ByzantinePaxos容忍:消息丢失(节点不可达)消息乱序Proposer:发起paxos的进程.Acceptor:存储节点，接受、处理和存储消息.Quorum(Acceptor的多数派):n2+1个Acceptors.Round：1轮包含2个阶段：Phase-1&Phase-2每1轮的编号(rnd):单调递增；后写胜出；全局唯一(用于区分Proposer)Paxos:概念概念Acceptor看到的最大rnd(last_rnd):Acceptor记住这个值来识别哪个proposer可以写。Value(v):Acceptor接受的值.Valueroundnumbe
8、r(vrnd):Acceptor接受的v的时候的rnd值被确定的定义：有多数(多于半数)个Acceptor接受了这个值.Paxos:概念概念.Paxos:Classic-phase1Xrnd=1Xlast_rnd=0v=nilvrnd=0last_rnd=0v=nilvrnd=0.Phase111-ProposerXAcceptor123当Acceptor收到phase-1的请求时：如果请求中rnd比Acceptor的last_rnd小，则拒绝请求将请求中的rnd保存到本地的last_rnd.从此这个Acceptor只接受带有这个last_rnd的phase-2请求。返回应答，带上自己之前的l
9、ast_rnd和之前已接受的v.Paxos:Classic-phase1.Xrnd=1XPhase111-ProposerXAcceptor123当Proposer收到Acceptor发回的应答：如果应答中的last_rnd大于发出的rnd:退出.从所有应答中选择vrnd最大的v:不能改变(可能)已经确定的值如果所有应答的v都是空，可以选择自己要写入v.如果应答不够多数派，退出last_rnd=0v=nilvrnd=0last_rnd=0v=nilvrnd=0.Paxos:Classic-phase2Xv=xrnd=1XAcceptedPhase211-1x11x1-ProposerXAcce
10、ptor123v=xvrnd=1Proposer:发送phase-2，带上rnd和上一步决定的vPaxos:Classic-phase2.Xv=xrnd=1XAcceptedPhase211-1x11x1-ProposerXAcceptor123v=xvrnd=1Acceptor:拒绝rnd不等于Acceptor的last_rnd的请求将phase-2请求中的v写入本地，记此v为已接受的值last_rnd=rnd保证没有其他Proposer在此过程中写入过其他值Paxos:栗子栗子1:Classic无冲突无冲突Xrnd=1Xlast_rnd=0v=nilvrnd=0Xv=xrnd=1XAcce
11、ptedPhase1Phase211-11-1x11x1-ProposerXAcceptor123v=xvrnd=1Paxos:栗子栗子2.1:解决并解决并发发写冲突写冲突XYrnd=1XPhase1forXrnd=2OKforgetXPhase1forYYXYv=xrnd=1Failv=yrnd=2OKPhase2Yround=1round=2Time2y21x12y221x1221x1221211-11-Paxos:栗子栗子2.2:X不会修改确定的不会修改确定的vXrnd=3Xv=yvrnd=2v=xvrnd=1chooseyPhase1Xv=yvrnd=3Phase2round=32y2
12、1x12y23y23x12y23y23x12y2XOK3y33y33y3X只能选择v=“y”，因为它可能是一个被确定的值。Paxos.其他其他Learner角色:Acceptor发送phase-3到所有learner角色，让learner知道一个值被确定了.多数场合Proposer就是1个Learner.Livelock:多个Proposer并发对1个值运行paxos的时候，可能会互相覆盖对方的rnd，然后提升自己的rnd再次尝试，然后再次产生冲突，一直无法完成MultiPaxos将多个paxos实例的phase-1合并到1个RPC；使得这些paxos只需要运行phase-2即可。应用:chu
13、bbyzookeepermegastorespannerFastPaxosProposer直接发送phase-2.FastPaxos的rnd是0.0保证它一定小于任何一个Classicrnd，所以可以在出现冲突时安全的回退到ClassicPaxos.Acceptor只在v是空时才接受Fastphase-2请求如果发成冲突，回退到ClassicPaxos，开始用一个rnd0来运行。但是FastPaxos比ClassicPaxos高效吗？FastPaxos的多数派的多数派-0 x0-0 x00 x00y00 x0Xfastrnd=0Xphase2OKYfastrnd=0phase225Fails-
14、0y0如果Fast的多数派也是n2+1=3:当上图中Y发现冲突，回退到Classic的时候:Y无法确定哪个值是可能被确定下来的：x0ory0解决方法是让未确定的值不占据n2+1个节点中的多数派因此:Fast的多数派必须nFastPaxos里的值被确定的条件是被n+1个Acceptor接受.FastPaxos的多数派的多数派.Q=n可用性降低，因为FastPaxos需要更多的Acceptor来工作.FastPaxos需要至少5个Acceptors，才能容忍1个Acceptor不可用.FastPaxos45Y发现发现冲突冲突-0 x0-0 x00 x00 x00y00 x00 x00 x00 x0
15、2y00 x00 x02x02x02x20 x00 x02x22x2Xfastrnd=0Xphase2OKYfastrnd=0phase215FailYclassicrnd=2phase1OKxYphase2OKwritesxY在3个Acceptor中看到2个x0因此Y必须选择x0，因为x0可能是1个被确定的值.y0不可能是1个被确定的值，因为即使剩下的2个Y没有联系到的Acceptor都接受了y0，也不会达到(5)的多数派。FastPaxos45XY都冲突都冲突-0 x00 x00 x00y00y01x01x01x00y00y01x01x02y02y02x0Xfastrnd=0Xphase2ConflictYfastrnd=0phase2YConflict0 x00 x00 x00y00y0Xclassicrnd=1phase1Yclassicrnd=2phase1XOKonlyxYOKchooseyYphase22y22y22y22y22y2Xfailinphase2Note在phase-2Acceptor可以接受rnd=last_rnd的请求Q&AThanksdrdr.xp:drdrxp
