首页 / 算法 / 分布式---Paxos算法
分布式---Paxos算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了分布式---Paxos算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2689字,纯文字阅读大概需要4分钟。
内容图文
![分布式---Paxos算法](/upload/InfoBanner/zyjiaocheng/774/8298c09b6d9d455c9e577059fd18fa91.jpg)
5.Paxos
??Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景就是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。Paxos算法就是一种基于消息传递模型的一致性算法。
主要有三类节点:
- 提议者(Proposer):提议一个值;
- 接受者(Acceptor):对每个提议进行投票;
- 告知者(Learner):被告知投票的结果,不参与投票。
执行过程
??规定一个提议包含两个字段:[n,v],其中n为序号(具有唯一性),v为提议值。
1.Prepare阶段
??下图演示了两个proposer和三个acceptor的系中运行该算法的初始过程,每个proposer都会向所有的acceptor发送prepare请求。
??当acceptor接受到一个prepare请求,包含的提议为[n1,v1],并且之前还未接受过prepare请求,那么发送一个prepare响应,设置当前接受到的提议为[n1,v1],并且保证以后不会接受序号小于n1的提议。
??如下图,Acceptor X 在收到 [n=2, v=8] 的 Prepare 请求时,由于之前没有接收过提议,因此就发送一个 [no previous] 的 Prepare 响应,设置当前接收到的提议为 [n=2, v=8],并且保证以后不会再接受序号小于 2 的提议。其它的 Acceptor 类似。
??如果acceptor接收到一个prepare请求,包含的提议为[n2,v2],并且之前已经接收到提议[n1,v1]。如果n1>n2,那么就该丢弃该提议请求;否则,发送prepare响应,该prepare响应包含之前已经接收过的提议[n1,v1],设置当前接收到的提议为[n2,v2],并且保证以后不会再接收序号小于n2的提议。
??如下图,Acceptor Z 收到 Proposer A 发来的 [n=2, v=8] 的 Prepare 请求,由于之前已经接收过 [n=4, v=5] 的提议,并且 n > 2,因此就抛弃该提议请求;Acceptor X 收到 Proposer B 发来的 [n=4, v=5] 的 Prepare 请求,因为之前接收到的提议为 [n=2, v=8],并且 2 <= 4,因此就发送 [n=2, v=8] 的 Prepare 响应,设置当前接收到的提议为 [n=4, v=5],并且保证以后不会再接受序号小于 4 的提议。Acceptor Y 类似。
2.Accept阶段
??当一个Proposer接收超过一半acceptor的prepare响应时,就可以发送accept请求。
??proposerA接收到两个prepare响应之后,就发送[n=2,v=8]accept请求。该accept请求会被所有acceptor丢弃,因为此时所有acceptor都保证不接受序号小于4的提议。
??Proposer B 过后也收到了两个 Prepare 响应,因此也开始发送 Accept 请求。需要注意的是,Accept 请求的 v 需要取它收到的最大提议编号对应的 v 值,也就是 8。因此它发送 [n=4, v=8] 的 Accept 请求。
3.Learn阶段
??Acceptor接收到Accept请求时,如果序号大于等于该Acceptor承诺的最小序号,那么就发送Learn提议给所有的Learner。当learner发现有大多数acceptor接收了某个提议,那么该提议的提议值就被paxos选择出来。
约束条件
1.正确性
??指只有一个提议值会生效。
??因为Paxos协议要求每个生效的提议都会被Acceptor接收,并且Acceptor不会接收两个不同的提议,因此可以保证正确性。
2.可终止性
??指最后总会有一个提议生效。
??Paxos协议能够让Proposer发送的提议朝着能被大多数Acceptor接受的那个提议靠拢,因此能保证可终止性。
内容总结
以上是互联网集市为您收集整理的分布式---Paxos算法全部内容,希望文章能够帮你解决分布式---Paxos算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。