这篇博文是关于Zookeeper官网上zookeeperInternals的翻译（http://zookeeper.apache.org/doc/trunk/zookeeperInternals.html），讲述了Zookeeper的内部机制。由于博主的水平有限，如有错误和疏漏之处，恳请读者不吝指正。

名词解释

Quorum: 在同一应用中服务器的一组复制（A replicated group of servers in the same application）（这个是在官网上找到的解释，可能这个解释太泛了，我更倾向于加上约束条件，也就是在同一应用中服务器的满足一定条件的一组复制。如Majority Quorum表示超过半数的同一应用中服务器的一组复制)

Epoch: ZooKeeper事务ID（zxid）的高32-bit， Leadership激活将确保每个Leader使用不同的Epoch。（这个单词很贴切，当新的Leader被激活，代表开启了新的纪元，所以epoch加1）

Counter: Zookeeper事务ID（zxid）的低32-bit。

介绍

这个文档包含了Zookeeper内部机制的信息。 在此，将讨论下列主题。

• 原子广播（Atomic Broadcast）

• 日志（Logging）

原子广播

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

保证（Guarantees），特性（Properties）和定义（Definitions）

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

可靠交付

如果消息m被一个服务器交付，那么它最终会被所有的服务器交付

全序

如果消息a在消息b之前被一个Server交付，那么消息a将在消息b之前被所有的Server交付。如果a和b是被交付的消息，要么a在b之前交付，要么b在a之前交付。

因果顺序 （Causal order）

如果消息b的发送者在交付了消息a 之后才发送消息b, 那么消息b必然是排在消息a之后。如果一个发送者在发送了消息b之后，才发送消息c, 那么消息c是排到消息b之后。

ZooKeeper消息传递系统需要是高效，稳定以及简单实现和维护。我们大量地使用了消息传递，所以我们需要这个系统能够处理上千级别的rps. 虽然我们能够要求至少k+1个正确服务器来发送新消息，但我们必须能够从如电力中断等相关故障中恢复过来。当我们实现这个系统时，我们只有很少的时间和工程师资源，所以我们需要一个对于工程师易于理解和实现的协议。我们发现我们的协议满足所有的这些目标。我们的协议假设我们能够在服务器之间构建点对点的FIFO通道。当然类似的服务通常假设消息交付会丢失或者消息顺序是会打乱的，但是我们通过TCP通信协议来实现FIFO通道是非常实用的。特别地，我们依赖TCP的下列特性：

有序交付（Ordered delivery）

数据按照它被发送的顺序交付，并且消息m只有在之前发送的消息交付之后才能交付。（对此的一个推论是如果消息m丢失，那么所有在它之后的消息也将会丢失)

关闭后没有消息传递（No message after close）

一旦FIFO通道被关闭，没有消息能够通过它来接收。

FLP已经证实了在可能出现故障的情况下，一致性是不能在异步分布式系统中达成的。为了确保在故障可能出现的情况下达到一致性，我们使用了超时机制。然而，我们依赖时间来解决存活问题，而不是正确性问题。所以，如果超时机制停止工作（例如时钟故障），那么这个消息传递系统可能就会中止，但它不会违反它的保证。

当描述ZooKeeper消息传递协议，我们将讨论数据包，提案和消息：

数据包（Packet）

通过FIFO通道发送的字节序列

提案（Proposal）

一个协定的单元。在ZooKeeper服务器的Quorum之间交换数据包来商定提案。大部分提案包含消息，然而NEW_LEADER提案是不关联消息的例子。

消息（Message）

字节序列被原子广播到所有的ZooKeeper服务器。消息被放入提案中，并在它交付前被商定。

如上所述，ZooKeeper保证了消息的全序性，并且它也保证提案的全序性。ZooKeeper通过ZooKeeper事务ID(zxid)来公布全序。所有的提案在它被提议时将会被打上zxid，并且准确地反映全序。提案将会发送到所有的ZooKeeper服务器。当有一个Quorum确认这个提案，它将会被提交。如果提案中包含一个消息，当这个提案提交时，这个消息也将会被交付。确认意味着这个服务器已经将这个提案记录到持久存储中。我们的Quorum有这样的要求：任何两个Quorum必须具有至少一个共同的server。我们通过要求所有的Quorum具有(n/2+1)的大小来保证这一点。这里的n是组成ZooKeeper服务的服务器数量。

zxid由两部分组成：Epoch和Counter。 在我们实现中，zxid是一个64-bit数字。我们使用高32-bits表示epoch, 和低32-bits表示counter。 因为zxid由两部分组成，所以可以将zxid表示成一个数字，也可以表示成一对整形数（epoch, count)。 Epoch数字表示leadership的改变。每次一个新的leader上台执政，它将有自己的epoch数字。我们使用一个简单的算法来分配一个唯一的zxid给一个proposal：Leader简单地增加zxid来为每一个proposal获得一个唯一的zxid。Leadership激活将确保只有一个leader使用一个给定的Epoch, 所以我们的这个简单算法能够保证了每一个提案将有一个唯一的id。

ZooKeeper消息传递包含两个阶段

Leader激活（Leader activation）

在这个阶段一个Leader建立系统的正确的状态，并准备开始做出提案。

活动消息传递（Active messaging）

在这个阶段，一个Leader接收消息的提议并协调消息的交付。

ZooKeeper是一个整体的协议。我们不会聚焦于单个提案，而是将提案流看成一个整体。o我们严格的排序允许我们可以高效地实现这个整体协议，并极大地简化了我们的协议。Leadership activation体现了这个整体的概念。一个leader成为active，只有当一个跟随者Quorum已经和这个leader同步（leader也可以算为跟随者，你总是可以投票给自己），他们有相同的状态。这个状态由Leader相信的所有已经提交的提案，跟Leader的提案，和NEW_LEADER提案组成。（希望你思考这个问题，leader相信已经提交的提案是否包含了所有真的已经提交的提案？答案是肯定的。下面，我们会搞清楚为什么。）

Leader激活（Leader Activation）

Leader activation包含了Leader选举。目前在ZooKeeper中有两个Leader选举算法：LeaderElection和FastLeaderElection(AuthFastLeaderElection是FastLeaderElection的一个变种，使用UDP协议，并且允许服务器执行一个简单认证来避免IP欺骗）。ZooKeeper消息传递并不关心具体的Leader选举方法，只要满足下列要求就可以：

• Leader已经看到所有跟随者的最高zxid。

• 已经有一个服务器Quorum提交来跟随这个leader。

在这两个要求中只有第一个，在跟随者中的最高zxid需要总是被保持（必须的）来保证系统正确运行。第二个要求，跟随者的Quorum仅需要保持高概率就可以。我们将重复检查第二个要求，所以如果事故在leader选举的时候或者之后发生，并且Quorum丢失，我们将通过放弃当前的Leader激活，并执行另一个选举。

在Leader选举之后，单一的server将被指定为Leader，并且开始等待跟随者们来连接。剩余的服务器将尝试连接到Leader。Leader将发送跟随者错过的所有提案来进行同步。或者如果一个跟随者错过了太多的提案，leader将会发送整个状态快照给这个跟随者。

这里有一个极端情况。一个跟随者有一个还没有被leader看到提案集合U到达。提案被按序被看到，所以提案集合U会有一个zxid比leader看到的zxid都高。这个跟随者必须在Leader选举之后才到达，否则这个跟随者将被选为leader, 因为它已经看到一个更高的zxid。因为已经提交的提案必须被服务器Quorum看到，而且选择Leader的服务器Quorum没有看到U。这些提案没有被提交，所以他们会被抛弃。当这个跟随者连接上Leader, Leader会告诉这个跟随者丢弃U。

新leader在新协议中开始使用的第一个zxid设为(e+1,0)，其中e是从leader看到的最高zxid中获得epoch值。在Leader和跟随者同步之后，它会提出一个NEW_LEADER协议。一旦这个NEW_LEADER协议被提交，这个leader将会激活并且开始接收和发起提案。

这个听起来比较复杂，但是leader激活过程可以下列基本的操作规则完成：

• 跟随者会在和leader同步之后应答NEW_LEADER协议

• 跟随者只会应答从单一server来的带有给定zxid的NEW_LEADER提案

• 当跟随者Quorum已经应答了这个NEW_LEADER提案，新leader将会提交这个提案

• 当NEW_LEADER提案已经提交，跟随者将会提交它从Leader那接收的任何状态

• 新Leader将不会接收新的提案直到NEW_LEADER提案被提交

如果Leader选举错误地终止，我们不会有问题，因为NEW_LEADER提案将不会提交。这是因为leader不会有法定人数。当这个发生，leader和任何剩余的跟随者将会超时，并回退到Leader选举。

活动消息传递（Active Messaging)

Leader激活完成了所有重担。一旦Leader被加冕，他会开始广发提案。只要他是Leader, 没有其它的Leader能够出现因为其他Leader不能获得跟随者的Quorum。如果一个新Lead确实出现了，这就意味着之前的Leader丢失了Quorum，并且这个新Leader将会在它的leadership激活过程中清理任何遗留下的混乱。

ZooKeeper消息传递操作类似一个经典的二阶段提交。

所有的通信通道都是 FIFO，所以每件事都是按序完成。特别地，下列操作约束会被遵守。

• Leader使用相同的顺序向所有的跟随者发送提案。而且，这个顺序和请求被接收的顺序一致。因为我们使用FIFO通道，这意味着跟随者也有序地接收提案。

• 跟随者们按照消息接收的顺序来处理消息。这意味着消息将被按序应答，并且因为FIFO通道，leader从跟随者们那按序接收应答信息。这也意味着如果消息m被写入持久性存储器，所有在消息m之前提议的消息已经写入到持久性存储器。

• 只要跟随者的Quorum已经应答了一个消息，Leader将会发起提交消息（COMMIT）给所有的跟随者。因为消息被按序应答，所以提交消息将会被Leader将会和跟随者接收顺序一样的发送COMMIT消息。

• 提交信息(COMMIT)被按序处理。当一个提案被提交，跟随者交付提案消息。

总结

到此已经讲完了，为什么它可以工作？特别地，为什么新Leader相信的提案集合中包含了所有已经提交的提案？首先，所有的提案有唯一的zxid，所以不像其他协议，我们不必担心两个具有相同的zxid的值被提出；跟随者们（一个Leader也是一个跟随者）按序看到和记录提案；提案是按序提交；一次只会有一个活动的Leader，因为跟随者一次只跟随一个单一的Leader; 一个新Leader已经从先前的epoch看到所有被提交的提案, 因为它已经从服务器Quorum中看到最高的zxid；在新Leader成为active之前，将会提交它所看到的任何未提交的之前epoch提案。

比较

难道这个不只是Multi-Paxos吗?不是，Multi-Paxos需要一些方法来确定仅有单一的协作者。我们不能依靠这些保证。然而我们使用Leader激活来从Leadership改变或者仍然相信自己是active的旧Leader中恢复过来。

难道这个不仅仅是Paxos吗?你的活动消息传递(Active Messaging)阶段看起来就像是Paxos的阶段2? 事实上，对于我们活动消息传递，看起来像不需要处理终止(abort)的2阶段提交。活动消息传递和这两个都不同了，就某种意义上它是实现跨提案顺序需求。如果我们没有保持所有数据包的严格FIFO顺序，它就崩溃了。并且，我们的Leader激活(Leader activation)阶段和它们两个都是不同。特别地，我们epoch的使用允许我们跳过因未提交提案而导致的阻塞，并且不需要担心一个给定zxid的重复提案。

Quorums

原子广播和Leader选举使用Quorum概念来保证系统的一致性视图。ZooKeeper使用多数派（Majority) Quorum，这意味着每一个投票在这些协议中发生需要一个多数派表决。例如确认一个Leader的提案；Leader只能在从服务器Quorum接收到确认才能提交。

如果我们从多数派使用中提取我们真正需要的特性，我们仅需要保证，当进程组投票验证一个操作时，它们两两至少相交于一个服务器。使用多数派可以保证这一个特性。然而，有其他不同于多数派的构建Quorum的方法。例如，我们可以赋予权重给服务器投票，以及说明这些服务器的投票更加重要。为了获得一个Quorum，我们需要获得足够的投票，这样所有投票的权重和就超过所有权重总体和的一半。

层次结构是不同于上述的一种结构。它使用权重并在广域部署很有用的。使用这种结构，我们把服务器分割成不相交的组，并给进程赋予权重。为了形成一个Quorum，我们不得不从组的多数派G中获得足够的服务器支持，这样对于在G中每个组g，从g中投票权重和超过在g中权重总和的半数。有趣的是这个结构可以出现更小的Quorum。例如我们有9个服务器，我们将它们分成3组，并且给每个服务器赋予权重1，然后我们就可以形成大小为4的Quorum。注意在每一个组的多数派中，如果两个进程子集分别构成服务器多数派，那么它们必定会有一个非空交集。期待协同定位（co-location)的多数派会有一个高可用的服务器多数派是合理的。

使用ZooKeeper, 可以通过配置服务器来使用多数派Quorum，权重或者组的层次结构。

日志（Logging）

ZooKeeper使用slf4j作为日志的抽象层。log4j版本1.2目前被选为日志最终实现。为了更好的嵌入支持，计划在将来将选择最终日志实现的决定留给最终用户。因此，我们总是在代码中使用slf4j api来写日志语句，但是目前在运行时配置的是Log4j来记录日志。注意slf4j没有FATAL级别，之前在FATAL级别的消息已经被移到ERROR级别。关于为ZooKeeper配置log4j信息，请看ZooKeeper Administrator‘s Guide的日志章节。

开发者指南

请在代码中写日志语句时遵循slf4j手册。在创建日志语句时，也需要阅读FAQ on performance 。补丁审核人将按照下列要求评判。

使用正确的级别记录日志

在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});    

命名（Naming)

Loggers should be named after the class in which they are used.

日志记录器的命名应该按照使用它们的类进行命名。

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
}

Zookeeper内幕