广州网站建设全包,百度怎么优化关键词排名,google play应用商店,成都著名设计师Paxo算法介绍
Paxos算法是莱斯利兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法。
Paxos产生背景
Paxos算法是基于消息传递且具有高度容错特性的一致性算法#xff0c;是目前公认的解决分布式一致性问题最有效的算法之一#xff0c;其解决的问题就是在分…Paxo算法介绍
Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法。
Paxos产生背景
Paxos算法是基于消息传递且具有高度容错特性的一致性算法是目前公认的解决分布式一致性问题最有效的算法之一其解决的问题就是在分布式系统中如何就某个值决议达成一致。
Paxos算法主要是针对Zookeeper这样的master-slave集群对某个决议达成一致也就是副本之间写或者leader选举达成一致。我觉得这个算法和狭义的分布式事务不是一样的。
在常见的分布式系统中总会发生诸如机器宕机或网络异常包括消息的延迟、丢失、重复、乱序还有网络分区也就是会发生异常的分布式系统)等情况。
Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中快速且正确地在集群内部对某个数据的值达成一致。也可以理解成分布式系统中达成状态的一致性。
Paxos保证一致性
Paxos算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。一个典型的场景是在一个分布式数据库系统中如果各节点的初始状态一致每个节点都执行相同的操作序列那么他们最后能得到一个一致的状态。
为保证每个节点执行相同的命令序列需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。
分布式系统中一般是通过多副本来保证可靠性而多个副本之间会存在数据不一致的情况。所以必须有一个一致性算法来保证数据的一致描述如下
假如在分布式系统中初始是各个节点的数据是一致的每个节点都顺序执行系列操作然后每个节点最终的数据还是一致的。 Paxos算法就是解决这种分布式场景中的一致性问题。对于一般的开发人员来说只需要知道paxos是一个分布式选举算法即可。 多个节点之间存在两种通讯模型共享内存Shared memory、消息传递Messages passingPaxos是基于消息传递的通讯模型的。 发生网络分区所导致的数据不一致问题就是Paxo算法需要解决的问题 拜占庭问题 拜占庭问题是指拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。 问题是这些将军在地理上是分隔开来的只能依靠通讯员进行传递命令但是通讯员中存在叛徒它们可以篡改消息叛徒可以欺骗某些将军采取进攻行动 促成一个不是所有将军都同意的决定如当将军们不希望进攻时促成进攻行动或者迷惑某些将军使他们无法做出决定。 Paxos算法的前提假设是不存在拜占庭将军问题即 信道是安全的信道可靠发出的信号不会被篡改因为Paxos算法是基于消息传递的。它也是 Paxos算法的提出者,由于硬件和网络原因而造成的消息不完整问题只需要一套简单的校验算法即可。 Paxos算法概念 在Paxos算法中有三种角色 Proposer投票发起者Proposer负责提出提案Acceptor投票接受者Acceptor负责对提案作出裁决accept与否Learner节点学习者learner负责学习提案结果 Proposal这里的一个很重要的概念叫提案Proposal可以理解为我们的一个操作或者数据信息传递最终要达成一致的value就在提案里。 Paxo算法的特点介绍 一个进程或者服务节点可能同时充当多种角色可能既是Proposer又是Acceptor又是Learner 。 只要Proposer发的提案被Acceptor接受半数以上的Acceptor同意才行Proposer就认为该提案里的value被选定了。 Acceptor告诉Learner哪个value被选定Learner就认为那个value被选定。只要Acceptor接受了某个提案Acceptor就任务该提案里的value被选定了。
Paxo算法的投票和认可机制 为了避免单点故障会有一个Acceptor集合Proposer向Acceptor集合发送提案Acceptor集合中的每个成员都有可能同意该提案且每个Acceptor只能批准一个提案只有当一半以上的成员同意了一个提案就认为该提案被选定了。 Paxos算法的解决的问题描述 有多个proposevaluevalue在提案Proposal里的进程集合。一致性算法需要保证提出的这么多value中只有一个value被选定chosen。 如果没有value被提出就不应该有value被选定。如果一个value被选定那么所有进程都应该能学习learn到这个被选定的value。 只有被提出的value才能被选定只有一个value被选定并且如果某个进程认为某个value被选定了那么这个value必须是真的被选定的那个。 保证最终有一个value会被选定当value被选定后进程最终也能获取到被选定的value。
Paxos算法的过程
Paxos算法类似于两阶段提提交其算法执行过程分为两个阶段。具体如下 阶段一prepare阶段 Proposer选择一个提案编号N然后向半数以上的Acceptor发送编号为N的Prepare请求:ProposalN。如果一个Acceptor收到一个编号为N的Prepare请求若小于它已经响应过的请求则拒绝不回应或回复error。若N大于该Acceptor已经响应过的所有Prepare请求的编号maxN那么它就会将它已经接受过的编号最大的提案作为响应反馈给Proposer同时该Acceptor承诺不再接受任何编号小于N的提案。 如果还没有的accept提案的话返回{poknullnull} 阶段二accept阶段 如果一个Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意V就是收到的响应中编号最大的提案的value如果响应中不包含任何提案那么V就由Proposer自己决定。如果Acceptor收到一个针对编号为N的提案的Accept请求只要该Acceptor没有对编号大于N的Prepare请求做出过响应它就接受该提案。如果N小于Acceptor以及响应的prepare请求则拒绝不回应或回复error当proposer没有收到过半的回应那么他会重新进入第一阶段递增提案号重新提出prepare请求。
Paxos算法的过半依据
Paxos基于的过半数学原理 我们称大多数过半进程组成的集合为法定集合 两个法定过半集合必然存在非空交集即至少有一个公共进程称为法定集合性质。 例如A,B,C,D,F进程组成的全集法定集合Q1包括进程A,B,CQ2包括进程B,C,D那么Q1和Q2的交集必然不在空C就是Q1Q2的公共进程。如果要说Paxos最根本的原理是什么那么就是这个简单性质。也就是说两个过半的集合必然存在交集也就是肯定是相等的也就是肯定达成了一致。
