ZooKeeper 的原子广播(ZAB 协议)

ZooKeeper 作为高可用的一致性协调框架,自然有着一致性算法的实现,ZooKeeper 使用的是 ZAB 协议作为数据一致性的算法,即 ZAB(ZooKeeper Atomic Broadcast )。ZAB 在 Paxos 算法上做了重要改造,和 Paxos 有着明显的不同。为讨论 ZAB,我们假定 ZooKeeper 已经开启仲裁模式(ZooKeeper 还有一种独立模式,除实验需求以外不要开,因为它无法避免脑裂)。

ZooKeeper使用的消息系统提供了以下特殊保证:
  • 可靠传输:如果消息 m 被一台服务器送达,它最终会被送达到所有服务器
  • 全序:如果一台服务器上消息 a 在消息 b 前送达,那么在所有服务器上 a 将比 b 先送达。如果 a 和 b 是已传输过的消息,那么要么 a 在 b 前送达,要么 b 在 a 前送达(即不可能有同时发生的情况)
  • 因果序:如果一个发送者在消息 a 送达后再发送消息 b,那么 a 必须排在 b 之前。如果发送者在送达 b 后再发送消息 c,那么 c 必须排在 b 之后

    ZooKeeper 的消息系统还需要是高效、可靠、容易实现和维护的。因为大量使用了消息,消息系统还必须满足每秒处理数千个请求的要求。开发者提出的协议假定可以在服务器间建立点对点的 FIFO 通道。使用 TCP 协议可以非常简单地实现这一假定,因为 TCP 具有以下属性:

  • 有序传输:数据发出和数据送达的顺序严格一致,即消息 m 被送达当且仅当 m 前发送的所有消息都已被送达。(推论:如果 m 丢失,m 后的所有消息必须丢弃)

  • 关闭后没有消息:一旦 FIFO 通道关闭,不会再从它收到消息。

    FLP 定理(以三个作者名字的首字母命名,nosql 一文中讲过)已经证明了在异步的分布式系统中如果容忍错误则不可能达到一致性。为了在允许错误的条件下达到一致性 ZooKeeper 的开发者使用了超时时间。如果超时计时器出了问题则整个消息系统可能 hang 住,但不会违背一致性保证。

    ZooKeeper 消息协议中有以下元素:

  • 包:通过 FIFO 通道传送的 byte 序列

  • 提案:一种共同协议。协议需要法定人数的 ZooKeeper 服务器来通过。大部分提案可以包含消息,但是像 NEW_LEADER 这样的提案是不包含消息的
  • 消息:原子地广播到所有 ZooKeeper 服务器的 byte 序列

    前面提到,ZooKeeper 保证消息的全序,同时它也保证提案的全序。ZooKeeper 使用一种 ZooKeeper 事务 id(zxid)来暴露整体顺序。所有提案在提出时均会被打上一个 zxid 标记,它代表了提案的整体顺序。zxid 由两部分组成:周期(epoch)和计数器(counter)。在当前的实现中 zxid 是一个 64 位整数,高 32 位为 epoch,低 32 位为 counter,因此 zxid 也可以记为一个整数对(epoch, count)。epoch 的值代表 leader 的改变,每当选举产生一个新的 leader 就会生成一个它独有的 epoch 编号。ZooKeeper 使用了一种简单的算法将一个唯一的 zxid 赋给提案:leader 对每个提案只是简单地递增 zxid 以得到一个唯一的 zxid 值。Leader 激活算法会保证只有一个 leader 使用一个特定的 epoch,因此这个简单的算法可以保证每个提案都有一个唯一的 id。

    提案被发送到所有的 ZooKeeper 服务器,在它们中的法定人数认可该提案后其被提交。如果该提案还包含一个消息,那么在提案被提交时消息被送达。“认可”意味着服务器已将提案保存到持久化存储上。“法定人数”代表一组服务器,必须满足任意两个法定人数对之间至少有一个共同的服务器。因此典型情况下,任意一个法定人数至少有(n/2+1)台服务器即可满足要求,这里 n 是 ZooKeeper 服务中的总服务器数。

    ZooKeeper 消息协议包含两个阶段:

  • Leader 激活:在这个阶段,leader 建立起正确的状态并准备发起提案

  • 消息激活:在这个阶段,leader 接受消息以发起或协调消息传输

    ZooKeeper 消息协议是一种整体协议。它不针对个别提案,而是将提案的流看作一个整体。严格的全序允许我们有效地实现并大大简化了协议。Leader 激活中包含了这种整体性的概念,一个 leader 被激活当且仅当 followers 中的法定人数(leader 自身也算作一个 follower)与该 leader 达成同步,即它们有相同的状态。这个状态包含 leader 认为所有已提交的提案,以及让 followers 跟随本 leader 的提案(NEW_LEADER 提案)。

Leader 激活

Leader激活阶段包含了leader选举。在我们当前使用的版本(3.5)中有两种leader选举算法:LeaderElection和FastLeaderElection(AuthFastLeaderElection是FastLeaderElection的变种,使用了UDP和简单的认证机制)。ZooKeeper消息机制不关心具体的leader选举方法,只需要能确保以下两点:
  • leader 已经获知所有 followers 的最大的 zxid
  • 一个服务器间的法定人数已经确认会跟随 leader

    这两点需求中,只有第一点需要永久保证,因为它是一切正确操作的基础。第二点,即服务器间形成法定人数,只需要大概率下保证即可。ZooKeeper 代码会经常检验第二点需求,如果在 leader 选举期间或之后发生故障导致不足法定人数,会通过终止此次 leader 激活来恢复状态,然后再次选举。

    Leader 选举完成后一台服务器会被指定为 leader 并等待 followers 的连接,其他服务器尝试连接到 leader。Leader 将和 followers 同步,通过发送 followers 缺失的提案(DIFF),但如果 followers 缺失太多提案,将发送一个完整的快照(SNAP)。

    一种特殊情况是,一个 follower 有一个未被 leader 获知的提案 U。根据因果序可知,提案是按顺序被获知的,因此提案 U 必有一个比 leader 已知的 zxid 更大的 zxid。可证明该 follower 一定是 leader 选举后才出现的,否则,因其获知了一个更大的 zxid,该 follower 才应该被选举为 leader,矛盾。因为已提交的提案必须被法定人数的服务器一致获知,而选出 leader 的法定人数并未获知提案 U,所以提案 U 必然还未提交,因此它可被丢弃。于是当该 follower 连接到 leader 时,leader 会通知该 follower 丢弃提案 U(TRUNC)。

    新 leader 通过获知的最大 zxid 来确定新的 zxid,如前最大 zxid 的 epoch 位是 e,则 leader 使用(e+1, 0)作为新的 zxid。在 leader 和 follower 同步后,leader 会发出一个 NEWLEADER 提案。一旦 NEWLEADER 提案被提交,leader 就算完全激活并开始收发其他提案。

    总之,在 leader 激活阶段有以下规则:

  • follower 在和 leader 同步后将 ACK NEW_LEADER 提案

  • follower 只能 ACK 一个有特定 zxid 的 NEW_LEADER 提案
  • 当一个法定人数的 followers 全部 ACK 该提案后,leader 将 COMMIT 该 NEW_LEADER 提案
  • 当 NEW_LEADER 提案 COMMIT 后,follower 会 COMMIT 所有从 leader 收到的状态
  • 新的 leader 在 NEW_LEADER 提案被 COMMIT 前不会接收任何新的提案
  • 如果 leader 选举非正常结束,NEW_LEADER 提案不会被 COMMIT,因为此时该 leader 相应的法定人数还未形成,因此不会导致问题

消息激活

完成leader激活后,该leader就可以开始收发提案了。在它仍然是leader的时期,其他leader是无法加入的,因为它达不到必须的followers法定人数个数。如果当前leader失去了必须的法定人数,新leader才会加入,此时它会在leader激活阶段清理不该被接受的提案。

ZooKeeper消息系统很像经典的两阶段提交,以下是官网的图:

因为图中所有信道都是FIFO的,所以一切都是有序的。本阶段有以下规则或限制:
  • leader 以相同的顺序向所有 followers 发送提案,且这一顺序和收到请求的顺序保持一致。因为使用了 FIFO 通道,于是保证 followers 也按此顺序收到提案。
  • followers 以收到提案的顺序处理消息。这意味着消息将被有序地 ACK 且 leader 按此顺序收到 ACK,仍然是由 FIFO 通道保证。这也意味着如果某提案上的消息 m 被写到非易失性存储(硬盘)上,所有在 m 前提出的提案上的消息也已被写到非易失性存储上。
  • 当法定人数的 followers 全部 ACK 某消息后,leader 会发出一个 COMMIT 提案。因为所有消息是按序 ACK 的,leader 发出 COMMIT 且 followers 收到该提案也是按序的。
  • COMMIT 按序被处理。提案被提交后意味着 followers 可以分发提案上的消息了(发送给客户端)。

与 Paxos 对比

ZAB是Multi Paxos吗?否,因为Multi Paxos要求以某种方式保证只有一个协调者。而ZAB不需要依赖于这样的保证,借助leader激活阶段,leader变化或旧leader仍然有效的情况都能很好处理。

ZAB是Paxos(Basic Paxos)吗?消息激活阶段是Paxos的第二阶段吗?否,实际上消息激活和两阶段提交很像,但不需要处理取消操作。消息激活本质上和两者的区别是,它需要保证在所有提案间有序。如果不能保证所有包之间严格的FIFO顺序,那就不是ZAB了(Paxos或两阶段提交都不需要)。另外leader激活阶段也和两者有区别,比如epoch的使用使得我们可以跳过未提交的提案,且不必担心某zxid的提案被提交两次。

法定人数

最后澄清一下不那么“典型”的法定人数情况。原子广播和leader选举都使用了法定人数的概念以保证系统的一致性。比如在leader选举提案中:当收到法定人数的服务器的认可后,leader能且仅能提交一次该提案。

最简单的法定人数是相对多数,即前面给出的(n/2 +1)。前面提到过法定人数的一个重要属性是,如果一个法定人数解散,另一个法定人数形成,两次之间至少要有一台服务器交集,相对多数显然符合这一要求。

但除了相对多数外,也有其他的构成法定人数的方法。比如可以对每台服务器分配一个投票的权重,代表某些服务器在投票时更重要。为达成一个法定人数,只需要加权的总票数大于所有服务器加权票数和的1/2即可。

另一种方法是分层法,这种方法也使用权重,并且很适合多地部署的ZooKeeper集群。使用这种方法时,我们将服务器分组成不相交的集合,并设定每台的权重,只要多数的组中的服务器加权投票形成多数,即可构成法定人数。例如有三个组,每个组中有三台服务器,每台的权重都设为1,我们只需要至少有两个组中的加权投票数达到2即可,于是最少只需要4台服务器来构成法定人数。如果有G个组,构成法定人数需要G’个组,满足G’>G/2,且对这G’个组中每组的服务器集合g,需要有一个集合g’,满足g’中所有机器的加权和W’大于g中所有机器的加权和W的一半,即W’>W/2。