鲍增辉的博客

我一直对Paxos协议感兴趣. 我听说过这种算法，但只知道皮毛. 最近我正在学习Zookeeper. 利用这种新鲜度，我花了一些时间研究Zookeeper选举算法的实现，然后重新学习了Paxos算法，本文是我的研究总结.

Paxos协议是一种通信协议，用于解决分布式系统中多个节点之间在某个值（建议值）上的协议（解决方案），也就是说，每个节点的建议将与相同内容的内容相同建议书达成协议（知识并成功提交）. 以下，提案ID称为提案IDpaxos 协议，提案内容为值.

第一阶段准备

P1a: 提议者发送准备请求

提议者会生成一个全局唯一的增量ProposalID，并将“准备”请求发送到Paxos集群中的所有计算机. 在这里，它不携带值，仅包含ProposalID.

P1b: 接受者答案准备

接收到“准备”请求后，接受方将判断收到的ProposalID是否大于先前已响应的所有投标的ProposalID:

第二阶段接受

P2a: 提议者发送接受

一段时间后，投标人收集了一些准备答复，出现以下情况:

（1）答复数>接受者数的一半，并且所有答复的值为空，然后Porposer发送一个接受请求并携带其自己指定的值.

（2）答复数>接受者数的一半，并且某些答复不为空，然后Porposer发送一个接受请求，并在答复中携带具有最大ProposalID的值（作为其自身的投标内容）

（3）答复数量<=接受者数量的一半，然后尝试更新并生成更大的ProposalID，然后转移到P1a执行.

P2b: 接受者回答接受

接收到Accpet请求后，Acpetor会判断:

（1）收到的ProposalID> = Max_ProposalID（通常等于），然后成功提交答复，并保留ProposalID和值.

（2）收到提案ID

P2c: 提议者统计投票

一段时间后，投标人收集了一些接受答复并成功提交，有几种情况:

（1）答复数量>接受者数量的一半表示值提交成功. 目前，您可以向所有“建议者”和“学习者”发送广播，以告知他们已确认的价值.

（2）答复数量<=接受者数量的一半，然后尝试更新并生成更大的ProposalID，然后转移到P1a执行.

（3）收到未能提交的回复后，请尝试进行更新以生成更大的ProposalID，然后将其传输到P1a以执行.

最后，经过多轮投票，得出的结果是:

（1）所有提案人均已成功提交提案，并且提交的值是相同的值.

（2）成功接受了一半以上的接受者，并且提交了相同的值.

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

（1）引入多个，以避免单个成为单个点.

投标人使用较大的投标人ID来获取临时访问权限，以避免投标人崩溃和停机导致死锁之一.

（2）为确保ProposalID，只能将一个Proposer运行到第二阶段，并且Proposer会按递增ProposalID的顺序运行.

（3）新的ProposalID的提议者采用后者以与前者一致.

容错要求:

（1）在一半的验收器故障和任何数量的投标人故障中都将起作用.

（2）确定该值后，即使接受器中的一半无效，也可以获取该值，并且不会对其进行修改.

如何在工程实践中确定ProposalID？

如“使Paxos变得简单”中所述，建议建议者从不相交的数据集中选择. 例如，如果系统中有5个提议者，则可以为每个提议者分配一个标识符j（0〜4）. 提案中每个提案的数量可以为5 * i + j（i可以表示提案数量）.

在实践中，您可以使用时间戳+建议数量+机器IP /机器ID来确保唯一性和增量性.

如何确保较大的ProposalID提议者不会破坏已经达到的确定性值？

在P2a阶段，投标者将使用所有响应中具有最大ProposalID的值作为投标内容.

其中，准备阶段的目的有两个目的: 1）检查是否存在批准的值，如果存在，则使用批准的值. 2）当然，如果先前的提案未获批准，请阻止它们，以防止它们与我们竞争，这最终取决于ProposalID的大小.

Paxos协议活动锁问题

新一轮的抢占将停止旧的一轮. 如果在第二阶段成功执行之前每个回合被新回合抢占，则将导致活锁. 如何处理？

此问题在实际应用中很少发生. 通常，可以通过随机更改ProposalID的增加或增加Proposer发送新一轮投标的间隔来解决.

在Paxos的操作过程中，不到一半的Acceptor将失败，并且它们都将能够运行. 为什么？

（1）如果少于一半的接受方未能确定最终价值，那么此时，所有投标人都将争夺投标书的授权，并最终成功提交投标书. 之后，将有一半的成功接受者使用此值提交.

（2）如果少于一半的受体失败，则确定最终值. 这时，所有投标者都必须在提交之前提交最终值，因为投标者必须收到一半以上的“接受”响应. 提交的受体有一个交集，因此它将继续使用P2a阶段中的值.

如果两个具有不同ProposalID的投标者处于P2a阶段paxos 协议，则收到的准备答复的值为空，则两个投标都将使用其自身的值作为值（投标内容），并向Acceptor提交请求，然后，最后，两个提案是否都认为自己已成功提交？

否，因为接受者将基于ProposalID批准最大ProposalID值，而另一个将答复执行失败. 提案收到执行失败的响应后，便知道已成功提交具有较大ProposalID的提案.

由于较大的ProposalID可以抢占较小的ProposalID的提交权限，如果接受者此时没有确定性值，则存在一个具有最大ProposalID的投标到P2a阶段的投标，但是该投标将挂起，会导致死锁状态（较小的ProposalID无法提交，但是具有最大ProposalID的投标无法提交接受请求），如何解决该死锁状态？

将不会发生此死锁状态. 接受者响应提交失败后，该提案将生成一个较大的ProposalID，下一轮可以使用其自己的值成功提交.

刚挂断的领导者具有领导才能.

在运行过程中，如果领导者节点崩溃，此时，所有从属节点都需要休眠几秒钟，才能竞争领导者，并且重新启动的节点可以立即竞争领导者.

这样做是为了解决由于重负载导致引导节点虚假死亡的问题. 优先选择原始领导者节点可以减少同步数据量.

ProposalID由Zxid +机器ID决定，其中Zxid代表此节点的最新Commit的事务ID.

Zookeeper将优化以选择具有最新提交记录（最大Zxid）的计算机作为领导者. 如果Zxid相等，则将选择具有较大计算机ID的Zxid.

Zookeeper中的节点同时具有Acceptor和Proposer，并且Prepare阶段和Accept阶段之间没有明显的区别.

提案的提案ID和提案值，使用相同的投票结构，在每轮投票中直接发送投票. 其他节点收到建议后，如果它们大于自己的建议，则将其ProposalID和值更新为接收到的Vote值，然后广播将新建议发送给其他节点.

经过多轮投票，每个节点的提案将趋于最终价值.

可以看出，基本Paxos实例完成后，它需要经历每个提议者的准备阶段和接受阶段. 它还需要在超过一半的节点上成功提交. 太多的过程导致性能降低. 通常在实践中使用Multi Paxos协议.

Multi Paxos协议消除了Basic Paxos的准备阶段. 领导者节点直接提交提议，并通知其他跟随者节点提交提议. 在领导者租约中，只有领导者可以提出建议. 如果领导节点崩溃并发生故障，或者在租约到期后租约没有续约，则其他跟随者将使用Basix Paxos协议来争夺领导权.

在使用Multi Paxos协议进行多节点复制时，需要注意一些细节. 有关详细信息，请参阅本文和本文.

我最近在项目中遇到了解决中央节点（以下称为DC节点）单点问题的需求. 我考虑了一下，有三种解决方法:

vip + keepalived

部署了两台计算机（一台主计算机和一台备用计算机），这两台计算机使用keepalive来检测心跳并向外界提供VIP. 每台计算机都设置了一个crontab脚本，每隔5分钟检查一次Dc进程是否存在，如果不存在，则将其启动.

Vip用于从外部访问此节点. 如果计算机的Dc进程崩溃，则crontab脚本将上拉. 如果整个计算机挂断，vip将切换到另一台计算机的ip.

使用Zookeeper选举一个领导者担任外部服务. 当领导节点挂断时，选择另一个节点. 通过Zookeeper实时从外部获取Dc的真实IP.

此方法有一个缺点: 部署Zookeeper集群，需要先运行Zookeeper，然后再运行其他节点.

Dc节点内置了基本Paxos协议以实现选举，并提供了一个接口来获取Dc领导者节点的IP.

Paxos制作了简单的纸

说明的分布式一致性协议Paxos

说明的动物园管理员FastLeader选举算法

“从Paxos到Zookeeper-分布式一致性的原理和实践”第2、3、4、7.6章

逐步了解Paxos算法

这篇文章非常简单易懂，我是通过这篇文章实现的！

[Paxos三部曲之一]使用Basic-Paxos协议进行日志同步和恢复

介绍Basic-Paxos的应用程序，以解决多节点复制日志的一致性问题.

[Paxos三部曲第二部分]使用Multi-Paxos协议进行日志同步和恢复

建筑师需要了解的Paxos原理，历史和实际战斗

视频Paxos和分布式系统

百度的高级工程师非常擅长解决Paxos协议！

Paxos在大型系统中的常见应用场景

多IDC数据分发设计（1）

多IDC数据分发设计（2）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-210401-1.html