本文将简要介绍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>

样例

结论

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

参考资料

paxos和分布式系统