【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
阅读原文

简介:一名系统研究者的攀登之路,欢迎关注微信公众号:多颗糖
(0)
打赏 喜欢就点个赞支持下吧 喜欢就点个赞支持下吧

声明:本文来自“多颗糖”,分享链接:https://www.zyxiao.com/p/293993    侵权投诉

网站客服
网站客服
内容投稿 侵权处理
分享本页
返回顶部