Paxos

Paxos

最经在弄论文，zk的原理还是不太明白，听说zk这些协调系统都是基于Paxos算法演变出来，看来得先理解Paxos算法才行。下面是本人根据网上资料对Paxos做的总结，希望对和我一样的菜鸟有点好处（错了，来吐槽吧，文明点）

Paxos 的理解困境

 

1 Paxos究竟在解决什么问题？

2 Paxos如何在分布式存储系统中应用？

3 Paxos算法的核心思想是什么

   第一阶段在做什么

   第二阶段在做什么

 

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

1、取值可以是任何二进制数据

2、一旦确定将不再更改，并且可以被获取到(不可变性、可读性)

 

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

1、 数据本身可变，采用多副本进行存储

2、 多副本的更行操作序列[Op1,Op2,…,Opn]是相同的，不变的

3、 用Paxos依次来确定不可变量Opi的取值（即第i个操作是神什么）

4、 每次确定完Opi之后，让各个数据副本执行Opi，依次类推。

 

Google的Chubby、Megastore 和Spanner都采用了Paxos来对数据副本的根性序列达成一致

 

Paxos 希望解决的一直性问题

设计一个系统，来存储名称为var的变量

1、 系统内部由多个Acceptor组成，负责存储和管理var变量。

2、 外部有多个proposer机器任意并发调用API，想系统提交不同的var取值，var的取值可以是任意二进制数据

3、 系统对外的API库接口为：propose(var,V)=> <ok,f> or <error>

系统需要保证var的取值满足一致性

1、 如果var的取值没有确定，则var的取值为null

2、 一旦var的取值被确定，则不可以被更改。并且可以一直获取到这个值

系统需要满足容错特性

1、 可以容忍任意propose机器出现故障

2、 可以容忍少数Accptor故障（半数一下）

 

暂时不考虑 网络分化 和 acceptor故障丢去var的信息。

 

确定一个不可变变量—难点

1、 管理多个Proposer的并发执行

2、 保证var变量的不可变性

3、 容忍任意Proposer机器故障

4、 容忍半数以下Acceptor机器故障

 

确定一个不可变量变量的取值----方案1

1、 先考虑系统由单个Acceptor组成。通过类似互斥锁机制，来管理并发的proposer运行。

2、 Proposer首先向Acceptor申请Acceptor的互斥访问权，然后才能请求Acceptor接受自己的取值。

3、 Acceptor给Proposer发放互斥访问权，谁申请到互斥访问权，就接收到谁提交的取值。

4、 让Proposer按照获取互斥访问权的顺序依次访问Acceptor

5、 一旦Acceptor接受了某个Proposer的取值，则认为var取值被确定，其他Proposer不再更改

 

基于互斥访问权的Acceptor的实现

1、 Acceptor保存变量var和一个互斥锁lock

2、 Acceptor::pareprare():

加互斥锁，给予var的互斥访问权，并返回var当前的取值f

3、 Acceptor::release():

解互斥锁，收回var的互斥访问权

4、 Acceptor::accept(var,V):

如果已经加锁，并且var没有取值，则设置var为V。并且释放锁

Propose(var,V)的两阶段实现

1、 第一阶段：通过Acceptor::prepare获取互斥访问权和当前var的取值，如果不能返回<error>（锁被别人占用）

2、 第二阶段：根据当前var的取值f，选择执行

如果f为null，则通过Acceptor::accept（var,V）提交数据V

如果f不为空，则通过Acceptor::release()释放访问权，返回<ok,f>

 

通过Acceptor互斥访问权让Proposer序列运行，可以简单的实现var取值的一致性

Proposer在释放互斥访问权之前发生故障，会导致系统陷入死锁

       不能容忍任意Proposer机器故障

 

未完，待续更新