MIT 6.824 - ZooKeeper: Wait-free coordination for Internet-scale systems

Posted on Word count in article: 15k Reading time ≈ 26 mins.

介绍

大型分布式系统需要各式各样的协同。配置就是其中一种最基础的形式，在其最简单的形式中，配置只是一系列供系统使用的参数，而对于更复杂的系统来说，配置还可以动态更新。群组成员关系和选主同样在分布式系统中很常见：通常各进程需要知道哪些进程还存活，以及哪些进程在负责统一管理。另外，分布式锁作为一种强大的协调原语能够对临界资源提供互斥访问保护。

一种实现协同的方式是为每一个不同的协同需求开发一个服务。例如，Amazon Simple Queue Service 专注于消息队列。同时也存在专门为了选主和配置所开发的服务。针对较强的原语开发的服务能够用于实现较弱一级的原语。例如，Chubby 是一个强同步性保证的锁服务。则可以借助锁来实现选主，群组成员关系等服务。

相较于在服务端实现特定的协同原语，ZooKeeper 的作者选择暴露某些 API 来让应用开发者自行实现需要的原语。这种设计选择需要实现一个协同内核（coordination kernel）使得新原语的开发不需要修改核心服务端代码。这种方式能够适配应用程序对不同协同形式的需求，而不是让开发者受限于某几个固定的原语。

在设计 ZooKeeper 的 API 时，设计者移除了阻塞原语，例如锁。一个协同服务的阻塞原语会导致某些问题，缓慢或出错的客户端会拖慢快速的客户端的性能。如果服务处理请求时需要依赖响应以及负责客户端的异常检测，那么服务的实现会变得更为复杂。因此，ZooKeeper 实现了一套 API 能够操作以类似文件系统的方式组织的无等待（wait-free）对象。实际上，ZooKeeper 的 API 类似于其他任何的文件系统，以及和去除了加锁（lock），打开（open），关闭（close）这些方法的 Chubby 类似。实现了无等待对象的 ZooKeeper 显著有别于其他基于阻塞原语（例如锁）的系统。

虽然无等待这一特性对于性能和容错很重要，但是对于协同来说来不够。ZooKeeper 还需要对各操作提供其他保证。对客户端 FIFO 的操作保证和线性化写入的保证确保了服务的高效实现，同时也能够满足应用程序实现自定义协同原语的需求。实际上，利用 ZooKeeper 的 API 可以实现任意节点数量的共识算法。

ZooKeeper 服务通过服务器间的复制来实现高可用和性能。它的高性能使得大量客户端进程能通过协同内核来管理方方面面的协同需求。通过一种简单的管道架构来实现 ZooKeeper 使得服务在承受几百或上千的请求的同时依然保持着低延迟。这种管道方式天然的支持对同一个客户端的请求以 FIFO 的方式执行。对客户端请求的 FIFO 顺序执行的保证使得客户端能异步的提交请求。异步提交也使得客户端同一时间有多个操作。这个特性很有用，例如当某个客户端成为主节点后，它需要操作元数据然后更新。如果缺少了多操作同时进行的特性，那么这个主节点初始化的时间可能达到秒级的数量级而不是亚秒级。

为了满足写入的线性化保证，ZooKeeper 实现了一个基于主节点的原子广播协议，即 Zab。典型的 ZooKeeper 应用属于读密集型应用，所以需要保证读操作的扩展性。ZooKeeper 的读操作由当前服务器完成，不涉及和其他服务器的交互，也不会使用 Zab 来保证读取的顺序性。

在客户端缓存数据是提高读性能的重要手段。例如，客户端可以缓存当前主节点的信息而不是每次请求 ZooKeeper。ZooKeeper 同时提供了监听机制来协助客户端缓存数据而无需直接管理客户端的缓存。借助这个机制，客户端可以对某个数据进行更新监听，从而在数据更新时收到通知。而 Chubby 会直接管理客户端的缓存，它会阻塞某个数据的更新直到所有缓存了该数据的客户端都清除了缓存。在这个设计下，如果某个客户端运行缓慢或者出错，则会拖慢数据的更新。Chubby 使用租约来避免某个客户端永久的阻塞系统。不过，租约只是确保了运行缓慢或者出错的客户端对性能的影响的上限，而 ZooKeeper 的监听机制则是完全的避免了这个问题。

本文主要介绍了 ZooKeeper 的设计和实现。借助 ZooKeeper，我们可以实现应用程序所需要的所有协同原语，即使只有写入是线性化保证的。为了验证这个设计，本文介绍了如何使用 ZooKeeper 来实现某些协同原语。

本文的关键点如下：

  • 协同内核（Coordination kernel）：本文提出了一种供分布式系统使用的无等待、宽松一致性保证的协同服务。特别的，本文描述了一种协同内核的设计和实现，并且已经在很多重要的应用程序中使用来实现各种各样的协同服务。
  • 协同示例（Coordination recipes）：本文描述了如何使用 ZooKeeper 来实现高层次的协同原语，包括在分布式应用中经常用到的阻塞和强一致性的原语。
  • 使用协同的经验（Experience with Coordination）：本文分享了使用 ZooKeeper 的方式以及评估了其性能。

ZooKeeper 服务

客户端通过 ZooKeeper 提供的客户端类库来向 ZooKeeper 提交请求。除了向客户端暴露 ZooKeeper 提供的 API 外，客户端类库还负责维护客户端和 ZooKeeper 服务器间的连接。

本节会首先从高层次来介绍 ZooKeeper 服务，然后再讨论客户端和 ZooKeeper 交互的 API。

术语：本文使用客户端（client）来表示使用 ZooKeeper 服务的一个用户；使用服务端（server）来表示 ZooKeeper 的服务提供者；使用 znode 来表示 ZooKeeper 的一个内存数据节点，这些数据节点以层次化的命名空间的形式所组织，即 data tree。同时，本文使用更新（update）和写入（write）来表示任何修改 data tree 状态的操作。客户端和 ZooKeeper 通过建立 session 进行连接，并且通过 session handle 发送请求。

服务概览

ZooKeeper 将数据抽象成数据节点（znodes）后供客户端访问，所有数据节点以层次化的命名空间进行组织。znodes 是客户端可通过 ZooKeeper 的 API 操作的数据对象。层次化的命名空间通常被用于文件系统。因为用户已经习惯了这种抽象，所以 ZooKeeper 很自然的以这种方式来管理数据，另外这也能更好的管理应用程序的元数据。ZooKeeper 使用和标准 UNIX 文件系统命名一样的方式来表示一个 znode。例如，A/B/C 表示 znode C 的路径，并且 C 的父节点是 B，B 的父节点是 A。每个 znode 都会保存数据，而且除了临时节点之外的所有节点都可以有子节点。

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

  • 常规（Regular）：客户端可以显式的创建和删除常规节点。
  • 临时（Ephemeral）：客户端创建临时节点后，可以显式的删除，或者当客户端和 ZooKeeper 的 session 结束后（客户端主动断开连接或者由于异常失去连接）由系统自动删除。

另外，客户端在创建一个 znode 时可以设置一个顺序标记。设置了顺序标记所创建的节点会在节点名称后追加一个单调递增的序号。如果 n 是一个新的 znode，p 是 n 的父节点，那么 n 的序号一定不会比在 n 之前所创建的 p 的子节点的序号小。

ZooKeeper 实现了监听器使得客户端能及时的收到数据修改的通知而无需轮询。当客户端发起一个读操作并设置监听时，这个读操作会和普通的读操作一样正常返回，不过当数据更新时，系统能通知客户端。监听器在单次 session 内只会被触发一次，一旦监听器被触发或者 session 关闭，该监听器就会被注销。监听器被触发表示监听的数据发生了修改，但是不会告知被修改后的值。例如，如果一个客户端在 "/foo" 被修改了两次之前执行了 getData("/foo", true)，那么客户端会收到一次通知表示 "/foo" 指向的数据被修改了。一些 session 级别的事件，例如连接丢失，也能通过监听回调通知给客户端，那么客户端就会知道监听通知可能会延迟。

数据模型

ZooKeeper 的数据模型基本上等同于简化版 API 的文件系统，只能一次性读取或者写入全部数据；或者等同于是一个以层次结构组织键的键值表。层次结构的命名空间能够为不同的应用程序分配子命名空间，同时也方便为不同的子命名空间分配访问权限。同时 ZooKeeper 在客户端这层提供了文件夹的概念，能够用于构建高层次的原语。

和文件系统中的文件不同，znodes 的设计目的并不是为了通用数据存储。相反，znodes 是作为客户端应用程序的抽象，典型场景是用于保存协同目的的元数据。在下图中有两个子树，其中一个用于应用程序1（/app1），另一个用于应用程序2（/app2）。应用程序1对应的子树实现了一个简单的群组成员关系协议：每个客户端 p_i 在 /app1 下会创建一个 znode p_i，只要客户端还存活，对应的节点就会存在，那么，根据 /app1 下的节点数量就能知道当前应用程序有多少个存活的进程能提供服务。

alt

虽然 znodes 的设计目的不是为了通用数据存储，不过 ZooKeeper 也允许客户端在 znode 中保存数据，例如分布式计算需要用到的元数据或者配置信息。例如，在一个基于选主的应用中，一个刚启动的应用程序节点需要知道当前的主节点是谁。为了实现这个目的，可以让当前主节点将主节点的信息写入到某个约定的 znode 路径中。此外，znode 本身也提供了时间戳和版本号这样的元数据，使得客户端能够监控 znodes 的数据变化，从而根据 znode 的数据版本进行数据更新。

会话

一个客户端连接到 ZooKeeper 时会初始化一个 session。每一个 session 伴随着一个超时时间。如果在一个超时时间之内 ZooKeeper 没有收到来自客户端的任何请求，那么 ZooKeeper 就会认为这个客户端发生了异常。客户端可以主动通过关闭 session handle 来结束一个 session 或者 ZooKeeper 监测到客户端发生异常而自动关闭 session。在一个 session 内，客户端所观察到的系统状态变化和其提交的操作一一顺序对应。在一个 session 内，如果当前客户端连接的 ZooKeeper 节点发生异常，ZooKeeper 客户端类库能无缝的将其连接到一台新的 ZooKeeper 节点上，从而在各节点间完成持久化。

客户端 API

ZooKeeper 提供了以下的核心 API：

  • create(path, data, flags)：创建一个路径为 path 的 znode，并将数据 data[] 保存其中，然后返回新建的 znode 的名称。flags 用于指定 znode 的类型：常规节点，临时节点，以及设置顺序标记。
  • delete(path, version)：如果指定路径 path 下的 znode 的版本号和 version 匹配，则删除该节点。
  • exists(path, watch)：如果指定路径 path 下的 znode 存在则返回 true，否则返回 false。如果 watch 为 true，则当 znode 的数据发生变化时，客户端会收到通知。
  • getData(path, watch)：获取指定路径 path 下的 znode 的数据和元数据，例如版本信息。watch 的功能和 exists() 中的 watch 的功能一致，只不过如果当前节点不存在，则 watch 不会生效。
  • setData(path, data, version)：如果指定路径 path 下的 znode 的版本号和 version 匹配，则将数据 data[] 写入到该节点。
  • getChildren(path, watch)：返回指定路径 path 下的 znode 的子节点的名称。
  • sync(path)：阻塞等待直到在操作开始时所有进行中的更新操作都同步到了当前客户端所连接的服务端。path 参数当前未使用。

ZooKeeper 通过 API 为每个方法提供了同步和异步两个版本。当应用程序希望执行单一 ZooKeeper 操作而且没有其他并发任务要执行时，可以选择调用同步方法。而如果应用程序希望同时执行多个 ZooKeeper 操作以及有其他任务需要并发执行时，可以选择调用异步方法。ZooKeeper 客户端类库保证了异步方法的回调顺序和提交请求的顺序一致。

ZooKeeper 不直接通过 handles 来访问 znodes。每个客户端请求会带上所要操作的 znode 的全路径。这不仅简化了 API（没有 open() 或者 close() 方法），同时服务端也不需要维护额外的状态。

客户端对 ZooKeeper 每个更新操作都会带上一个期望的版本号，这就能实现按条件更新。如果当前 znode 的版本号和期望的版本号不一致，那么此次更新就会失败并返回版本不匹配错误。如果传入的版本号是-1，则表示不进行版本号校验。

ZooKeeper 的保证

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

  • 线性化写入（Linearizable writes）：所有对 ZooKeeper 的状态修改都会按序串行化执行。
  • 先来先执行的客户端顺序（FIFO client order）：来自同一个客户端的所有请求会按照请求发送的顺序执行。

ZooKeeper 提出的线性化和 Herlihy 提出的线性化有所不同，ZooKeeper 的作者称之为 A-linearizability（asynchronous linearizability）。在 Herlihy 的线性化定义下，一个客户端只能有一个进行中的操作（一个客户端对应一个线程）。而在 ZooKeeper 中，一个客户端允许有多个进行中的操作，那么从设计上可以选择对多个进行中的任务不保证执行顺序，或者保证 FIFO 顺序。ZooKeeper 选择了后者。如果一系列操作的结果适用于 linearizable 的对象，那么也同时适用于 A-linerizalbe 的对象，因为 A-linearizability 本身就满足线性化。因为只有更新操作需要满足 A-linerizalbe，所以 ZooKeeper 的读操作可以直接通过本地副本执行。进一步使得添加新的服务器时能实现对服务的线性扩展。

下面将通过一个场景示例来说明上述两个保证是如何交互的。某个系统需要选举一个主节点来分配任务给其他工作节点执行。每当新选举了一个主节点，它需要更新大量的配置参数并且当更新完成时通知其他的工作节点。这就带来了两个重要的需求：

  • 当主节点在更新配置参数时，其他工作节点不能使用还未更新完成的配置参数。
  • 如果主节点在配置参数更新完成前发生异常，其他工作节点也不能使用未更新完成的配置参数。

类似 Chubby 提供的分布式锁能满足第一个需求，但是不足以满足第二个需求，因为当其他工作节点获取锁读取配置参数时，它并不能知道配置参数是否已更新完成。在 ZooKeeper 中，主节点可以在某个约定的路径创建一个 ready 节点，只有在 ready 节点存在的情况下，其他工作节点才可以认为配置参数已更新完成。在更新配置参数前，主节点会先删除 ready 节点，然后更新配置参数，最后再创建 ready 节点。所有这些操作都可以以管道的方式进行并异步提交请求，从而使得配置参数能快速更新。虽然一次更新操作的耗时是2毫秒的数量级，但是如果主节点需要阻塞的依次更新5000个配置参数的话则一共需要10秒才能完成；通过异步提交更新，所有的请求能在一秒内完成。因为 ZooKeeper 的顺序性保证，如果某个工作节点发现 ready 节点存在，那么就说明配置参数也必然更新完成了，因为 ready 节点的创建晚于配置参数的更新。如果主节点在配置参数更新完成前发生异常，那么也就不会创建 ready 节点，其他工作节点就知道配置参数更新未完成。

不过上述方案还存在一个问题：如果某个工作节点此时看见 ready 节点存在，但是同时主节点删除了 ready 节点然后开始更新配置参数，那么工作节点就会读取到正在更新的配置参数。这个问题通过监听通知的顺序性保证来解决：如果客户端对某个节点 A 开启了监听，此时系统先对节点 A 进行了修改，然后对另一个节点 B 进行了修改，此时客户端发起了对节点 B 的读请求，那么 ZooKeeper 会保证客户端先收到节点 A 修改的异步通知。所以，如果客户端在判断 ready 节点是否存在时开启了监听，那么它就会在读取到修改中的配置参数前先收到 ready 节点修改的通知，从而可以中断配置参数的读取。

如果客户端之间还有除了 ZooKeeper 之外的通信方式也会引发另一个问题。例如，两个客户端 A 和 B 通过 ZooKeeper 共享配置，然后通过其他某种方式通信。如果 A 修改了 ZooKeeper 中的配置然后告诉 B，那么 B 收到通知后读取 ZooKeeper 就期望能获取到修改后的配置。不过如果 B 连接的 ZooKeeper 副本落后于主节点，那么 B 可能无法读取到最新的配置。而采用写入 ready 节点再读取的方式能保证 B 读取到最新的配置。ZooKeeper 提供了 sync 方法来更高效的解决这个问题：如果 sync 请求之后有一个读请求，则 ZooKeeper 会暂缓这个读请求。sync 会同步在这之前进行中的写请求，而无需等待当前所有的待写入操作完成。这个原语类似于 ISIS 中的 flush 原语。

ZooKeeper 同时也有存活性（liveness）和持久性（durability）的保证：只要 ZooKeeper 集群中过半数的机器存活，那么访问 ZooKeeper 服务就没有问题；如果 ZooKeeper 成功响应了某个修改请求，只要过半数的机器在异常后最终能恢复，那么不管经历了多少次系统异常这个更新都不会丢失。

原语示例

本节描述了如何利用 ZooKeeper 的 API 来构建更强大的原语。对于 ZooKeeper 来说，它并不知晓这些原语的存在，因为这些原语是由客户端通过 API 自行实现的。一些通用的原语例如群组成员关系和配置管理都是无等待原语。对于其他原语如 rendezvous，客户端则需要等待某个事件发生。虽然 ZooKeeper 是无等待服务，客户端也同样可以实现阻塞的原语。ZooKeeper 的顺序保证可以高效的审视系统的状态，而监听机制则实现了高效的等待。

配置管理（Configuration Management）

ZooKeeper 可以用于分布式系统中实现动态配置管理。在最简单的形式中，配置信息保存在一个 znode 中，例如 z_c。应用启动时会读取 z_c 的数据并设置监听状态。如果 z_c 的数据更新了，那么应用就会收到通知，然后就可以读取最新的配置，并继续设置监听状态。

在这个例子以及其他大多数使用监听器的例子中，监听器确保了应用能获取到最新的数据。例如，如果某个监听 z_c 的应用收到了 z_c 的修改通知，而在这个应用读取 z_c 之前，z_c 又被修改了3次，那么这个应用不会再收到通知。这并不会影响应用的行为，因为 ZooKeeper 的变更通知不会返回更新后的数据，应用需要再次读取才能获得节点最新的数据，只通知一次已经使得应用知道当前节点的数据已经过期，没有必要重复通知。

Rendezvous

有时候在分布式系统中并不能清晰的预知系统的最终配置是什么。例如，某个客户端可能会希望启动一个主节点和几个工作节点，不过由于节点的启动是由某个调度器执行，客户端并不能事先知道某些需要的信息，例如工作节点需要连接的主节点的地址和端口号。这个问题可以由客户端通过 ZooKeeper 创建一个 rendezvous 节点 z_r 来解决。客户端将 z_r 的全路径作为启动参数传给主节点和工作节点。当主节点启动后，它就将自己的地址和端口号写入到 z_r 中。当工作节点启动后，它就能从 z_r 中读取主节点的地址和端口号，并设置节点的监听状态。如果工作节点启动时主节点还未写入数据到 z_r，那么工作节点就会等待数据写入的通知。如果 z_r 是临时节点，那么创建 z_r 节点的客户端下线后，主节点和工作节点就能收到节点删除通知，并在完成资源清理后退出。

群组成员关系（Group Membership）

客户端可以利用临时节点的特性来实现群组成员关系管理。这里利用了可以通过监听临时节点来观测创建该节点的 session 状态的特性。首先创建一个节点 z_g 来表示群组。当群组中的某个进程启动时，它会在 z_g 下创建一个临时的子节点。如果每个进程都有唯一的命名或标识，那么这个命名或标识就可以作为 ZooKeeper 节点的名称；否则就可以在创建节点时设置 SEQUENTIAL 标记让 ZooKeeper 自动在节点名称后追加一个单调递增的数字，以保证名称的唯一性。各进程可以将进程相关的信息放到临时节点中，例如当前进程的地址和端口号。

当进程在节点 z_g 下创建完临时进程后就可以正常启动。它不需要做其他任何事。如果这个进程发生异常或者主动结束，那么它所创建的临时节点也会自动被删除。

各进程可以简单的通过查询 z_g 的所有子节点来获取当前群组成员的信息。如果某个进程想要监控群组成员的变化，那么它可以设置监听标记（通过 getChildren(path, watch) 方法设置 watch），然后在收到通知时更新群组信息。

简单锁（Simple Locks）

虽然 ZooKeeper 不是一个锁服务，但也可以用来实现锁。使用 ZooKeeper 的应用通常使用同步原语来适配其需求。本节通过使用 ZooKeeper 实现锁来展示可以通过 ZooKeeper 来实现各种各样的通用同步原语。

最简单的锁实现借助于 lock files。使用一个 znode 来表示一把锁。为了获取锁，客户端会尝试以 EPHEMERAL 标记创建一个临时节点。如果创建成功，那么这个客户端就获得了锁。否则，客户端就会去读取这个 znode 并设置监听状态，从而当这个临时节点被删除时能收到通知。当持有锁的客户端发生异常或者主动删除该节点时，则代表释放了锁。其他监听的客户端就会收到通知并尝试重新创建临时节点来获取锁。

虽然这种方式能实现锁，不过也存在几个问题。首先，它会造成羊群效应（herd effect）。如果有大量的客户端在等待释放锁，那么当锁被释放时，这些客户端都会被通知然后都会尝试获取锁，而实际上只会有一个客户端能获得锁。第二，这种方式只实现了互斥锁。下面两种原语展示了如何解决这两个问题。

没有羊群效应的简单锁（Simple Locks without Herd Effect）

首先定义节点 l 来实现锁。然后，将所有希望获取锁的客户端按照请求顺序排序，之后这些客户端就能按照请求的顺序获取锁。客户端希望获取锁时需要执行下面的操作：

1
2
3
4
5
6
7
8
9
10
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)

第一行 SEQUENTIAL 的标记用来将所有希望获取锁的客户端进行排序。每个客户端首先在节点 l 下创建一个临时顺序的子节点，然后获取 l 的所有子节点。之后在第三行判断自己创建的节点是否在所有子节点中有着最小的序号，如果是，则表示当前客户端获得了锁。如果不是，说明有其他序号更小的子节点存在，当前客户端需要排在这之后获取锁。然后客户端会尝试判断排在当前序号前的子节点是否存在，如果存在则设置监听状态等待前一个节点删除的通知，如果不存在，则继续回到第二行执行。每个客户端只监听排在自己前面的子节点避免了羊群效应，因为任何一个子节点删除的通知只会发给其中的一个客户端。每当客户端收到前面节点删除的通知时，需要再次获取 l 的所有子节点来判断自己是否是最小子节点（因为排在前面的子节点并不一定持有锁，可能是更前面的子节点持有锁。这里能否直接复用第一次请求 getChildren 的信息？实现起来会较麻烦些，因为需要挨个判断排在前面的子节点是否还存在，不如直接拉取一份最新的子节点信息）。

释放锁就是简单的删除对应的临时节点 n。而通过 EPHEMERAL 创建节点能保证进程异常时自动释放锁或者放弃对锁的获取请求。

这种锁实现有以下几个优势：

  1. 一个节点的删除只会唤醒一个客户端，因为每个节点都只会被一个客户端监听，所以也不会有羊群效应。
  2. 锁的获取和释放不依赖轮询或超时。
  3. 使用这种方式创建锁使得可以通过查看 ZooKeeper 中的数据来监测锁竞争的数量，以及调试锁相关的问题。

读写锁（Read/Write Locks）

在前面锁的基础上稍加修改就能实现一个读写锁。释放锁的操作和前面的相同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 watch 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 watch event
6 goto 3

写锁是互斥锁，这里的实现和前面的锁的实现一模一样，只是改变了创建节点的名称。而由于读锁之间没有互斥，所以获取读锁时只需要检查有没有序号更小的写锁即可。另外，读锁实现时最后的 goto 直接跳到了第三行而没有到第二行，这个在 ZooKeeper FAQ 中也提到可能是个笔误。这里看起来会有羊群效应，即存在大量的客户端会监听某个写锁，当写锁被删除时这些客户端都会收到通知，不过这本身就是预期的行为，因为读锁之间没有互斥，写锁释放后就应该唤醒所有等待中的读锁。

双屏障（Double Barrier）

双屏障用于客户端在某个计算开始和结束时进行同步，当指定数量的进程加入到屏障中后，就可以开始各自的计算任务，每个进程在整个计算任务结束后就可以离开屏障。MapReduce 任务就是一个典型示例，reduce 任务的开始需要所有 map 任务的完成，当所有 map 任务完成后，各进程就可以进入屏障开始 reduce 任务，而整个 MapRecuce 任务的完成依赖所有 reduce 任务的完成，当所有 reduce 任务完成后，各进程就可以离开屏障。客户端可以使用一个 znode 来表示屏障，记作 b。每个进程在 b 下创建一个子节点来表示进入屏障，通过删除子节点来表示离开屏障。如果 b 下的子节点的数量超过了指定值，那么就允许开始执行计算任务。当 b 下的子节点都被删除后，进程就可以离开屏障。这里同样使用监听机制来高效的等待进入屏障和离开屏障的事件发生。一旦 b 下的子节点数量满足了阈值，创建最后一个子节点的进程会同时创建一个 ready 子节点，那么通过监听 ready 子节点是否存在就可以判断是否可以开始计算。另一方面，论文中提到通过监听某个特定的子节点来判断是否可以离开屏障，这里略显模糊，这个特定的子节点是谁创建的？创建了这个子节点的进程什么时候可以删除这个子节点？ZooKeeper FAQ 中提出了另一种方案，每个进程各自监听 b 下的子节点，并且在任务完成后删除所创建的节点，如果各进程发现 b 下没有子节点了，就说明可以离开屏障，整个计算任务已结束。

ZooKeeper 的实现

ZooKeeper 通过将数据复制到每台服务器上来实现服务的高可用。ZooKeeper 处理的服务器异常针对的是服务器宕机，且这些异常的服务器可能之后会恢复。下图展示了 ZooKeeper 服务的主要组件。当 ZooKeeper 服务收到一个请求时，会对这个请求进行预处理（request processor），如果这个请求需要各服务器协同完成（例如写请求），则会通过一致性协议处理（一种 atomic broadcast 的实现），最终 ZooKeeper 会将修改提交到各服务器副本中。而对于读请求，服务端则直接从本地数据库中读取数据然后返回给客户端。

alt

上图中的复制数据库是包含了整个数据树（data tree）的内存数据库。每个 znode 默认最多保存 1MB 数据，不过这个值可以根据需要通过配置修改。从可恢复性考虑，ZooKeeper 会高效的将更新写入到磁盘，并且将更新写入到内存数据库前会先强制将数据刷新到磁盘中。类似于 Chubby，ZooKeeper 也会将提交的操作写入到重放日志中，并且会周期性的对内存数据库生成快照。

每个 ZooKeeper 服务端都能对客户端提供服务。客户端只会连接一个服务端然后提交请求。在之前提到过，读请求会直接返回当前服务端本地的数据。而修改系统状态的请求、写请求则会交由一致性协议处理。

作为一致性协议的一部分，客户端的写请求会转发给单台服务器，称之为主节点（leader）。其他的 ZooKeeper 服务器被称之为从节点（followers），从节点会收到来自主节点的状态更新请求，并就状态更新达成一致。

请求处理器（Request Processor）

由于 ZooKeeper 的消息层是原子的，它保证各副本的状态不会和主节点产生分歧，虽然在任一时间点有可能某些副本会比其他副本多提交一些事务。和客户端发送的请求不同，ZooKeeper 中的事务是幂等的。当主节点收到一个写请求时，它会先计算出系统提交了这个写请求后的系统状态，然后将其转化为一个能达到该系统状态的事务。这里之所以要先计算出将来的状态是因为当前可能存在未提交的事务。例如，当前客户端正在进行一个 setData 的条件更新，请求中的版本号和被修改的 znode 的某个未来的版本号所匹配，ZooKeeper 会生成一个 setDataTXN 事务，这个事务包含了更新后的数据，更新后的版本号，以及更新的时间戳。而如果发生了异常，例如 setData 期望的版本号不匹配或者要更新的 znode 不存在，则会生成一个 errorTXN 错误。

原子广播（Atomic Broadcast）

所有更新 ZooKeeper 状态的请求都会被转发给主节点。主节点会执行写请求然后将写请求通过 Zab 协议广播给所有的从节点，Zab 是一种原子的广播协议。当主节点就更新达成一致后，会返回结果给客户端。Zab 默认使用的是简单的大多数同意协议，所以只有过半数的节点存活时 Zab 和 ZooKeeper 才能正常工作（例如，由 2f + 1 个节点组成的 ZooKeeper 系统可以最多容忍 f 台节点异常）。

为了提高系统的吞吐，ZooKeeper 会尽量保持请求处理管道满载运行。请求管道的不同部分可能有着几千个请求。因为系统状态变更依赖于之前的状态变更，所以 Zab 比常规的原子广播协议提供了更强的顺序保证。具体来说，Zab 保证了主节点广播的状态变更被分发执行的顺序和主节点发出广播的顺序一致，同时 Zab 会先将之前主节点的修改先发送给新的主节点，等到这些修改都执行完成后，新的主节点才能广播自己的修改。

另外还有些实现细节有利于高性能。ZooKeeper 使用 TCP 协议来发送消息，所以消息的有序性天然得到了保证，这同时也简化了实现。ZooKeeper 使用 Zab 协议选择的主节点作为集群的主节点，这就使得创建事务的节点同时也能发起事务。ZooKeeper 使用日志来记录事务的发起，这同时也作为内存数据库的预写日志，从而避免了将消息写入到磁盘两次。

在正常情况下 Zab 协议能按序发送所有消息，且每条消息只发送一次，不过由于 Zab 不会持久化已发送的消息的 id，所以在宕机恢复时可能会重复发送消息。因为 ZooKeeper 的事务是原子的，所以只要消息依然能保证有序发送，重复发送就没有问题。实际上，ZooKeeper 会要求 Zab 再次发送至少上次快照开始后的所有已发送的消息。

复制数据库（Replicated Database）

每个副本在内存中都有一份 ZooKeeper 状态的拷贝。当 ZooKeeper 宕机重启后，它需要能恢复到宕机前的状态。如果重新发送所有已发送的消息来恢复状态则需要较长时间，尤其是当服务器已经运行了一段时间之后，所以 ZooKeeper 周期性的对系统状态建立快照，并且只重新发送快照之后的所有消息。ZooKeeper 的快照被称之为 fuzzy snapshots 因为执行快照时不会加锁；ZooKeeper 会对数据树进行深度优先搜索，并且能原子的读取每个 znode 的数据和元数据，然后将其写入到磁盘中。这种方式生成的快照有可能包含部分在生成快照期间执行的事务的结果，最终生成的快照可能不会和任一时间点的 ZooKeeper 状态一致。不过由于状态更新是原子的，ZooKeeper 可以在后续恢复阶段重新按序执行已提交的事务。

例如，当 ZooKeeper 开始执行快照时有两个节点 /foo 和 /goo，对应的节点值分别为 f1 和 g1，节点值的版本号都是1。此时，对系统状态的修改以 <transactionType, path, value, new-version> 的形式到达：

1
2
3
<SetDataTXN, /foo, f2, 2>
<SetDataTXN, /goo, g2, 2>
<SetDataTXN, /foo, f3, 3>

当系统执行了这些更新后，节点 /foo 的值变为 f3，对应版本号为3，而节点 /goo 的值变为 g2，对应版本号为2。不过，执行 fuzzy snapshot 后的快照中的节点 /foo 的值可能是 f3，而节点 /goo 的值可能是 g1，对应版本号分别为3和1，这并不是一个有效的 ZooKeeper 系统状态。如果服务器宕机后恢复，系统会先读取快照然后重新发送状态更新消息，由于消息执行的顺序性，最终系统的状态和宕机前的状态保存一致。

客户端-服务端交互（Client-Server Interactions）

当 ZooKeeper 处理了一个写请求时，它会给所有监听了该节点的客户端发送数据更新通知，并同时删除该节点的监听（因为监听只会触发一次）。服务端会按顺序处理写请求，而且同时不会并发的处理其他写请求或者读请求。这就保证了严格的监听通知顺序。不过服务端的监听通知是由各服务器自行负责，只有和当前服务器连接的客户端才会收到通知，其他客户端对同一节点的监听由其他服务器负责。

读请求由当前客户端所连接的服务端直接读取内存中的数据返回。每个读请求处理时会标记上一个 zxid，这个 zxid 对应当前服务端所知道的最新的事务。这个 zxid 定义了读写操作之间的相对顺序。通过直接读取内存中的数据返回的方式来处理读请求，ZooKeeper 能保证非常好的读性能，因为这不涉及任何磁盘 IO 或者其他一致性协议。这个设计是满足读密集型应用对性能要求的关键点。

直接从本地内存读取数据的一个缺点是不保证一定能读取到最新更新的数据，即可能返回过期的数据，即使当前节点的更新已经被 ZooKeeper 所提交，因为只要过半数的节点已完成数据更新就可以认为本次数据已提交，而当前节点可能还没有执行更新。对于必须保证读操作能读取到最新的数据的应用，ZooKeeper 提供了 sync 接口。sync 原语能异步执行，并且会由主节点将所有待写入的更新应用到当前副本中。如果希望读操作能读取到最新的数据，客户端需要在执行读操作前调用 sync 方法。ZooKeeper 对客户端操作的 FIFO 执行顺序保证以及 sync 写操作的全局顺序保证使得读操作在执行读时 sync 发起之前的所有写操作都已经应用到了当前服务器中。在 ZooKeeper 的实现中，执行 sync 操作时不需要原子广播协议，因为使用了基于主节点的算法，只需要将 sync 请求放在主节点和当前节点的请求队列的末尾即可。这种方式能正确工作的前提是当前的主节点依然是主节点。如果当前主节点还有进行中的事务并提交，那么从节点就可以认为当前主节点依然是主节点。如果主节点的请求队列为空，那么主节点就会先提交一个空的事务然后再发起 sync 请求。这样当主节点处于低负载运行时，不需要生成额外的广播请求。在 ZooKeeper 的实现中，主节点会有一段过期时间，所以主节点自己就能知道什么时候不再是主节点，从而不再发起空事务。

ZooKeeper 的服务器会以 FIFO 的顺序来处理客户端请求。响应结果中会附带上 zxid。即使客户端和服务端之间没有请求，在常规的心跳返回中也会附带上当前服务端所知道的最新的 zxid。如果客户端连接上了一台新的服务器，那么这个服务器会保证自己所知道的 zxid 不会比客户端的 zxid 旧。如果客户端发送的 zxid 更新，那么服务端在将自己本地的数据更新到最新前不会和客户端再建立连接。而 ZooKeeper 能保证客户端能连接上一台数据版本满足 zxid 的服务端，因为客户端连接到的服务器必然是过半数有着最新系统状态的服务器之一。这个行为对保证持久性来说至关重要。

ZooKeeper 使用超时来检测客户端的 session 异常。如果在 session timeout 期间没有一台服务器收到来自客户端的请求，那么主节点就会认为发生了异常。如果客户端发送请求的频率足够高，那么就不需要发送其他消息来告诉主节点没有异常。否则，在非活跃期间客户端会发送心跳来维持连接。如果客户端和某台服务器无法发送请求或者心跳，那么客户端会和另外一台服务器建立连接。为了避免客户端的 session 过期，ZooKeeper 客户端类库会在 session 空闲了 s/3 毫秒后发送心跳，并且如果在 2s/3 毫秒内没有收到响应则会连接上另外一台服务器，这里的 s 指的是 session 的过期时间，以毫秒为单位。

参考