百度网站关键词优化在哪里做,普通人做电商赚钱吗,网站空间已过期,简单好看个人主页网站模板前言 相关系列
《分布式 目录》《分布式 Paxos算法 总结》《分布式 Paxos算法 问题》 参考文献
《图解超难理解的 Paxos 算法#xff08;含伪代码#xff09;》《【超详细】分布式一致性协议 - Paxos》
Basic-Paxos 基础帕克索斯算法…前言 相关系列
《分布式 目录》《分布式 Paxos算法 总结》《分布式 Paxos算法 问题》 参考文献
《图解超难理解的 Paxos 算法含伪代码》《【超详细】分布式一致性协议 - Paxos》
Basic-Paxos 基础帕克索斯算法 Paxos算法是目前公认解决分布式一致性问题的最有效算法之一甚至可以说它是过去几十年里一切分布式一致性算法的源头。我们对Paxos算法进行描述时通常都会带上“容错共识”两个关键字那么它们具体代表的是什么呢
容错是指分布式系统在部分节点宕机的情况下依然能够对外提供服务即CAP理论中的分区容错性共识是指分布式系统的各节点都能就某个操作达成共识即所有节点都批准执行这个操作。例如在分布式系统中操作A/B都想访问某服务那么令集群中的所有超半数/自定义数量服务都批准执行操作A/B的的过程就是所谓的达成共识。 概念 在正式对流程进行阐述之前我们需要先对Paxos算法的各类角色变量进行讲解。Paxos算法具有四类角色…其名称/作用具体如下
client 客户端负责向提案者发送操作请求proposer 提案者提案者负责接收封装客户端的操作请求为proposal 提案并为之生成全局唯一增长的编号。随后向各接收者广播准备/接收请求并根据其返回的通过/批准情况决定是否继续发送接收请求/判定其已达成一致acceptor 接收者接收者负责对准备接收请求中的提案进行判定以决定是否通过/批准该提案learner 学习者学习者负责获取已达成共识的提案并应用于分布式系统中。 Paxos算法具有三类“持久化”变量…其名称/作用具体如下
maxProposal 最大提案接收者在准备请求中通过的最大提案编号acceptedProposal 已批准提案接收者在接收请求中批准的最大提案编号acceptedValue 已批准值接收者在接收请求中批准的最大提案值。 流程 Paxos算法的流程分为“批准/获取”两个部分这其中“批准”部分负责提案的实际批准具体又可分为“准备/接收”两个阶段而“获取”部分则负责提案批准后的对外开放。关于提案批准的完整流程具体如下
prepare 准备阶段提案者在接收到客户端的操作请求后其会将之封装为提案并为之生成全局唯一增长的编号关于全局编号的具体生成方式此处不予讨论提案者会向各接收者广播即全体发送准备当前提案编号请求各接收者在收到准备当前提案编号请求后会比较“当前提案编号”和“最大提案”的大小如果“当前提案编号” “最大提案”则记录“最大提案”为“当前提案编号”并返回通过回应。而如果该接收者曾chosen 选中/批准过某项提案则“已批准提案/已批准值”会随通过回应一同返回否则便会无视请求/返回拒绝回应。而在未能收到超过半数/自定义数量通过回应的情况下提案者会为提案生成重新新编号并再次开始流程accept 接收阶段提案者在收到超过半数/自定义数量的通过回应后会向接收者广播接收当前提案编号当前提案值请求。如果在之前的准备请求回应中存在“已批准值”那么在接收请求中携带的“当前提案值”就必须应用该值否则就由当前提案者负责自定义。通过该规则可以得知Paxos算法只支持单个值/操作的共识各接收者在收到接收当前提案编号当前提案值请求后会再次比较“当前提案编号”与“最大提案”的大小如果“当前提案编号” “最大提案”则记录“已批准提案已批准值”为“当前提案编号当前提案值”并将“当前提案编号”返回意味着已批准当前提案否则便将原本的“最大提案”返回提案者在收到超过半数/自定义数量的“当前提案编号”后便会认为各接收者已对当前提案达成共识至此该提案便可以被学习者所获取应用于分布式系统了否则便意味着当前提案被否决提案者需要为提案重新生成新编号以再次开始流程。 当提案达成共识后如何让学习者获取该提案也是值得细究的问题。提案获取通常有以下几种方案
全量发送接收者一旦批准提案便将该提案广播给所有学习者。这种做法虽然可以让学习者尽快的获得批准提案但是却需要每个接收者与所有学习者逐一进行通信通信次数为二者乘积所以效率较低主从同步选定主学习者提案批准后由接收者通知主学习者并由主学习者负责通知其它的学习者。这个方案虽然多了一个步骤但是通信次数大大降低通信次数为学习者的数量。该方案同时引出另一个问题主学习者随时可能出现故障。多主从同步在主从同步的基础上由单个主学习者扩展成一个主学习者集合。集合中学习者数量越高可靠性也越好。 模拟 为了更好的熟悉Paxos算法此处我们举例描述Paxos算法“提案批准”的完整过程该案例中的Paxos集群共有A/B/C三个节点。注意这里的任意节点都可同时扮演提案者接收者。 提案者A/B分别将X赋值成3/5的操作请求封装为提案并为之生成全局唯一增长的编号1/2随后向各接收者广播。在准备阶段它们的交互结果如下 提案者A/B分别进入准备阶段并向各接收者广播准备1/2请求接收者A/B在收到提案者A的准备1请求后发现自身并没有通过/批准任何准备/接收请求因此直接返回空的通过回应接收者C由于在收到通过提案者B的准备2请求之后再收到提案者A的准备1请求并且提案者B的提案编号2大于提案者A的提案编号1因此无视了准备1请求/返回了拒绝回应接收者A/B在收到提案者B的准备2请求后由于其提案编号2 已通过的提案编号1因此两者都会返回空的通过回应。 由于提案者A/B的准备请求都收到了超过半数的通过回应因此提案者A/B都将进入Paxos算法的接收阶段。 提案者A向各接收者广播接收13请求。由于之前的通过回应中没有携带“已批准提案”因此提案的值可以完全自定义接收者A/B/C在收到接收13请求后由于其之前已经各自通过了准备2请求因此其都会返回提案编号2来表示未曾批准该请求提案者A在收到回应后发现提案编号2比自己的提案编号1大因此知晓自身提案未曾被批准因此重新回到准备阶段进行协商提案者B向各接收者广播接收25请求。由于之前的通过回应中没有携带“已批准提案”因此提案的值可以完全自定义接收者A/B/C在收到接收25请求后由于其都未通过提案编号更大的准备请求因此其都会返回提案编号2来表示批准了该请求提案者B在收到回应后发现提案编号2与自身提案编号相同且数量超过半数因此判定接收者对该提案已达成共识学习者可正式获取应用该提案。 在提案批准的流程中还有一种常见的情况是接收者在已批准某项提案的情况下收到提案编号更大的准备请求这种情况下其就需要在通过回应中返回已批准提案的编号值…模拟如下 提案者B向各接收者广播接收36请求接收者A收到批准了提案者B的接收36请求提案者A向各接收者广播准备4请求接收者B/C收到通过提案者A的广播准备4请求并因此未批准提案者B的接收36请求接收者A收到通过提案者A的准备4请求并在通过回应中携带了已批准提案编号值36提案者B判定接收者未能就提案达成共识重新进入准备阶段提案者A因为收到超过半数的通过请求而进入接收阶段向各接收者广播接收46请求。这其中6是因为在之前接收者A的通过回应中包含有已批准提案值因此该值便被作为了提案者A的提案值接收者A/B/C收到批准了接收46请求提案者A判定各接收者已就该提案达成共识。
Multi-Paxos算法 多帕克索斯算法 原始的Basic-Paxos算法只能达成一个值/操作的共识而Leslie Lamport则提出可以通过多次执行Basic-Paxos算法来达成一系列值/操作的共识。但由于多次协商会增加通信开销影响协商活性即指协商进入死循环因此Leslie Lamport则进一步提出了名为Multi-Paxos算法的解决方案。 Multi-Paxos算法对于Basic-Paxos算法的主要区别在于其引入了领导提案者的概念。在Multi-Paxos算法中提案准备接收请求的发送是由领导提案者专属负责的。Multi-Paxos系统会在启动时先通过Basic-Paxos算法从各提案者中选举出唯一的领导提案者用于“串行”发送提案请求这样就能避免并发提交而解决Basic-Paxos算法的活锁接收者不断通过编号更大的提案而导致无法批准已通过的旧提案该问题正常情况下可通过随机延迟的方式进行缓解问题。此外由于领导提案者会连续发送提案请求因此除去首个提案请求需要完整执行准备接收两个阶段为了应对网络分区而保留否则也可以不执行外后续提案请求的发送都可以只执行接收阶段从而便能减少RPC来提升共识的达成效率。 Multi-Paxos算法可以支持多领导提案者并存的场景。在实际的Multi-Paxos系统中由于网络分区情况的存在其可能出现选举出多个领导提案者的情况。对于这种情况Multi-Paxos算法是提供支持的因为如此一来其会自动退化成Basic-Paxos算法的多次执行场景。 领导提案者的宕机会导致Multi-Paxos系统不可用。对于一个功能完善的Multi-Paxos系统其应该具备对领导提案者的故障监测转移功能。理论上领导提案者需要不断向系统中的其它节点发送心跳以表示自身存活而一旦在指定时间内未收到心跳及一系列综合性盘点那么Multi-Paxos系统就会判定领导提案者已经宕机。这种情况下其就会选举新的领导提案者来代替工作即使旧领导提案者只是因为网络分区而无法连接。而在不存在可用提案者的情况下Multi-Paxos系统将陷入不可用的状态。
