zookeeper ZAB协议的实现

2019-08-08 本文已影响0人 Monica2333

在 zookeeper源码分析系列中按照服务端客户端启动或交互等主线讲解了源码，但并没有将Zab协议的完整实现串起来。本文主要翻译自ZooKeeper’s atomic broadcast protocol:
Theory and practice这篇论文，可完整的展现Zab协议的理论和实现。
Zab协议是zookeeper原子广播协议，依赖它选举出一个Leader，同步节点，通过Leader按顺序广播修改内容，并且从故障中快速恢复正常状态。在介绍上述实现之前，我们先了解下Zab协议的背景和协议的理论知识。

Paxos协议和Zab协议的异同点

原子广播协议的重点在于通过leader进程原子的顺序广播到其他节点进程，同时保证这个操作一致性的成功或者失败，最终不会出现节点之间状态不一致的情况。满足四个特性：

Validity：如果一个正常的节点广播了一个消息，则所有正常的其他节点都会最终提交。
Uniform Agreement：如果一个节点提交了一个消息，则所有正常的其他节点都会最终提交。
Uniform Integrity：对任何消息，每个节点最多提交一次，并且先前必须广播过。
Uniform Total Order：如果节点q和p提交两个消息m和m',则q和p对消息m和m'的提交顺序应是一样的。
Paxos是解决分布式共识（分布式一致性）的协议。它的目的不在于原子广播，当然它可以对原子广播的协议提供支持，如Zab协议。但是它不对上述原子广播中的特性提供保证，如所有节点的一致性顺序提交。它只是一个达成分布式共识的算法。
Zab协议两个重要的要求是提供处理大量的客户端请求和从崩溃中快速恢复的能力。这种并发按顺序的提交是通过zookeeper内部的FIFO队列实现的，同时对崩溃恢复也是有作用的。经典的Paxos算法不能满足处理大量的客户端请求的要求，因为Paxos算法不要求使用FIFO通道通信，所以它允许消息的丢失和乱序提交。在主节点崩溃后，Paxos不能利用事务的顺序序列来恢复集群，而Zab协议通过事务标示（zxid）来表示事务的顺序性，这样在选举时会优先考虑zxid最高的节点作为Leader节点，这样可使用Leader节点的提交记录来同步其他节点。而在Paxos中节点同步时，Leader节点还需要提交所有先前自己为提交的事务。
ZooKeeper还需要满足一些性能要求：如低延迟，高吞吐，一定的容错性等。

崩溃恢复模型

有选举权的节点叫做peer节点，假设共有N个peer节点 (Π= {fp1, p2.. pN})，如果其中大于N/2的peer节点投票的leader节点是同一个( Q> N=2,Q ⊆ Π)，则选主完成，这组peer节点称为一个quorum。每个peer节点两两建立双向通道，从而保证：

Integrity：节点p从特定通道接收到的消息一定是另一端节点发送的。
Prefix：节点p从特定通道接收到的消息顺序一定是另一段节点发送的消息顺序。ZooKeeper使用tcp通信的先进先出通道来实现。

Zab协议的满足特性

为了实现一致性保证，Zab协议必须满足一些特性。首先先声明下一些协议定义。
ZooKeeper中需要保证事务的顺序性，所以同一时刻只能有一个leader节点。我们定义leader节点的变化为ρ1ρ2 ... ρe....(ρe ⊆ Π)，其中e代表一个整数epoch,表示在这个周期内ρe是这组集群的leader节点。此外如果e < e',则 ρe节点不是祝节点，ρe'才是。
事务代表的是leader节点向其他节点广播的新状态，用<v,z>表示。其中v代表新状态的内容,z代表zxid。事务的提交是两阶段提交，首先leader节点发送事务的 proposal，得到超过一半的peer节点的ack之后，再发送commit给所有节点。下面这些特性Zab协议必须满足：

Integrity：如果节点提交<v,z>事务，则节点一定收到过事务的proposal。
Total order：如果一些节点先提交<v,z>，后提交<v',z'>，则其他任何节点也是这个提交顺序。
Agreement：就是说一个事务要么成功，要么失败。且成功的内容所有节点都是一样的。
每个集群节点的事务一致性顺序性（Primary order）需要满足：
Local primary order：如果 leader节点上<v,z>先于<v',z'>广播，则<v,z>，先于<v',z'>提交。
Global primary order：如果epoch i<i'，ρi节点广播了<v,z>，ρi'节点广播了<v',z'>，如果均提交的话，则<v,z>，先于<v',z'>提交。
Primary integrity:如果epoch i<i'，ρi节点广播了<v,z>并且有些节点提交了<v',z'>，则<v,z>的提交要先于<v',z'>的广播。

Local primary order是由节点本地FIFO队列实现的，Primary integrity保证了新的epoch的前epoch事务都已经提交了。

Zab协议的理论实现

在Zab协议中，一个peer节点可能有三种状态：

following
leading
electing
同时，一个peer节点对应ZooKeeper中的三种执行阶段：
Phase1:discovery
此时peer节点处于electing状态，正在投票选举出一个leader节点出来，同时确定自己的节点状态。有时集群选举也叫做Phase0阶段。
Phase2:synchronization
leader节点和其他节点数据同步。
Phase3:broadcast
Phase3阶段完成了过半peer节点的数据一致性同步，此阶段至多有一个leader节点用来广播原子事务消息，类似于两阶段提交。Phase1和Phase2对于集群整体数据一致性至关重要，特别是在崩溃回复时。在这三个阶段中，如果peer节点有节点间通信失败或者超时发生，peer节点可决定是否回到Phase0阶段重新选举。
ZooKeeper客户端通常和一个ZooKeeper服务端节点建立会话连接，如果是写请求，ZooKeeper节点会将请求转发给leader节点，读请求的话则节点自己处理。客户端可发送sync请求是建立连接的节点数据副本和leader节点保持一致。

Zab协议中zxid对total order 特性至关重要。一个事务<v,z>中的z(zxid)由两部分构成，记为<e,c>。其中 e 为发出当前事务的leader节点的epoch, c 是自增整数计数器。当一个新的选举周期epoch产生时，一个新的leader节点被激活，c 从0开始递增，而 e 在原来epoch值的基础上递增。因此，事务的顺序由它们的zxid保证。对于两个zxid <e,c>和<e',c'>,如果 <e,c> < <e',c'>，则e < e' or (if e = e' and c < c')

对于一个peer节点，有四个重要的属性影响着它的节点状态，在各个执行阶段均有所作用。
history:最新log文件中接受的事务proposals
//todo
acceptedEpoch:最近一次接收到的NEWEPOCH消息的epoch值（也是最近一次的选举epoch值）
currentEpoch:最近一次接收到的NEWLEADER消息的epoch值（也是最近一次被推举的leader的epoch值）
lastZxid:history中最大的zxid值

Phase0：Leader election

这阶段peer节点进行初始化（会初始化上面四个属性），节点状态为electing。当集群获得一个quorum节点集合的一致投票时，leader节点就被选出了。每个peer节点会将这个选票保存到内存volatile变量中。如果leader选票节点是自己，增更新状态为leading，否则为following。

Phase1：Discovery

这阶段其他节点主动和leader节点建立连接，leader节点可以收集follower节点的最近事务信息。这个阶段的目的是在一个quorum中发现最新接收的proposal，并且确定新一轮的epoch，从而使之前的leader无法原子广播事务。

如果这期间的主从连接出现断掉，follower节点会重新回到Phase0阶段。

Phase2：Synchronization

同步阶段是使集群节点的副本数据状态统一更新为Phase1中leader节点的数据状态。leader节点首先将自己的history发送给各个节点，当leader接收到一个quorum的ack之后，leader会发送commit消息给各个节点。从而leader节点真正建立了。

Phase3：Broadcast

如果不发生崩溃，peers节点将永远待在这个状态，并开启对客户端的服务提供。由leader节点负责客户端的写入请求的原子广播。同时，leader节点也允许新的follower节点加入这个epoch中。

算法1，2，3是异步的并且没有考虑可能的节点崩溃情况。Zab协议通过主从节点周期性的心跳消息来检测节点的崩溃异常。如果leader节点没有在心跳时间内收到一个quorum集合的心跳，则放弃自己的lead权限并回到Phase0阶段。如果follower在在心跳时间内没有收到leader节点的心跳，也同样回到Phase0阶段重新选举。

Zab协议算法分析

从上面三个算法中，可以得出一些不变性：

在phase3阶段，一个从节点接收一个proposal <e,<v,z>>只有当它当前的currentEpoch=e才行。
在一个epoch=e的phase3阶段，只有从节点的currentEpoch=e才能根据zxid的顺序接收事务的proposal和commit。
在phase1阶段，从节点不会接收比自己的acceptEpoch小的任何周期的leader的proposal。
在phase1阶段，ACKEPOCH（F.currentEpoch,F.history,F.lastZxid）消息中F.history的事务不会改变，重排序或丢失。在phase2阶段，NEWLEADER（e',L.history）消息中,L.history的事务不会改变，重排序或丢失。
在phase3阶段，从节点提交的事务顺序就是当前leader节点广播并提交的事务顺序。
同样可得出一些声明：
在每个周期epoch e内，在phase3阶段只能🈶️一个进程调用ready(e)。
Zab协议满足我们上面提到的broadcast integrity, agreement, total order, local primary order, global primary order, and primary integrity特性。
Liveness property:如果位于Quorum中的主从节点均是正常通信状态，则leader节点发送的事务proposal和commit消息，位于Quorum中的从节点会及时收到并且作出对应的状态修改。

ZooKeeper中Zab协议的具体实现

首先需要明白ZooKeeper节点之间的FIFO顺序通信Zab协议的保证，本文大致基于ZooKeeper 3.3.4的版本进行分析。ZooKeeper对Zab协议的实现大体遵循上面的算法1，2，3，此外会有一些算法优化导致具体实现有所不同。
在ZooKeeper中，默认实现的选举算法是Fast Leader Election（FLE），其中Phase0和Phase1阶段是紧紧耦合在一起的。这个算法的优化在于：它尝试在集群选举中从quorum节点中选出拥有最新history的节点作为leader节点，这样在phase1阶段leader节点不需要和其他从节点通信来发现最新的history了。在FLE的实现中，Phase1阶段的部分功能可省略，我们将Phase1和Phase2阶段合并为Recovery Phase。对比zab协议的阶段划分，zookeeper中具体阶段实现为：

接下来我们将看下zookeeper中这些阶段的具体实现。

Recovery Phase

Recovery Phase更多的用来做phase2阶段的同步工作。
从节点连接leader节点，并发送FOLLOWERINFO(F.lastZxid)消息给leader节点，这样leader节点可以决定和从节点的同步方式。这里数据同步时和phase2阶段的不同是：如果从节点接收到了TRUNC消息，这里从节点可丢失掉比leader节点还大的事务，如果从节点接收到了DIFF消息，这里从节点可只接收leader节点上自己没有的事务消息。
这些特性是由history.lastCommitedZxid（history中最新提交的zxid）和history.oldThreshold(history中保存的最老的提交zxid)保证的。

同步的目的是使得所有节点上的副本数据和主节点保持一致。所以leader节点上已提交的事务必须按同样的顺序同步到所有其他节点，未提交的proposal（包括所有节点上比leader.history.lastCommitedZxid大的proposal）必须抛弃掉使得所有节点都不会提交。SNAP和DIFF消息保证提交不丢失，TRUNC消息保证未提交proposal被丢弃掉。

这里如果zookeeper并没有区分acceptedEpoch和currentEpoch，从节点会从history.lastCommitedZxid 中获得current epoch，如果F尝试连接的本地prospective leader L不是leading状态，则L会拒绝连接，F会执行22行。

Fast Leader Election

FLE算法是Recovery Phase的重要保证，它尝试保证leader节点拥有所有历史提交的事务，基于如果一个peer节点有最新的proposal（lastZxid）,那么它同样拥有最新的commit这样一个假设。
下面我们将看一下FLE的实现细节。选举过程中peer节点相互交换自己的选票，期间如果接收到更新的选票则更新自己的选票，最终从一个quorum节点中选出一个leader。选票结束时，每个peer节点会根据选票结果确定自己是leader还是follower。期间出现异常会导致peer节点回到electing状态并重新选举，新一轮FLE的开始会导致选举轮次自增。
其中如何确定谁的选票最大呢？假设有N个peer节点，peer节点 pi 的选票为用<zi,i>表示，其中 zi 代表 pi 上最新proposal的zxid（即lastZxid），i 代表节点的的server id（在集群中是唯一的，就是zookeeper中的myid）。如果<zi,i> > <zi',i'>则满足zi > zi' or (zi = zi' and i>i')。这样可保证当选举结束时，从节点自己的选票票值是小于主节点的。

在FLE选举过程中，是没有将变量状态持久化到磁盘的。这意味着FLE的选举轮次（也就是acceptedEpoch）是没有持久化的。其中有持久化的变量是lastZxid,没有持久化的变量有选票vote，选举状态state，当前选举轮次round，identification number（id）和接收选票的队列内容。对于zookeeper来说，发送给其他peer节点的选举投票消息是notification消息，包括(vote, id, state, round)这些信息。完整的算法伪代码为：

每个peer节点都知道所有的peer节点地址和总的peer节点数目SizeEnsemble。一开始peer节点会投票给自己，然后将notification发送给其他peer节点，等待其他peer节点的notifications。当接收到其他的peer节点的notifications时，会根据
它们的notification中的state来处理这些选票。如果收到的选票state是electing状态，位于相同轮次round的选票会进行选票大小比较，并将本节点选票更新为比自己大的选票。轮次round比自己的轮次小的选票会被忽略掉。如果选举轮次比自己大，说明本节点的选举轮次是落后的，应该清空当前收到的所有选票信息，并更新自己的选举轮次，再比较选票大小。如果收到的选票state是following或leading状态,同样会根据轮次判断怎么处理选票。如果是相同轮次的选票，则将当前轮次的选票放在一起，看是否能选出一个quorum,确定出leader，如果可以再确定自己的state状态并结束选举。如果是不同轮次的选票，将选票放在外部的选票集合中（因为此时可能处于当前节点崩溃，但集群仍正常可用的状态），并收集所有外部选票，如果能选出一个quorum,确定出leader，并确定自己的state状态结束选举。

算法中有几个需要注意的点：

DeduceLeader(id):从quorum中确定leader节点是谁时，需要根据leader节点信息确定出自己的state状态。
Put(Table(id), vote, round):收集来自其他peer节点的选票set集合，key为server id。
Notifications Receiver:会有一个专门的线程负责接收其他节点的Notifications，并依次放到fifo队列中并传递到FLE选举过程中。并且比较选票之后，发出自己的最新选票给其他peer节点。

ZooKeeper实现Zab协议中的问题

这里主要讨论两个问题。
1.节点在Recovery Phase和FLE之间循环
ZooKeeper 3.3.3版本没有区分acceptedEpoch和currentEpoch，会可能导致节点在Recovery Phase和FLE之间循环。当一个peer节点内部选票达成一致，并称为leader（称为proposal leader）时，运行到Algorithm4 的第4行,将自己的lastZxid发送给其他follower节点（注意Algorithm4 的第2行此时leader将epoch递增了，lastZxid也会更新epoch）。因为当follower节点的lastZxid.epoch大于leader节点的lastZxid.epoch时，将会重新回到electing状态（Algorithm4 的第25行）。当proposal leader节点出现异常并放弃自己的领导权限并且成为之前epoch选举出来的新leader的follower时，便会出现Algorithm4 的第25行的情况。此时这个原来的proposal leader节点便会在Recovery Phase和FLE之间循环。

产生这个问题的原因就是用peer节点用lastZxid来记录epoch值，并不能区分出来最新选举过程中的epoch和认定的最新leader的epoch，因此定义了acceptedEpoch和currentEpoch。这样在Algorithm4 的第25行便可通过proposal leader节点的新的epoch（在acceptedEpoch的基础上加1）和follower的acceptedEpoch做比较，前者一定大于后者，从而避免循环。

2.丢掉follower节点proposal事务
Algorithm4假设第11行当follower.lastZxid>L.history.lastCommittedZxid时，leader节点就发送TRUNC消息使follower节点丢掉L.history.lastCommittedZxid之后的proposal，但有时follower节点可能存在L.history.lastCommittedZxid之前的应丢弃的proposal。(参考issue ZOOKEEPER-1154)。下面将考虑导致这个问题的一种场景：

假设有三个peer节点p1,p2,p3，此时处于广播阶段，p1是leader节点且所有peer节点都处于正常工作状态。此时它们均同步一致并提交了zxid <e = 1,c = 3>事务，p1节点接收并创建了新的事务zxid <e = 1,c = 4>，但还没有将这个proposal发给p2,p3便挂掉了。p2,p3经过重新选举，p2成为新的leader节点，并且成功进入广播状态，提交事务到zxid <e = 2,c = 1>，并且p2.history.oldThreshold = <1,1>。此时p1节点重新处于正常工作状态,会成为p2的follower节点。在p1的Recovery阶段，p1会给p2发送FOLLOWERINFO(p1.lastZxid = <1, 4>)消息，因为 p2.history.oldThreshold (1,1) <1, 4> < p2.history.lastCommittedZxid (<2,1>)，按照Algorithm4此时p2会给p1发送DIFF请求进行差异同步。但是 <1, 4>只存在于p1节点上，应该被丢弃掉。

对于这种场景，p2可发送TRUNC消息使p1丢弃掉 <1, 4>，或者p2可发送SNAP消息使p1全量同步自己的数据。ZooKeeper采用的后一种方式来解决这个问题。