网站建设 工商注册,不重名的建筑公司名字,抖音seo查询工具,做门户网站广告写在前面
分布式共识是分布式系统中的重要内容#xff0c;本文来一起看下#xff0c;一种历史悠久#xff08;1998由兰伯特提出#xff0c;并助其获得2003年图灵奖#xff09;的实现分布式共识的算法Paxos。Paxos主要分为两部分#xff0c;Basic Paxos和Multi-Paxos,其中…写在前面
分布式共识是分布式系统中的重要内容本文来一起看下一种历史悠久1998由兰伯特提出并助其获得2003年图灵奖的实现分布式共识的算法Paxos。Paxos主要分为两部分Basic Paxos和Multi-Paxos,其中Basic Paxos用来使得一个值在多个副本集中达成共识Multi-Paxos用来使得多个值在副本集中达成共识所以Multi-Paxos可以看做是basic paxos的批量版本。下面我们就一起来看下吧
1paxos算法的角色和阶段
一部电影有各种角色主角配角龙套一部电视剧也一样自然的一个算法也是如此paxos亦是如此所以我们先来看下paxos都有哪些角色:
1提议者Proposer负责发起某个值的修改一般是多个副本中收到更新请求的那个副本
2接受者Acceptor,对提议的值进行投票一般是多个副本中其他副本
3学习者learner被动接收达成共识的值一般是slave可参考下图 2basic paxos
假定有客户端1和客户端2作为提议者角色在时间1和时间2时间1早于时间2分别发起设置x为2和x为7的提议接受者有节点A,节点B节点C如下图 该算法一共分为两个阶段分别是准备阶段和接受阶段。另外达成共识传递的数据是(提案编号提案值)提案编号可以认为是数据的版本号时间越新则编号越新提案值就是要达成共识的值首先我们按照上图进入准备阶段。假设客户端1的提案编号是1000客户端2的提案编号是2000则客户端1的完整消息是(1000,2),客户端2的完整消息是(2000,7)。
2.1准备阶段 注意该阶段发送的消息不需要提案值因为只是确定在接受阶段使用哪个提案编号即可。 在时间1节点A和节点B收到了客户端1的消息(1000,),节点C收到了客户端2的消息(2000,)因为此时是各个节点收到的第一条消息所以都会返回尚无提案以节点A为例返回尚无提案的意思是当前自己还没有通过任何提案且保证之后如果是收到小于1000的提案则不会做任何响应且不会通过任何编号小于1000的提案如下图 在时间2节点A和节点B收到了客户端2的消息(2000,)因为20001000,所以节点A和节点B会给客户端2返回尚无提案节点C收到了客户端1的消息(1000,),因为10002000所以节点C不会对客户端1做出任何的响应而是直接丢弃如下图 到这里准备阶段结束进入接受阶段。
2.2接受阶段
此时节点A节点B节点C所能够接受的最小提案编号是2000所有提案编号小于等于2000的消息都将会被丢弃如下图 在一段时间后客户端1和客户端2分别将消息(1000,2),(2000,7)发送给节点A节点B和节点C如下图 因为此时节点A节点B节点C所能够接受的最小提案编号是2000,所以来自客户端1消息(1000,2)将会被丢弃而最终消息(2000,7)被接受如下图 这样节点A节点B节点C就对x的值达成了共识即x7。
2.3源码实现
以上准备阶段和接受阶段源码实现参考这里 运行截图解释如下 3multi paxos
首先说明兰伯特的论文中关于multi paxos的描述很抽象并没有给出具体的方案以及实现只是给出了一些概念所以准确来说multi paxos只是一种思想而非一种具体的算法但是可以基于这种思想来提供具体的算法实现比如chubby类似于zookeeper的一种分布式服务框架对于multi paxos的实现和落地。以及raft算法也是其具体实现。
在basic paxos中分为了准备阶段和接受阶段其中准备阶段用于确定某个数据的最新版本的修改接受阶段用于同步值到所有的节点。这里需要准备阶段的原因是可能存在多个提议者提案有冲突的情况那么如果我们能够解决提案冲突的问题是不是就可以将准备阶段取消掉了会直接减少一半的网络交互性能会得到极大的提高multi paxos解决这个问题的方式是来引入一个leader节点此时结构可能如下 所有提案都从这个leader发出因为只会从一个节点发出提案也就不存在冲突的问题了如下图 那么当我们有多个值需要达成共识时只需要进行多轮优化后的basic paxos就可以了。
写在后面
小结
本文分析了paxos算法的basic paxos和multi paxos并详细分析了basic paxos然后给出了具体的代码实现。最后分析了basic paxos存在的问题以及multi paxos基于此的优化。希望本文能够帮助到你。
参考文章列表
