ZooKeeper: 互联网系统无等待协调服务

本文描述分布式应用的协调服务：ZooKeeper。ZooKeeper 是关键基础设施的一部分，其目标是给客户端提供简洁高性能内核用于构建复杂协调原语。在一个多副本、中心化服务中，结合了组播消息、共享寄存器和分布式锁等内容。ZooKeeper 提供的接口有与带有事件驱动的分布式系统缓存失效类似的无等待共享寄存器，还提供了强大的协调服务。

ZooKeeper 接口具有高性能服务实现。除了无等待特性，还提供了对于客户端请求消息先进先出(FIFO)执行顺序保证，以及改变 ZooKeeper 状态的所有请求的线性化保证。这些设计决策支持实现一个满足由本地服务器处理读请求的高性能处理管道。我们给出了在2:1到100:1的读/写比率下，ZooKeeper 每秒可以处理数万到数十万个事务。这样的性能使得ZooKeeper 可以被客户端应用程序广泛地使用。

大规模分布式应用需要不同形式的协调程序，配置是一种协调的最基本的形式。其最简单的形式，对于系统进程，配置由一个操作参数列表构成，当然对于更加复杂的系统还会有动态配置参数。群组成员关系和领导者选举也很常见：通常，需要知道哪些进程是否正常，哪些进程负责管理。对于实现互斥访问临界资源，锁是一个强大的协调原语。

协调的一种方式是对于不同的协调需求开发不同服务。例如，亚马逊简单队列服务仅用于实现队列，开发其它服务实现领导者选举和配置。实现了较强原语的服务可以用来实现较弱原语服务。例如，Chubby 是保证强一致性的锁服务，锁服务可以被用来实现领导者选举、群组成员关系等。

设计协调服务时，从服务器端移除了与特定原语相关的部分，取而代之的是提供 API 给应用开发人员实现自己的原语。这一选择导致必须要实现一个 协调内核，可以不用改变服务核心就能实现自己的原语。这种方式可以根据应用的需求实现多种协调，而不是给开发者固定的几种原语。

设计 ZooKeeper API，移除了阻塞原语，例如锁。阻塞原语对于一个协调服务会引起其它问题，速度较慢或者故障的客户端会对速度较快的客户端产生负面的影响。如果处理的请求依赖于其它客户端的应答消息和故障探测，服务本身实现会更加复杂。ZooKeeper 实现了操作类似于文件系统的简单无等待数据对象的 API。实际上，ZooKeeper API 与文件系统非常类似，ZooKeeper API 与除去 lock、open、 close 的 Chubby 很像。实现无等待数据对象将 ZooKeeper 与那些实现了基于阻塞原语（如锁）的系统区分开来。

虽然无等待属性对性能和容错非常重要，但对于协调并不够。ZooKeeper 对于操作还提供了顺序保证。特别地，我们发现保证所有操作 先进先出的顺序 和 线性化写 能够使得服务的实现更加高效，并且对于实现应用的协调原语也是足够的。实际上，对于使用我们提供的 API 的任意数量的进程，都可以实现共识，根据 Herlihy 给出的层次结构，ZooKeeper 实现了全局对象。

Zookeeper 服务包含几个副本组成的服务来实现高可用性和高性能。高性能使得包含大量进程的应用也可以使用这样的内核来管理所有的协调。可以使用单管道架构实现 ZooKeeper，这种架构对于成百上千的请求仍然可以保证低延迟。这样的管道自然也可以保证单个客户端所有操作执行的顺序性。FIFO 客户端顺序使得客户端可以异步提交操作请求。使用异步操作，客户端可以同时处理多个操作。这个特性是很有用，比如，当一个客户端成为了领导者，必须要操作元数据，根据需要对其进行更新。没有处理多个操作的能力，初始化时间可能是亚秒的数量级。

为了保证更新操作满足线性化，实现了基于领导者的原子广播协议 Zab。ZooKeeper 应用的主要负载是读操作，所以需要保证读吞吐量的可扩展。在 ZooKeeper 中，服务器在本地处理读操作，并不需要使用 Zab。

在客户端缓存数据是提高读性能重要技术，例如一个进程可以缓存当前领导者的 ID，而不是每次都探测领导者。ZooKeeper 使用 watch 机制使得客户端不需要直接管理客户端缓存。使用这一机制，对于一个给定的数据对象，客户端可以监视到更新，当有更新的时候收到通知消息。Chubby 直接操作客户端缓存，会阻塞更新直到所有的客户端缓存都被改变。如果任何客户端速度较慢或者故障，更新都会延迟。Chubby 使用租约防止客户端无限阻塞系统。租约仅仅可以约束影响，ZooKeeper watches 避免了这样的问题。

本文讨论 ZooKeeper 的设计和实现，使用 ZooKeeper，可以实现应用所需的所有协调原语，只有写是线型化的。为了验证这一思路，我们展示如何使用 ZooKeeper 如何实现一些协调原语。

总的来说，本文主要贡献如下： - 协调内核：我们提出了一种可用于分布式系统的无等待的、具有宽松的一致性保证的协调服务。描述了 协调内核 的设计和实现，并且在很多应用中使用其实现了各种协调技术。 - 协调示例：展示如何使用 ZooKeeper 构建高级协调原语，阻塞和强一致性原语都是分布式系统经常使用的。 - 协调相关的经验：分享一些使用 ZooKeeper 的思路，评测其性能。

2 ZooKeeper 服务

客户端使用 API 向 ZooKeeper 提交请求。除了提供客户端 API，客户端库还提供了客户端与 ZooKeeper 服务器的网络连接。

在这一节，先看一下 ZooKeeper 的高级视图，然后讨论与 ZooKeeper 交互的 API。

术语. 在本文中，使用 客户端 表示 ZooKeeper 服务的用户。服务器 表示提供服务的进程。znode 表示 ZooKeeper 数据的内存数据节点，znode 以层次命名空间的方式组织起来称之为 数据树。使用更新和写表示任意修改数据树状态的操作。当客户端连接到ZooKeeper 时，会建立一个 会话，然后通过会话句柄来提交请求。

2.1 服务概述

Zookeeper 给客户端提供了数据节点集（znodes）抽象表示，数据节点集以层次化命名空间的形式组织。znodes 是 Zookeeper 层次化结构中提供给客户端通过 API 操作的数据对象。层次化命名空间通常在文件系统中使用。因为用户经常会使用这一抽象，并且应用程序元数据也以这种方式更好组织起来，所以这是一种组织数据对象非常理想的方式。对于 znode，使用标准 UNIX 文件系统路径记号。例如，使用 /A/B/C 给出 znode C 的路径，C 的父节点是 B，B 的父节点是 A。所有 znodes 都存储数据，除了临时 znode，所有 znode 都可以有孩子节点。

客户端可以创建两种类型 znode：

普通：客户端通过创建和删除显式地操作普通节点。

临时：客户端创建这类节点，显式地删除或者系统在会话结束（主动结束或者因为故障结束）时自动删除。

创建新的 znode 节点时，也可以指定 sequential 标识，创建带有序号标识的节点会每次在创建一个节点时将单调递增计数器的值添加到名称后。如果 n 是新节点，p 是父节点，n 的序号值不会比在p 下创建的任何序号节点的序号值小。

ZooKeeper 实现了 watches，其使得客户端无需轮询就能够及时接受到状态变化的通知信息。当客户端发送了带有 watch 标识的读请求时，操作会正常完成，但服务器会在数据发生变化时通知客户端。与一个会话关联的 watches 只会触发一次；一旦触发或者会话结束，就会被注销。比如，在 /foo 变更两次之前，客户端发送了 getData("/foo", true)，但客户端只会接受到一次 /foo 变化的通知信息。会话事件，例如连接断开也会被发送给 watch 回调，这样客户端就能知道 watch 事件可能会被延迟。

数据模型。ZooKeeper 使用简化 API 提供了基本的文件系统，只能一次读取或写入所有数据，或者带有层次的键值表。层次命名空间对不同应用的命名空间分配子树很有用、并且对子树设置访问权限也比较方便。在客户端可以利用目录结构构建高级原语，如2.4所示。

与文件系统不一样的是，设计 znode 不是用来保存通用数据，znode 用来映射客户端应用的抽象，主要是对于协调用途的元数据。如图1所示，两棵子树，一个对应 app1，一个对应 app2，app1 的子树实现实现了一个简单群组关系协议：每个客户端进程 PiPi 在 /app1 下创建 znode p_i，其表示进程在运行。

尽管 znode 并没有被设计成存储通用数据，但在分布式计算中可以用其来保存元数据或者配置信息。例如，在基于领导者的应用中，对应用服务而言，确定当前的领导者很有用。为了实现这一目标，可以使用当前领导者将信息写入 znode 空间的一个已知位置，znode 也可以将时间戳和版本计数与元数据关联起来，这样客户端就可以跟踪 znode 的变化，并且可以根据 znode 版本变化执行有对应的更新操作。

会话: 客户端连接 ZooKeeper 初始化一个会话。会话有超时时间。当超时时间到期之后，ZooKeeper 认为客户端故障。客户端关闭之后或者 ZooKeeper 探测到客户端故障之后，会话终止。在会话周期内，客户端可以观察到持续的状态变化，这些状态变化反映了有操作在执行。会话使客户端能够透明地从一个 ZooKeeper 集成的一个服务器移动到另一个服务器，因此在 ZooKeeper 服务器之间持久化。

2.2 客户端API

下面给出了 ZooKeeper API 的一个子集，并讨论每个请求的语义。

• create(path, data, flags)：使用 path 名称创建一个 znode 节点，保存 data，返回新创建的 znode 名称。 flags 用于创建普通或者临时节点，也可以设置顺序标识。

• delete(path, version)： 删除指定 path 和 version 的 znode 节点。

• exists(path, watch)： 如果指定 path 的 znode 存在则返回真，如果不存在则返回假。watch 标识用于在 znode 上设置监视器。

• getData(path, watch)： 返回数据和元数据，如版本信息。watch 标识与 exists() 的 watch 标识一样，但如果 znode 不存在则不会设置监视器。

• setData(path, data, version)： 根据 path 和 version 将数据写入到 znode。

• getChildren(path, watch)： 返回 znode 所有子节点的名称集合。

• sync(path)： 在操作开始时，等待所有挂起的更新操作发送到客户端连接的服务器。path 当前未使用。

所有方法有同步和异步两个版本，当一个应用只需要执行单一操作，并且没有其它并发任务执行时，可以使用同步 API，这样对于ZooKeeper 调用和阻塞是必须的。异步 API，可用用来实现多个操作，并且有其它任务正在运行。客户端保证每个操作对应的回调被按照先后顺序调用。

ZooKeeper 不使用句柄来访问 znode，每个请求包含 znode 的路径，这种实现方式不仅可以简化 API（没有 open 和 close 操作），而且减少了额外需要服务器维护的状态。

每次的更新都是对给定版本的更新，这样实现了有条件的更新，如果实际版本号与期望的版本号不一致，更新操作就会失败。如果版本号为-1，不会检查版本号。

2.3 ZooKeeper 的保证

ZooKeeper 有两个基本的顺序保证：

• 线性化写入： 所有更新 ZooKeeper 状态的请求都是序列化的并且遵守优先级。
• 先进先出客户端顺序： 对于一个客户端的所有请求，都会按客户端发送的顺序执行。

这里定义的线性化与 Herlihy 最初提出的线性化有所不同，我们称之为异步线性化。Herlihy 定义的线性化是一个客户端每次只能有一个未完成的操作（一个客户端是一个线程）。我们的异步线性化，可以允许一个客户端有多个未完成的操作，因此对于同一客户端需要保证先进先出的顺序。值得注意的是，所有对可线性化对象适用的结果对异步线性化对象也适用，因为满足异步线性化的系统也满足线性化。因为只有更新请求是可线性化的，所以 ZooKeeper 在每个副本本地处理读请求。这使得服务在服务器添加到系统时可以进行线性扩展。

为了说明两个保证如何交互，考虑下面的场景。有多个进程组成的系统需要选举一个领导者指挥工作者进程，当新领导者接管系统时，其需要变更很多配置参数，当其完成时，需要通知其它进程。下面的两个需求很重要： - 新领导者开始更新时，其它进程还不能使用更新的配置； - 如果新领导者在配置全部更新完成前挂死，其它进程不能使用部分更新的配置。

分布式锁，如 Chubby 提供的锁，可以满足第一个需求，但第二个无法满足。使用 ZooKeeper，新领导者可以指定一个 path 作为 就绪 znode，如果就绪 znode 存在，其它进程可以使用配置。新的领导者通过删除就绪 znode 的方式更新各种配置 znode，然后创建就绪 znode。所有的这些变更可以管道化，并且可以异步提交来快速更新配置状态。尽管变更操作的延迟是2毫秒的数量级，如果请求是一个接一个方式提交，那么新领导者更新 5000 个不同的节点需要 10s，如果请求是异步方式提交，处理时间少于 1s。因为顺序的保证，如果进程查看到了就绪节点，就会看到新的领导者已经完成了全部更新。如果新领导者在创建就绪节点之前挂了，其它进程也会知道配置没有更新完成，也不会使用。

上面的模式仍然有问题：如果在新领导者开始更新之前，一个进程查看到就绪节点已经存在，但领导者恰好已经开始在更新配置了，这时会发生什么？这个问题可以使用通知的顺序性保证解决，如果客户端监视到变更，在其看到新的状态之前会收到通知事件。因此，如果读取就绪节点请求的进程收到了节点变化的通知，在可以读取新的配置之前，该进程会收到变更通知。

客户端除了与 ZooKeeper 之外还有其它通讯通道时，就会有新的问题。例如，客户端 A 和 B 共享配置信息，通过共享的通讯通道进行通讯，如果 A 变更了配置，B 重新读取时会看到变化。如果 B 的ZooKeeper 副本比 A 的稍微有延迟，则 B 不会看到更新。使用上面的保证，B 可以通过写入请求在重新读取之前确保看到最新的信息。为了更加有效的处理这一场景，ZooKeeper 提供了 sync 请求：当读取时，就是一次慢读取。sync 操作不需要一次完全的写操作负载就可以在读之前使得服务器将所有等待的写请求完成。这一原语与 ISIS 的原语 flush 类似。

ZooKeeper 有下面的两个活性和持久性保证：如果 ZooKeeper 的大部分服务器状态 OK，与服务通信就是可用的；如果 ZooKeeper 服务成功地响应了一个更改请求，那么只要有多数服务器最终能够恢复，这个更改就会在任何数量的故障中持久地存在。

2.4 原语的例子

在这一节，使用 API 实现更多更加强大的原语。ZooKeeper 服务不会知晓高级原语的任何信息，因为其完全通过客户端 API 实现，一些通用原语如群组关系和配置管理也是无等待的。对其它原语而言，如汇合，客户端需要等待一个事件。尽管 ZooKeeper 是无等待的，但也可以实现阻塞原语。ZooKeeper 的顺序保证系统状态的有效性，监视器保证是有效的等待。

配置管理 ZooKeeper 可以用来实现分布式应用的动态配置。以最简单的形式来描述，配置信息保存在节点 Zc 中，进程使用全路径 Zc 启动，并且 watch 标识设为真。如果在 Zc 中的配置被更新，进程会被通知，然后读取新的配置信息，重新设置 watch 标识为真。

在这种模式中及其它的使用监视器的模式中，监视器用来确保进程有最近的信息。例如，如果一个进程监视 Zc，被通知 Zc 的变化，并且在其发送读请求给 Zc 之前，对 Zc 又有三次更新，进程不会收到三次通知事件。这不会影响进程的行为，因为这三个事件通知对该进程而言已经知道了：Zc 的信息是过时的。

信息汇合 在分布式系统中，有时对于系统的最终的配置信息并不能提前知道，例如，客户端要启动一个主进程和几个工作进程，但启动进程由调度器完成，所以客户端不能提前知道相关信息，如用于工作进程连接主进程的IP和端口。对于这种场景，可以通过客户端创建一个信息汇合节点 Zr。客户端将 Zr 全路径作为主进程和工作进程的启动参数。当主进程启动时，可以将 IP 地址和端口信息写入 Zr，工作进程启动时，读取 Zr 并将 watch 标识设置为真。如果 Zr 没有被填充内容，则工作进程等待直到 Zr 被更新，如果 Zr 是一个临时节点，当客户端结束时，主进程和工作进程可以通过监视 Zr 是否被删除对自己进行清理。

群组关系 利用临时节点可以实现群组关系。通过临时节点可以查看创建节点的会话信息。设计一个 Zg 的节点表示组，这个组的成员进程启动时，在 Zg 下创建一个临时节点，如果每个进程有唯一的名字或ID，可以用来代表这个子进程，如果没有唯一的名字则可以通过顺序标识分配一个唯一的名称。进程会将一些信息放到子节点中，如地址和端口。

子节点创建后，进程启动。如果进程故障或者终止，不需要其它处理，标示其的 znode 自动会被删除。

通过列出 Zg 的所有子节点，进程可以获取群组信息。如果进程监视群组变化，可以设置 watch 标识，收到通知时刷新群组信息。

简单锁 ZooKeeper 不是一个锁服务，但可以用来实现锁。使用ZooKeeper 的进程会经常使用根据其需求裁剪过的同步原语。通过ZooKeeper 实现锁来说明它可以实现各种通用的同步原语。

简单锁实现使用了“锁文件”。用一个 znode 表示锁。客户端尝试创建一个带有临时标识的节点来获取锁。如果创建成功，客户端可以持有该锁。如果创建失败，客户端设置 watch 标识读取 znode，如果当前使用锁的领导者终止，会通知客户端。客户端在终止或显式删除 znode 来释放锁，其它等待的客户端重新尝试获取锁。

虽然简单锁协议可以工作，但还有一些问题。首先，有群体效应问题，如果很多客户端等待锁，对这个锁的竞争就会很激烈，当锁释放时，仅仅有一个等待的客户端获得锁。其次，仅仅实现了互斥锁。下面两个原语克服了这些问题。

无群体效应的简单锁 定义一个znode ll 来实现这种锁，将所有客户端按请求顺序排列，依次获得锁。希望获得锁的客户端做如下的操作：

lock

1 n = create(l + “/lock-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for watch event
6 goto 2

unlock

1 delete(n)

在 lock 第1行中，使用顺序标识将所有获取锁的客户端排序。如果客户端有最小的序号，则获得锁，否则，客户端等待删除已经获得锁或者这个客户端之前接受锁的 znode。通过监视先于客户端的 znode，当释放锁或者放弃锁请求时，一次唤醒一个客户端，这样就避免了群体效应。一旦监视的 znode 不存在，客户端要检查是否获得了锁。（前面的锁请求会被放弃，有一个小序号的 znode 还在等待锁。）

释放锁的操作很简单，删除代表了锁的 znode 即可。创建节点时使用临时标识，进程崩溃时会自动锁请求释放所有的锁。

总结一下，锁模式有下面的优点： 1. 移除一个 znode 仅仅会唤起一个客户端，因为每个 znode 只会有一个客户端监视，避免了群体效应。 2. 没有轮询或超时。 3. 由于我们实现锁的方式，通过浏览 ZooKeeper 的数据，我们可以观察锁的竞争，解锁，调试锁。

读写锁 为了实现读写锁，稍微改一下前面的锁步骤即可，将其分解为读锁和写锁，释放锁的过程与前面全局锁一样。

write lock

1 n = create(l + “/write-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 2

read lock

1 n = create(l + “/read-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if no write znodes lower than n in C, exit
4 p = write znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 3

这个锁过程与前面的锁稍微有点差异，写锁仅仅命名不一样。读锁可以共享，第三、四行稍微变了一下，如果前面有写锁就不能获得读锁，当一些客户端等待读锁时，如果写锁被删除了，似乎会出现群体效应，实际上这种情况是正常的情况，所有客户端可以获得锁同时读取。

双屏障 双屏障使得客户端在计算开始和结束时进行同步。通过屏障阈值定义进程个数，当有足够多进程加入到屏障后，开始启动计算，计算结束时离开屏障，在 ZooKeeper 中使用一个 znode bb 来表示屏障。每个进程 p 进入时，创建 b 的子节点向 b 注册，当进程离开时删除子节点向 b 注销。在所有进程移除了子节点后进程可以退出屏障。使用监视器等待进入和离开的条件满足。进入时，进程监视 b 的就绪节点是否存在，这个节点由进程满足屏障阈值的那个进程创建，离开时，监视一个特殊子节点是否消失，一旦子节点被移除，仅检查退出条件即可。

3 ZooKeeper应用

这一节给出使用 ZooKeeper 的应用，并给出如何使用的简要介绍。使用黑体字表示每个示例的原语。

爬取服务 搜索引擎的一个重要部分是爬虫，雅虎爬取了数十亿的网页文件，爬取服务（FS）是雅虎雅虎爬虫的一部分，并且已经用于生产环境，有一些主进程向页面爬取进程发送指令，主进程向爬取进程提供配置，爬取进程写回其状态信息。FS 使用 ZooKeeper 的主要优势是可以从主进程的故障恢复，即使发生故障也可以保证可用性，将客户端与服务器解耦，读取状态信息就能将请求指向健康的服务器。FS 使用 ZooKeeper 的主要作用是管理 配置元数据，还用于 选举主进程。

图2给出了 FS 使用3天的一个 ZooKeeper 服务器的读写流量，为了生成这张图，计算了周期内每秒的操作数，每个点表示一秒的操作数，读取流量要比写入流量高很多。在周期内，每秒的速率高于 1000，读写比例在 10:1 到 100:1 之间变化。读负载主要是 getData(), getChildren() 和 exists()，并且依次递增。

Katta Katta 是一个使用 ZooKeeper 作为协调器的分布式索引服务，是一个非雅虎的应用例子。Katta 将任务进行分片索引。主服务给从服务分片并跟踪进度。从服务故障后，主服务必须要重新分布负载给从服务。主服务也可能故障，其它服务器必须时刻准备接管。Katta 使用 ZooKeeper 跟踪主从服务的状态（群组关系）然后处理主服务的故障转移（领导者选举）。Katta 还使用 ZooKeeper 跟踪分发分片任务给从服务（配置管理）。

雅虎消息协商器 雅虎消息协商器（YMB）是一个分布式发布订阅系统，系统管理成千的主题用于客户端发布订阅消息和接受消息。主题分发给一系列提供可伸缩性的服务。每个主题使用主备复制模式来保证消息被复制到两个服务器，这样可以保证消息的可靠投递。YMB 服务器使用无共享的分布式架构，其组成了保证正确操作的基础。YMB 使用 ZooKeeper 管理主题的分发（配置管理），在系统中处理机器故障（故障探测 和 群组关系），控制系统的运行。

图3给出了 YMB 部分 znode 数据布局，每个协调器域有一个 nodes 的节点，组成 YMB 的每个活动服务器都有一个临时节点。每个 YMB 服务器在 nodes 下面创建一个临时节点，临时节点包含负载和状态信息用于提供群组关系和状态。例如 shutdown 和 migration_prohibited 节点被所有服务器节点监视，允许 YMB 的中心控制。topics 目录对于每个主题都有一个子节点。这些主题节点有子节点，用于表示主题订阅者每个主题的主备服务，主和备服务节点不仅允许服务器控制主题的服务器，而且还管理领导者选举和服务器宕机。

4 ZooKeeper 实现

ZooKeeper 通过复制 ZooKeeper 数据给所有 ZooKeeper 服务提供了高可用。假设服务器宕机，这个故障服务器可以随后恢复。图4给出了ZooKeeper 高层组件。在收到请求时，一个服务准备执行（请求处理器）。如果这个请求需要在服务器之间协调（写入请求），需要使用一致性协议（原子广播的一个实现），最后服务器提交请求给在所有服务之间复制的ZooKeeper数据库。对于读请求，一个服务读取本地数据库的状态生成请求的响应消息。

复制的数据库是一个包含整个数据树的内存数据库。树的每个节点存储默认最大 1MB，最大值是可配置的，并且可以根据特殊使用情况变更。为了保证恢复，将更新高效写入磁盘，在写入内存数据库之前，会强制写入磁盘。如 Chubby，使用回放日志（在我们的例子中是 WAL 日志）将提交的请求记录生成内存数据库周期快照。

每个 ZooKeeper 服务器服务几个客户端。客户端连接一个服务器提交请求。如前所述，读请求在服务器数据库的本地副本上进行。对于改变服务状态的写请求，通过一致性协议处理。

作为共识协议的一部分，写请求被转发到单个服务器，称之为领导者。其余的服务称之为跟随者，收到主服务发来的状态变化组成消息提议，并且同意状态变更。

4.1 请求处理器

由于消息层是原子的，可以保证本地副本不会出现差错，虽然在任何时刻一些服务可能比其它服务处理的事务多。与从客户端发送来的请求不一样的是，事务是 幂等 的。当领导者收到写请求，会计算系统写入后的状态并且将其转化为捕获新状态的事务。未来状态必须计算，因为可能会有未写入到数据库的事务。例如，一个客户端使用带有条件的 setData，请求中的版本信息匹配了更新后的 znode 的版本信息，服务器生成包含新数据、版本号和更新后的时间戳的setDataTXN。如果异常发生，不匹配版本号或者将要更新的 znode 不存在，会生成 errorTXN。

4.2 原子广播

所有更新 ZooKeeper 状态的请求被转发到领导者。领导者执行请求并且通过原子广播协议 Zab 广播变更信息。服务器收到客户端请求后，当成功发送状态变更后，给客户端发送响应。Zab 默认使用简单的多数服从原则，所以如果大部分服务器正常时（例如，对于 2f+1 个服务器，可以允许 f 个故障）Zab 和 ZooKeeper 就会正常工作。

为了获得高吞吐量，ZooKeeper 尽量保持请求处理管道是满的，在处理管道不同部分会有成千的请求，因为状态变化依赖前面的状态变化，Zab 提供强一致性保证，Zab 保证发送请求顺序广播，所有前领导者的变更请求会在其自己状态变更之前广播。

有一些实现细节简化了实现过程并且提供了高性能，使用 TCP 传输，消息顺序通过网络保证。使用 Zab 选择的领导者作为 ZooKeeper 领导者，这样在创建事务的同时，也可以使用同一个进程提出事务。对于内存数据库使用日志跟踪协议作为 WAL 日志，这样不需要将消息写入磁盘两次。

在操作过程中，Zab 按顺序发送所有消息，并且仅发送一次，但如果 Zab 对每个发送的消息不永久记录 id，Zab 可能在恢复阶段再次发送消息。因为使用幂等的事务，只要按顺序发送，多次发送也是可以接受的。事实上，ZooKeeper 要求 Zab 至少重新发送上次快照开始后发送的所有消息。

4.3 复制数据库

每个副本都在内存中有一份 ZooKeeper 状态的拷贝，当 ZooKeeper 从故障中恢复时，需要恢复其内部状态。当服务器运行一段时间之后，重新发送所有消息恢复状态需要很长时间，所以 ZooKeeper 使用周期性的快照，每次只需要重新发送从快照开始的消息。将 ZooKeeper 快照称之为模糊快照，因为不需要锁定 ZooKeeper 状态来生成快照，使用深度优先扫描树，读取 znode 的数据和元数据并写到磁盘。虽然最终的模糊快照可能会包含状态变化的子集，因为在生成快照的时候也可能会有状态变化，结果与 ZooKeeper 某个状态不一致，但只要顺序写入状态变更消息，由于是幂等的，可以进行两次变更。

例如，假设 ZooKeeper 数据树节点 /foo 和 /goo 各设置有 f1 和 g1，模糊快照开始时版本号都是1，状态变化流有如下的形式：

⟨transactionType, path, value, new-version⟩ 

⟨SetDataTXN, /foo, f2, 2⟩ 
⟨SetDataTXN, /goo, g2, 2⟩ 
⟨SetDataTXN, /foo, f3, 3⟩

在处理这些状态变更之后，/foo 和 /goo 的值变为 f3 和 g2。但模糊快照可能记录 /foo 和 /goo 有 f3 和 g1，版本分布为3和1，这种状态不是 ZooKeeper 数据的最终状态，如果服务器宕机从快照恢复，Zab 重新发送状态变更，最终保证与宕机前的服务状态一致。

4.4 C/S交互

当服务器处理写请求时，也会将更新相关的通知发送出去并清空。服务器按顺序处理写请求，并且不会同时并发地处理其它的写或读请求，这保证了通知的严格一致，服务器在本地处理通知。仅仅客户连接的服务器跟踪触发通知消息。

读请求在每个服务器本地处理。每个读请求都会被处理，并使用对应于服务器看到的最后一个事务的 zxid 标记。zxid 定义了读请求相对于写请求的部分顺序。通过在本地处理读请求，可以获得非常高的读性能，因为是本地服务器的内存操作，没有磁盘操作和共识协议。这一设计对以读为主的工作负载可以满足高性能的目标。

一个不足的地方是读请求不能保证读请求的优先级顺序，读操作可能读取到旧的状态信息，虽然最近有更新被提交。不是所有应用需要优先级顺序，对于那些需要优先级顺序的应用，提供了 sync 实现。这个原语异步执行，并且由领导者在待处理写操作全部写入到本地副本之后执行。为了保证给定的读操作返回最新的更新值，客户端调用sync，然后调用读操作。先进先出顺序保证客户端顺序保证以及 sync 的全局顺序保证，保证 sync 之前的所有变更都会被反映到读请求的结果中。在我们的实现中，不需要自动广播 sync 操作，因为使用了基于领导者的算法，仅将 sync 操作放到请求队列的末尾，在领导者和服务器之间。为了保证工作，跟随者必须保证领导者仍然是领导者。如果有未提交的事务，服务器就不能怀疑领导者。如果挂起队列是空的，领导者需要提交一个空事务，完成后执行 sync 操作。这保证了领导者在低负载时没有额外的广播流量生成。在我们 的实现中，使用了超时机制，这样领导者就能在跟随者抛弃它之前知道自己已经不是领导者，因此我们不需要提交空事务。

ZooKeeper 服务器以先进先出的顺序处理请求。应答包含了 zxid。心跳消息包含最后一个 zxid，如果客户端连接到新的服务，新服务器通过检查客户端的最后一个 zxid 和其自己的 zxid，保证 ZooKeeper 数据视图是最新的。如果客户端有比服务器更新的视图，服务器不再重新建立会话。客户端保证能够找到其它有新视图的服务器，因为客户端仅仅看到变更被复制到了大部分服务器上。这一行为对保证持久性很重要。

ZooKeeper 使用超时来检测客户端会话失败。如果在会话超时时间内没有其他服务器从客户端会话接收到任何消息，则领导者确定发生了故障。如果客户端发送请求的频率足够高，那么就不需要发送任何其他消息。否则，客户端在低活动期间发送心跳消息。如果客户端无法与服务器通信发送请求或心跳，它将连接到另一个 ZooKeeper 服务器并重新建立会话。为了防止会话超时，ZooKeeper 客户端库在会话空闲 s/3s/3 ms ​后发送心跳，如果在 2s/32s/3 ms 内没有收到服务器的消息，则切换到新的服务器，其中 ss 是会话超时时间，以毫秒为单位。

在 50 个服务器的集群上进行了测评，每个服务器的规格是 Xeon 双核 2.1GHZ 处理器，4GB 内存，千兆以太网和两个 SATA 硬盘。分两个部分讨论：吞吐量和请求延迟。

5.1 吞吐量

为了评估我们的系统，我们对系统饱和时的吞吐量和各种注入故障时吞吐量的变化进行基准测试。改变组成 ZooKeeper 服务的服务器数量，但始终保持客户端数量不变。为了模拟大量的客户机，我们使用35 台机器来模拟 250 个并发客户机。

用 Java 实现 ZooKeeper 服务，客户端有 Java 和 C 两种。配置 Java服务器写日志文件到一个专用的磁盘，在另一个磁盘上进行快照。基准客户端使用异步 Java 客户端 API，每个客户端至少有 100 个未处理请求，每个请求由一个读或写 1K 数据的操作组成，因为所有修改状态的操作都是近似的，所以没有给出其它操作的基准测试，所有不修改状态的操作，除了 sync 也是近似相同。（sync 的性能与轻量写操作近似，因为请求必须到达领导者，但不需要广播。）客户端每 300ms 发送所有的全部操作，每 6s 进行一次采样。为了防止内存不足，服务器会限制系统中并发请求的数量。ZooKeeper 使用请求限制来防止服务器过载。在这些实验中，我们将 ZooKeeper 服务器配置为进程中最多有 2000 个请求。

在图5中，改变读写比例请求观察吞吐量， 每个曲线对应提供ZooKeeper 服务的服务器个数。表1给出了读负载的极限。读吞吐量比写吞吐量高，因为读不需要原子广播。图中还给出服务器个数对广播协议性能有负面影响，从图中可以看出，服务器个数不仅影响服务器可以处理的故障数量，还影响服务器可以处理的负载。三个服务器的曲线与其他相比大约在60%，这种情况不排除三个服务器配置，对所有配置并行本地读开启都一样。在该图中，不能观察到其它配置，因为已经比y轴的最大的吞吐量还要大。

写比读需要更长时间主要是两个因素造成的，第一，写请求必须通过原子广播进行，这需要一些额外处理增加了延时。第二，服务器必须保证在发送确认信息给领导者之前，事务被记录到非易失存储器中。原则上来说，这个要求有点严格，但对于生产系统，需要权衡性能和可靠性，因为 ZooKeeper 是应用服务的基础。使用更多服务器可以容纳更多服务故障，通过将 ZooKeeper 服务器分区可以提升写吞吐量，在副本和分区之间的这一性能权衡，之前 Gray 等人已经做了验证。

ZooKeeper 能够通过在组成服务的服务器之间分配负载来实现很高的吞吐量。我们可以分配负载，因为我们的宽松的一致性保证。而 Chubby 的客户端则把所有的请求都转给领导者。图6显示了如果我们不利用这种宽松一致性并强制客户端只连接到领导者会发生什么。正如预期的那样，对于以读为主的工作负载，吞吐量要低得多，但是即使对于以写为主的工作负载，吞吐量也要低得多。服务客户端带来的额外 CPU 和网络负载会影响领导者对提案广播的协调能力，反过来又会对整体写性能产生不利影响。

原子广播协议完成系统中的大部分工作，所以比较其它组件而言，它限制了 ZooKeeper 的性能。图7给出了原子广播组件的吞吐量。为了测试其性能，通过在领导者上直接生成事务的方式模拟客户端。以最大的吞吐量，原子广播组件成为 CPU 瓶颈。理论上来说，图7中的性能与 ZooKeeper 100% 写入操作的性能一致。ZooKeeper 客户端通信，ACL 检查，事务转换请求都需要 CPU 处理，关于 ZooKeeper 吞吐量 CPU 降低的主要原因还是在于原子广播组件。因为 ZooKeeper 是关键生产组件，到目前为止 ZooKeeper 的主要开发集中在正确性和健壮性。有许多方法可以影响性能，比如额外拷贝，同一对象的多次序列化，更高效的内部数据结构等。

为了给出注入故障后随时间系统的行为，使用由5个服务器组成的集群。与前面一样也是饱和的基准测试，但这次写请求保持30%，对于我们期望的工作负载，这是一个保守的比例。周期性低杀死一些服务，图8给出系统随时间变化的吞吐量。图中标示的事件解释如下： 1. 一个跟随者故障和恢复 2. 另一个跟随者的故障和恢复 3. 领导者故障 4. 两个跟随者故障（a，b），恢复（c） 5. 领导者故障 6. 领导者恢复

从图中可以观察出一些重要信息，第一，如果单个跟随者故障，并快速恢复，ZooKeeper 能支撑高吞吐量。单个跟随者不会导致整个系统故障，仅仅降低了在故障前服务处理共享读请求的吞吐量。第二，领导者选举算法能够保证快速恢复，避免系统吞吐量下跌。根据观察，ZooKeeper 需要少于 200ms 时间选出新的领导者，所以，尽管服务器有几百ms停止服务请求处理，但因为我们的采样周期内没有观察到0吞吐量。第三，即使追随者需要更多的时间来恢复，ZooKeeper 能够再次提高吞吐量，一旦他们开始处理请求。我们在事件1、2和4之后没有恢复到完整吞吐量水平的一个原因是，客户端仅在与跟踪者的连接断开时才切换跟踪者。因此，在事件4之后，客户端不会重新分配，直到领导者在事件3和5中失败。在实践中，随着客户端的加入退出，这种失衡会随着时间的推移而显现出来。

5.2 请求延迟

为了评估请求的延迟，创建了以 Chubby 基准为模型的测试。创建一个工作进程发送创建请求，等待结束，发送异步删除请求，然后进行下一个创建。根据情况改变工作进程的个数，每次运行时每个工作进程创建5万个节点。通过创建请求完成个数除以所有工作进程需要的总时间计算吞吐量。

表2给出基准测试的结果，创建请求包含 1K 的数据，而不是 Chubby 的5字节，这样做是为了与我们实际期望使用的情况一致。虽然请求数据更大，ZooKeeper 的吞吐量是 Chubby 公开发表的吞吐量的3倍。单个 ZooKeeper 工作进程基准测试吞吐量表明，平均的请求延迟对于3个服务器是1.2ms，9个服务器是1.4ms。

5.3 屏障的性能

在这个实验中，执行几个屏障来评价用 ZooKeeper 实现的原语的性能。对于给定的屏障个数 b，每个客户端第一次进入所有的 b 个屏障，然后离开所有的 b 个屏障。使用2.4节中的双屏障算法，在进入下一次调用之前（与leave()类似）之前，客户端等待所有其他客户端执行 enter() 过程。

实验结果如表3所示，在这个实验中，有 50,100 和 200 个客户端相继进入 b 个屏障，b 属于{200, 400, 800, 1600}。尽管应用程序可以有成千的 ZooKeeper 客户端，通常情况下，很小一部分参与每个协调操作，因为客户端根据特定的应用进行分组。

这个实验中可以看到两个有意义的信息，处理所有屏障的时间大致随屏障的个数线型增长，同时访问数据树的相同部分不会产生任何非期望的延迟，延迟随着客户端数量成比例增加。这是服务不饱和的结果。实际上，可以看出，虽然客户端使用锁，在所有情况下每秒处理的操作在 1950 到 3100 之间。在 ZooKeeper 运行中，这与每秒 10700 到 17000 吞吐量一致。在实现时，读写比例是 4:1（80%读操作），基准测试代码使用的吞吐量与原始的 ZooKeeper 可以获得的吞吐量（根据图5超过40000）要低，这是因为客户端在等待其它客户端。

6 相关工作

ZooKeeper 的目标是提供一种服务来解决分布式应用程序中的进程协调问题。为了实现这个目标，它的设计使用了以前的协调服务、容错系统、分布式算法和文件系统的思想。

这篇文章并不是第一个提出分布式应用的协调服务，一些更早的系统提出了对于事务应用的分布式锁服务，用于在集群计算机中共享信息。更近一点，Chubby 提出了一个系统用于管理分布式应用的锁，Chubby 与 ZooKeeper 的一些目标一致。其也有与文件系统类似的接口，只用一致性协议保证副本的一致性，但 ZooKeeper 不是锁服务，客户端可以使用 ZooKeeper 实现锁服务，但 API 中没有锁操作，与 Chubby 不一样的是，ZooKeeper 允许客户端连接到非领导者的 ZooKeeper 服务器，ZooKeeper 客户端可是使用本地副本来提供数据和管理监视器，因为其一致性协议比 Chubby 的更宽松，这使得 ZooKeeper 提供了比 Chubby 更高的性能，并且允许应用使用 ZooKeeper 更多的扩展。

文献中已经提出了容错系统，目的是缓解构建容错分布式应用程序的问题。一个早期的系统是 ISIS[5]。ISIS 系统将抽象类型规范转换为容错的分布式对象，从而使容错机制对用户透明。Horus[30] 和 Ensemble[31] 是由 ISIS 演化而来的系统。ZooKeeper 采用了 ISIS 的虚同步概念。最后，在一个利用本地网络[22]的硬件广播的架构中，Totem 保证了消息传递的总体顺序。ZooKeeper 与各种各样的网络拓扑结构一起工作，这促使我们依赖于服务器进程之间的 TCP 连接，而不假定任何特殊的拓扑结构或硬件特性。我们也不公开任何在ZooKeeper 内部使用的集成通信。

构建容错服务的一个重要技术是状态机复制，Paxos 是一个异步系统保障副本状态机非常有效的算法。使用了一个与 Paxos 有一些类似特征的算法，但结合了保持一致性的事务日志和用于数据高效恢复的WAL日志记录。有一些提出了拜占庭容错复制状态机的实际实现的协议。ZooKeeper 不假定服务器是拜占庭式的，但使用了了如校验和和正常性校验的机制来捕获非恶意的拜占庭故障。Clement 等人讨论了不修改当前服务器代码来实现完全的拜占庭容错。到现在，并没有观察到生产环境中使用完全的拜占庭容错协议避免的故障。

Boxwood 是使用了分布式锁服务的系统。Boxwood 给应用提供了高级的抽象，其依赖基于 Paxos 的分布式锁服务。与 Boxwood 一样，ZooKeeper 是一个用于构建分布式系统的组件，ZooKeeper 有高性能的要求在客户端应用中使用更加广泛。ZooKeeper 提供给了低级原语，应用可以使用这些原语实现高级原语。

ZooKeeper 与一个小型的文件系统类似，但仅仅提供了文件系统操作的一个子集，但加入了一些大多数文件系统不具备的功能，如顺序性保证和条件写入。ZooKeeper 监视器与 ATS 的缓冲回调类似。

Sinfonia 使用了 mini 事务，这是一个构建可伸缩分布式系统的新的模型，Sinfonia 被设计用于保存应用数据，ZooKeeper 用于保存应用元数据，ZooKeeper 保存状态副本在内存中，保证系统高性能和一致的延迟，使用文件系统类似操作和顺序保证功能与 mini 事务类似，znode 对于添加监视器是一个比较实用的抽象，Sinfonia 没有提供。Dynamo 允许客户端在分布式键值存储中读取相对较小（小于1M）数量数据。与 ZooKeeper 不一样的是，Dynamo 键的空间结构不是层次化的。Dynamo 对于写也没有提供持久性和一致性保证，但解决了读的冲突。

DepSpace[4] 使用元组空间提供拜占庭容错服务。像 ZooKeeper 一样，DepSpace 使用一个简单的服务器接口在客户端实现强同步原语。虽然 DepSpace 的性能远低于 ZooKeeper，但它提供了更强的容错和机密性保证。

ZooKeeper 通过向客户端提供无等待对象来解决分布式系统中协调进程的问题。我们发现 ZooKeeper 对雅虎内外的几个应用程序都很有用。对于以读为主的工作负载，ZooKeeper 通过带有 watch 的快速读取，实现了每秒数十万次操作的吞吐量，这两种操作都由本地副本提供。虽然我们的一致性保证读取和 watch 似乎较弱，但是我们已经展示了我们的示例，这种组合使我们能够在客户端实现高效且复杂的协调协议，即使读取不是按照优先顺序进行的，而且数据对象的实现是无等待的。无等待特性已被证明是高性能的关键。

虽然我们只描述了几个应用程序，但还有很多其他的应用程序使用 ZooKeeper。我们相信这样的成功是由于它简单的接口，可以通过这个接口实现的强大的抽象。此外，由于 ZooKeeper 的高吞吐量，应用程序可以对其进行扩展，而不仅仅是粗粒度锁。

感谢 Andrew Kornev 和 Runping Qi 对于 ZooKeeper 的贡献；Runping Qi 和 Mark Marchukov 提供了有价值的反馈；Brian Cooper 和 Laurence Ramontianu 对早期 ZooKeeper 的贡献；Brian Bershad 和 Geoff Voelker 对发表给了重要评论。

见原论文《ZooKeeper: Wait-free coordination for Internet-scale systems》

History:

• 2016-03-05 王世德 初始版翻译完成
• 2020-12-25 王世德 修订版本，准确性以及格式