【MIT 6.824】学习笔记 6: ZooKeeper 设计原理

▲ 点击上方"多颗糖"关注公众号

本周学习 ZooKeeper，主要讨论以下两个问题：

• 分布式协调系统可以有一个独立的通用服务来处理吗？API 应该是什么样的？其他分布式应用程序如何使用它？

• 我们花了很多钱购买 N 倍数量的服务器，能否将系统的性能提高 N 倍？

由于网上讨论 ZooKeeper 的内容已经非常多了，本文尽量避免重复，但一些关键的内容还是需要反复讨论：ZooKeeper 的架构和两个保证，本文还讨论一些细节的问题，但不展开讨论如何使用 ZooKeeper 进行开发。

注：本文根据 6.824 教学视频和讲义整理，以论文 ZooKeeper: Wait-free coordination for Internet-scale systems 的内容为主，不讨论 Apache ZooKeeper 源码。

ZooKeeper 是什么？

ZooKeeper 是一个分布式协调服务，什么叫协调服务好像也比较抽象，具体来说，ZooKeeper 提供：

• 统一命名服务

• 配置管理

• 成员管理

• Leader 选举

• 协调分布式事务

• 分布式锁

就是分布式系统中经常用到的服务，ZooKeeper 并没有直接提供这些服务，而是提供 API 供开发者实现自己需要的服务。

ZooKeeper 是一个独立的、通用的服务，用来帮助开发者轻松构建分布式应用。相比于上一章学习的 Raft，Raft 可以用于一些多副本系统中，但一般来说 Raft 并不是一个可以直接交互的独立服务。ZooKeeper 实际上运行在 Zab 之上，站在一个更高的系统设计维度上看，Raft 和 Zab 是一样的，都是为了让多个服务器达成共识。至于 Zab 和 Raft 的细节异同，此文不表。

ZooKeeper 技术架构

和之前学习的 Raft 类似，ZooKeeper 集群分为 Leader 和 Follower；和 Raft 有所不同，Raft 只有 Leader 能处理读写请求，ZooKeeper 允许所有节点处理读请求，但写操作仍然只发送给 Leader，这样做的缺点是读操作可能会返回过时的数据，但提高了读的性能。考虑下 Raft，当我们加入更多服务器时，Leader 几乎可以确定是一个瓶颈，因为 Leader 需要处理每一个读写请求，需要将每个请求的拷贝发送给每个其他服务器，随着服务器数量的增加，Raft 系统的性能可能反而会降低。

ZooKeeper 专门为大量的读负载而设计的系统，所以允许所有节点处理读请求，除了 Leader 以外的任何一个副本的数据都可能不是最新的。

但如果系统都不提供线性一致性，我们为什么还要相信这个系统是可用的？

ZooKeeper 有两个基本的一致性保证：线性写和先进先出(FIFO)的客户端请求

线性写

All requests that update the state of ZooKeeper are serializable and respect precedence.

Leader 保证写操作的顺序，并且该顺序在所有 Follower 上保持一致。注意这里用了串行化(serializable)而不是线性一致性(linearizability)。

前面提到 ZooKeeper 不保证线性读。例如，client A 更新了键 X 的值，而 client B 在另一台服务器上读取键 X 的值可能会读到更新之前的值——ZooKeeper 只保证线性写

先进先出的客户端请求

All requests from a given client are executed in the order that they were sent by the client.

另一个保证是，每个客户端可以为其操作(读和写)指定一个顺序，ZooKeeper 会按照客户端指定的顺序来执行。

该如何理解这里呢？分两种情况讨论。

对于写请求，所有的写请求会以客户端发送的相对顺序，加入到所有客户端的写请求中，保证满足线性写。所以如果一个客户端要求，先完成写操作 A，接着写操作 B，之后是写操作 C，那么，在最终整体的写请求中将看到是先写 A 再写 B 再写 C 的，但 A B C 可能不是相邻的。

对于读请求，由于读请求不需要经过 Leader，可能会复杂一些，多个读请求可能先在先在某个副本，但这个副本宕机了，剩余读请求切换到了另外的副本上。

ZooKeeper 通过 zxid 来实现，zxid 是最后一个事务的标记，当客户端发出一个请求到一个相同或者不同的副本时，会在请求带上 zxid 标记，副本通过检查客户端的 zxid 和自己的 zxid，保证读到的是更新的 zxid 的数据(没有具体说怎么处理，是阻塞等待还是拒绝请求)。

更进一步，如果同一个客户端发送一个写请求<X, 17>，然后立即去某个副本服务器读 X，这里会暂缓一下读请求，直到这个副本发现写请求的 zxid 已经执行了，即客户端将会读到 <X, 17>，不会读到过期的数据。

这样子看，ZooKeeper 究竟是不是线性一致的？

按照教授的说法，认为 ZooKeeper 不是线性一致的，但也不是完全非线性一致的，只能说对于单个客户端请求来说是线性一致的。

那么 zxid 必须要等到写请求执行完成才返回吗？

实际上不知道具体是如何工作的，可能需要看看 Apache ZooKeeper 源码，但这是个合理的假设。

同步操作 sync

为什么 ZooKeeper 如此流行，其中一个原因是，有一个弥补线性一致性的方法。

ZooKeeper 提供一个 sync 操作，本质上是一个写请求，如果想读到最新写入的数据，可以发送一个 sync 请求，最终会在所有副本中读到最新的数据。

这其实与前面提到的 FIFO 客户端请求类似，sync 就是一个写请求，然后后面跟着一个读请求，保证读请求能读到自己写请求的内容。

同时也要认识到，sync 是一个代价很高的操作，因为我们将一个读操作转换成了一个写+读操作，如果不是必须，还是不要这么做。

数据模型

ZooKeeper 用 znode 表示内存数据节点，znode 以层次命名空间的方式组织起来称为数据树(data tree)，与文件系统非常类似。例如，使用 /A/B/C 给出 znode C 的路径，C 的父节点是 B，B 的父节点是 A。

我猜，znode 就是借用文件系统 inode 来命名。

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

• 普通(Regular)，Apache ZooKeeper 也叫持久的(Persistent)：持久化存储的普通节点。

• 临时(Ephemeral)：在会话结束（主动结束或者因为故障结束）时自动删除的节点，也可以显示删除。

所有 znodes 都存储数据。除了临时 znode，所有 znode 都可以有子节点。

创建新的 znode 节点时，还可以指定 sequential 标识创建顺序的 znode，当设置了这个标识后，znode 的名字末尾会添加上一个单调递增计数器，即 name+ seqno，由父节点维护，如果 n 是新节点，p 是父节点，n 的 seqno 将大于所有在 n 之前创建的 p 的子节点的 seqno。

这样组合后其实有四种类型的 znode：

• PERSISTENT

• EPHEMERAL

• PERSISTENT_SEQUENTIAL

• EPHEMERAL_SEQUENTIAL

ZooKeeper 实现

如图，ZooKeeper 主要由以下组件构成：

• 请求处理器(Request Processor)：将收到的请求转为幂等的事务，根据版本信息，生成包含新数据、版本号和更新的时间戳的 setDataTXN

• 原子广播（Atomic Broadcast）：使用 zab 协议达成共识，这里不展开

• 多副本数据库（Replicated Database）：将内存状态存储为模糊快照(fuzzy snapshot)，用来恢复状态。做快照时不锁定当前状态。

模糊快照论文中有简单解释，例如：

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

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

客户端 API

create(path, data, flags)：使用 path 创建一个新的 znode 节点存储 data，仅第一次创建会成功。flags 用于创建普通或者临时节点，也可以设置 sequential 标识。
delete(path, version)：如果 znode.version = version，则删除 znode。
exists(path, watch)：如果指定 path 的 znode 存在则返回真，如果不存在则返回假。watch 标识用于在 znode 上设置监视器。
getData(path, watch)：返回数据和元数据，如版本信息。watch 标识与 exists() 的 watch 标识一样，但如果 znode 不存在则不会设置监视器。
setData(path, data, version)：如果 znode.version = version，则更新 znode 上的 data。
getChildren(path, watch)：返回 znode 所有子节点的名称。
sync(path)：等待所有更新操作发送到客户端连接的服务器。

几个重要特性：

• 排他地创建 znode，有且仅有一个 create 返回成功

• 当客户端连接到 ZooKeeper 时，建立一个会话(session)

• 所有的方法都有同步和异步的版本

• 更新操作（delete 和 setData）会有预期的版本号，如果与 znode 的实际版本号不同，操作将失败

• 用 watch 来避免轮询

ZooKeeper 应用

对应前面学习到的分布式系统，可以应用在：

• VMware-FT 中的 test-and-set 服务；

• GFS 中的 master 可以使用 ZooKeeper 来扮演，甚至可以提高性能，因为所有副本都能提供读服务；

• 在 MapReduce 中用来管理成员信息，谁是当前的 master、谁是 worker、worker 列表、什么工作分配给什么 worker 等等；

论文中还提到一些配置管理、成员管理、锁、读写锁等应用，Apache ZooKeeper 有更详细的代码示例，网上资源也很多了，在此不表。

遗憾：未涵盖的主题

• 如何持久化

• batching 和 pipelining 性能的详细信息

• fuzzy snapshot 实现细节

• 幂等运算细节

• 重复的客户端请求检测

也许看看 Apache ZooKeeper 源代码能有答案。

FAQ

来源：https://pdos.csail.mit.edu/6.824/papers/zookeeper-faq.txt

Q: 线性化(linearizability)和串行化(serializability)有什么不同？

通常来说串行化很像线性化，但不要求遵守实时顺序。详细解释可以查看：http://www.bailis.org/blog/linearizability-versus-serializability/

ZooKeeper 论文的 2.3 节里写到一致性是 serializable 的。

还可以看看：https://jepsen.io/consistency

Q: 什么是流水线(pipelining)

首先，ZooKeeper 的 Leader 会将多次请求合并成一次发送到磁盘和网络，这里是利用 batching 来解决请求很多的情况。

其次，pipelining 可以让客户端不用等待请求返回，就可以继续处理后面的请求，就像异步的操作。

这里和 Raft 提到的性能优化中的 Batching 和 Pipelining 一模一样。

Q: 什么是 wait-free？

精确的定义是：一个 wait-free 的并发数据对象保证任何进程都能在有限的步骤中完成任何操作，无论其他进程的执行速度如何。可以查阅论文：https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

ZooKeeper 是 wait-free 的，因为它在处理一个客户端请求的时候，无需等待其他客户端的结果。

不过，根据 watch 机制，ZooKeeper 客户端有时候也会等待别的客户端的结果。

Q: Leader 如何知道客户端异步更新时的执行顺序？

论文没说，可能是客户端对异步请求进行编号，追踪每个会话的请求列表。

Q: 如果客户端没有收到请求的响应，它会做什么？

论文没说，Leader 可能会跟踪它收到的每个请求，过滤掉一些重复的请求。和 Lab 3 类型。

Q: 如果客户端发送异步写，然后立即执行读操作，读操作会看到写操作的结果吗？

论文没有明说，但是按照 FIFO 的客户端请求的含义，应该是可以看到的写操作的结果的。这似乎意味着，读操作可能会阻塞，直到服务器收到前面的写操作。

Q: 为什么要实现 fuzzy snapshots？

一个精确的快照将对应日志中的一个特定点，该快照包含这个点之前所有的写，不包含之后所有的写，所以需要防止在创建和写入快照时发生任何写操作，这将降低很多性能。

ZooKeeper 的快照是将内存状态导出写入持久存储:

• 异步线程生成快照文件；

• 快照文件名的后缀是最后提交的事务的 zxid；

• 快照文件生成过程中，仍然有新的事务提交；

• 因此，快照文件不是精确到某一时刻的快照文件，可能与实际存在的任何数据树都不对应，因此是模糊的；

• 这就要求事务操作是幂等的，否则产生不一致；

参见：https://zookeeper.apache.org/doc/r3.7.0/zookeeperAdmin.html

Q: ZooKeeper 如何选主？

使用 Zab 原子广播算法。Zab 的 paper：http://dl.acm.org/citation.cfm?id=2056409

Q: ZooKeeper 的数据库有多大？看起来服务器要有很多内存。

这取决于应用，但论文没有提及，鉴于 ZooKeeper 只是一个协调服务，不是一个常规的存储服务，内存数据库是合理的选择。

Q: 什么是 universal object？

一种并发理论，通常和前面的 wait-free 放在一起理解，同样参见论文：https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

作者称使用这种并发理论，以表明 Zookeeper 的 API 是通用的：API 包括足够的功能来实现任何你想要的协调方案。

更多：https://en.wikipedia.org/wiki/Non-blocking_algorithm

Q: 能否在不停止 ZooKeeper 服务的情况下添加更多的服务器?

虽然论文里 ZooKeeper 集群成员是静态的，但开源的 ZooKeeper 支持动态扩容：https://zookeeper.apache.org/doc/r3.7.0/zookeeperReconfig.html

有论文阐述其机制：https://www.usenix.org/system/files/conference/atc12/atc12-final74.pdf

Q：客户端的库如何实现 watch 机制？

在大多数情况下，客户端库可能会注册一个回调函数，该函数将在监视触发时被调用。例如，ZooKeeper 的 Go 客户端通过 GetW() 返回一个 channel 来实现。

参见：https://godoc.org/github.com/samuel/go-zookeeper/zk#Conn.GetW

Q: 为什么第6页代码中的读锁跳到第3行，而不是像写锁那样跳到第2行？

这应该是一个 bug，正确的代码块参见：https://zookeeper.apache.org/doc/r3.7.0/recipes.html#Shared+Locks

小结

ZooKeeper 是一个为特定用途而设计的好的例子，放宽了一致性，以提高以读为主的工作负载，论文中的结果显示，ZooKeeper 的吞吐量可以线性拓展。

如今许多分布式系统中应用了 ZooKeeper，可以在这里查看：https://zookeeper.apache.org/doc/r3.7.0/zookeeperUseCases.html。

Reference

• ZooKeeper：https://zookeeper.apache.org/

• ZooKeeper wiki：https://cwiki.apache.org/confluence/display/ZOOKEEPER/Index

• Zab：http://dl.acm.org/citation.cfm?id=2056409

• Wait-Free Synchronization：https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

• ZooKeeper FAQ：https://pdos.csail.mit.edu/6.824/papers/zookeeper-faq.txt

• Linearizability versus Serializability：http://www.bailis.org/blog/linearizability-versus-serializability/

• Consistency Models：https://jepsen.io/consistency

• Non-blocking algorithm：https://en.wikipedia.org/wiki/Non-blocking_algorithm

• Dynamic Reconfiguration of Primary/Backup Clusters：https://www.usenix.org/system/files/conference/atc12/atc12-final74.pdf

• ZooKeeper Go Client：https://github.com/samuel/go-zookeeper

相关阅读

欢迎关注我的公众号：