Zab：针对主备份系统的高性能广播

论文地址：Zab：针对主备份系统的高性能广播

本文描述了支持Zookeeper的原子广播协议。Zab并不像我们目前看到的Paxos和VR那样复制操作，而是复制状态更改。
Zab设计的关键是观察到每个状态变化相对于前一个状态是递增的，因此存在对状态变化顺序的隐式依赖。因此，状态更改不能以任何任意顺序应用，关键是要确保给定主服务器生成的状态更改的前缀被传递并应用于服务状态。
Zab也是为高性能而设计的，这导致了同时拥有多个未完成事务的愿望。提出的论点是，Paxos不能处理多个未完成的ttransactions和incremental state属性的组合。在我看来，情况并不像论文上说的那么糟：

 在我们的设置中，启用多个未完成的ZooKeeper操作以及ZooKeeper客户端同时提交的操作前缀是根据FIFO顺序提交的，这一点很重要。然而，实现复制状态机的传统协议（如Paxos）并不能直接启用这种特性。如果主项单独提出事务，则学习事务的顺序可能不满足顺序依赖性，因此学习事务的顺序不能未经修改而使用。解决此问题的一个已知解决方案是将多个事务批处理为单个Paxos建议，并且一次最多有一个未完成的建议。这种设计会对吞吐量或延迟产生不利影响，具体取决于批大小的选择。<br />下面是一个例子，其中三个不同的提议者为三个连续的序列号提出建议。后一个提案被接受，但第一个提案未能达到法定人数，后来被另一个提案取代。由于FIFO排序要求（增量状态依赖），这违反了Zookeeper要求。

现在，Lamport自己在Paxos中做了一个简单的陈述，即需要一个杰出的提议者（因此我们通常没有多个提议者提出建议），我们知道这个杰出的提议者（或虚拟现实中的虚拟现实主要者）可以对客户交易进行排序。此外，Lamport还描述了同时执行的多轮Paxos。如果学习者在所有先前的操作都被应用之前，不从他们的日志中应用某个操作，这似乎表面上给了我们Zab所需要的东西。在正常情况下我相信会的。那么为什么Zab会担心“如果初选提议单独进行交易…？“这并不是因为出于性能原因，他们想启用它，因为Zab本身也使用主备份模型。因此，在我看来，Paxos留下的差距是在杰出的提议者因未完成但未被接受的提议而失败的情况下。这可能导致序列中的空白，新的杰出的提议者将用无操作来填补空白。

Zab排序要求称为主排序。
…我们需要满足一个以上的属性，才能从给定的主进程中启用多个更改。由于每个状态更改都基于上一个状态（如果跳过上一个状态的更改），因此还必须跳过从属更改。我们称此属性为primary order，并将其分为两部分：本地primary order和全局primary order。

• 本地主顺序表示，如果主广播m1在m2之前，那么任何传递m2的进程都必须先传递m1。
• 全局主顺序表示，如果一个主广播m1，然后主广播发生变化，而新的主广播m2，那么任何同时传递m1和m2的进程都必须首先传递m1。注：在这种情况下，本规则允许交付m2，但不允许交付m1。

……不同初选发送的交易不一定被视为因果关系，即使它们实际上是通过同一流程发送的。
现在我们已经排除了动机，让我们看看核心Zab协议是如何工作的。有三个阶段：发现、同步和广播（正常操作）。正是同步阶段使Zab与众不同：

• 为了在主崩溃的情况下保证主订单，Zab实现了三个阶段。同步是保证性能得到满足的一个关键阶段。当主进程发生更改时，进程的仲裁必须在新主进程广播新事务之前执行同步阶段。执行此阶段可确保已选择或将要选择的前一个纪元中广播的所有事务都位于新纪元事务的初始历史记录中。

本文对算法的正确性进行了分析，并对算法的实现进行了评价。在这里，我将集中讨论核心协议本身。
根据协议，Zab进程可以执行两个角色：leader和follower。领导者同时执行主要角色，并根据主要角色的广播调用顺序提出事务。跟随者根据协议的步骤接受事务。领导者也执行跟随者的步骤。

此外，每个进程都实现一个leader oracle，以确定它应该遵循的其他进程（例如，请参阅Viewstamped Replication的循环方案，以了解这种方法的一种工作方式）。如果一个过程的领导者甲骨文确定它是领导者，那么这个过程执行协议的领导者步骤——这还不足以建立它的领导者，但是第2阶段（同步）做到了这一点。
Zab进程可以查找领导者（选举状态）、跟随者（跟随状态）或领先者（领先状态）。当一个进程开始时，它进入选举状态。在这种状态下，该过程试图选举新的领导人或成为领导人。如果流程找到一个当选的领导者，它将移动到以下状态并开始跟随领导者。处于以下状态的进程是跟随者。如果这个过程被选为领导者，它将进入领导状态并成为领导者。考虑到一个引导的过程也随之而来，引导和跟随的状态并不是唯一的。如果发现领导人失败或放弃了领导权，跟随者将过渡到选举，而一旦观察到不再有足够的跟随者支持其领导权，跟随者将过渡到选举。
算法的迭代过程贯穿于这三个阶段。注意，Zab在每次迭代的进程之间重新建立TCP连接，从而确保不再传递来自旧迭代的消息。

发现
追随者将当前Epoch消息（CEPOCH）发送给未来的领导者（由甲骨文选择），其中包括他们承认的上一个新纪元（new epoch）消息的Epoch号（如果有的话）。
一旦潜在领导人收到来自追随者群体的CEPOCH消息，它将分配一个新的epoch号码，该号码大于这些消息中追随者发送的任何号码，并将一个新的epoch消息发送给每个成员，包括这个新的epoch号码。
当一个跟随者收到这个新纪元消息时，如果纪元数大于它先前确认的最后一个纪元数，它就会确认它。下面发送的epoch确认消息包括跟随者的当前epoch，以及跟随者的事务历史记录。

建议进行优化的点：
如果跟随者的历史可以任意长，则在ACK-E中发送整个历史是无效的。跟随者的最后一个zxid足以让潜在的领导者确定是否需要从任何给定的跟随者复制事务，并且只复制丢失的事务。
当被提名的领导人收到法定人数中每个成员的纪元确认时，它从确认中发送的所有历史中选择最新的历史作为新纪元的初始历史。最新的历史记录是具有最高纪元号的历史记录，并且在该Epoch内具有最高的事务id。

同步
从一个新的Epoch开始，新的领导人被提名。同步步骤证实了这种领导力。

• 选举产生的领导人在完成第二阶段之前不会为某一特定的Epoch e建立起来，在第二阶段中，他成功地就提案历史和作为e领导人的身份达成了共识。
• 提议的领导人向法定人数中的每个成员发送一条新领导人（new leader）消息，其中包含新启动的历元的历元编号以及该历元的初始历史。
• 当一个跟随者收到一个新的leader消息时，它将检查epoch号和它上次确认的epoch号。如果它们不同，它将启动协议的新迭代。当然，在预期的情况下，它们是相同的，跟随者通过接受初始历史中的所有交易并将其自身历史设置为匹配来进行。然后它承认新领导人的提议。
• 一旦提议的领导者收到法定人数的确认，它就被建立为新的领导者，并向所有追随者发送一条提交消息。
• 当一个跟随者接收到这个提交消息时，它按顺序传递（参见VR的service up call）初始历史中的每个事务。
  

广播
这是系统在怀疑有问题之前一直处于的正常阶段：

为了以细粒度和方便的方式相互检测崩溃，避免操作系统重新配置，领导者和追随者交换周期性心跳。如果领袖在一个超时时间间隔内没有收到来自法定追随者的心跳信号，他将放弃这个时代的领袖，并过渡到选举状态。一旦它选择了一个leader，它就开始一个新的算法迭代，并开始一个新的协议迭代，进入第1阶段……一个follower每次只跟随一个leader，只要它在一个超时间隔内接收到心跳信号，它就保持与leader的连接。
广播阶段的基础现在看起来应该已经很熟悉了：leader按照事务id的递增顺序提出事务。对于每个提议，leader都要等到收到一个确认的仲裁，然后为该事务发送一个提交消息。注意，Zab的通信媒介保证了有序的消息传递。
跟随者按照接收事务的顺序（事务id顺序）接受事务，并在接收到提交消息并以较低的id传递了所有先前接受的事务后传递这些事务。
在这一阶段中，领导者可能从跟随者（例如，从正在从失败中恢复的进程）接收到CEPOCH消息。如果是的话，它会用当前的纪元号来表示NEWEPOCH，用当前的纪元历史来表示NEWLEADER。如果它收到了对这个新的leader提议的确认，那么leader将发送一个commit消息。
注意，当一个新的领导者出现时，以及当一个追随者连接到一个已建立的领导者时，追随者和领导者都遵循恢复协议。如果leader已经建立，那么NEWLEADER建议已经提交，因此对NEWLEADER建议的任何确认都将被忽略。

这个协议的最后一部分在我看来在这个版本的论文中没有详细说明。第2阶段（同步）的全部目的是在多个未完成的事务面前使整个组位于同一页上。所以在第三阶段，当CEPOCH交换发生在一个现有的领导者身上时，我们需要保留这个属性。在收到确认之前（在最坏的情况下，这当然会阻止进程直到超时），在用当前历史记录发送回new leader之后，leader是否不建议任何新事务？或者是否有一个隐含的追赶机制，以便新的跟随者可以接收到NEWLEADER和后续提交之间的任何历史增量？我怀疑是后者。这样的复制机制被非正式地描述为在同步期间引导者追赶：
跟随者的最后一个zxid足以让潜在的领导者确定是否需要从任何给定的跟随者复制事务，并且只复制丢失的事务。