ZooKeeper 内部机制

• 简介
• 原子广播
  • 保证、属性与定义
  • Leader 激活
  • Active Messaging
  • Summary
  • 比较
• 一致性保证
• 法定人数(Quorums)
• 日志记录
  • 开发者指南
    • 选择合适的日志级别
    • 使用标准的slf4j惯用法

简介

本文档包含有关ZooKeeper内部工作原理的信息。它讨论了以下主题：

• 原子广播
• 一致性保证
• 法定人数(Quorums)
• 日志记录

原子广播

ZooKeeper的核心是一个保持所有服务器同步的原子消息系统。

保证、属性与定义

ZooKeeper所使用的消息传递系统提供的具体保证如下：

• 可靠交付 : 如果消息 m 被一个服务器交付，那么消息 m 最终会被所有服务器交付。

• 全序 : 如果一个服务器先投递消息a再投递消息b，那么所有服务器都会按照先a后b的顺序投递。

• 因果顺序 : 如果消息 b 是在消息 a 已被 b 的发送者传递之后发送的，则消息 a 必须排在 b 之前。如果发送者在发送 b 之后发送 c，则 c 必须排在 b 之后。

ZooKeeper消息系统还需要高效、可靠且易于实现和维护。我们大量使用消息传递，因此需要系统能够每秒处理数千个请求。尽管我们可以要求至少k+1台正常服务器来发送新消息，但必须能够从诸如断电等关联故障中恢复。在实现该系统时，我们时间紧迫且工程资源有限，因此需要一个工程师易于理解且容易实现的协议。我们发现我们的协议满足了所有这些目标。

我们的协议假设我们能够在服务器之间构建点对点的FIFO通道。虽然类似的服务通常假设消息传递可能会丢失或重新排序消息，但鉴于我们使用TCP进行通信，我们对FIFO通道的假设非常实用。具体来说，我们依赖于TCP的以下特性：

• 有序传递 : 数据按照发送顺序进行传递，消息m只有在所有先于m发送的消息都传递完成后才会被传递。（由此得出的推论是：如果消息m丢失，那么所有在m之后的消息都会丢失。）

• 关闭后无消息 : 一旦FIFO通道关闭，将无法再从该通道接收任何消息。

FLP理论证明，在异步分布式系统中如果存在故障可能，就无法达成共识。为了确保在出现故障时仍能达成共识，我们采用了超时机制。然而，我们依赖时间是为了活性而非正确性。因此，如果超时机制失效（例如时钟偏差），消息系统可能会挂起，但不会违反其保证。

在描述ZooKeeper消息协议时，我们将讨论数据包(packets)、提案(proposals)和消息(messages)：

• 数据包 : 通过FIFO通道发送的字节序列。

• 提案 : 一个协议单元。提案通过与ZooKeeper服务器集群交换数据包达成一致。大多数提案包含消息，但NEW_LEADER提案是不包含消息的提案示例。

• 消息 : 一组将被原子广播到所有ZooKeeper服务器的字节序列。消息在被投递前会被放入提案并获得一致同意。

如上所述，ZooKeeper保证了消息的全局顺序性，同时也保证了提案的全局顺序性。ZooKeeper通过ZooKeeper事务ID（zxid）来体现这种全局顺序。所有提案在被提出时都会被打上zxid标记，该标记精确反映了全局顺序。提案会被发送到所有ZooKeeper服务器，当获得法定数量服务器的确认后，提案就会被提交。如果提案包含消息，则在提案提交时该消息将被投递。确认意味着服务器已将提案记录到持久化存储中。我们的法定数量机制要求任何两个法定集合必须至少包含一个共同的服务器。我们通过要求所有法定集合的大小为（n/2+1）来确保这一点，其中n是组成ZooKeeper服务的服务器数量。

zxid由两部分组成：epoch(纪元)和计数器。在我们的实现中，zxid是一个64位数字。我们使用高32位存储epoch，低32位存储计数器。由于zxid由两部分组成，因此可以同时表示为数字和整数对(epoch, count)。epoch编号代表领导权的变更。每当新领导者上任时，都会拥有自己的epoch编号。我们采用一个简单算法为提案分配唯一zxid：领导者只需递增zxid即可为每个提案获取唯一标识。领导权激活机制将确保只有一个领导者使用特定epoch，因此我们的简单算法能保证每个提案都具有唯一ID。

ZooKeeper消息传递包含两个阶段:

• 领导者激活：在此阶段，领导者将建立系统的正确状态，并准备开始提出提案。

• 主动消息传递：在此阶段，领导者接收待提议的消息并协调消息传递。

ZooKeeper是一个整体性协议。我们并不关注单个提案，而是将提案流视为一个整体。严格的顺序性使我们能够高效实现这一点，并极大简化了协议。领导者激活机制体现了这一整体概念：只有当法定数量的追随者（领导者本身也计为追随者，你永远可以投票给自己）与领导者完成同步、达成相同状态时，该领导者才会被激活。这个状态包含领导者认为已提交的所有提案，以及追随领导者的提案——即NEW_LEADER提案。（此时你可能会想：领导者认为已提交的提案集合是否包含真正已提交的所有提案？答案是肯定的。下文将阐明原因。）

领导者激活

领导者激活包括领导者选举(FastLeaderElection)。ZooKeeper消息传递不关心选举领导者的具体方法，只要满足以下条件：

• 领导者已确认所有跟随者的最高zxid。
• 多数服务器已承诺跟随领导者。

在这两个要求中，只有第一个要求——即追随者中拥有最高zxid的节点必须满足——对正确运行至关重要。第二个要求，即多数追随者的法定人数，只需要以高概率满足即可。我们将重新检查第二个要求，因此如果在领导者选举期间或之后发生故障且法定人数丢失，我们将通过放弃领导者激活并重新进行选举来恢复。

在领导者选举之后，单个服务器将被指定为领导者并开始等待追随者连接。其余服务器将尝试连接到领导者。领导者将通过发送追随者缺失的任何提案来与追随者同步，或者如果追随者缺失过多提案，领导者将向追随者发送状态的完整快照。

存在一种边界情况：当一个拥有提案集合U（这些提案未被领导者看到）的追随者加入时。提案是按顺序被观察的，因此U中的提案将具有比领导者所见更高的zxid。该追随者必然是在领导者选举完成后加入的，否则鉴于它拥有更高的zxid，本应被选为领导者。由于已提交的提案必须被多数服务器所确认，而选举领导者的多数服务器并未见过U，因此U中的提案尚未被提交，可以安全丢弃。当该追随者连接到领导者时，领导者会指示其丢弃U。

新领导者通过获取它所见过的最高zxid的纪元e，并将下一个要使用的zxid设置为(e+1, 0)，来建立一个新的zxid以开始用于新提案。在领导者与跟随者同步后，它将提出一个NEW_LEADER提案。一旦NEW_LEADER提案被提交，领导者将激活并开始接收和发布提案。

这一切听起来很复杂，但以下是领导者激活期间的基本操作规则：

• 一个跟随者(follower)在与领导者(leader)同步后，会对NEW_LEADER提案进行ACK确认。
• 一个跟随者只会对来自单一服务器的特定zxid的NEW_LEADER提案进行ACK确认。
• 当法定数量的追随者确认了NEW_LEADER提案后，新的领导者将提交该提案。
• 当NEW_LEADER提案被提交(COMMIT)时，跟随者(follower)将提交从领导者(leader)接收到的任何状态。
• 新领导者只有在NEW_LEADER提案被提交(COMMITTED)后，才会接受新的提案。

如果领导者选举错误终止，我们不会出现问题，因为NEW_LEADER提案将不会被提交，因为领导者将无法获得法定人数。当这种情况发生时，领导者和任何剩余的跟随者将超时并返回领导者选举。

主动消息传递

Leader Activation（领导者激活）承担了所有繁重的工作。一旦领导者被加冕，就可以开始发送提案。只要他仍然是领导者，就不会有其他领导者出现，因为没有其他领导者能够获得法定数量的追随者。如果确实出现了新的领导者，则意味着原领导者已失去法定人数，新领导者将清理她在领导激活期间留下的任何混乱。

ZooKeeper的消息传递机制类似于经典的两阶段提交。

所有通信通道都遵循先进先出(FIFO)原则，因此所有操作都按顺序执行。具体遵循以下操作约束：

• 领导者按照相同的顺序向所有跟随者发送提案。此外，这个顺序遵循接收请求的顺序。因为我们使用FIFO通道，这意味着跟随者也会按顺序接收提案。
• Followers按照接收顺序处理消息。由于FIFO通道的特性，这意味着消息将按顺序被确认(ACK)，且领导者会按顺序收到来自followers的确认。同时也意味着如果消息m已被写入非易失性存储，那么在m之前被提出的所有消息也都已写入非易失性存储。
• 一旦大多数跟随者确认(ACK)了一条消息，领导者就会向所有跟随者发出COMMIT指令。由于消息是按顺序确认的，领导者也会按照跟随者接收的顺序发送COMMIT指令。
• COMMITs按顺序处理。当提案被提交时，跟随者会发送提案消息。

概述

这就是原因所在。为什么它能正常工作？具体来说，为什么新领导者所相信的提案集合总能包含所有实际已提交的提案？首先，所有提案都有唯一的zxid，因此与其他协议不同，我们永远不必担心同一个zxid会对应两个不同的提案值；追随者（领导者同时也是追随者）会按顺序查看并记录提案；提案是按顺序提交的；由于追随者同一时间只追随单个领导者，所以同一时间只会有一个活跃领导者；新领导者已经看到了前一个纪元所有已提交的提案，因为它已从法定数量的服务器中获取了最高zxid；新领导者观察到的前一个纪元中任何未提交的提案，都会在该领导者转为活跃状态前被提交。

比较

这不就是Multi-Paxos吗？不，Multi-Paxos需要某种方式来确保只有一个协调者。我们不依赖这种保证。相反，我们使用领导者激活机制来从领导者变更或旧领导者仍认为自己是活跃状态的情况中恢复。

这不就是Paxos吗？你们的主动消息阶段看起来就像Paxos的第二阶段？实际上，对我们而言主动消息机制更像是无需处理中止的两阶段提交。但主动消息与两者都不同，因为它具有跨提案排序要求。如果我们不严格保持所有数据包的先进先出顺序，整个机制就会崩溃。此外，我们的领导者激活阶段也与两者不同。特别是，我们使用epoch（纪元）机制的特性，可以跳过未提交提案的区块，并且不必担心针对特定zxid的重复提案问题。

一致性保证

ZooKeeper的一致性保证介于顺序一致性和线性一致性之间。在本节中，我们将详细说明ZooKeeper提供的具体一致性保证。

ZooKeeper中的写操作是线性化的。换句话说，每个write操作都会在客户端发出请求和收到相应响应之间的某个时间点以原子方式生效。这意味着ZooKeeper中所有客户端执行的写操作都可以按照这些写操作的实际时间顺序进行完全排序。然而，除非我们也讨论读操作，否则仅说明写操作是线性化的没有意义。

ZooKeeper中的读取操作不具备线性一致性，因为它们可能返回过时数据。这是因为ZooKeeper中的read操作不属于法定人数操作，服务器会立即响应执行read的客户端。ZooKeeper这样设计是为了在读取场景中优先考虑性能而非一致性。不过，ZooKeeper的读取操作具有顺序一致性，因为read操作会按照某种顺序生效，且该顺序会遵循每个客户端的操作顺序。常见的解决方案是在执行read前先发起sync操作。但这同样无法严格保证获取最新数据，因为sync目前不是法定人数操作。举例说明，假设两个服务器同时认为自己是领导者（当TCP连接超时时间小于syncLimit * tickTime时可能发生这种情况）。需要注意的是，这种情况在实践中不太可能发生，但在讨论严格的理论保证时仍需牢记。在此场景下，sync可能由持有过时数据的"领导者"提供服务，从而导致后续的read也可能获取过时数据。如果在read前执行实际的法定人数操作（如write），则能提供更强的线性一致性保证。

总体而言，ZooKeeper的一致性保证在形式上被精确地描述为有序顺序一致性或更准确地说OSC(U)，它介于顺序一致性和线性一致性之间。

法定人数

原子广播和领导者选举使用法定人数(quorum)的概念来保证系统视图的一致性。默认情况下，ZooKeeper采用多数决法定人数，这意味着在这些协议中进行的每次投票都需要获得多数票才能通过。例如确认领导者提案时：领导者只有在收到来自服务器法定数量的确认后，才能提交提案。

如果我们从使用多数派机制中提取真正需要的属性，可以发现我们只需要保证用于通过投票验证操作（例如确认领导者提案）的进程组在至少一个服务器上成对相交。使用多数派机制可以确保这一属性。然而，还存在其他不同于多数派机制构建法定人数的方法。例如，我们可以为服务器的投票分配权重，并规定某些服务器的投票更为重要。要获得法定人数，我们需要收集足够的投票，使得所有投票的权重之和大于所有权重总和的一半。

一种在广域部署（共址环境）中实用且采用权重的不同构建方式是分层结构。通过这种构建方式，我们将服务器划分为互不相交的组别，并为进程分配权重。要形成法定人数，我们必须从大多数组G中获取足够数量的服务器，使得对于G中的每个组g，来自g的投票总数大于g内权重总和的一半。有趣的是，这种构建方式可以实现更小的法定人数规模。例如，如果我们有9台服务器，将其分为3组，并为每台服务器分配权重1，那么我们就能形成规模为4的法定人数。需要注意的是，由多数组中多数服务器组成的两个进程子集必然存在非空交集。可以合理预期，在大多数共址场景下，服务器高可用性的概率较大。

通过ZooKeeper，我们为用户提供了配置服务器使用多数仲裁、权重或组层级结构的能力。

日志记录

Zookeeper使用slf4j作为日志记录的抽象层。自ZooKeeper 3.8.0版本起，选择Logback作为日志记录后端。为了提供更好的嵌入支持，未来计划将最终日志实现的选择权交给终端用户。因此，在代码中编写日志语句时请始终使用slf4j api，但在运行时配置logback来控制日志记录方式。请注意slf4j没有FATAL级别，原FATAL级别的消息已移至ERROR级别。有关为ZooKeeper配置logback的信息，请参阅ZooKeeper管理员指南中的日志记录章节。

开发者指南

在代码中创建日志语句时，请遵循slf4j手册。同时，在创建日志语句时请阅读性能常见问题解答。补丁审查人员将关注以下内容：

选择合适的日志级别

slf4j中有多个日志级别。

选择正确的选项非常重要。按照严重程度从高到低的顺序排列：

1. ERROR级别表示可能导致应用程序仍能继续运行的错误事件。
2. WARN级别表示可能存在潜在危害的情况。
3. INFO级别用于标识在粗粒度层面上突出显示应用程序进度的信息性消息。
4. DEBUG级别用于指定对调试应用程序最有用的细粒度信息事件。
5. TRACE级别比DEBUG级别提供更细粒度的信息事件。

ZooKeeper在生产环境中运行时，通常会将INFO级别及更高严重程度（更严重）的日志消息输出到日志中。

标准slf4j惯用法的使用

静态消息日志记录

LOG.debug("process completed successfully!");

然而，当需要创建参数化消息时，请使用格式化锚点。

LOG.debug("got {} messages in {} minutes",new Object[]{count,time});

命名

日志记录器应根据使用它们的类来命名。

public class Foo {
    private static final Logger LOG = LoggerFactory.getLogger(Foo.class);
    ....
    public Foo() {
        LOG.info("constructing Foo");

异常处理

try {
    // code
} catch (XYZException e) {
    // do this
    LOG.error("Something bad happened", e);
    // don't do this (generally)
    // LOG.error(e);
    // why? because "don't do" case hides the stack trace

    // continue process here as you need... recover or (re)throw
}