JasonChen Blog

Paxos 算法详解

小记

Google Chubby的作者Mike Burrows说过,there is only one consensus protocol, and that’s “Paxos” – all other approaches are just broken versions of Paxos. 意即世上只有一种一致性算法,那就是Paxos,所有其他一致性算法都是Paxos算法的不完整版。这也是本博客的主题。

Paxos 究竟在解决什么问题

Paxos用来确定一个不可变变量的取值

  • 取值可以是任意二进制数据
  • 一旦确定将不再更改,并且可以被获取到(不可变性、可读性)

在分布式存储系统中应用Paxos

  • 数据本身可变,采用多副本进行存储
  • 多个副本的更新操作序列【op1,op2,op3,…..,opn]是相同的、不变的
  • 用Paxos依次来确定不可变变量opi的取值(即第i个操作是什么)
  • 没确定完opi之后,让各个副本执行opi,依次类推
  • Google的Chubby、 Megastore和Spanner都采用了Paxos来对数据副本的更新序列达成一致

Paxos 算法的核心思想是什么

第一阶段在做什么?
第二阶段在做什么?

这是两个很重要的问题,先针对这个问题进行详细阐述

具体实现发展

1.首先是基于互斥访问权的单Acceptor

互斥锁

  • 一阶段:获取锁
  • 二阶段:var有值f,则释放锁Acceptor:release然后返回,否则会努力使Acceptor:accept
2.基于前者提出抢占式访问权

采用发放访问权的策略,接受访问权epoch新的,修改能接受的epoch的新旧底线,也就是拒绝比epoch旧的Proposer的访问权,就是Acceptor采用喜新厌旧的原则。为了保持一致性,不同的epoch的Proposer之间采用后者认同前者的原则(如果旧的epoch无法生成确定性取值时,新的epoch会提交自己的value,不会冲突;如果就的epoch形成确定性取值,新的epoch肯定可以获取此值并且认同此取值,不会破坏)

  • 一阶段:获取epoch轮次访问权和当前var的取值

    简单选取当前的时间戳为epoch,通过Acceptor::prepare(epoch),获取epoch轮次的访问权和当前var的取值
    如果不能获取,返回

  • 二阶段:采用后者认同前者的原则进行

    如果var的取值为空,则肯定旧epoch无法生成确定性取值,则通过Acceptor::accept(var,epoch,V)提交数据V。成功后返回
    如果accept失败,返回(被新epoch抢占或者Acceptor故障)
    如果var取值存在,则此取值肯定是确定性取值,此时认同它不再更改,直接返回

3.Paxos 基于方案2 引入多Acceptor

1.Acceptor的实现保持不变,仍然采用“喜新厌旧”的原则运行
2.Paxos采用“少数服从多数”的思路
3.一旦某epoch的取值f被半数以上acceptor接受,则认为此var取值被确实为f,不再更改

  • 一阶段:选定epoch,获取epoch访问权和对应的var取值

    获取半数以上acceptor的访问权和对应的一组var取值

  • 二阶段:采用后者认同前者的原则进行
    1.在肯定旧epoch无法生成确定性取值时,新的epoch会提交自己的取值,不会冲突。
    2.一旦旧epoch形成确定性取值,新的epoch肯定可以获取到此值,并且会认同此取值,不会破坏

    如果获取的var取值都为空,则旧epoch无法形成确定性取值。此时努力使成为确定性取值
    1) epoch对应的所有acceptor提交取值
    2) 如果收到半数以上成功,则返回
    3) 否则,则返回(被新epoch抢占或者acceptor故障)
    如果var的取值存在,认同最大aaccepted_epoch对应的取值f,努力使成为确定性取值
    1) 如果f出现半数以上,则说明f已经确定性取值,直接返回
    2) 否则,向epoch对应的所有acceptor提交取值

Paxos 解决半数一下故障问题以及会出现的活锁问题

Paxos 可以解决半数以下故障问题,但会引发活锁问题:
旧一轮的epoch总是被新一轮的epoch所抢占
解决办法
选举Leader/Master节点,然后统一也只能由Leader发送,具体的讲解参考如下链接:https://zhuanlan.zhihu.com/p/20417442,里面提到multi-paxos。