ZooKeeper 论文精读

info

ZooKeeper: wait-free coordination for internet-scale systems 用于互联网规模系统的无阻塞协调服务

• 中文翻译: https://github.com/mapleFU/zookeeper_paper_cn
• 论文精读理解: 论文精读理解

00 Abstract

在这篇论文中，我们描述了 ZooKeeper，一个协调分布式应用的服务。ZooKeeper 是基础架构的一部分，目标是提供一个简单的、高性能的内核，供客户端构建更复杂的协调原语。它在多副本、中心化的服务中，组合了消息群发(group messaging), 共享寄存器(shared registers)和分布式锁(Distributed Lock)服务。ZooKeeper 提供的接口有 wait-free 的共享寄存器和一个事件驱动机制，与分布式文件系统的 cache 失效机制类似，提供了一个简单但功能强大的协调服务。

ZooKeeper 接口支持实现高性能服务。除了 wait-free 的属性之外，ZooKeeper 还为每个客户端请求提供了 FIFO 执行的语义，和 ZooKeeper 状态更新请求线性化(Linearizable) 的语义。通过这些设计决策， ZooKeeper 的本地服务器可以处理读请求，从而实现高性能请求处理流水线。对于目标工作负载，读/写请求比例为 2:1 到 100:1，表明 ZooKeeper 每秒可以处理成千上万的事务。 这种性能使 ZooKeeper 可以广泛应用于各种客户端应用程序。

01 Introduction

大规模的分布式应用需要不同形式的协调。配置是最基础的形式之一。配置最简单的形式仅仅是作为系统进程的运行参数列表，而更多复杂系统有动态的配置参数。集群关系(Group Membership)和领导选举(Leader Election)在分布式系统中也很常见：通常，进程需要知道哪些其他进程是可用的(alive)以及这些进程负责什么。锁(Locks)建立了一个强大的同步原语，实现对关键资源的互斥访问。

一种协调的方式是，为不同的需求开发不同的服务。例如，Amazon Simple Queue Service 专注于队列服务。另外一些服务专门用于领导选举和配置。实现了更强原语的服务可以被用于实现没有那么强大原语的服务。例如，Chubby 是一个有很强同步保证的锁服务。锁可以用来实现领导选举，组成员等服务。

当设计我们的协调服务的时候，我们抛弃了在服务端侧实现特定的原语，作为替代，我们选择暴露一个能够使应用开发者实现他们自己同步原语的 API。这样的决定让我们实现一个不需要改变 ZooKeeper 即可实现不同服务的协调内核。这种方法允许用户实现多种形式的协调，以适应应用程序的需求，而不是将开发人员限制在一组固定的原语上。

当设计 ZooKeeper 的 API 的时候，我们抛弃了阻塞原语，例如 Locks。阻塞原语对于一个协调服务会引起其它问题，速度较慢或者故障的客户端会对速度较快的客户端产生负面的影响。如果请求的处理需要依赖其它客户端的响应和故障检测，则服务本身的实现将会变得更加复杂。因此，我们的系统 ZooKeeper 实现了一个 API，该 API 可以按文件系统的层次结构来组织简单的 wait-free 数据对象。 实际上，ZooKeeper API 类似于任何其他文件系统，并且仅从 API 签名来看，ZooKeeper 很像没有锁定(lock)方法，打开(open)和关闭(close)方法的 Chubby。 但是，实现 wait-free 数据对象使 ZooKeeper 与基于锁之类的阻塞原语的系统明显不同。

尽管 wait-free 对于性能和容错性很重要，但不足以进行协调。我们还必须提供操作的顺序保证。特别是，我们发现，对客户端所有操作提供 FIFO 语义与提供 linearizable writes 可以高效的实现服务，并且足以实现应用程序感兴趣的协调原语。实际上，对于任意数量使用 API 的进程，都可以实现一致性，根据 Herlihy 给出的层次结构，ZooKeeper 实现了全局的对象。

ZooKeeper 使用副本来保证服务的高可用和性能。它的高性能使包含大量进程的应用程序可以使用这种协调内核来管理协调的各个方面。我们能够使用一个简单的流水线架构，让我们在处理成百上千个请求的同时仍然保持低延迟。这样的流水线很自然地可以保证单个客户端按照 FIFO 的顺序执行操作。客户端的 FIFO 顺序使得客户端可以异步提交操作请求。使用异步操作，客户端一次可以执行多个未完成的操作。这个功能是很实用的，例如，当新客户端成为领导者时，它需要对相应的元数据进行修改和更新。如果不能并行的执行多个未完成的操作，则初始化时间将会是秒级而不是亚秒级。

为了保证更新操作满足 linearizability，我们实现了一个基于 leader 的原子广播协议 Zab。一个 ZooKeeper 应用的典型工作负载来自读操作，所以需要保证读吞吐量的扩展性。在 ZooKeeper 中，服务器在本地处理读操作，并不需要使用 Zab 来广播。

在客户端侧缓存数据是提升读性能的重要技术。例如，对于一个进程，缓存现有 Leader 的 id，而不是每次需要时都探测 ZooKeeper。ZooKeeper 并不直接操作缓存，而是使用一种 watch 机制。有了 watch 机制，一个客户端可以 watch 一个给定的对象，并在该对象更新时收到提醒。(作为对比) Chubby 直接管理客户端的 cache，它会阻塞更新，以使更新部分的客户端的缓存全部失效。在这样的设计下，如果任何客户端响应慢或者出现错误，更新会变得很慢。Chubby 使用 lease 机制防止一个慢或者宕机的客户端阻塞系统。但 leases 只能约束慢客户端或者宕机客户端的影响，ZooKeeper 的 watches 可以完全避免这个问题。

本论文讨论 ZooKeeper 的设计和实现，使用 ZooKeeper，我们可以实现应用程序所需的所有协调原语，即使只有写入是可线性化的。 为了验证我们的方法，我们展示了如何使用 ZooKeeper 实现一些协调原语。

作为总结，这篇文章中，我们主要的贡献是:

• Coordination kernel: 我们提出了一种 wait-free 的协调服务，可用于在分布式系统中提供宽松的(relaxed)一致性保证。特别是，我们描述了协调内核的设计和实现，我们已经在许多关键应用程序中使用了协调内核来实现各种协调技术。
• Coordination recipes: 我们展示了如何使用 ZooKeeper 在分布式系统中构建高级协调原语，甚至是常用的阻塞和强一致性原语
• Experience with Coordination: 我们分享了一些我们使用 ZooKeeper 的方式，并评估其性能。

02 The ZooKeeper Service

客户端通过 API 使用 ZooKeeper 客户端库来想 ZooKeeper 提交请求. 除了提供 API 供客户端联系 ZooKeeper 外, ZooKeeper 库还负责管理客户端和服务器之间的网络连接。

在本节中, 我们首先提供一个 ZooKeeper 服务端高层次描述, 然后讨论了客户端使用的与 ZooKeeper 服务器交互的 API.

• 客户端 (client): 指使用 ZooKeeper 服务的用户或进程。
• 服务器 (server): 指提供 ZooKeeper 服务的进程。
• znode: 指 ZooKeeper 中的数据节点，这些节点存储在内存中，并组织在一个称为数据树 (data tree) 的层级命名空间中。
• 数据树 (data tree): znode 组成的层级命名空间结构，用于组织和存储 ZooKeeper 的数据节点。
• 更新和写入 (update and write): 指任何修改数据树状态的操作。
• 会话 (session): 客户端连接到 ZooKeeper 时建立的连接状态，客户端通过会话句柄发送请求。

2.1 Service Overview

ZooKeeper 给它的客户端提供“若干数据节点(znodes)”的抽象，这些数据节点通过分层的命名空间来组织。客户端通过 ZooKeeper API 操纵在这个层级中的数据对象。分层的命名空间被广泛应用于文件系统里。这是一种可靠的数据对象组织方式，因为用户已经习惯了这种抽象，同时它可以更好的组织应用程序元数据。为了引用一个给定的 znode ，我们使用标准的 UNIX 文件系统路径符号。例如，我们使用 /A/B/C 来表示一条到 znode C 的路径，B 是 C 的父节点，同时 A 是 B 的父节点。所有的 znode 都存储数据，并且除了临时节点(ephemeral znodes)外的所有 znode 都能拥有子节点。

客户端可以创建两种 znode:

• 常规节点 Regular: client 可以通过创建或删除来显式操纵 regular znodes；
• 临时节点 Ephemeral: client 创建临时节点，这类节点要么显式删除它们，要么让系统在创建它们的会话终止时(故意或由于故障)自动删除它们。

此外，当客户端创建新的 znode 的时候，可以设置 sequential 标志。带有 sequential 标志创建的节点会在节点名称后附加一个单调递增的计数器的值。如果 n 是新的 znode, p 是 n 的父节点，那么 n 的附加值不会小于 p 已有子节点的任何一个附加值。

ZooKeeper 通过实现 watch 来让 client 不需要轮询即可及时接收到值变化的通知。当客户端设置 watch 标志发起读取操作时，除了服务器承诺在返回的信息发生变化时通知客户端外，其他操作都会正常完成。 Watches 是与会话关联的一次性触发器； 一旦被触发或者该会话关闭，它们将被注销。 Watches 表明节点发生了变更，但并不提供变更的内容。 例如，如果客户端在两次更改 /foo 之前发出了请求 getData('/foo'，true)，则客户端将只获得一个 watch 事件，告知客户端/foo 的数据已更改。会话事件(例如连接丢失事件)也将发送到 watch 回调，以便客户端知道 watch 事件可能会延迟。

Data model

ZooKeeper 的数据模型本质上是一个简化了 API 的文件系统，只支持完整数据的读写，或者可以说是一个带有层级式 key 的 key/value 表。分层命名空间便于为不同应用的命名空间分配子树，也便于为这些子树设置访问权限。

与文件系统中的文件不同，znodes 不是为通用数据存储设计的。 相反，znodes 映射到客户端应用程序的抽象，通常与用于协调的元数据相对应。为了说明， Figure 1 中有两个子树，一个用于应用程序 1 (/app1)，另一个用于应用程序 2 (/app2)。应用程序 1 的子树实现了一个简单的组成员身份协议(group membership protocol):每个客户端进程 pi 在 /app1 下创建一个 znode p_i ，只要该进程还在运行，节点便会持续存在。

尽管 znode 并非为通用数据存储设计，但是 ZooKeeper 允许客户端存储一些可用于分布式计算中的元数据或配置的信息。例如，在基于主节点(leader-based)的应用程序中，对其他应用程序的服务而言，znode 非常便于用来确定当前的主节点是哪个服务器。为了实现这种方式，我们可以让当前的主节点在 znode 空间中的已知位置写入信息。 znode 还将元数据与时间戳(timestamp)和版本计数器( version counter )关联，这样客户端就可以跟踪对 znode 的更改并根据 znode 的版本执行条件更新。

Sessions

客户端连接到 ZooKeeper 并初始化 session。session 具有关联的超时时间 timeout。如果 ZooKeeper 在 超时时间内没有收到来自创建 session 的客户端的任何消息，则认为该客户端故障。 当客户端显式关闭会话句柄或 ZooKeeper 检测到客户端故障时，会话结束。在 session 中，客户端可以观察到一系列反应其操作执行的状态变化。 session 使客户端能够在 ZooKeeper 集群中透明地从一台服务器转移到另一台服务器，从而在 ZooKeeper 服务器之间持续存在。

2.2 Client API

我们在下方展示了一个 ZooKeeper API 的子集，并讨论了每个请求的语义:

• create(path, data, flags): 根据路径名称 path，它存储的 data[]，创建一个 znode, 并返回这个新的 znode 的名称。flags 允许客户端选择选定的 znode 类型：regular, ephemeral 及设置 sequential flag。
• delete(path, version): 如果 znode 符合给定的 version 版本，则删除 path 下的 znode。
• exists(path, watch): 如果 path 下的 znode 存在，返回 true, 否则返回 false.watch 标志可以使 client 在 znode 上设置 watch。
• getData(path, watch): 返回 znode 的数据和 znode 相关的元数据 (例如版本信息)。watch 和 exists() 里面的作用一样，不同之处在于，如果 znode 不存在，则 ZooKeeper 不会设置 watch。
• setData(path, data, version): 如果 version 是 znode 现有的版本，把 data[] 写进 znode.
• getChildren(path, watch): 返回 path 对应的 znode 的子节点集合。
• sync(path): 等待操作开始时所有没有同步的更新传播到 client 连接到的服务器。 该 path 当前被忽略。

API 中的所有的方法都有一个同步版本和一个异步版本。 当应用程序需要执行单个 ZooKeeper 操作且没有要并发执行的任务时，使用同步 API，因此它会进行必要的 ZooKeeper 调用并进行阻塞。但是，异步 API 使应用程序可以并行执行多个未完成的 ZooKeeper 操作和其他任务。ZooKeeper 客户端保证每个操作的相应回调按照按顺序调用。

需要注意的是，ZooKeeper 不使用句柄来操纵 znode。相反，每个请求都带有需要操作的 znode 的完整路径。这样不仅仅简化了 API (没有 open() 和 close() 方法)，也消除了服务器需要维护的额外状态。

每种更新方法均需要一个预期的 version，从而可以实现条件更新。如果 znode 的实际版本号与预期版本号不匹配，则更新将失败，并出现 unexpected version error。如果给定的预期版本号为 -1，则不执行版本检查。

2.3 ZooKeeper guarantees

ZooKeeper 有两个基本的顺序保证

• 线性写入 Linearizable Writes: 所有的更新 ZooKeeper 状态的请求都是 serializable，并且遵循优先级。
• FIFO 的客户端顺序 FIFO client order: 给定客户端发送的所有请求都按照客户端发送顺序有序执行。

注意我们对 linearizability 的定义和 Herihy 提出的原始定义不同，我们叫它 A-linearizability (asynchronize linearizability 异步线性)。 在 Herilihy 的原始 linearizable 定义中，一个客户端在同一时间只能有一个未完成的请求 (一个客户端是一个线程)。在我们的系统中，允许一个客户端有多个未完成的操作，所以我们可以选择不保证未完成操作的执行顺序，或者保证 FIFO 顺序。我们选择后者作为 ZooKeeper 的属性。可以观察到，对于保持 linearizable 对象也会保持 A-linearizable ，因为满足 A-linearizable 的系统也必然满足 linearizable。由于只有更新请求是 A-linearizable 的，ZooKeeper 在每个副本本地处理读请求。因此，当系统添加服务器时，服务可以线型扩展。

为了了解两个保证是怎么交互的，考虑以下场景。系统由一组进程组成，它选择出一个 leader，并由 leader 操作工作进程。当一个新的 Leader 接管整个系统时，它必须更新大量的配置参数，并在更新结束的时候通知其它进程。这样我们有两个重要的需求

• 当新的 Leader 开始更改系统时，我们不希望其它进程开始使用正在被更改的配置。
• 当新的 Leader 在配置完全更新完成之前就宕机时，我们不希望其它进程使用半更新的配置。

注意到，分布式锁，例如 Chubby 提供的锁，可以满足需求 1，但是无法满足需求 2。有了 ZooKeeper，新的 Leader 可以指定一个路径作为 ready znode，其他的进程只会在这个 znode 存在的时候使用这套配置。新的 leader 靠 删除 ready, 更新各种配置的 znode, 重新创建 ready 来完成上述需求。上述的所有变更可以被流水线处理，并发起一个异步请求来快速更新配置状态。尽管更改操作的延迟约为 2 毫秒，但是如果一个请求接一个发出 (即同步的一个一个请求处理)，则需要更新 5000 个不同 znode 的新 leader 将花费 10 秒。 通过异步发出请求，请求将花费不到一秒钟的时间。由于顺序保证，如果进程看到 ready znode，则它还必须看到新的 Leader 所做的所有配置更改。 如果新的 Leader 在创建完 ready znode 之前宕机，则其他进程知道该配置尚未完成，因此不使用它。

上述的模式仍然有一个问题：如果一个进程在新的领导开始进行变更之前看到 ready 存在，然后在变更进行中开始读取配置，会发生什么？这个问题通过 notification 的顺序保证解决：如果一个客户端正在 watch 一个变更，这个客户端会在它看到配置变更之前收到一个通知。因此，如果读取 ready znode 的进程请求要在 znode 变更的时候被通知，它的 client 会在收到配置变化之前，收到 ready znode 变化的通知。

当 client 除了 ZooKeeper 之外还拥有自己的通信信道时，可能会出现另一个问题。 例如，考虑两个客户端 A、B 在 ZooKeeper 中有共享的配置，并通过一个共享的通信信道通信。如果 A 更改了 ZooKeeper 中的共享配置，并通过 channel 告知 B，B 会期望在重新读取的时候看到配置的变化。 如果 B 的 ZooKeeper 副本稍微落后于 A，则可能看不到新配置(因为读是在本地进行的) 。使用上一段中的保证 B 可以通过在重新读取配置之前发出写入操作来确保它能看到最新信息。为了更有效地处理这种情况，ZooKeeper 提供了 sync 请求：当 sync 请求之后，下一个请求是读，则构成了一个慢速的读取。sync 使服务器在处理读操作前应用所有之前未完成的写请求，节省了一次全量写 (full write)的开销。这一原语与 ISIS 的 flush 原语类似。

ZooKeeper 也有下述两个存活性 liveness 和持久性保证:

• 如果大部分 ZooKeeper 服务器是活跃的并且可以通信，ZooKeeper 服务是可用的。
• 若服务对于某个更新请求成功响应，只要服务 (quorum 数量的节点)能最终恢复，变更就能在任何数量的故障中持久化。

2.4 Examples of primitives

在本节中，我们将展示如何使用 ZooKeeper API 来实现更强大的原语。 ZooKeeper 服务对这些更强大的原语一无所知，因为它们是完全使用 ZooKeeper client API 在客户端上实现的。 一些常见的原语(例如 group membership 和配置管理) 也是 wait-free 的。 对于其他场景，例如 rendezvous，client 需要等待事件。 虽说 ZooKeeper 无需等待，但我们也可以使用 ZooKeeper 实现高效的阻塞原语。ZooKeeper 的顺序保证允许对系统状态进行有效的推理，而 watch 则可以进行有效的等待。

配置管理

ZooKeeper 可以被用来实现分布式应用中的动态配置。在它最简单的形式中，配置被存储在 znode Zc 中， 进程以 Zc 的完整路径名启动。启动进程通过读取 Zc 并将 watch 标志设置为 true 来获取其配置。如果 Zc 中的配置出现任何更新，进程会收到通知并读取新配置，然后再次将 watch 标志设置为 true。

注意在这个模式中，如同大部分其它使用 watch 的模式，watch 被用来保证进程有最近的信息。例如，如果一个 watch Zc 的进程收到了 Zc 发生变化的通知，而在它读取 Zc 之前又发生了三个对 Zc 的更改，那么这个进程不会收到后续事件的三个通知。这并不会影响进程的行为，因为这三个事件只是简单的通知进程它已经知道的信息：它拥有的关于 Zc 的信息已经过期了。

Rendezvous 信息汇合

有时在分布式系统中，我们不会预先知道最终的系统配置会是什么样子的。例如，一个客户端可能需要启动一个 master 进程和一些 worker 进程，但是启动进程是由调度器完成的，所以客户端无法提前知道连接 master 需要的 Address 和 Port 等相关的信息。我们通过 client 创建 rendezvous znode (即 Zr) 来解决这个问题。客户端把 Zr 的整个路径作为启动参数传给 master 和 worker 进程。当 master 启动时，它会把自己的地址和端口信息填充进 Zr. 当 workers 启动的时候，它们会以 watch flag 读取 Zr。如果 Zr 还没有被填充， worker 就会等待 Zr 被更新。如果 Zr 是一个 ephemeral 节点，master 和 worker 进程可以 watch Zr 是否被删除，并在 client 终止时自行清理

Group Membership 组成员管理

我们利用 ephemral 节点来实现 group membership. 更确切地说，我们利用了 ephemeral 节点允许我们看到创建 znode 的 session 状态的特性。我们从指定一个 znode Zg，来代表这个 group 开始。当一个 group 的成员启动后，它在 Zg 下创建一个临时节点。如果每个进程都有一个唯一的名称或者标识符，那么这个名称就会被用作创建的子 znode 的名称; 否则，他会用 SEQUENTIAL flag 来创建一个有唯一名称的 znode。进程可以将进程信息放入子 znode 的数据中，比如该进程使用的地址和端口。

在 Zg 下创建子 znode 后，该进程将正常启动。不需要额外的操作。如果进程失败或结束，在 Zg 下代表该进程的 znode 会被自动删除。

进程可以通过简单列出 Zg 的孩子来获取组信息。 如果某个进程希望监视组成员身份的更改，则该进程可以将监视标志设置为 true，并在收到更改通知时刷新组信息(这个进程始终将监视标志设置为 true)。

Simple Locks 简单锁

尽管 ZooKeeper 不是锁服务，但可以用来实现锁。使用 ZooKeeper 的应用程序通常使用根据其需求量身定制的同步原语，例如上面所示的那些。在这里，我们展示了如何使用 ZooKeeper 实现锁，以表明它可以实现各种各样的常规同步原语。

最简单的锁实现使用 lock files. 该锁由 znode 表示。为了获取锁，客户端尝试使用 EPHEMERAL 标志创建指定的 znode。如果创建成功，则客户端将持有该锁。否则，客户端可以设置 watch 标志读取 znode，以便在当前领导者宕机或显式删除 znode 以释放锁时，得到通知。其他等待锁定的客户端一旦观察到 znode 被删除，就会再次尝试获取锁 (即创建 znode)。

尽管此简单的锁定协议有效，但确实存在一些问题。首先，它具有惊群效应。如果有许多等待获取锁的客户端，则即使只有一个客户端可以获取锁，他们也会争夺该锁。其次，它仅实现互斥锁(没有实现读写锁等模式)。以下两个原语显示了如何同时解决这两个问题。

Simple Locks without Herd Effect

Herd Effect 羊群效应 指的是在分布式系统中，多个客户端同时对某个共享资源的状态变化作出反应，导致大量无效的资源竞争、负载增加或者性能下降的现象。具体来说，当锁释放或资源状态改变时，所有等待的客户端都同时被唤醒，去争抢同一个锁或资源，这种大规模的唤醒和竞争就像一群羊同时奔向一个草地，因此被称为羊群效应。

我们定义一个锁 znode=l 来实现这种锁。 直观地说，我们令所有请求锁定的客户端排队，每个客户端都按照请求到达的顺序获得锁。 因此，希望获得该锁的客户端执行以下操作：

Lock
1: n = create(1 + "/lock-", EPHEMERAL | SEQUENTIAL)
2: C = getChildren(1, 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 行中使用 SEQUENTIAL 标志，命令 client 尝试获取锁，并且所有尝试拿锁的客户端都将获得一个序列号。如果客户端的 znode 在第 3 行的序列号最小，则客户端将持有该锁。否则，客户端将等待下列两种 znode 被删除: 持有 Lock 的 znode，将在此客户端的 znode 之前获得锁的 znode 。通过仅查看客户端 znode 之前的 znode，我们仅在释放锁或放弃锁请求时才唤醒一个进程，从而避免了惊群效应。客户端 watch 的 znode 消失后，客户端必须检查它现在是否持有该锁。（先前的 Lock 请求可能已被放弃，或者具有较低序号的 znode 仍在等待或持有锁。）

释放锁就简单地直接删除代表 Lock 请求的 znode=n. 通过在创建 znode 时使用 EPHEMERAL 标志，崩溃的进程将自动清除所有锁定请求或释放它们可能拥有的任何锁定。

总之, 这样上锁的方案有以下几个优点:

• 节点的删除只会让一个客户端唤醒, 因为一个节点只会被一个进程 watch, 所以没有羊群效应.
• 没有轮询和超时机制.
• 因为上锁的实现机制, 我们可以通过查看 ZooKeeper 的数据来观察锁的竞争, 打断上锁, 以及调试上锁时出现的问题.

Read/Write Locks

为了实现读/写锁，我们略微更改了锁过程，并分别设置了读锁和写锁。 解锁过程与全局锁定情况相同。

Write Lock:
1: n = create(1 + "write-", EPHEMERAL|SEQUENTIAL)
2: c = getChildren(1, 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(1 + "read-", EPHEMERAL|SEQUENTIAL)
2: c = getChildren(1, 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 (这里论文写的是 goto 3, 经网友提醒, 实际上应该是 goto 2)

此上锁的机制和之前的方法有些许区别. 写锁只是改了个函数名. 因为读锁可以共享, 第三行和第四行变化了一下, 因为只有之前的写锁会阻止一个读锁的上锁. 这里可能会出现惊群效应, 当一个写锁被删掉时, 之后的很多读锁都会被释放. 实际上, 这种惊群效应是我们期望得到的, 这些读锁都应给被释放, 因为之前没有了写锁.

Double Barrier

双重屏障允许客户端在计算的开始和结束进行同步. 当有足够多的进程进入到屏障中, 进程就会一起开始他们的计算, 并在完成时离开屏障. 我们在 ZooKeeper 中使用一个节点代表屏障, 用 b 来表示. 每个 p 进程通过创建一个节点作为 b 的子节点, 并在离开时删除这个子节点来取消注册.

双重屏障是一种同步机制，主要用于协调分布式系统中多个客户端在两个阶段的同步:

1. 进入屏障阶段: 确保所有客户端都达到某个状态后再开始计算。
2. 退出屏障阶段: 确保所有客户端都完成计算后再一起离开。

进程可以在 b 的子节点数量超过阈值时进入屏障, 并在所有的进程都删掉自己的子节点时离开屏障. 我们使用 watch 机制来高效的等待进入屏障和离开屏障. 要进入, 进程需要 watch 一个在子节点中的就绪节点的存在, 这个节点由创建节点时导致 b 的子节点数量达到阈值的进程创建. 要退出屏障时, 进程可以 watch 随便 watch 一个子节点并当他消失时判断是否可以退出.

• 进入屏障
  • 客户端监听/barrier/ready 结点, 通过判断该结点是否存在来决定是否启动任务
  • 每个任务进程进入屏障时创建一个临时节点/barrier/process/${process_id}，然后检查进入屏障的结点数是否达到指定的值
  • 如果达到了指定的值，就创建一个/barrier/ready 结点
  • 否则等待客户端收到/barrier/ready 创建的通知，以启动任务
• 离开屏障
  • 客户端监听/barrier/process节点，若子节点为空，离开屏障
  • 任务进程完成后，删除/barrier/process/${process_id}节点

03 ZooKeeper Applications

我们现在描述一些使用 ZooKeeper 的应用程序, 并简单的解释怎么使用它. 使用到的原语都会加粗.

3.1 The Fetching Service

爬虫抓取时搜索引擎的一个重要部分, 雅虎抓取了数十亿的网络页面. Fetching Service(FS) 是雅虎的一部分, 目前已经进入了生产环境. 本质上说, 有一个 Master 进程来控制抓取页面的进程. 主进程提供给抓取进程配置, 而抓取进程写回他们的状态和健康状况. 使用 ZooKeeper 来控制抓取服务端好处体现在主进程从错误中恢复, 在出错的情况下保证可用性, 以及对服务器和客户端解耦, 允许他们通过读取 ZooKeeper 中的状态来把请求发送给健康的服务器. 因此, FS 主要使用 ZooKeeper 来维护 configuration metadata, 以及 leader election.

图 2 展示了一个 ZooKeeper 服务器管理的抓取服务三天内读写的流量. 为了生成这张图, 我们每一秒钟都数了一下操作的数量, 每个点代表着这一秒钟的操作数. 我们发现读操作的流量远大于写操作. 在速度大于每秒 1000 次请求的时间段, 读写比基本在 10:1 至 100:1 之间. 在这个负载中, 读操作有 getData(), getChildren()和 exists(), 调用频率依次增加.

3.2 Katta

Katta 是一个分布式的索引器, 使用 ZooKeeper 来协调. 这是一个非 Yahoo 应用程序的例子. Katta 使用分片来划分索引的工作. Master 服务器把分片后的任务发送给 Slave 工作服务器, 并且追踪进度. 工作服务器可能会出错, 所以主服务器必须把任务重新分配到分片服务器上. Katta 使用 ZooKeeper 来追踪主服务器和工作服务器的状态(group membership), 处理领导者的崩溃(leader election). Katta 还使用 ZooKeeper 来追踪并传播任务的分发(configuration management).

3.3 Yahoo! Message Broker

Yahoo! Message Broker (YMB) 是一个分布式的发布-订阅系统, 这个系统管理数千个 Topics, Client 可以在里面发布和接受消息. 这些 Topics 分布在多个服务器上来提供可拓展性. 每个主题都使用主服务器备份的方法来保证消息在多个服务器之间复制, 保证消息的传递. 组成系统的服务器采用一个无共享的分布式结构, 这让协调的正确性非常重要. 系统使用 ZooKeeper 来管理标题的分配(configuration metadata), 处理机器的崩溃(failure detection and group membership), 以及控制系统操作.

图 3 显示了 YMB 的 znode 数据分布的一部分。 每个 broker 域都有一个称为节点的 znode，该节点对组成 YMB 服务的每个活跃的服务器都有一个 EPHERMERAL znode。每个 YMB 服务器创建一个带有负载和状态的 EPHERMERAL znode, 写入节点的负载和状态信息，来提供 group membership 和状态信息。表示 shutdown 和 migration_prohibited 的节点受所有服务器监视，并且允许对整个 YMB 的中心化控制。topics 目录下每个 topic 会创建一个子节点 znode，这些 topic znode 对于订阅它们的 topic 和从服务器也有子 znode. primary and backup 节点不仅允许服务器寻找到负责一个 topic 的服务器，还能在主服务器宕机后进行 领导选举 (leader election).

04 ZooKeeper Implementation

ZooKeeper 通过在每个服务器上复制 ZooKeeper 的数据提供了高可用性. 我们假设服务器会崩溃, 并且这些有问题的服务器会在之后一段时间重新恢复. 图 4 展示了 ZooKeeper 服务的一些高层次的组件. 接收到一个请求时, 服务器会首先进行一些准备工作 (Request Processor). 如果这个请求需要在多个服务器上协同(写请求), 就会使用 共识协议 Agreement Protocol(一个原子广播的实现), 最终所有的服务器都会执行这个操作到被所有服务器复制的 ZooKeeper 数据库中。如果是读操作, 服务器可以简单的读取本地数据库的状态并且对请求进行返回.

被复制的数据库是一个内存中的数据库, 包含了整个数据树. 每个树里的节点 znode 默认包含最多 1MB 的数据, 这个上限可以在特殊情况下改变. 对于可恢复性, 我们高效的把所有更新日志写入到硬盘里, 并且强制所有写操作在被应用到内存中数据库前先写入到硬盘里. 实际上, 跟 Chubby 一样, 我们保存一个包含着所有应用过的操作的重放日志 write-ahead log, 并且定期生成内存中数据库的快照.

每个 ZooKeeper 服务器都直接服务客户端. 客户端每次只向一个服务器提交请求. 向我们之前注意到的一样, 读请求直接从各个服务器的本地的数据库拿到返回. 而修改系统状态的写请求, 会被 Agreement Protocol 处理.

作为共识协议的一部分, 写请求被转发到一个单独的服务器上, 叫做 leader. 其他的服务器叫做 followers. 他们从 leader 接受包含状态变化的 proposal, 并对状态变化达成一致.

4.1 Request Processor

因为 Message Layer 是 atomic 的，我们保证副本不会出现分歧，尽管在某些时刻，一些服务器可能会应用了比其他服务器更多的事务。与客户端的请求不同，事务是幂等的 idempotent. 领导者收到写请求后，它将计算应用写操作时系统的状态，并将其转换为捕获该新状态的事务。 因为可能存在尚未应用到数据库的未完成事务，所以必须计算未来的状态. 例如，如果客户端执行条件 setData:

• 成功时。即请求中的版本号与正在更新的 znode 的未来的版本号匹配，则该服务将生成一个 setDataTXN，其中包含新数据, 新版本号, 更新的时间戳.
• 失败时。例如版本号不匹配或要更新的 znode 不存在，则会生成 errorTXN 错误.

4.2 Atomic Broadcast 原子广播

所有更新 ZooKeeper 的请求都会被转发给 leader, 然后由 leader 广播到 follower 上，通过原子广播协议 Zab 来广播状态变更。从客户端接收请求的服务器在收到对应的状态变更后响应客户端。Zab 默认使用简单的 majority quorum 来决定一个 proposal，所以 Zab 和 Zookeeper 只有在大多数机器正确相应的时候才能工作(i.e. 2f+1 台服务器，我们可以容忍 f failures).

为了实现高吞吐量, ZooKeeper 尝试让请求的处理流水线是满的. 流水线上可能会有几千个请求. 因为状态依赖于之前的状态变化, Zab 提供了比一般的原子广播更强的顺序保证. 更准确的说, Zab 保证:

• 保证 Leader 的变更广播按照发送顺序发送.
• 新的领导在收到 previous leaders 的所有变化之后才开始广播自己的变化.

在实现上:

• 使用 TCP 协议，保证了传输可靠 (完整性、顺序等) 以及高性能.
• 使用 Zab 选出的 Leader 作为 ZooKeeper 的 Leader.
• 使用 WAL 来记录 Zab 的广播.
• Zab 广播消息实现 exactly-once，由于事务是幂等的，且消息按顺序发送，则 Zab 重新广播（如恢复时）也是可以接受的. ZooKeeper 要求 Zab 在恢复时至少重新发送从最后一次快照之后开始的所有消息。 这确保了在快照之后的所有状态变更都能正确恢复。

为什么需要重新发送快照之后的消息:

1. 快照仅包含创建时的状态，但不能反映快照之后的状态变化。
2. 如果只恢复快照，系统会丢失快照之后的所有变更，导致状态不一致。
3. 从最近的快照恢复状态后，ZooKeeper 需要通过重新发送快照之后的所有消息，将系统恢复到故障前的完整状态。

4.3 Replicated Database 副本数据库

每个备份在内存中都有一个 ZooKeeper 的状态. 当一个 ZooKeeper 服务器从崩溃中恢复时, 他需要恢复他的初始状态. 重放所有的消息来恢复状态需要花费很长时间, 所以 ZooKeeper 使用周期的快照, 每次只需要从一个快照开始恢复一小段消息. 我们把 ZooKeeper 的快照叫做 Fuzzy Snapshot 模糊快照, 因为我们在生成快照的时候不会去对 ZooKeeper 使用 Write Lock 并获取快照, 而是在使用深度优先搜索读取每个节点的数据和元数据时做一次原子性的读, 并写入磁盘. 因为最后的模糊快照可能只应用了在生成快照期间产生的变化的子集, 所以最终的快照可能不代表任何时刻的 ZooKeeper 的状态. 然而, 因为状态是幂等的, 只要我们按照顺序读日志, 变更可应用多次，满足 exactly-once.

举个例子，假设 ZooKeeper 的数据树中，在模糊快照开始的时候，两个节点 /foo=f1 /goo=g1 at version=1. 接下来到达的状态变更流以形式 <事务类型, 路径, 值, 新版本> 表示:

<SetDataTxn, /foo, f2, 2>
<SetDataTxn, /goo. g2, 2>
<SetDataTxn, /foo, f3, 3>

在处理完这些状态变更后，/foo=f3 和 /goo=g2，并且版本是 3 和 2。然而，模糊快照可能记录 /foo=f3 和 /goo=g1 的值，并且版本是 3 和 1.这不是任何一个时刻的 ZooKeeper 状态. 如果服务器崩溃, 并且从这个快照开始恢复, 最终也能恢复到之前的状态.

4.4 Client-Server Interactions

当一个服务器处理 write request 时, 他同时发出并清空所有与这次更新相关的 watch. 服务器按照顺序处理 write request, 并且不会同时处理其他的 write/read request. 这保证了通知的严格一致性. 服务器在本地处理通知, 只有被客户端连接的服务器才会追踪并为客户端触发通知.

读请求在每个服务器本地处理. 每个读请求被处理的时候会被标上一个 zxid, 对应着这个服务器看到额最后一个事务. 这个 zxid 定义了 reads and writes 之间的偏序关系. 通过在服务器本地处理 reads, 我们得到了优秀的读性能, 因为这只是一个内存中的操作, 不设计磁盘和共识协议的运行. 这个设计是我们实现 read-dominant workloads 的性能关键.

即:

• 写请求:
  • 将更新相关的通知发出去，并将对应的 watch 清空
  • 写请求不会和任何请求并发进行（包括和读并发进行），严格按照顺序处理，这保证了通知的严格一致
  • 通知是在各个副本的本地进行，而并非全在 Leader
• 读请求:
  • 请求在各个副本的本地执行 (无读盘以及协商，性能很高)
  • 每个读请求被赋上 zxid，它等于最后一个服务端见到的事务

ZooKeeper 的快速读操作不保证读取的数据是最新的。例如, 即使一个写操作已经完成，快速读操作可能仍然返回旧数据。原因是写操作需要通过 leader 来传播和同步，而快速读直接从本地副本读取，可能尚未同步最新状态

但是有些应用场景要求 读取的数据必须是最新的(如强一致性需求).

为了解决这一问题，ZooKeeper 引入了 sync 原语，用于确保客户端读取到最新的数据。

• 什么是 sync 原语?
  • 一个阻塞操作，会等待所有服务器按照 Leader 的顺序执行完所有已提交的操作。
  • 客户端在调用 read 之前，先调用 sync。
  • 通过 sync 保证，read 读取到的数据会反映出在 sync 之前发起的所有操作的结果。
• 如何保证一致性?
  • 客户端操作的先进先出 FIFO 顺序: 即客户端的所有请求按照顺序依次处理。
  • sync 的保证: 阻塞等待，直到所有操作完成。
• 实现方式
  • sync 并不需要全局广播操作，而是将一个 sync 请求添加到 Leader 与请求的从节点 follower 的请求队列末尾。
  • 如果系统中没有事务需要提交，Leader 可能会发起一个空事务，并将 sync 放置在其后，以保证一致性。
  • 当领导者负载较低时，这种机制避免了额外的广播，提升了效率。
• 超时机制的优化
  • 如果 Leader 在超时时间内没有收到消息或心跳包, Follower 会怀疑其失效。
  • 在实现中，Leader 会主动检测超时并放弃 Leader 身份，避免额外发起空事务。