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请求

 

目录
相关文章
|
算法
Paxos一致性协议
Paxos一致性协议
82 0
|
机器学习/深度学习 存储 前端开发
理解分布式一致性:Paxos协议之Basic Paxos
理解分布式一致性:Paxos协议之Basic Paxos
理解分布式一致性:Paxos协议之Basic Paxos
|
安全 算法 数据安全/隐私保护
理解分布式一致性:Paxos协议之Cheap Paxos & Fast Paxos
理解分布式一致性:Paxos协议之Cheap Paxos & Fast Paxos
理解分布式一致性:Paxos协议之Cheap Paxos & Fast Paxos
理解分布式一致性:Paxos协议之Generalized Paxos & Byzantine Paxos
理解分布式一致性:Paxos协议之Generalized Paxos & Byzantine Paxos
理解分布式一致性:Paxos协议之Generalized Paxos & Byzantine Paxos
|
前端开发
理解分布式一致性:Paxos协议之Multi-Paxos
理解分布式一致性:Paxos协议之Multi-Paxos
理解分布式一致性:Paxos协议之Multi-Paxos
|
存储 算法 架构师
【架构师指南】带你彻底认识 Paxos 算法、Zab 协议和 Raft 协议的原理和本质
【架构师指南】带你彻底认识 Paxos 算法、Zab 协议和 Raft 协议的原理和本质
323 0
【架构师指南】带你彻底认识 Paxos 算法、Zab 协议和 Raft 协议的原理和本质
|
算法 关系型数据库 MySQL
Egalitarian Paxos
Egalitarian Paxos
Egalitarian Paxos
|
存储 Java
paxos 实现
原文地址:http://rdc.taobao.com/blog/cs/?p=162 本文主要介绍zookeeper中zookeeper Server leader的选举,zookeeper在选举leader的时候采用了paxos算法(主要是fast paxos),这里主要介绍其中两种:LeaderElection 和FastLeaderElection.
903 0

相关产品