Zookeeper Paxos算法一致性协议

Love The Way You Lie 2022-05-25 09:38 222阅读 0赞

# 前言 #

Paxos 一致性协议可以说是一致性协议研究的起点，也以难以理解闻名。其实协议本身并没有多难理解，它的难理解性主要体现在：为何如此设计协议以及如何证明其正确性。本文尝试通过流程图来说明协议的内容以及基本应用过程，不涉及如何证明其正确性。

## 基本概念 ##

Paxos 可以分为两种：

*  **Single-Decree Paxos**：决策单个 Value
 *  **Multi-Paxos**：连续决策多个 Value，并且保证每个节点上的顺序完全一致，多 Paxos 往往是同事运行多个单 Paxos 协议共同执行的结果。

本文只关注单 Paxos 的原理，理解了单 Paxos，多 Paxos 也就不难理解了。

### Paxos 协议中的三种角色 ###

*  **倡议者（Proposer）**：倡议者可以提出提议（数值或者操作命令）以供投票表决
 *  **接受者（Acceptor）**：接受者可以对倡议者提出的提议进行投票表决，提议有超半数的接受者投票即被选中
 *  **学习者（Learner）**：学习者无投票权，只是从接受者那里获知哪个提议被选中

在协议中，每个节点可以同时扮演以上多个角色。

### Paxos 的特点 ###

*  一个或多个节点可以提出提议
 *  系统必须针对所有提案中的某个提案达成一致（超过半数的接受者选中）
 *  最多只能对一个确定的提议达成一致
 *  只要超半数的节点存活且可互相通信，整个系统一定能达成一致状态，即选择一个确定的提议

## 协议图示 ##

# #

![20180511213943348][]  
通过上面的流程，如果有多个节点同时提出各自的提议，Paxos 就可以保证从中选出一个唯一确定的值，保证分布式系统的一致性。

## 实例 ##

下面我们通过例子来理解 Paxos 的实际应用过程。

假设现在有五个节点的分布式系统，此时 A 节点打算提议 X 值，E 节点打算提议 Y 值，其他节点没有提议。

![20180511214041476][]

假设现在 A 节点广播它的提议（也会发送给自己），由于网络延迟的原因，只有 A，B，C 节点收到了。注意即使 A，E 节点的提议同时到达某个节点，它也必然有个先后处理的顺序，这里的“同时”不是真正意义上的“同时”。

![20180511214105740][]

A，B，C接收提议之后，由于这是第一个它们接收到的提议，acceptedProposal 和 acceptedValue 都为空。

![20180511214132421][]

由于 A 节点已经收到超半数的节点响应，且返回的acceptedValue 都为空，也就是说它可以用 X 作为提议的值来发生 Accept 请求，A，B，C接收到请求之后，将 acceptedValue 更新为 X。

![20180511214203798][]

A，B，C 会发生 minProposal 给 A，A 检查发现没有大于 1 的 minProposal 出现，此时 X 已经被选中。等等，我们是不是忘了D，E节点？它们的 acceptedValue 并不是 X，系统还处于不一致状态。至此，Paxos 过程还没有结束，我们继续看。

![2018051121421836][]

此时 E 节点选择 Proposal ID 为 2 发送 Prepare 请求，结果就和上面不一样了，因为 C 节点已经接受了 A 节点的提议，它不会三心二意，所以就告诉 E 节点它的选择，E 节点也很绅士，既然 C 选择了 A 的提议，那我也选它吧。于是，E 发起 Accept 请求，使用 X 作为提议值，至此，整个分布式系统达成了一致，大家都选择了 X。

以上内容均引用自: [http://blog.jobbole.com/106327/][http_blog.jobbole.com_106327]

感谢作者画图解说如上的paxos算法

原设计师的最先设计方案：

![20180511214247317][]

上图的图解，缺了一部分同步的操作，当然不是作者画错了，而是我们的分布式发现服务的问题，当一个节点不可用，那么发起议案的时候，节点不可用，那么提交议案成功后，也不会去再同步此节点，因为不可用。

## 交叉分布式事务 ##

下图将解说交叉分布式同步问题，下图将采用的另一个收费课程的图解：更复杂！！！！

![20180511214302281][]

模拟场景：战略会议       交叉分布式事务

制定作战计划，两位作战计划的制定者，分别制定一个计划，上面的进攻时间改为进攻目标更妥当

三位将军作为计划的执行者。

开始：

1：参谋1  制定作战目标成功，发送给三个将军。但是将军3与他有意见，拒绝他的意见，此时的将军1，将军2，觉得作战目标可行。同意

2：在参谋1还没做表决的时候，参谋2，将作战目标做完，分别发给三位将军，这时将军1跟参谋2有意见，不接受他的作战目标。其他两个将军觉得作战目标可行，同意

3：这是参谋1 举行表决，超过半数即可行。将军2 将军1 做表决，但是将军2接受了新的作战计划，此时不再能执行作战计划1了，所以参谋一的作战计划未通过

4：此时参谋2开始做作战计划的表决，因为将军2 将军3 同意，因此此计划通过。这时其实意味这分布式事务的成功，数据一致性处理成功

5：此时参谋1 又做了一个作战计划，3 发给将军1，将军2，此时将军1，2返回他们手里的作战计划，看是否领先作战计划3。

6：参谋1发现将军1，将军2 的作战计划已执行，可以表决自己的作战计划，则提交表决

7：将军1 将军2 表决通过参谋1的作战计划3

哈哈，懵了没有，其实这模拟的是：

如淘宝交易，同一时间两个会员购买同一个商品 第一个会员需要去修改淘宝的分布式系统的商品剩余数量，此时第二位会员同时间消费的会员也要来修改数据。时间在0.00毫秒间产生。交叉型的分布式事务处理出现在超大型并发系统中。这时两个会员会出现争夺谁先去修改库存的操作。

看得懂的行家可能会说，在参谋2提交计划成功的时候，参谋1又提交议案，就造成了死锁了。Paxos算法在提交失败后，睡眠1毫秒参谋2的提议就表决通过了。当然算法内还有更深层次的实现，无法得知：，目前 Google Facebook IBM 都有自己的算法实现，可是都没有公开源码，zookeeper的实现源码好像说也很晦涩。但是算法内部用队列或者一些简单的类似MQ处理机制就可以避免上面这种彼此死锁的方式。

[20180511213943348]: /images/20220525/1889fa3c6daf46b5b1c694e543c2b11b.png
[20180511214041476]: /images/20220525/d759343d6dcf41938dacfd5c1b4dd72c.png
[20180511214105740]: /images/20220525/7681281ac00b490b8f49d5a8b7665344.png
[20180511214132421]: /images/20220525/e1274f585ae24857a43ee0df267f59e9.png
[20180511214203798]: /images/20220525/72cad06ed82f4923a4e068413cf41503.png
[2018051121421836]: /images/20220525/77505713d9e24895809929e96fa6f8e8.png
[http_blog.jobbole.com_106327]: http://blog.jobbole.com/106327/
[20180511214247317]: /images/20220525/50536cef726749079ab93ecc90625b89.png
[20180511214302281]: /images/20220525/d2e04d82b1294e3b9d17c55636b05b30.png