一文通吃：从 ZooKeeper 一致性，Leader选举讲到 ZAB 协议与 PAXOS 算法（下）

本文首发自「慕课网」，想了解更多IT干货，程序员圈热闻，欢迎关注“慕课网”或慕课网微信官方账号！

作者：大能 | 慕课网讲师

在最后一篇文章中，我们介绍了Zookeper集群的数据一致性和Zookeeper集群的Leader选举，然后介绍了ZAB协议和Paxos算法

Zookeeper在处理事务请求时提到了一个协议，即ZAB协议，然后在Leader选举中，Zookeeper也是基于该协议实现的。因此，事实上，这种ZAB协议在整个Zookeeper集群模式中非常重要。

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议)。ZAB协议为分布式协调服务 ZooKeeper 一种专门设计的支持 崩溃恢复和原子广播这里需要注意的是，它不是一种通用的分布式一致性算法，而是Zookeeper 自己定制的好处是比较简单，没那么复杂，跟着 ZooKeeper 完美契合。

基于此协议，ZooKeeper 每个副本之间都实现了数据一致性，当集群初始化或主节点出现故障时，需要通过本协议进行Leader节点选举，让我们来看看这个问题：

数据一致性的保证和Leader节点选举都很依赖事务ID，在ZAB协议中叫做 ZXID ，那么这个 ZXID 是怎么设计的？是不是只是一个从小到大递增的简单过程？

让我们来看看这个问题。 ZXID 它是如何产生的

在 ZAB 协议的事务编号 ZXID 设计中，ZXID 是一个 64 位数，其中：

• 低 32 位置：可视为一种简单的递增计数器，针对客户端的每一个事务要求，Leader 都会产生新的事务 Proposal 并对计数器进行测量 + 1 操作。
• 高 32 位置：代表 Leader 取出当地日志中最大的事务 Proposal 的 ZXID，并从该 ZXID 对应的中分析 epoch 值，然后加一个值。

高 32 位代表每一代 Leader 独一无二，低 32 代表了每代 Leader 事务的独特性。同时，它也可以使 Follwer 通过高 32 不同的位置识别 Leader。

基于这一策略，当一个服务器启动并加入集群时，包含了上一个Leader周期中尚未提交的事务Proposal，发现此时集群中已经存在Leader，并将自己与Follower角色连接到Leader服务器，根据Leader服务器 当您的服务器上最终提交的Proposal与Follower服务器的Proposali进行比较时，您会发现follower中有最后一个leader）周期的事务Proposal，Leader将要求Follower进行返回操作(返回到集群中一半以上机器提交的最新事务Proposalal.)。

当整个集群启动时，或当 Leader 当服务器出现网络中断、崩溃、退出或重启等异常情况时，Zab协议将出现 进入崩溃恢复模式，选举产生新的Leader。

一旦崩溃，数据将不一致，ZAB的崩溃恢复将开始工作。有以下两个保证：

1. ZAB协议需要确保所有服务器最终都提交了Leader提交的事务。
2. ZAB协议需要确保只在Leader服务器上丢弃的事务。

根据前两个要求，如果Leader选举算法确保新选举的Leader服务器拥有集群中所有机器的最高数量（ZXID最大）的事务Proposal，则可以确保新的Leader 必须有所有已提交的提案。更重要的是，如果这样做，Leader服务器可以节省检查Proposal提交和丢弃工作的步骤。

一旦Leader服务器崩溃，或者由于网络原因，Leader服务器与超过一半的Folllower失去联系，就会进入崩溃恢复模式。为了保证程序的正常运行，需要在整个恢复过程后选择新的Leader服务器。因此，ZAB协议需要一种高效可靠的Leader选举算法，以确保新的Leader能够快速选举。同时，新的Leader选举算法不仅需要让Leader知道他已经被选为Leader，还需要让集群中的所有其他机器快速感知选举产生的新的Leader服务器。

ZAB协议规定，如果一个事务Proposal在一台机器上成功处理，即使机器崩溃，它也应该在所有机器上成功处理。

当新的Leader出来，同时，一半以上的机器完成同步后，ZAB协议将退出恢复模式。进入新闻广播模式。此时，如果遵守Zab协议的服务器加入集群，因为集群中已经有一个Leader服务器在广播新闻，新加入的服务器将自动进入恢复模式：找到Leader服务器并完成数据同步。同步完成后，作为新的Follower参与新闻广播流程。

收到客户端事务请求后，集群中的其他机器将首先转发Leader服务器，由Leader统一处理。

1. 在zookeper集群中，数据副本的传输策略是采用新闻广播模式。zookeper中数据副本的同步模式类似于第二段提交，但不同。第二段提交要求协调员在发送commit消息之前，必须等到所有参与者反馈ACK确认消息。要求所有参与者要么成功，要么失败。第二段提交会造成严重的堵塞。
2. Zab协议中 Leader 等待 Follower ACK反馈信息是指“只要超过一半的Follower成功反馈，就不需要收到所有Follower反馈”
3. 在整个过程中，Leader为每个事务请求制作相应的Proposal，并在广播前为这个事务分配一个全球唯一的ID，这是ZXID(事务ID)，必须按照增加的事务顺序处理。

ZAB协议涉及的第二阶段提交与2pc不同。在ZAB协议的第二阶段提交过程中，删除中断逻辑，所有Follower服务器要么正常反馈Leader提出的事务Proposal，要么放弃Leader服务器。在ZAB协议中，只要集群中一半以上的服务器反馈ACK，就开始提交事务，不需要等待集群中所有的服务器反馈。该模型无法处理Leader服务器崩溃退出带来的数据不一致，因此在ZAB协议中增加了另一种模式，即使用崩溃恢复模式来解决问题。此外，整个新闻广播协议是基于具有FIFO特征的TCP协议进行网络通信的，因此在新闻广播过程中很容易保证新闻接收和发送的顺序。

在整个新闻广播过程中，Leader服务器将为每个事务请求生成相应的Proposal进行广播，在Proposal之前，Leader服务器将首先分配一个全球单调增长的唯一ID，我们称之为事务ID（即ZXID）。由于ZAB协议需要确保每个消息之间严格的因果关系，因此必须按照ZXID的顺序对每个事务Proposal进行排序和处理。

在新闻广播过程中，Leader服务器将为每个Follower服务器分配一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列，并根据FIFO策略发送消息。每个Follower服务器在接收到Proposal后，将首先以事务日志的形式将其写入当地磁盘，并在成功写入后反馈给Leader服务器ACK响应。当Leader服务器收到超过一半的FollowerACK响应时，它将向所有Folllower服务器广播一条Comit消息，通知其提交事务。同时，Leader本身也将完成事务提交，每个Follower服务器在收到Commit消息后也将完成事务提交。

• 崩溃恢复:正常情况下运行很好。一旦Leader崩溃或者Leader服务器因为网络原因与超过一半的Follower失去联系，就会进入崩溃恢复模式。为了程序的正确运行，需要在整个恢复过程后选择新的Leader，因此需要高效可靠的选举方法来快速选择Leader。
• 新闻广播：类似于两个阶段的提交过程，针对客户端的事务请求， Leader服务器将为其生成相应的事务Proposal，并将其发送到集群中的所有其他机器，然后分别收集各自的选票，最后提交事务。

当启动过程或Leader出现网络中断、崩溃退出、重启等异常情况时。

当选举出新的Leader时，集群中一半以上的机器与Leader服务器完成状态同步后，ZAB将退出恢复模式。

我们已经学习了Zokeper的ZAB协议。我们知道这个协议是根据Zokeeper自身的功能特点实现的一致性协议。通过这个协议，我们可以保证Zookeper集群的数据写作操作能够有序进行，从而保证集群节点之间的数据同步和一致性。然后在这个过程中，Zookeper集群的Leader节点起着重要的作用，所有的写作操作都需要处理和协调。这样做的好处是，多个节点之间的数据同步处理相对简单，我们可以反过来思考，如果它不是这样，或者不止一个节点来处理写作请求，那么它在同步数据时会有什么困难呢？

假设有五个节点，server 1 ～ server 5.它们的初始值为0。现在我们假设这个集群节点没有Leader节点，或者我们的集群有多个节点可以处理写请求，我们假设这里有server 5.server 写请求可以处理。

现在我们假设Client1 向server 5发现写请求，将v=0改为v=1，Client2也发起写请求，将v=0改为v=2，那么此时同步会出现什么问题呢？如下图所示，我们会发现写作顺序无法保证。由于网络问题，有些节点在数据同步时接收v=1，然后接收v=2，但有些节点在接收v=1之前接收v=2，因为server 5 和server 2之间没有“合作”，会导致集群各节点的最终状态不同，无法保证一致性。

因此，在Zookeep中，通过引入Leader节点来协调不同的写作请求。这样可以保证写作操作的有序性和同步的有序性，最终保证集群同步后所有节点数据都是一致的。

如图所示，由于Leader的存在，Client1和Client2的操作均转发给Leader统一处理。然后Leader可以控制这两个操作的顺序，并获得每个操作数据同步的结果。这样，如果Clinet1优先考虑，Leader节点将首先应用v=1，然后将v=1同步到每个节点，然后处理Clinet2的操作，以避免数据不一致。

然后你可能会想，介入一个Leader角色不是一切都好吗？但是，想想Leader模式可能存在的问题。很明显，你可以想到:

• Leader单个节点负载过高
• Leader存在单点故障的风险

那么，鱼和熊掌能兼得吗？我们不仅可以避免单点问题，而且可以解决我们上面提到的多个节点在编写数据时的数据不一致性。

所以答案是肯定的，这是另一种分布式一致性算法——Paxos

事实上，Paxos算法在整个分布式领域中起着非常重要的作用。它实际上比Zookeper早出现。它是莱斯利·兰伯特（Leslie Lamport，该人于1990年在微软研究院提出了基于消息传递的一致性算法。Zookeper的ZAB协议实际上是基于Paxos定制的。因此，相比之下，Paxos是一种更通用、更普遍的分布式一致性算法，其目标是解决分布式系统如何就某一值（决议）达成一致 这样的问题。

典型的场景就像我们刚才分析的场景。如何确保我们的多个写作操作数据与整个集群同步，以确保一致性。该算法可以解决这样的问题。

这里的核心思想是，多个写作操作对应于多个命令，然后我们想确保每个节点一致，可以转换问题，是让这些节点，他们执行这些命令，顺序是一致的，所以最终效果可以保持每个节点的数据一致。因此，每当集群节点收到写作请求时，它不会像Zookeeper那样直接交给老板处理，而是与集群的其他节点进行谈判，让这些有决策权的节点一起参与决议，以确定现在是否可以接受这个请求，然后我们一起投票。如果超过一半，则表示通过了决议。这个过程有点像我们之前谈论Zookeper的Leader选举，但细节仍然不同。接下来，让我们详细学习Paxos算法的操作过程。

首先，Paxos算法中有三个角色：

• Proposer
• Acceptor
• Learner

在具体实现中，一个过程可能同时扮演各种角色。例如，一个过程可能是Proposer、Acceptor和Learner。

还有一个重要的概念叫做提案（Proposal），也就是说，你想要其他节点来决定什么，首先要表达出来。例如，在我们之前的场景中，Client1的要求是把它放在一边 v 的值改为 1.那么这个值就会放在提案里。

这里需要注意的是，这个过程也有一个轮换的概念，每一轮提议和决策都有一个编号，跟随Zookeeper Leader选举时，每一轮投票都有一个zxid。所以准确地说 提案 = 编号 + value

因此，目前总结了这些角色与概念之间的关系：

Proposer可以提出（propose）提案：Acceptor可以接受（accept）提案；如果选择提案；（chosen），然后选择提案中的value，然后这个值会同步给learner。它不需要参与决策。人们告诉它多少就多少，不会讨价还价。

因此，回顾我们刚才提到的Paxos的目标，解决分布式系统如何就某个值（决议）达成协议。这里的数据值是指Proposer、Acceptor、Learner认为同一个value被选中（chosen）。那么，Proposer、Acceptor、在什么情况下，Learner可以认为value是被选中的？

• Proposer：只要Proposer发送的提案被Acceptor接受(超过一半的Acceptor同意)，Proposer就会认为提案中的value被选中。
• Acceptor：只要Acceptor接受了一个提案，Acceptor就选择了任务提案中的value。
• Learner：Acceptor告诉Learner哪个value被选中，Learner认为value被选中。

最后，我们需要补充的是，在Proposer生成提案内容之前，它会先去『学习』已经被选中或可能被选中的value，然后以value作为自己提出的提案。如果没有value被选中，proposer可以自己决定value的值。这样才能达成协议。这个过程叫做 学习提案。

好吧，接下来，我们将结合之前的场景和刚才对Paxos的分析。让我们结合一个案例场景来看看这个过程

我们还是按照前面集群五个节点的例子来解释，对应右边。我们可以看到这个集群节点有两个Proposer和三个Acceptor，所以对于这两个节点，他们可以接受这个写作操作。然后收到后，我们会去这个Acceptor进行询问和协商。 然后，这个写作操作将在协商后应用。

所以整个场景都是这样的，让我们逐渐看看。在这里，让我们转换这个图形。所以我们可以把整个过程理解为两个阶段的处理过程。然后，第一阶段是我们在这里可以看到的。对于这个Proposer，它将首先向三个Acceptor发起这个Propose请求，对吗？然后同时发起这个请求。会带上一个号码，这里的这个号码是100。

所以这是第一步。好吧，接下来的三个Acceptor接收到这个report请求后，他们会记录当前的编号是100，然后因为目前的三个Acceptor还没有收到其他请求。(暂时没有接受其他提议)然后三个Acceptor会做出这样的回应，告诉Proposer没有接受其他提议。

好吧，接下来的第三步。这个时候，Proposer一收到之前的响应，就可以在这个时候发起这个第二阶段的请求。第二阶段的请求是Accept的请求(对应上述提案)。所以在这里我们可以看到，这个Accept的请求中会有这个号码100，同时也会有这个提案的内容（v=1）.

对于这三个请求，他们的情况会有所不同。

所以首先发送到这个Accept1，它可以正常到达，然后发送到另外两个Acceptor的请求，因为网络的问题，还没有到达。所以我们说这两个请求暂时没有到达这两个Acceptor的节点。

好了，然后这个时候这个Proposer2也收到了写作请求，这个时候也会发起prepaper的请求。就像前面的Proposer1一样，它首先会在第一阶段发起一个请求，然后这个时候会带一个号码(101)，就是在前面的基础上做一个加一操作。所以对于这个prepaper(101)，我们可以看到这里有三个请求，然后有些请求到达Acceptor1节点，有些还没有，对吧？然后我们可以看到Acceptor1和Acceptor3，他们收到了这个prepaper(101)的请求，那么这个时候会发生什么呢？我们可以先想想。

然后我们在这里再注意一下，就是这个Acceptor1，因为我们可以看到前面是这个Accept，请到达这个Acceptor1，所以这个时候可以去这个Proposer1做这个响应。因为第一阶段收到的prepaper号是100，第二阶段收到的accept请求号也是100，所以这个号是对的。此时，它可以将之前提案的内容v=1应用到当前的节点上。因此，我们在这里可以看到，现在这个Acceptor1上的v已经等于1了，然后它就会对这个Proposer1做出反应。此时Proposer1，收到了这张票的回应。

好吧，然后我们继续往下看。让我们来看看这个prepaper（101）的请求。当它到达两个acceptor节点时，会发生什么。在这里，我们可以看到这个acceptor1和这个acceptor3。当他们收到这个prepaper（101）时，他们的情况会有所不同。

• Acceptor3的处理

首先，让我们来看看这个Acceptor3，因为它没有收到这个Accept(100，1)个提案的。所以这个时候它的值是零，id是100。当它收到这个prepaper(101)时，很明显这个101大于100，因为这个id的编号前面是100，现在是101。而且因为这个Acceptor3还没有响应这个提案，所以现在这个Acceptor3会先把这个id改成这个101，因为这个101现在是这个最大的数字。同时，它会告诉Proposer2，我还没有接受过其他建议，你可以发起这个建议。

• Acceptor1的处理

然后我们看看左边的Acceptor1，那么这个Acceptor1就有点不一样了。因为之前已经接受过这个propose提案，所以这个时候除了把这个数字从100改成101之外，还会告诉这个proposer2，说之前接受过另一个提案，然后提案的内容是v=1。

因此，对于这个Proposer2，它现在将学习这样一个提案的内容，即v=1。因此，对于这个Proposer2，当它处理第二阶段时，它将发送这个v=1作为提案的内容。这就是我们前面提到的学习提案的过程。

好吧，然后我们继续往下看。此时，这个Proposer1发起的提案现在已经到达Acceptor2和Acceptor3两个节点。所以当我们到达这两个节点时，我们可以看到它的提案是100，然后Acceptor2的id是100，但Acceptor3，因为它已经接受了Proposer2的请求，所以它的id是101。

那我们来看看这个时候会发生什么。所以在这里我们可以看到，对于这个Acceptor2，它现在可以接受这个propose提案了，对吧？因为这个数字是对的，所以它会告诉这个Proposer1，它接受了这个提案。

到目前为止，这个Proposer1已经收到了Acceptor1和Acceptor2两个响应的提案，即通过这个半数以上的Acceptor的决议，对吗？

所以到目前为止，这个Proposer1现在上面的值可以变成1。因为它的提案已经通过一半以上的Acceptor投票了，对吧？然后我们再来看看这个Acceptor3，因为这个100小于101，所以对于Proposer1。当它发起的提案到达节点时，它现在会被节点拒绝，因为它已经小于节点上的数字，所以此时它的提案将被节点拒绝。所以这个时候，对于这个节点来说，上面的v还是0，因为它拒绝回复这个提案。但是，这种拒绝并不影响Proposer1，其上值变为1，对吗？因为它已经通过了Acceptor半数以上的表决。

好吧，我们再来看看这个Acceptor2。这时，它才收到前面的这个。prepaper(101)这个请求由Proposer2发起。所以根据我们之前的分析，这个时候这个101是100。好吧，那么它就可以接受这个prepaper(101)了。然后因为这个Acceptor2此时已经接受了这个Proposer1的提案，对吧？所以它也会告诉这个Proposer2像v=1这样的提案内容。所以这也是一个学习提案的过程。就是这个Acceptor2会把这个v=1这样的提案内容响应给这个Proposer2。然后我们再往下看。这个时候，对于这个Proposer2来说，他之前已经得到了这三个Acceptor的响应，也就是在第一阶段prepaper请求时，他已经收到了这三个Acceptor的响应，这个Proposer2从这个Acceptor1和这个Acceptor2中学到了这样一个新的提案。就是v=1。

所以最后一步是发起这个提案。这一步，他会把这个提案的内容是v=1，放在他的提案内容中，然后去三个Acceptor节点，发起这个Accept请求。

在这里，我们可以看到三个Accept请求，它的编号是101，然后它的值等于1，这是他从之前的学习过程中得到的提案。所以现在对于这个Acceptor3，这个数字现在可以匹配101，然后他可以将提案应用到这个节点。所以这个时候我们可以看到，这个节点的值也变成了这个1。

所以这就是Paxosos 在这种情况下，算法是它的处理过程。

① Proposer生成提案

1、Proposer选择N2号的新提案、向半数以上的Acceptor发送请求：Prepare(N)3、Acceptor接受后做出以下响应：  a. Acceptor不再接受任何编号小于N的提案  b. 如果Acceptor已经接受了提案，对Proposer响应已接受的编号小于N的最大编号提案4. 如果Proposer收到超过一半的Accceptor响应，则可以生成编号为N、值为V的提案[N,V]，并向Acceptor发送请求：Accept(N, V)///这里的V是所有响应中编号最大的提案值，如果所有响应都没有提案，Proposer可以自己决定V

② Acceptor决策提案

1、Acceptor可以接受Prepare和Accept请求2、而且，在不影响算法安全性的情况下，可以选择忽略要求。、Acceptor对这两个请求做出了这样的决定：  a. 对于Prepare(N)，而且N大于Acceptor响应的所有Prepare请求号，它将向Proposer反馈已接受的最大编号提案（如果有）作为响应，Acceptor将不再接受编号小于N的提案  b. Accept(N, V)，而且N大于Acceptor响应的所有Prepare请求号，它接受了提案4、Acceptor只需记住：编号最大的请求和编号最大的提案

③Paxos算法描述

Paxos算法分为两个阶段。具体如下:

• 阶段一：(a) Proposer选择提案编号N，然后将编号N的Prepare请求发送到半数以上的Acceptor。(b) 如果Acceptor收到N的Prepare请求，N大于Acceptor已经响应的所有Prepare请求的编号，那么它将向Proposer反馈最大的提案（如果有）作为响应，Acceptor承诺不再接受任何编号小于N的提案。
• 阶段二：(a) 如果Proposer收到一半以上Acceptor对其N号Prepare请求的响应，那么它将发送一个[N,V]提案的Accept请求超过一半的Acceptor。注意:V是收到响应中最大的提案的value。如果响应中没有提案，v将由proposer自己决定。(b) 如果Acceptor收到了N号的Accept请求，只要Acceptor没有响应N号以上的Prepare请求，它就会接受该提议。

以上是文章的全部内容。谢谢你的阅读。

欢迎关注「慕课网」在官方账号中，我们将始终坚持提供IT圈的优质内容，分享干货知识，共同成长！

本文原创发布于慕课网。 ，请注明转载来源，谢谢合作