paxos协议-阿里云开发者社区

开发者社区> jephon> 正文

paxos协议

简介: 两将军问题 有两支军队,它们分别有一位将军领导,现在准备攻击一座修筑了防御工事的城市。 这两支军队都驻扎在那座城市的附近,分占一座山头。 一道山谷把两座山分隔开来,并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。
+关注继续查看

两将军问题

有两支军队,它们分别有一位将军领导,现在准备攻击一座修筑了防御工事的城市。
这两支军队都驻扎在那座城市的附近,分占一座山头。
一道山谷把两座山分隔开来,并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。
不幸的是,这个山谷已经被那座城市的保卫者占领,并且存在一种可能,那就是任何被派出的信使通过山谷是会被捕。 
请注意,虽然两位将军已经就攻击那座城市达成共识,但在他们各自占领山头阵地之前,并没有就进攻时间达成共识。
两位将军必须让自己的军队同时进攻城市才能取得成功。因此,他们必须互相沟通,以确定一个时间来攻击,并同意就在那时攻击。
如果只有一个将军进行攻击,那么这将是一个灾难性的失败。  

两将军问题本质上就是通信被篡改时能否解决一致性问题。这个问题已经被很多人证明不能。因而由此推及的拜占庭将军问题(多将军问题)也同样不能被解决。

PAXOS算法

一个叫做Paxos的希腊城邦,这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。
所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。
但是这里假设没有拜占庭将军问题(Byzantine failure,即虽然有可能一个消息被传递了两次,但是绝对不会出现错误的消息),只要等待足够的时间,消息就会被传到。
另外,Paxos岛上的议员是不会反对其他议员提出的决议的

两阶段提交

基本思想是两阶段提交。但是与两阶段目的不同:

  1. 第一阶段主要目的是选出提案编号最大的proposer(提案人)。其描述如下,所有的proposer向超过半数的acceptor(接受者)提出编号为n的提案,acceptor收到编号为n的请求,会出现两种情况
    • 编号n大于所有acceptor之前已经批准过的proposal(提案)的最大编号及内容m。acceptor同意该proposal,响应[n, m]回proposer,并且承诺今后不再批准任何编号小于n的提案
    • 编号n小于acceptor之前批准过的任意proposal的编号。acceptor拒绝该proposal。
  2.  第二阶段尝试对某一proposal达成一致。proposer收到超过半数的acceptor返回的响应,proposer就会将响应的最大编号[n, m]对应的提案提交到acceptor要求acceptor批准该提案。acceptor收到最大编号[n, m]的提案,也分为两种情况
    • 未响应过编号大于n的prepare请求。通过该提案。
    • 已响应过编号大于n的prepare请求。拒绝该提案。

如此反复,整个算法表面上并不难理解,难在实现细节的难易程度和各种异常情况的推导及考虑。

关键点

  • 算法描述里有好几个地方要求投票必须超过半数,这个超过半数恰恰是保证一致的一个必要条件
  • 算法里也有多处要求只选择编号最大的,这种选择编号最大的方式,是一种最为简单经济的达成共识的方法,能够快速在多个冲突中找到一个突破口
  • paxos算法的关键是,如果一个值m被选中了,那么必须保证更高的proposal其值也为m
  • 第一阶段比较的是已经批准过的proposal的最大编号第二阶段比较的是prepare请求

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10071 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
11610 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
9157 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13880 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7363 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4500 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
22390 0
+关注
jephon
一直在路上..........
390
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载