未备案的网站可以百度推广吗,长沙营销网站设计,泰安房产网签,建设工程施工合同范本免费下载自从Lamport在1998年发表Paxos算法后#xff0c;对Paxos的各种改进工作就从未停止#xff0c;其中动作最大的莫过于2005年发表的Fast Paxos。无论何种改进#xff0c;其重点依然是在消息延迟与性能、吞吐量之间作出各种权衡。为了容易地从概念上区分二者#xff0c;称前者C…自从Lamport在1998年发表Paxos算法后对Paxos的各种改进工作就从未停止其中动作最大的莫过于2005年发表的Fast Paxos。无论何种改进其重点依然是在消息延迟与性能、吞吐量之间作出各种权衡。为了容易地从概念上区分二者称前者Classic Paxos改进后的后者为Fast Paxos。 1. Fast Paxos概览 Lamport在40多页的论文中不仅提出了Fast Paxos算法并且还从工程实践的角度重新描述了Paxos使其更贴近应用场景。从一般的Client/Server来考虑Client其实承担了Proposer和Learner的作用而Server则扮演Acceptor的角色因此下面重新描述了Paxos算法中的几个角色 Client/Proposer/Learner负责提案并执行提案CoordinatorProposer协调者可为多个Client通过Coordinator进行提案Leader在众多的Coordinator中指定一个作为LeaderAcceptor负责对Proposal进行投票表决就是Client的提案由Coordinator进行Coordinator存在多个但只能通过其中被选定Leader进行提案由Leader交由Server进行表决之后Client作为Learner学习决议的结果。 这种方式更多地考虑了Client/Server这种通用架构更清楚地注意到了Client既作为Proposer又作为Learner这一事实。 同样要注意到的是如果Leader宕机了为了保证算法的正确性需要一个Leader的选举算法但与之前一样Lamport并不关心这个Leader选举算法他认为可以简单地通过随机或超时机制实现。 另外在Classic Paxos中从每次Proposer提案到决议被学习需要三个通信步骤 Proposer-----Leader-----Acceptor-----Learner 从直观上来说Proposer其实更“知道”提交那个Value如果能让Proposer直接提交value到Acceptor则可以把通信步骤减少到2个。Fast Paxos便是基于此而产生。 2. Make Paxos Faster 我们再回顾下Classic Paxos的几个阶段 Phase1aLeader提交proposal到AcceptorPhase2bAcceptor回应已经参与投票的最大Proposer编号和选择的ValuePhase2aLeader收集Acceptor的返回值Phase2a.1如果Acceptor无返回值则自由决定一个Phase2a.2 如果有返回值则选择Proposer编号最大的一个Phase2bAcceptor把表决结果发送到Learner 很明显在Phase2a.1中如果Leader可以自由决定一个Value则可以让Proposer提交这个Value自己则退出通信过程。只要之后的过程运行正常Leader始终不参与通信一直有Proposer直接提交Value到Acceptor从而把Classic Paxos的三阶段通信减少为两阶段这便是Fast Paxos的由来。因此我们更加形式化下Fast Paxos的几个阶段 Phase1a与之前相同Phase1b与之前相同Phase2aLeader收集Acceptor的返回值Phase2a.1如果Acceptor无返回值则发送一个Any消息给Acceptor之后Acceptor便等待Proposer提交ValuePhase2a.2如果有返回值则根据规则选取一个Phase2bAcceptor把表决结果发送到Learner包括Leader算法主要变化在Phase2a阶段即 若Leader可以自由决定一个Value则发送一条Any消息Acceptor便等待Proposer提交Value若Acceptor有返回值则Acceptor需选择某个Value先不考虑实现从形式上消息仅需在Proposer-----Acceptor-----Learner之间传递即可也即仅需2个通信步骤。下面我们详细说明算法过程 3 一些定义 Quorum在Classic Paxos中一直通过多数派Majority来保证算法的正确性对多数派再进一步抽象化称为“Quorum”要求任意两个Quorum之间有交集从而间接表达了majority的含义Round在Classic Paxos中Proposer每次提案都用一个全序的编号表示如果执行顺利该编号的Proposal在经历Phase1Phase2后最终会执行成功。在Fast Paxos称这个带编号的Proposal的执行过程为“Round”i-Quorum在Classic Paxos执行过程中一般不会明确区分每次Round执行的Quorum虽然也可以为每个Round指定一个Quorum。在Fast Paxos中会通过i-Quorum明确指定Round i需要的QuorumClassic Round执行Classic Paxos的Round称为Classic RoundFast Round如果Leader发送了Any消息则认为后续通信是一个Fast Round若Leader未发送Any消息还是跟之前一样通信则后续行为仍然是Classic Round。根据Lamport描述Classic Round和Fast Round可通过Round Number进行加以区分。4 Any消息 在正常情况下Leader若可以自由决定一个Value应该发生一条Phase2a消息其中包含了选择的Value但此时却发送了一条无Value的Any消息。Acceptor在接收到Any消息后可做一些开始Fast Round的初始化工作等待Proposer提交真正的Value。Any消息的意思是Acceptor可以做任意的处理。 因此一个Fast Round包括两个阶段由Any消息开始的阶段和由Proposer提交Value的结束阶段而Leader只是起到一个初始化过程的作用如果没有错误发生Leader将退出之后的通信中过程。 下面是Classic Paxos交互图 下面是Fast Paxos的交互图 5 冲突 在Classic Paxos中Acceptor投票的value都是Leader选择好的所以不存在同一Round中投票多个Value的场景从而保证了一致性。但在Fast Round中因为允许多个Proposer同时提交不同的Value到Acceptor这将导致在Fast Round中没有任何value被作为最终决议这也称为“冲突”Collision Proposer提交的Round是全序的不同的Proposer提交的Round肯定不一样同一Proposer不可能在同一Round中提交不同的Value那为什么还会有同一Fast Round中有多个Value的情况原因在于Fast Round与Round区别当Fast Round开始后会被分配一个唯一的Round Number之后无论多少个Proposer提交Value都是基于这个Round Number而不管Proposer提交的Round是否全序。 比如Fast Round Number为10Proposer1提交了111Proposer2提交了122但对Fast Round来说存在1012两个Value。 因为冲突的存在会导致Phase2a.2的选择非常困难原因是 在Classic Paxos中如果Acceptor返回多个Value只要排序选择最高的编号对应的Value即可因为Classic Paxos中的Value都是有Leader选择后在Phase2a中发送的因此最高编号的Value肯定只有一个。但在Fast Paxos中最高编号的Value会发现多个比如1012。 假如当前Leader正在执行第i个Classic Round(i-Quorum为Q) 得到Acceptor反馈的最高编号为k有两个valuev、w说明Fast Round k存在两个k-QuorumRv,Rw。 O4(v)下面定义在Round k中v或w被选择的条件 如果v在Round k中被选择那么存在一个k-Quorum R使得对任意的Acceptor a∈Q∩R都对v作出投票。 这个问题也可表述为R中的所有Acceptor都对v作出投票并且Q∩R≠φ因为如果Q∩Rφ则Round i将无法得知投票结果 因此如果保证下面两个条件 每个Acceptor在同一Fast Round中仅投票一个ValueQ∩Rv∩Rw≠φ则v、w不可能同时被选择 6 确定Quorum 根据上面描述为了防止一次Fast Round选择多个ValueQuorum需要满足下面两个条件 任意两个Classic Quorum有交集任意一个Classic Quorum与任意两个Fast Quorum有交集不妨设总Acceptor数为NClassic Round运行的最大失败Acceptor数为FFast Round允许的失败数为E即N-F构成Classic Round的一个QuorumN-E构成Fast Round的一个Quorum。 上面两个条件等价于 N2FN2EF设Qc,Qf分别为Classic和Fast Round的Quorum大小经过整理可得两个下限结果 |Qc| |Qf| ≥ N − ⌈N/3⌉ 1 ≥ ⌊2N/3⌋ 1|Qc| ≥N-⌈N/2⌉1 ⌈N/2⌉1|Qf|≥N-⌈N/4⌉≥⌈3N/4⌉证明请参考一致性算法中的节点下限 7 冲突Recovery 作为优化Acceptor在投票Value时也应该发送到Leader这样Leader就很容易能发现冲突。Leader如果在Round i发现冲突可以很容易地开始Roun i1从Phase1a开始重新执行Classic Paxos过程但这个其实可以进一步优化我们首先考虑下面这个事实 如果Leader重启了Round i1并且收到了i-Quorum个Acceptor发送的Phase1b消息则该消息明确了两件事情 报告Acceptor a参与投票的最大Round和对应的Value承诺不会对小于i1的Round作出投票假如Acceptor a也参与了Round i的投票则a的Phase1b消息同样明确了上述两件事情并且会把对应的RoundValue在Phase2b中发送给Leader当然还有Learner一旦Acceptor a执行了Phase2b则也同时表明a将不会再对小于i1的Round进行投票。 也就是说Round i的Phase2b与Round i1的Phase1b有同样的含义也暗含着如果Leader收到了Round i的Phase2b则可直接开始Round i1的Phase2a。经过整理产生了两种解决冲突(Recovery)的方法 7.1 基于协调者的Recovery 如果Leader在Round i 中收到了(i1)-Quorum个Acceptor的Phase2b消息并且发现冲突则根据O4(v)选取一个value直接执行Round i1的Phase2a否则从Phase1a开始重新执行Round i1 7.2 基于非协调的Recovery 作为基于协调Recovery的扩展非协调要求Acceptor把Phase2b消息同时发送给其他Quorum Acceptor由每个Acceptor直接执行Round i1的Phase2a但这要求i-Quorum与(i1)-Quorum必须相同并且遵循相同选择value的规则。 这种方式的好处是Acceptor直接执行Round i1的Phase2a无需经过Leader节省了一个通信步骤缺点是Acceptor同时也作为Proposer搞的过于复杂。 8 Fast Paxos Progress 至此再完整地总结下Fast Paxos的Progress Phase1a与之前相同Phase1b与之前相同Phase2aLeader收集Acceptor的返回值Phase2a.1如果Acceptor无返回值则发送一个Any消息给Acceptor之后Acceptor便等待Proposer提交ValuePhase2a.2如果有返回值 2.1 如果仅存在一个Value则作为结果提交 2.2 如果存在多个Value则根据O4(v)选取符合条件的一个 2.3 如果存在多个结果并且没有符合O4(v)的Value则自由决定一个Phase2bAcceptor把表决结果发送到Learner包括Leader9. 总结 Fast Paxos基本是本着乐观锁的思路如果存在冲突则进行补偿。其中Leader起到一个初始化Progress和解决冲突的作用如果Progress一直执行良好则Leader将始终不参与一致性过程。 因此Fast Paxos理论上只需要2个通信步骤而Classic Paxos需要3个但Fast Paxos在解决冲突时有至少需要1个通信步骤在高并发的场景下冲突的概率会非常高冲突解决的成本也会很大。 另外Fast Paxos把Client深度引入算法中致使其架构远没Classic Paxos那么清晰也没Classic Paxos容易扩展。 还有一点要注意的是Fast Quorum的大小比Classic的要大一般Fast Quorum至少需要4个节点(3E1)而Classic Paxos需要3个(2F1)请参考一致性算法中的节点下限。 总之在我看来Fast Paxos是一个理论上可行但实际中很难操作的算法实际中用的比较多的还是Classic Paxos的各种简化形式 10 参考资料 Fast Paxos(Lamport 2005)Multicoordinated PaxosOn the Coordinator’s Rule for Fast PaxosClassic Paxos vs. Fast Paxoshttp://en.wikipedia.org/wiki/Paxos_(computer_science) 转载于:https://www.cnblogs.com/kaffeetrinken/p/8490736.html
