《分布式系统的倚天剑和屠龙刀.ppt》由会员分享，可在线阅读，更多相关《分布式系统的倚天剑和屠龙刀.ppt（19页珍藏版）》请在三一办公上搜索。
1、分布式系统的倚天剑和屠龙刀,-Paxos 与Consistent Hashing 简介,云计算的挑战,尽管淘宝肯定对双十一的购物潮早有预料，但是淘宝支付宝业务在11号最初的几分钟还是出现了无法服务的现象。不过从这个现象中我们可以看出来一些东西。如何维护不同服务器上业务的一致性？面对海量变化的负载，如何高效调度？,一致性,业务逻辑的维护,大量负载的调度,不同设备上接收到的指令的顺序（外部一致性）,尽量少的资源切换（保持内部数据的一致）,Paxos,一致性哈希,倚天剑：Paxos,“安得倚天剑，跨海斩长鲸”-临江王节士歌李白一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个
2、节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。银行的存取业务多个节点的操作不仅只用在分布式系统，凡是多个过程需要达成某种一致性的都可以用到Paxos 算法。,P:proposer,也可以是客户端，提交议案。C:coordinator,协调者，A:acceptor,选举者，L:learner,学习者，A round include two phases:(i)phase 1(ii)phase 2crnd:某C开始的rounds中的最高的round numbercval:某C在round crnd中提出的value。rnd:某A参加过的rounds中最高的round numbervr
3、nd:某A批准过的rounds中最高的round numbervval:某A在round vrnd中批准的value。Quorum:a majority of the acceptors所有的消息可能丢失或者延时，但是不会出错。,message,Phase 1a:preparePhase 1b:promisePhase 2a:acceptPhase 2b:accepted,1、C要提出一个value并获得批准的过程叫做一个round,它两个阶段：phase1和phase2.2、C开始某个round i,发送phase 1ai给所有的A,如果收到某A的rejectj(ji),重新发送phase
4、1aj+x（为方便举例，令x=1）,并设置crnd=j+1,cval=0。3、Pick a value:收到来自某quorum的phase 1bj+1,vrnd,vval消息回复。令K为来自该quorum消息中所有vrnd的最大值,V为来自该quorum的消息中vrnd=k的消息对应的vval值的集合（当k0时,fast paxos在文中证明了这样的vval值只有一个）。If k=0,C可以任意挑选一个来自P的value作为value_selse，将V中的那个唯一的value作为我们的挑选value_s将value_s和round number j+1 作为phase 2a的内容发送给所有的A
5、,并设置cval=value_s,若收到某A的Nackh,hj，设置crnd=h+1并重复上述prepare过程。否则，若收到来自某quorum的phase2b消息，则说明对该value_s的选举已经完成。,任何一个A必须批准它收到的第一个value。A在round i的prepare过程(phase 1)收到phase1a:(a)如果i=rnd,令rnd=i，发送phase 1b消息。Phase 1b:rnd,vrnd,vvalA在round i的phase 2收到phase 2ai,vval_i:(a)如果i=rnd,令rnd=vrnd=i,vval=vval_i,发送phase2b故而在
6、其它的C开始更高round number的过程时,Round有可能被中断。,C Receive phase1b from a quorum,pick any value proposed by p.,C(0,null),初始化(round 1),A(0,0,null),A(0,0,null),A(0,0,null),A(0,0,null),A(0,0,null),P,P,P,P,L,L,L,L,C(0,null),C(0,null),C(1,null),Phase1a 1,because 10 A(1,0,null),because 10 A(1,0,null),because 10 A(1,
7、0,null),because 10 A(1,0,null),Phase1b1,0,null,C(1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),Phase2b,Phase2b,L receive phase2b from a quorum,then learn value_s,L receive phase2b from a quorum,then learn value_s,L receive phase2b from a quorum,then learn valu
8、e_s,L receive phase2b from a quorum,then learn value_s,because 10 A(1,0,null),Phase2a1,Value_s,正常运行(round 2 as an example),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),A(1,1,value_s),P,P,P,P,L,L,L,L,C(1,value_s),C(0,null),C(0,null),Phase1a1,Reject 1,Phase 1a2,Phase 1b2,1,value_s,C(1,n
9、ull),C(2,null),Phase 2a2,value_s,Phase 2b,Phase 2b,A(2,1,value_s),A(2,1,value_s),A(2,1,value_s),A(2,1,value_s),A(2,1,value_s),A(2,2,value_s),A(2,2,value_s),A(2,2,value_s),A(2,2,value_s),A(2,2,value_s),实用,微软对Paxos拥有专利Google的实现：chubby（未开源）应用于Spanner的TrueTime系统中。ZooKeeper(开源)一个类Paxos实现,屠龙刀：一致性哈希,武林至尊，宝
10、刀屠龙，号令天下，莫敢不从！-倚天屠龙记对多台服务器的调度 应用背景：有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。需求：当系统增加一台或减少一台机器的时候，颠簸尽可能的少,HASH算法单调性,Hash算法的一个衡量指标是单调性（Monotonicity），定义如下：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。,传统的HASH,1，4,3，6,2，5,1，2，3，4，5，6,2，4，6,1，3，5,3，6,不管是对于增加服务器，还是减少服务器，需要迁移的数据都是4个，也就是有(N-1)/N(减少)和N/(N+1)(增加)的数据需要转移,一致性哈希,虚拟节点,创新的特点,一致性哈希相对于传统哈希来说，在思路上有了很大的不同。传统HASH是取一个较小的模数，从而将数据映射到一个小范围内。consistent hashing 的本质是将模数取的比较大，为2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向。,
