Paxos

Paxos是什么?

Paxos是用于一种分布式系统并且具有容错性的一致性算法，那么为什么需要一致性算法呢?

场景: 当多个客户端同时对集群做事务操作时,如果不对集群做任何限制条件,我们是无法保证集群中所有节点的数据保持一致.如图所示,集群中是很难保证数据完全一致的.

为什么需要一致性算法.png
而Paxos算法则解决了分布式系统中的数据不一致问题.所有问题均围绕着在分布式环境达成一致性而展开讨论的。Paxos算法为了达成一致性，算法就必须保证其安全性和活性.

• 安全性：只有被提出的提议才能被选定，并且只有一个提议被选定.

• 活性：最终保证会有一个提议被选定.

安全性和活性的组合结果就是：最终有且只有一个被提出的提议被选定.

---

paxos算法中有三种角色

Paxos算法三种角色.png

每个节点都可以充当多个角色.

paxos算法流程

提案:

• 提议编号: 唯一,保证全局单调递增,体现提议的先后顺序

• 更新值

写流程,两阶段:

1. 准备阶段(投票阶段):

   • 提议者提出提议给接收者;

   • 接收者如果同意该提议,做出promise响应,并不再accept比当前提议号低的提议;

   • 提议者收到超过半数的响应,则进入下一阶段;否则重新提议.

2. 接受变更阶段(提交阶段):

   • 提议者向接收者发送accept消息;

   • 接收者比较accept消息中的提议号,如果比自己当前已promise的提议号低,则回应Nack(带上自己当前promise的提议号),否则accept,广播accepted.

     
     Paxos算法流程.png

上图请细品,看明白了那么paxos主要的流程就明白了,下面模拟两次提议来帮助大家理解.

提议正常流程

提案正常流程.png

解读 :

1. 提议者2创建编号1的提议编号,先发起提议,三个接收者都收到了该提议;

2. 三个接收者都收到编号1并同意该提议,做出promise响应给提议者2并带上提议编号;

3. 提议者2收到超过半数的响应,进入第二阶段,广播accept(编号1,值1);

4. 三个接收者发现承诺的预请求编号是编号1,等于自己promise的编号,则接受提议,并且广播accept(编号1,值1),此处也发生广播accept是因为paxos还有个Learner角色,Learner角色本身只负责同步数据,提高读吞吐量以及备份的作用;

5. 至此所有节点都把数据更新成了值1;接着提议者1创建了编号2的提议编号发起提议;

6. 三个接收者都收到编号2并同意该提议,做出promise响应给提议者1并带上提案编号;

7. 提议者1收到超过半数的响应,取最大编号 进入第二阶段,广播accept(编号2,值2);

8. 三个接收者发现承诺的预请求编号是编号2,等于自己promise的编号,则接受提议,并且广播accept(编号2,值2),此处也发生广播accept是因为paxos还有个Learner角色,Learner角色本身只负责同步数据,提高读吞吐量以及备份的作用;

9. 所有节点的数据同步完成.

提议异常流程

13624215-24c19eb1e330225d.png

解读 :

1. 提议者2创建编号1的提议编号,先发起提议,只有两个接收者收到了该提议.接受者3可能由于网络分区或者故障没收到提议请求;

2. 两个接收者都收到编号1并同意该提议,做出promise响应给提议者2并带上提议编号;

3. 这时提议者1也发起了提议,接收者2和3收到了该提议,但接收者1可能网络分区或故障导致没收到;

4. 接收者2和3同意该提议,做出promise响应给提议者1并带上提议编号;

5. 提议者2收到了大于半数的响应,进入第二阶段,广播accept(编号1,值1);

6. 接收者1拿到编号1和自己最大编号对比,发现自己的最大编号也是1,则接受提议;但是接收者2此时的最大编号为2,大于了提议者广播appept的编号1,则拒绝此次提议,并且告知提议者2自己目前的最大编号为编号2(NACK 编号2);

7. 提议者1此时也收到了大于半数的响应,进入第二阶段,广播accept(编号2, 值2);

8. 接收者2和3收到accept的编号和值,和自己最大的编号对比,发现相等,同意提议,修改自己的值并广播accept(编号2, 值2). (此处广播主要是为了让Learner角色同步数据)

9. 提议者2提议失败后重新发起提议,提议编号单调递增,变为编号3;

10. 接收者1和2收到提议,并和自己最大编号对比,发现收到的提议编号为最大,但是接收者2有已接受的提议,于是响应已接受的最大编号内容promise(编号3, 编号2, 2);

11. 提议者2收到过半响应,并且不都是promise(n). 接收者1是promise(n),接收者2是promise(n,m,v),请参考流程图配合理解,所以提议者2取最大编号m对应的v值,也就是2,进入第二阶段,广播accept(编号3, 值2);

12. 接受者1和2收到accept的编号和值,已承诺的预请求编号等于n,接受提议,广播accept(编号3, 值2) (此处广播主要是为了让Learner角色同步数据)

13. 至此,所有节点的数据保持一致.

---

如有错误,烦请指正.谢谢!