Chubby 分布式锁服务

来自 Google 于 2006 年在 OSDI 发表的论文 The Chubby lock service for loosely coupled distributed systems

Chubby 是粗粒度锁和松耦合的分布式低容量存储服务，设计重心在于可靠和可用性，而非高性能（吞吐量）。

1. 介绍

帮助开发者：

1. 粗粒度的系统内同步
2. 选主
3. 存储少量元数据

Google File System（GFS）和 Bigtable 都使用 Chubby 锁来选主和存储少量元数据

分布式计算的真实网络环境中丢包、延迟和乱序是无法避免的，需要异步通信，异步共识由 Paxos 协议解决。

2. 设计

2.1 原理

一种论点是构建一个内嵌 Paxos 的库，而非一个访问中央锁服务的库。

锁服务相较于客户端库的优缺点：

• 虽然一开始开发者可能无需高可用，但随着服务成熟，可用性变得越来越重要；现有的设计中还会加入多副本和选主
• 锁服务使得维护现有的程序结构和通信模式更容易
• 更容易地使得现有的服务参与共识协议，在过渡期保持兼容
• 客户端可以存储和读取少量数据，与锁服务结合在一起
• 基于锁的接口对程序员更友好（顺序编程）
• 很多用过锁的程序员在分布式系统中对锁的认知是错误的
• 分布式共识算法使用 quorum 来决策，因此会有多个副本来实现高可用（Chubby 通常有 5 个副本）

两个关键设计决策：

1. 选择锁服务而不是客户端库或共识服务
2. 选择用小文件服务来使得被选出 leader 可以公告它们的参数，而非构建第二个服务

有些决策是根据我们的预期和环境做出的：

• 使用 Chubby 的服务可能有几千个客户端，必须允许成千上万个客户端观察该文件
• 客户端希望得知 leader 何时发生变更，事件通知机制比轮询更好
• 许多开发者希望缓存文件
• 一致的缓存
• 提供安全机制，比如访问控制

出人意料的是，我们不希望锁被细粒度地使用，在这种情况下，锁可能只被持有很短时间（几秒甚至更短）；相反我们希望粗粒度地使用锁。举个栗子，应用程序使用锁来选择 leader，然后该服务将在相当长的时间内处理访问。相比细粒度锁，后者

• 锁服务负载小得多
• 粗粒度锁很少被获取，锁服务不那么高可用也能够为许多客户端提供足够的服务

2.2 系统架构

两个主要组件，通过 RPC 通信:

• Chubby 服务器
  • 多副本
  • 使用分布式共识协议（Paxos）来选主
  • 主节点定期续租
  • 只有主节点可读写，其他副本只从主节点复制更新，写请求通过共识协议传播至所有副本
  • 如果副本故障并在数小时内未恢复，将从备用池中选一台全新的机器并在上面部署服务
• 链接入客户端应用程序的库
  • 客户端先向所有节点询问主节点，非主节点会应答主节点的位置；客户端只会向主节点发送读写请求

2.3 文件和路径

Chubby 暴露类似 UNIX 文件系统的接口，呈树状结构：/ls/foo/wombat/pouch

1. ls 前缀是固定的
2. 第二段 foo 是 Chubby 服务器的名称，
3. 剩下的部分 /wombat/pouch 在 Chubby 服务内部来转换

文件和目录统称为节点，每个节点都有元数据，包含了 ACL 等信息。元数据也有 4 个单调递增的 64 位数字来让客户端感知到变更：

1. ID
2. 内容版本号：写文件内容时增加
3. 锁版本号：上锁时增加
4. ACL 版本号：写节点 ACL 规则时增加

2.4 锁与 sequencer

每个文件和路径都可以作为读写锁，类似 Golang 的 RWMutex。

锁在分布式系统中是一个复杂的问题，因为通信是不靠谱的，而且进程也可能挂掉。当一个持锁的进程发送了请求 R，随后挂掉了。另一个进程要获取锁并在请求 R 到达目的地之前做一些操作。如果 R 到达晚了，就会在没有锁保护的情况下被执行，导致操作后数据不一致。解决接收消息顺序错乱问题的方案有 virtual time 和 virtual synchrony。

在复杂系统的所有交互中引入序号是有开销的，相反，Chubby 只为使用锁的交互引入序号。持锁者请求 sequencer，这是一个描述锁状态的字符串，包含了锁名，模式（独占还是共享）和版本号。客户端如果想要操作被锁保护，就将 sequencer 传给服务器。

尽管 sequencer 易于使用，但并非主要协议都支持。因此 Chubby 提供了一个不完美但更简单的机制：如果一个客户端正常释放锁，那其他客户端立即就能获取锁。但是如果锁是因为持有者挂了或无法访问释放的，锁服务会延迟其他客户端获取锁一段时间。客户端可以指定锁延迟，最长不超过一分钟。虽然不完美，但是应对消息延迟和重启还是足够的。

2.5 事件

Chubby 客户端能够订阅一系列事件（异步地传给客户端）：

• 文件内容变更——通过文件来服务发现
• 子节点添加、移除和变更——用于实现监控
• Chubby 主节点故障切换——警告客户端
• 句柄（和锁）失效——通常代表通信问题
• 求锁——用于选主
• 来自其他客户端的锁请求

2.6 API

Chubby 句柄由 Open() 打开文件或路径创建；由 Close() 销毁，和 UNIX 文件操作类似。

Open() 时还可以多个选项来：

• 句柄将被如何使用（读；写和上锁；修改 ACL）
• 是否订阅事件
• 锁延迟时间
• 是否创建一个新的文件或路径

句柄主要的方法有：

• GetContentsAndStat() 返回文件的内容和元数据
• GetStat() 只返回元数据
• ReadDir() 类似 ls -al
• SetContents() 写文件内容
• SetACL() 设置指定的 ACL
• Delete() 删除节点
• Acquire() 和 TryAcquire() 获取锁
• Release() 释放锁
• GetSequencer() 返回可以描述当前句柄持锁的 sequencer
• SetSequencer() 将 sequencer 与句柄关联
• CheckSequencer() 检查 sequencer 是否还有效

客户端可以这样利用上述 API 来选主：所有候选者都打开锁文件来尝试持锁，成功的那个通过 SetContents() 将它的 ID 写入锁文件，这样就可以被其他人看到，它们通过 GetContentsAndStat() 读取文件。理想情况下，leader 通过 GetSequencer() 获取 sequencer，随后传给它正在通信的服务器；它们就可以通过 CheckSequencer() 确认 leader 是否还在任期。无法检查 sequencer 的服务就用锁延迟。

2.7 缓存

为了减少读取流量，Chubby 客户端在内存中一致性地缓存文件数据和节点元数据。缓存由租约机制维护，确保客户端的视图与 Chubby 状态一致。

当文件内容或元数据即将变更，当服务器向客户端发送使数据无效化的通知时，变更会被阻塞；该机制基于心跳（KeepAlive）RPC。在客户端收到无效化通知后，将缓存刷新至无效状态，并通过心跳来通知主节点已确认（ACK）。只有在服务器确认每个客户端都确认或缓存租约到期后，变更才会进行下去。

这种缓存协议很简单：因为在数据发生变化时只会使缓存无效，而非更新缓存。其实更新而非失效同样简单，但非常低效，数据并不是在每一次更新后都会被使用的。

强一致性是以额外的开销为代价的，但我们毅然拒绝弱一致性的模型，因为程序员会发现更难使用。

Chubby 的协议还允许客户端缓存锁，希望同一个客户端能够再次使用它们。如果其他客户端请求了一个冲突的锁，会有事件通知持锁者来释放它。

2.8 会话和心跳（KeepAlive）

Chubby 服务器与客户端之间的会话通过周期性的握手（被称为心跳）来维护。除非客户端主动通知，否则只要会话有效，其句柄、锁和缓存数据都将保持有效。

客户端首次访问 Chubby 服务器（主节点）就开始新的会话；当客户端终止或会话空闲（一分钟内没有操作）时，会话结束。

传递事件和缓存失效通知也会搭心跳的顺风车。

客户端维护一个本地的租约超时时间，它只是一个对主节点租约超时时间的保守估计。有所讲究，客户端必须同时考虑心跳应答在网络上的传输时间和主节点的时钟推进速率。

当客户端的本地租约超时失效，它其实并不确定主节点是否已经终止该次会话。客户端清空并禁用它的缓存，我们称这次会话处于危险期。客户端会等待一段时间（默认 45s），如果在此期间成功与主节点（很可能是重新选举出来的）交换心跳，它就会再次打开缓存；否则客户端认为会话过期，在重新建立会话前 API 调用都将报错。

2.9 故障切换

当主节点发生故障，会丢失内存中的状态，包括会话、句柄和锁。如果客户端在租约过期前能够连接上重新选举出的主节点，一切照旧；但要是选主时长超过了上述的等待时间，客户端清空本地缓存并寻找新的主节点。

如图 2，原主节点的会话租约期为 M1；客户端租约期为 C1。主节点在应答心跳包通知客户端前提交至租期 M2，然后就挂了。选主花了一些时间。最终客户端的 C2 租约过期了，随后客户端清空缓存并等待一段时间。

在此期间，客户端并不确定它的租约在主节点那是否已经过期。客户端不直接结束会话，但会阻塞所有 API 调用来保证数据的一致性。

最后新主节点被成功选举，它一开始使用 M3 作为租约期。客户端给新主节点发送的第一次心跳会被拒绝因为主节点 epoch number 对不上。因为客户端的等待时间长到足以覆盖 C2 尾和 C3 头，对它来说这次主节点切换相当于一次延迟。如果等待时间（默认 45s）不够，客户端将废弃这次会话并向应用程序返回失败。

客户端和新主节点的协同使得应用程序以为没有任何故障发生。要达成该目标，新主节点必须还原出之前主节点的内存状态。通过读取磁盘（数据库）、从客户端获取状态还有推测来实现。数据库会记录每个会话、锁和临时文件。

新的主节点按下面流程处理：

1. 挑选一个新的 epoch number，客户端的每次调用都必须带上。主节点会拒绝 epoch number 不匹配的调用，并返回正确的 epoch number。这样做确保主节点不会应答过期的请求，因为那是发给之前的主节点的。
2. 主节点一开始不会处理会话相关的操作。
3. 根据数据库中的记录在内存中重建会话和锁数据结构。
4. 现在客户端可以向主节点发送心跳包了，但仅仅只有心跳包而已。
5. 向每个会话通知故障切换事件，这会导致客户端清空本地缓存，并警告应用程序其他事件可能丢失。
6. 等待直到所有会话都确认了故障切换事件。
7. 主节点允许所有操作继续。

故障切换的使用频率远低于系统中其他部分，产生了相当多的 bug。

2.10 数据库实现

Chubby 首个版本使用 Berkeley DB 作为数据库。Berkeley DB 本身使用分布式公式协议来复制数据库日志到一组服务器上。一旦添加了主节点租约，这是符合 Chubby 设计的。

但是我们觉得直接使用 Berkeley DB 的源码存在商业上的风险，因为自己编写了一个简单的数据库，使用 WAL 和快照技术。和前者一样数据库日志通过分布式共识协议分发至副本。因为 Chubby 只使用了 Berkeley DB 少量的特性，所以这次重写大大简化了整个系统。例如，我们需要原子操作，但并不需要通用事务。

2.11 备份

每几个小时，Chubby 主节点会将数据库的快照写入异地的 GFS 文件服务器，确保备份能在意外发生时留存下来。

备份既提供了灾难恢复能力，也为初始化数据库副本提供了方案，避免对正在工作的副本产生额外的负载。

2.12 镜像

Chubby 能够从一个单元镜像一组文件至另一个单元。镜像的速度很快，因为文件都很小还有事件机制。只要网络没问题，全球数十个镜像站点的变化都能在一秒以内反映出来。更新的文件通过比较校验和识别。

文件镜像最常用于复制配置文件到分布在世界各地的集群中，还有 Chubby 本身的 ACL。

3. 扩展机制

Chubby 客户端都是独立的进程，我们曾见过 9W 个客户端同时直接访问一台 Chubby 主节点。因为只有一台主节点，很容易被海量的客户端冲垮，因为最有效的扩展技术是减少与主节点的通信频率。主节点没有严重的性能问题，对它处理请求的改进收效甚微。我们采用了其他方法：

• 客户端尽可能找附近的 Chubby 服务集群（通过 DNS）避免访问远程的机器。通常在一个数千台机器的数据中心内部署一个 Chubby 集群。
• 在高负载下，主节点将租约时间从默认的 12s 上调至 60s，低频率地处理心跳包
• 客户端缓存文件数据和元数据来减少对主节点的访问
• 使用协议转换服务将 Chubby 协议转换为 DNS 等较简单的协议。

3.1 代理

Chubby 的协议可以被代理。由代理来处理 KeepAlive（心跳）和读请求，降低服务器负载；但写流量会穿透代理的缓存，是无法减少的。因为写入流量少于 Chubby 正常工作负载的百分之一，所以代理可以显著地增加客户端数量。

2.9 节描述的故障切换并不适用于代理。

3.2 分区

Chubby 的接口被设计为可以在服务器之间划分集群的命名空间。如果开启的话，一个 Chubby 集群可由 N 个分区组成，每个分区都有一个主节点和一组副本节点。目录 D 中的每个节点（文件或目录） D/C 会被存储在分区 P(D/C) = hash(D) mod N。D 的元数据也可能存储在不同的分区 P(D) = hash(D') mod N，此处 D' 是 D 的父目录。

分区的目的是使得大型 Chubby 集群和分区之间少量通信。尽管 Chubby 缺失硬链接、跨目录重命名操作，但仍有一些操作需要跨分区通信：

• ACL 本身就是文件，因为一个分区可能会使用另一个分区来权限检查。
• 当一个目录被删除，可能需要跨分区调用确保该目录为空。

每个分区都独立处理大部分请求，我们预期这种通信只会对性能或可用性产生较小的影响。

我们预计每个客户端都会接触大部分的分区，因此分区可以将原先一个分区上的读写流量减少 N 倍。

4. 使用、惊喜和设计错误

4.1 使用和行为

一个 Google 内部的普通 Chubby 单元的快照统计数据：

• 很多文件被用于命名
• 配置、访问控制和元数据文件很常见
• 被动缓存相当重要
• 230k/24k ≈ 10 个客户端使用每个缓存文件
• 少量客户端持锁，共享锁基本非常罕见
• RPC 流量大头还是心跳（KeepAlive）；还有少量读和更少的写还有请求锁

在样本集群中，记录了几周内的 61 次故障。排除掉因维护而关闭数据中心，所有其他原因包括网络拥塞、维护、过载及操作员、软件和硬件错误。大多数故障在 30 秒以内，对大多数应用影响不大。

在多年的运营中，因数据库错误（4 次）和操作员失误（2 次）丢数据共六次。讽刺的是，这些错误都与升级修复软件错误有关。

我们还发现扩展 Chubby 的关键并非服务器性能，减少通信带来的影响更大。我们并未投入大量精力在调优代码上，只检查是否存在严重的 bug，将注意力聚焦在可能更有效的扩展机制上面。

4.2 Java 客户端

Google 大多数基础设施都用 C++ 编写，但由 Java 编写的系统数量也在增长。Java 鼓励应用程序的可移植性却牺牲了性能。Java 常用 JNI 机制访问本地库，但这个东西又慢又烦，我们非常不喜欢 JNI，宁愿用 Java 重写客户端库。

Chubby 的 C++ 客户端库长达 7000 行，维护该库的 Java 版本耗时耗力。即使事后诸葛亮，我们也不知道如何才能避免这些成本。

4.3 作为域名服务器

尽管 Chubby 是作为锁服务设计的，我们发现它最受欢迎的用法是作为域名服务器。

DNS 记录有一个存活时间（TTL），但如果要及时替换掉失效的服务器，TTL 值设置的太小会导致 DNS 服务器过载。

相反，Chubbty 的缓存使用主动失效机制，在不变的情况下，会话的心跳（KeepAlive）可以在客户端无限期地维持缓存条目。Chubby 无需轮询每个域名就能快速更新，这点非常好，现在 Chubby 已为公司大部分系统提供域名服务。

虽然单个 Chubby 集群支持大量客户端，但负载峰值仍可能是个问题。Chubby 提供的缓存语义比域名服务器所需的语义更精确，域名解析只要求及时通知而非完全一致。因此我们可以引入专门为域名查找而设计的协议转换服务器来减轻 Chubby 的负载。

4.4 故障切换的问题

故障切换原先的设计需要主节点在会话创建时将其写入数据库。Berkeley DB 版本的锁服务器中，创建会话的开销有问题。为了避免过载，我们修改为在会话尝试首次变更、获取锁或打开临时文件时才入库。此外，每次心跳握手时，激活的会话以一定的概率被记录到数据库中。

但这种过载优化是有代价的，在故障切换时开始不久的只读会话可能会丢失。虽然这些会话没有锁，但还是不安全的，在大型系统中，某些会话将无法 check in，从而迫使新的主节点等待租约到头。

在新的设计中，我们完全避免了在数据库中记录会话，而是以当前主节点重建句柄来重建会话。一旦会话不依赖盘上的状态了，就可以引入代理服务器管理会话。

4.5 客户端滥用

许多服务都共同使用 Chubby 集群，这就要将有不当行为的客户端拉黑。Chubby 在公司内部运行，一般不会被攻击。

审查的核心是确定 Chubby 资源（RPC 速率、磁盘空间、文件数量）的使用是否随用户数量或项目处理的数据量线性增长。

当应用程序在短时间内多次尝试打开同一个文件时，我们引入指数级增长的延迟来处理重试循环。

Chubby 从未打算用作大量数据的存储系统，所以没有存储配额。事后看来这是败笔。

经验教训

开发者很少考虑可用性。大家倾向于把 Chubby 这样的服务当作始终可用，不考虑故障概率。实际上 Chubby 还是会中断的，我们更希望开发者为此做好准备，降低基础设施设施故障对应用程序造成的影响。

忽略细粒度锁。我们发现为了优化应用程序，往往要去除不必要的通信，通常意味着要找到使用粗粒度锁的方法。

不恰当的 API 选择会产生意外的影响。例如 Chubby 提供了一个事件，让客户端检测到主节点已经发生了切换。遗憾的是很多开发者在收到该事件时选择直接让应用程序崩溃，大大降低了系统的可用性。

复用心跳包，既用于刷新客户端的会话租约，也用于发布事件和缓存失效。看起来很理想，但在网络高度拥塞时，基于 TCP 的 KeepAlive 会导致许多会话丢失。我们不得不用 UDP 实现 KeepAlive RPC。但 UDP 没有拥塞控制，我们还是倾向于只在必须满足低延迟要求时才使用 UDP。