Zookeeper -- Base-Paxos协议

本文将简要介绍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接受自己的取值
  • AcceptorProposer发放互斥锁Acceptor只接收持有互斥锁的Proposer提交的取值
  • Proposer按照获取Acceptor互斥锁的顺序来依次访问Acceptor
  • 一旦Acceptor接收了某个Proposer的取值,则认为var的取值被确定,其他Proposer无法再更改var的取值

实现

基本方法

  • Acceptor保存变量var和一个互斥锁Lock
  • Acceptor::prepare()ProposerAcceptor请求申请互斥锁
  • Acceptor::release()ProposerAcceptor请求释放互斥锁
  • 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
  • ProposerAcceptor申请访问权时必须指定编号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_epochProposer如果要成功抢占访问权,指定的新epoch必须大于latest_prepared_epoch
Acceptor::prepare(epoch)

ProposerAcceptor请求访问权,具有抢占性质

  • Proposer指定epoch
  • Acceptor只接受大于latest_prepared_epochepoch,并给予Proposer关于该epoch的访问权
  • 更新latest_prepared_epoch=epoch,返回var的当前取值(即<ok,accepted_epoch,accepted_value>
  • 使其他Proposer(之前已经获得过访问权)的访问权失效,不再接受它们的访问
Acceptor::accept(var,prepared_epoch,V)

prepared_epochAcceptor::prepare(epoch)指定的epoch,验证latest_prepared_epochprepared_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不比Acceptorlatest_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了形成确定性取值,不再更改

半数以上

  • 5Acceptor半数以上为:3、4、5
  • 6Acceptor半数以上为: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>
    • Proposerepoch对应的所有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和分布式系统

0%