本文将简要介绍Paxos
协议
基础概念
Paxos协议
Paxos
协议是一种通用的分布式一致性协议
,用于解决一致性问题
一致性问题
Paxos
协议用来确定一个不可变
变量的取值,取值具有2个特点:
- 取值可以为
任意二进制数据
- 取值
一旦确定将不可被更改
,并且可以被获取到(不可变性,可读取性
)
系统抽象
设计一个系统,来存储名称为var的变量,满足以下4个条件:
- 系统内部由多个
Acceptor
组成,负责存储和管理var变量 - 系统外部有多个
Proposer
,这些Proposer
可以并发
地调用Acceptor
对外提供的API接口,向系统提交不同的var取值 - var取值为任意二进制数据
Acceptor
对外提供的API接口:propose(var,V) => <ok,f> or <error>
,f可能是当前Proposer
提交成功的V
,也可能是其他Proposer
提交成功的V'
var的一致性
- 如果var取值
没有确定
,则var的取值为null
- 一旦var的取值
被确定
,则不可被更改
,并且可以一直获得这个值
系统的容错特性
- 可以容忍
任意数量
的Proposer
出现故障 - 可以容忍
半数以下
的Acceptor
出现故障
实现方案
互斥访问权
适用场景
系统由单个Acceptor
组成
策略
- 通过
互斥锁
机制,来管理Proposer
的并发
执行 Proposer
首先向Acceptor
申请互斥锁
,申请成功后才能请求Acceptor
接受自己的取值Acceptor
向Proposer
发放互斥锁
,Acceptor
只接收持有互斥锁的Proposer
提交的取值- 让
Proposer
按照获取Acceptor
互斥锁的顺序来依次访问Acceptor
- 一旦
Acceptor
接收了某个Proposer
的取值,则认为var的取值被确定,其他Proposer
无法再更改var的取值
实现
基本方法
- Acceptor保存
变量var
和一个互斥锁Lock
Acceptor::prepare()
:Proposer
向Acceptor
请求申请互斥锁Acceptor::release()
:Proposer
向Acceptor
请求释放互斥锁Acceptor::accept(var,V)
:如果Proposer
已经持有互斥锁,并且var没有取值,则设置var为V
,然后向Acceptor
请求释放互斥锁
propose(var,V)的两阶段实现
第1阶段
Proposer
通过调用Acceptor::prepare()
向Acceptor
请求申请互斥锁
- 申请互斥锁
失败
,返回<error>
,说明当前互斥锁被其他Proposer
占用,尚未释放 - 申请互斥锁
成功
并且返回var变量的当前值f
,然后进入第2阶段
第2阶段
进入第2阶段,说明当前Proposer
申请互斥锁成功
并且返回var变量的当前值f
- 如果当前var的取值
f不为null
,说明var变量已经被其他Proposer
设置成功,形成了确定性取值
,那么Proposer
通过Acceptor::release()
向Acceptor
请求释放互斥锁,返回<ok,f>
- 如果当前var的取值
f为null
,说明var变量尚未形成确定性取值
,那么Proposer
通过Acceptor::accept(var,V)
提交数据V,并且向Acceptor
请求释放互斥锁,返回<ok,V>
结论
- 通过
Acceptor
的互斥锁让Proposer串行运行
,可以简单地实现var取值的一致性
- 如果
Proposer
在释放互斥锁之前宕机
,将会导致系统陷入死锁
➔ 不能容忍任意数量
的Proposer
出现故障!!
抢占式访问权 + 后者认同前者
适用场景
系统由单个Acceptor
组成,引入抢占式访问权
,用于解决互斥访问权的死锁
问题
策略
抢占式访问权
Acceptor
可以让某个Proposer
获取到的访问权失效,不再接受该Proposer
的访问Acceptor
可以将访问权发放给其他Proposer
,让其他Proposer
访问Acceptor
Proposer
向Acceptor
申请访问权时必须指定编号epoch(值越大,代表越新)
Proposer
在获取到访问权之后,才能向Acceptor
提交取值Acceptor
采用喜新厌旧
的原则Acceptor
一旦接收到的新epoch
(epoch值更大),立马让旧epoch
的访问权失效,不再接受持有旧epoch
访问权的Proposer
提交的取值Acceptor
给新epoch
对应的Proposer
发放访问权,只接收该Proposer
提交的取值(同样可以被抢占)
保证一致性
为了保证一致性
,不同epoch
对应的Proposer
之间采用后者认同前者
的原则
- 在确定
旧epoch无法形成确定性取值
时,新epoch
提交自己的value,不会冲突 - 一旦
旧epoch形成了确定性取值
,新的epoch
肯定可以获得此值,并且会认同
此值,不会进行更改
实现
基本方法
Acceptor保存的状态
- 当前var的取值:
<accepted_epoch,accepted_value>
,表示变量var在accepted_epoch
形成了_确定性取值
_accepted_value
- 最新发放访问权的epoch:
latest_prepared_epoch
,Proposer
如果要成功抢占访问权,指定的新epoch
必须大于latest_prepared_epoch
Acceptor::prepare(epoch)
Proposer
向Acceptor
请求访问权,具有抢占性质
Proposer
指定epoch
Acceptor
只接受大于latest_prepared_epoch
的epoch
,并给予Proposer
关于该epoch
的访问权- 更新
latest_prepared_epoch=epoch
,返回var的当前取值(即<ok,accepted_epoch,accepted_value>
) - 使其他
Proposer
(之前已经获得过访问权)的访问权失效,不再接受它们的访问
Acceptor::accept(var,prepared_epoch,V)
prepared_epoch
为Acceptor::prepare(epoch)
指定的epoch
,验证latest_prepared_epoch
与prepared_epoch
是否相等
- 相等,说明当前
Proposer
持有的epoch访问权依然有效
,那么设置var的取值,即<accepted_epoch,accepted_value>
➔<prepared_epoch,V>
- 不相等,说明当前
Proposer
持有的epoch访问权已经被抢占
,无法继续运行
propose(var,V)的两阶段实现
第1阶段
Proposer
指定epoch
,并通过调用Acceptor::prepare(epoch)
向Acceptor
请求访问权
- 请求访问权
失败
,返回<error>
,说明当前Proposer
指定的epoch
不比Acceptor
的latest_prepared_epoch
大 - 请求访问权
成功
并且返回var变量的当前值<accepted_epoch,accepted_value>
,然后进入第2阶段
第2阶段
采用后者认同前者
的原则执行
var取值为<null,null>
,则旧epoch肯定尚未形成确定性取值
,Proposer
通过调用Acceptor::accept(var,prepared_epoch,V)
向Acceptor
提交取值- 提交成功,返回
<ok,prepared_epoch,V>
- 提交失败,返回
<error>
(被新epoch抢占
或者Acceptor发生故障
)
- 提交成功,返回
var取值不为<null,null>
,则其他Proposer
设置成功,变量var已经形成确定性取值
,认同此值不再更改,直接返回<ok,accepted_epoch,accepted_value>
样例

结论
- 让
Proposer
按照epoch递增的顺序
抢占式地依次运行,采用后者认同前者
的原则 - 这样可以了
避免Proposer故障带来的死锁问题
,并且仍然保留var取值的一致性
- 但仍然存在_
单点问题
_,Acceptor
故障会导致整个系统宕机
Paxos
适用场景
系统内部由多个Acceptor
组成,避免单点Acceptor故障
策略
Acceptor
的实现与抢占式访问权类似,采用喜新厌旧
的原则Paxos
采用少数服从多数
_的思路:一旦某个epoch的取值f被半数以上
_的Acceptor
接受,系统则认为此var了形成确定性取值
,不再更改
半数以上
5
个Acceptor
,半数以上
为:3、4、5
6
个Acceptor
,半数以上
为:4、5、6
实现
propose(var,V)的两阶段实现
第1阶段
Proposer
指定epoch
,向所有的Acceptor
请求该epoch
的访问权
Proposer
获取少于半数以上
的Acceptor
关于epoch
的访问权,Proposer
结束第1阶段的运行,但无法进入第2阶段Proposer
获取半数以上
的Acceptor
关于epoch
的访问权(并返回var的当前值),进入第2阶段
关键点:半数以上
➔ 当多个Proposer
并发地向所有Acceptor
请求关于同一个epoch
的访问权,_最多只有一个Proposer
_能获得半数以上
Acceptor请求关于该epoch
的访问权并进入到第2阶段!!
第2阶段
采用后者认同前者
的原则执行
- 如果在第1阶段获取到的var的当前值
都为null
,说明var尚未形成确定性取值
,此时Proposer
努力使V
成为确定性取值
(对应<epoch,V>
)Proposer
向epoch对应的所有Acceptor
(半数以上的Acceptor,不一定是所有)提交取值<epoch,V>
- 如果收到
半数以上
提交成功,则已经形成确定性取值,返回<ok,V>
- 否则,返回
<error>
(被新epoch抢占
或者Acceptor发生故障
)
- 如果第1阶段获取到的var的当前值
不都为null
,认同最大accepted_epoch对应的取值f
,努力使得f
成为确定性取值
(对应<epoch,f>
)- 如果此时f已经被
半数以上
的Acceptor
接受,则说明f已经是确定性取值
,直接返回<ok,f>
- 否则,向
epoch对应的所有Acceptor
提交取值<epoch,f>
- 如果此时f已经被
样例

结论
- 在抢占式访问权的基础上引入
多Acceptor
,避免了Acceptor
的单点问题 - 保证
一个epoch的访问权只能被一个Proposer获取
,Proposer
是按照epoch递增的顺序依次运行的 - 新的epoch的
Proposer
采用后者认同前者
的思路运行 - 可以满足容错性要求
半数以下Acceptor
出现故障时,存活的Acceptor
依然可以形成var的确定性取值- 一旦var取值确定,即便出现
半数以下Acceptor
故障,此取值依然可以被获取,并且将不再被更改