--Paxos 与Consistent Hashing 简介 分布式系统的 倚天剑和屠龙刀 --Paxos 与Consistent Hashing 简介

云计算的挑战 如何维护不同服务器上业务的一致性？ 面对海量变化的负载，如何高效调度？ 尽管淘宝肯定对双十一的购物潮早有预料，但是淘宝支付宝业务在11号最初的几分钟还是出现了无法服务的现象。 不过从这个现象中我们可以看出来一些东西。 如何维护不同服务器上业务的一致性？ 面对海量变化的负载，如何高效调度？ Google Spanner 和 淘宝的快速恢复。（业务逻辑的一致性和快速的、低成本的负载均衡）

一致性 大量负载的调度 业务逻辑的维护 尽量少的资源切换 不同设备上接收到的指令的顺序 （保持内部数据的一致） （外部一致性） Paxos 一致性哈希

倚天剑：Paxos “安得倚天剑，跨海斩长鲸” ---《临江王节士歌》李白 一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。 银行的存取业务 多个节点的操作 不仅只用在分布式系统，凡是多个过程需要达成某种一致性的都可以用到Paxos 算法。

P:proposer,也可以是客户端，提交议案。 C:coordinator,协调者， A:acceptor,选举者， L:learner,学习者， A round include two phases: (i)phase 1 (ii)phase 2 crnd:某C开始的rounds中的最高的round number cval:某C在round crnd中提出的value。 rnd:某A参加过的rounds中最高的round number vrnd:某A批准过的rounds中最高的round number vval:某A在round vrnd中批准的value。 Quorum:a majority of the acceptors 所有的消息可能丢失或者延时，但是不会出错。

message Phase 1a:prepare Phase 1b:promise Phase 2a:accept Phase 2b:accepted

1、C要提出一个value并获得批准的过程叫做一个round,它两个阶段：phase1和phase2. 2、C开始某个round i,发送phase 1a[i]给所有的A,如果收到某A的reject[j](j>i),重新发送phase 1a[j+x]（为方便举例，令x = 1）,并设置[crnd = j+1,cval = 0]。 3、Pick a value: 收到来自某quorum的phase 1b[j+1,vrnd,vval]消息回复。令K为来自该quorum消息中所有vrnd的最大值,V为来自该quorum的消息中vrnd = k的消息对应的vval值的集合（当k>0时,fast paxos在文中证明了这样的vval值只有一个）。 If k = 0,C可以任意挑选一个来自P的value作为value_s else，将V中的那个唯一的value作为我们的挑选value_s 将value_s和round number j+1 作为phase 2a的内容发送给所有的A,并设置cval = value_s,若收到某A的Nack[h],h>j，设置crnd = h+1并重复上述prepare过程。否则，若收到来自某quorum的phase2b消息，则说明对该value_s的选举已经完成。

任何一个A必须批准它收到的第一个value。 A在round i的prepare过程(phase 1)收到phase1a: (a)如果i<rnd,且round rnd的C(beginner)不是round i的C’(beginner),即C!=C’，则通知round i的C’拒绝(reject[rnd])它的prepare请求。如果C = C’，则忽略这个prepare请求。(important!) (b)如果i >= rnd,令rnd = i，发送phase 1b消息。 Phase 1b:[ rnd,vrnd,vval] A在round i的phase 2收到phase 2a[i,vval_i]: (a)如果i<rnd, 即C!=C’，则通知round i的C’拒绝(Nack[rnd])它的accept请求。如果C = C’，则忽略这个accept请求。(important!) (b)如果i>=rnd,令rnd = vrnd = i,vval = vval_i,发送phase2b 故而在其它的C开始更高round number的过程时,Round有可能被中断 。

角色介绍 A(rnd,vrnd,vval) P L C(crnd,cval)

L receive phase2b from a quorum,then learn value_s Phase2a[1,Value_s] 初始化(round 1) Phase2b Phase2b L receive phase2b from a quorum,then learn value_s A(0,0,null) Phase2a[1,Value_s] C Receive phase1b from a quorum,pick any value proposed by p. Phase1a [ 1] because 1>0 A(1,0,null) P Phase1b[1,0,null] A(1,1,value_s) C(1,value_s) L C(1,null) C(0,null) A(0,0,null) A(1,1,value_s) because 1>0 A(1,0,null) L receive phase2b from a quorum,then learn value_s L P C(0,null) because 1>0 A(1,0,null) A(0,0,null) A(1,1,value_s) L receive phase2b from a quorum,then learn value_s L because 1>0 A(1,0,null) A(1,1,value_s) P C(0,null) A(0,0,null) L L receive phase2b from a quorum,then learn value_s because 1>0 A(1,0,null) A(1,1,value_s) A(0,0,null) P

正常运行(round 2 as an example) A(2,1,value_s) A(1,1,value_s) P A(2,2,value_s) Phase 2b Phase 2b L C(1,value_s) Reject [1] A(1,1,value_s) Phase 1a[2] A(2,1,value_s) Phase 1b[2,1,value_s] A(2,2,value_s) Phase1a[1] Phase 2a[2,value_s] C(2,null) L P C(1,null) C(0,null) A(1,1,value_s) A(2,1,value_s) A(2,2,value_s) L C(0,null) P A(1,1,value_s) A(2,1,value_s) A(2,2,value_s) L A(1,1,value_s) A(2,1,value_s) P A(2,2,value_s)

实用 微软对Paxos拥有专利 Google的实现：chubby（未开源）应用于Spanner的TrueTime系统中。 ZooKeeper (开源)一个类Paxos实现

屠龙刀：一致性哈希 武林至尊，宝刀屠龙，号令天下，莫敢不从！ --《倚天屠龙记》 对多台服务器的调度 应用背景：有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。 需求：当系统增加一台或减少一台机器的时候，颠簸尽可能的少

HASH算法单调性 Hash 算法的一个衡量指标是单调性（ Monotonicity ），定义如下： 　　单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

传统的HASH 1，2，3，4，5，6 1，4 1，3，5 2，5 2，4，6 3，6 3，6 不管是对于增加服务器，还是减少服务器，需要迁移的数据都是4个，也就是有(N-1)/N(减少)和N/(N+1)(增加)的数据需要转移

一致性哈希

虚拟节点

创新的特点 一致性哈希相对于传统哈希来说，在思路上有了很大的不同。 传统HASH是取一个较小的模数，从而将数据映射到一个小范围内。 consistent hashing 的本质是将模数取的比较大，为 2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向。