面向松耦合分布式系统的Chubby锁服务

The Chubby Lock Service for Loosely-Coupled Distributed Systems

贡献：分布式协调服务的开山之作，催生了ZooKeeper，成为所有分布式系统的标准协调组件

Mike Burrows，Google Inc.

摘要

本文介绍了Chubby锁服务的实践经验，该服务旨在为松耦合分布式系统提供粗粒度锁能力，以及高可靠（但低容量）的存储功能。Chubby提供的接口与带有咨询锁的分布式文件系统非常相似，但设计的侧重点在于可用性与可靠性，而非高性能。该服务的多个实例已投入使用超过一年，其中部分实例可同时承载数万个客户端。本文阐述了Chubby的初始设计与预期用途，将其与实际使用情况进行对比，并解释了为适配这些差异而对设计做出的调整。

1 引言

本文介绍了一款名为Chubby的锁服务，它适用于由大量小型机器通过高速网络连接组成的松耦合分布式系统。例如，一个Chubby实例（也称为Chubby单元，Chubby cell）可以为一万台配备4处理器、通过1Gbps以太网连接的机器提供服务。大多数Chubby单元都部署在单个数据中心或机房内，但我们也运行了至少一个副本分布在数千公里之外的Chubby单元。

锁服务的作用是让客户端能够同步自身的活动，并就环境的基础信息达成一致。设计的核心目标包括可靠性、对中等规模客户端群体的可用性，以及易于理解的语义；吞吐量和存储容量则被视为次要目标。Chubby的客户端接口类似于简易文件系统，支持整文件读取与写入，并额外提供了咨询锁以及文件修改等各类事件的通知机制。

我们最初期望Chubby帮助开发者在系统中实现粗粒度同步，尤其是解决从一组对等服务器中选举主节点的问题。例如，谷歌文件系统（GFS）[7]通过Chubby锁来指定GFS主服务器；Bigtable[3]则在多个场景下使用Chubby：选举主节点、让主节点发现其管控的服务器，以及让客户端找到主节点。此外，GFS和Bigtable都将Chubby作为一个稳定可用的位置，存储少量元数据；实际上，它们将Chubby用作自身分布式数据结构的根节点。还有一些服务通过锁在多台服务器之间进行粗粒度的任务划分。

在Chubby部署之前，谷歌的大多数分布式系统要么采用临时方案实现主节点选举（适用于工作重复不会造成损失的场景），要么需要人工干预（适用于正确性至关重要的场景）。对于前者，Chubby节省了少量计算开销；对于后者，系统不再需要在故障时人工介入，可用性得到了显著提升。

熟悉分布式计算的读者会意识到，对等节点间的主节点选举本质上是分布式共识问题，并且我们需要采用异步通信的解决方案；这一术语描述了绝大多数真实网络的行为，比如以太网或互联网，这类网络允许数据包丢失、延迟和乱序。（从业者通常应当警惕那些基于更强环境假设模型的协议。）Paxos协议[12,13]解决了异步共识问题。Oki和Liskov也使用了相同的协议（参见他们关于视图标记复制的论文[19,第4节]），二者的等价性已被其他研究者指出[14,第6节]。事实上，我们目前接触到的所有可运行的异步共识协议，核心都是Paxos。Paxos无需依赖时间假设即可保证安全性，但必须引入时钟来保证活性；这也突破了Fischer等人提出的不可能性结论[5,第1节]。

开发Chubby是一项工程工作，目的是满足上述需求，而非研究创新。我们并未提出新的算法或技术。本文的目的是描述我们的实现与设计思路，而非鼓吹该方案。在后续章节中，我们将介绍Chubby的设计与实现，以及它在实践中如何演进。我们会描述Chubby意料之外的使用场景，以及被证实存在缺陷的设计。对于已有文献覆盖的细节，比如共识协议或RPC系统的具体实现，我们不再赘述。

2 设计

2.1 设计原理

有人可能会提出，我们应当开发一套实现Paxos的客户端库，而不是开发一个访问中心化锁服务的客户端库——哪怕这个锁服务具备高可靠性。客户端Paxos库不需要依赖其他服务器（域名服务除外），并且可以为程序员提供标准框架，前提是他们的服务可以实现为状态机。实际上，我们确实提供了这样一套独立于Chubby的客户端库。

尽管如此，锁服务相比客户端库仍具备一些优势：
第一，我们的开发者有时不会按照理想方式为高可用性做设计。他们的系统通常从原型开始，负载很低，可用性要求也很宽松；代码通常也没有针对共识协议做特殊的结构设计。随着服务成熟、用户增多，可用性变得愈发重要，此时才在现有设计基础上增加复制和主节点选举功能。虽然这可以通过提供分布式共识的库来实现，但锁服务器更容易兼容现有的程序结构和通信模式。例如，要选举一个主节点来向现有文件服务器写入数据，只需要在现有系统中增加两行代码和一个RPC参数：获取锁以成为主节点，在写入RPC中额外传递一个整数（锁获取计数），并在文件服务器中增加一条判断语句——如果获取计数低于当前值则拒绝写入（用于防范延迟数据包）。我们发现，相比让现有服务器参与共识协议，这种技术实现起来更简单；如果需要在过渡期间保持兼容性，这种优势会更加明显。

第二，许多需要选举主节点或在组件间划分数据的服务，都需要一种机制来广播选举结果。这意味着我们应当允许客户端存储和获取少量数据，也就是读写小文件。这一功能可以通过域名服务实现，但我们的经验表明，锁服务本身非常适合这项任务：既减少了客户端依赖的服务器数量，又可以共享协议的一致性特性。Chubby作为域名服务的成功，很大程度上得益于它采用了一致性客户端缓存，而非基于时间的缓存。特别是，我们发现开发者非常不用再像设置DNS生存时间（TTL）那样选择缓存超时时间——如果设置不当，要么会导致DNS负载过高，要么会延长客户端故障切换的时间。

第三，基于锁的接口对我们的程序员来说更熟悉。Paxos的复制状态机，以及排他锁对应的临界区，都能给程序员带来串行编程的错觉。但很多程序员之前接触过锁，自认为知道如何使用。讽刺的是，这类程序员通常都是错的，尤其是在分布式系统中使用锁时；很少有人会考虑在异步通信的系统中，机器独立故障对锁产生的影响。尽管如此，锁表面上的熟悉性，还是降低了说服程序员使用可靠分布式决策机制的门槛。

最后，分布式共识算法需要法定人数来做决策，因此需要多个副本才能实现高可用性。例如，Chubby每个单元通常有5个副本，其中3个正常运行即可保证单元可用。相比之下，如果客户端系统使用锁服务，哪怕只有一个客户端，也能安全地获取锁并推进任务。因此，锁服务减少了客户端系统实现可靠运行所需的服务器数量。宽泛地说，可以将锁服务视为一种通用的“选举群体”，让客户端系统在自身成员不足半数的情况下，也能正确做出决策。

有人可能会想到用另一种方式解决这个问题：提供一种“共识服务”，用多台服务器充当Paxos协议中的“接受者”。和锁服务一样，共识服务也允许客户端哪怕只有一个活跃进程也能安全推进任务；类似的技术已被用于减少拜占庭容错所需的状态机数量[24]。然而，如果共识服务不是专门用来提供锁（那样就退化成锁服务了），它就无法解决上述其他问题。

基于这些考量，我们做出了两个关键设计决策：

我们选择开发锁服务，而非共识库或共识服务；
我们选择提供小文件服务，让选举出的主节点可以广播自身身份与参数，而不是额外开发和维护一套独立的服务。

还有一些决策源于我们的预期用途和部署环境：

通过Chubby文件广播主节点的服务可能拥有数千个客户端。因此，我们必须支持数千个客户端同时观测该文件，并且最好不需要太多服务器。
复制服务的客户端和副本可能需要知道主节点何时发生变更。这意味着事件通知机制会很有用，可以避免轮询。
即使客户端不需要定期轮询文件，很多开发者还是会这么做；这是支持大量开发者必然会出现的情况。因此，文件缓存是很有必要的。
我们的开发者容易对不符合直觉的缓存语义产生困惑，因此我们更倾向于一致性缓存。
为了避免经济损失和合规风险，我们提供了包括访问控制在内的安全机制。

可能让一些读者意外的一个选择是：我们并不期望锁被细粒度使用（即只持有很短时间，几秒或更短）；相反，我们预期的是粗粒度使用场景。例如，应用程序可能用锁选举出一个主节点，然后由该主节点在相当长的一段时间内（数小时甚至数天）处理所有对该数据的访问。这两种使用模式对锁服务器的要求截然不同。

粗粒度锁给锁服务器带来的负载要小得多。特别是，锁的获取频率通常与客户端应用的事务频率只有很弱的关联。粗粒度锁很少被获取，因此锁服务器临时不可用给客户端造成的延迟更少。另一方面，锁在客户端之间的转移可能需要高昂的恢复开销，因此人们不希望锁服务器的故障转移导致锁丢失。因此，粗粒度锁可以很好地承受锁服务器故障，几乎不需要考虑这样做的开销，而且少量锁服务器就能以不算很高的可用性，为大量客户端提供足够的服务。

细粒度锁的结论则完全不同。哪怕锁服务器短暂不可用，也可能导致大量客户端停滞。性能和按需扩容的能力至关重要，因为锁服务的事务速率会随着客户端事务速率的总和而增长。通过不跨锁服务器故障维持锁，可以降低锁的开销；而且由于锁持有时间很短，偶尔丢弃锁造成的时间损失并不严重。（客户端本来就必须做好网络分区期间丢失锁的准备，因此锁服务器故障转移导致的锁丢失并不会引入新的恢复流程。）

Chubby的定位是仅提供粗粒度锁。幸运的是，客户端可以很容易地自行实现适配自身应用的细粒度锁。应用程序可以将锁划分为多个组，用Chubby的粗粒度锁将这些锁组分配给应用专属的锁服务器。维护这些细粒度锁只需要很少的状态；服务器只需维护一个非易失性、单调递增且很少更新的获取计数器。客户端可以在解锁时得知锁是否丢失；如果使用简单的固定时长租约，协议可以做到简单高效。这种方案最大的好处是，客户端开发者可以自行负责支撑其负载所需的服务器部署，同时又不必自行实现复杂的共识算法。

2.2 系统结构

Chubby包含两个通过RPC通信的核心组件：服务器，以及客户端应用链接的客户端库；如图1所示。Chubby客户端与服务器之间的所有通信都通过客户端库中转。可选的第三个组件——代理服务器，将在3.1节讨论。

图1：系统结构

一个Chubby单元由一小组服务器（通常为5个）组成，这些服务器被称为副本，部署时会尽量降低关联故障的概率（例如分布在不同机架上）。副本通过分布式共识协议选举出一个主节点；主节点必须获得多数副本的投票，并且这些副本会承诺在数秒的“主节点租约”期内，不会选举其他主节点。只要主节点持续赢得多数投票，副本就会定期更新主节点租约。

副本维护着同一个简易数据库的副本，但只有主节点可以发起数据库的读写操作。其他所有副本仅通过共识协议同步主节点发送的更新。

客户端通过向DNS中记录的副本发送主节点位置查询来找到主节点。非主节点副本会在响应中返回主节点的身份信息。客户端定位到主节点后，就会将所有请求直接发送给主节点，直到主节点不再响应，或者主节点表明自己已不再是主节点。

写入请求会通过共识协议同步到所有副本；当写入操作同步到单元内的多数副本后，请求才会被确认。读取请求仅由主节点直接响应；只要主节点租约未过期，这么做就是安全的，因为不可能存在其他主节点。

如果主节点发生故障，其他副本会在主节点租约到期后运行选举协议；新的主节点通常会在几秒内选举产生。例如，最近两次选举分别耗时6秒和4秒，但我们也见过长达30秒的情况（见4.1节）。

如果某个副本发生故障且数小时内无法恢复，简易替换系统会从空闲资源池中选择一台新机器，启动锁服务进程。之后系统会更新DNS表，用新副本的IP地址替换故障副本的地址。当前主节点会定期轮询DNS，最终会察觉到这一变化，然后更新单元数据库中的成员列表；该列表通过常规的复制协议在所有成员间保持一致。在此期间，新副本会从文件服务器上存储的备份，以及活跃副本的更新中，获取最新的数据库副本。一旦新副本处理完当前主节点待提交的某个请求，它就获得了参与新主节点选举的投票权。

2.3 文件、目录与句柄

Chubby对外提供的文件系统接口与UNIX[22]类似，但更简单。它采用标准的文件与目录树形结构，名称组件通过斜杠分隔。一个典型的名称如下：
/ls/foo/wombat/pouch

前缀ls是所有Chubby名称的公共前缀，代表锁服务（lock service）。第二部分（foo）是Chubby单元的名称；通过DNS解析可以得到对应单元的一个或多个Chubby服务器地址。特殊的单元名local表示使用客户端本地的Chubby单元；通常是同一栋建筑内的单元，因此也是最可能访问到的单元。名称的剩余部分/wombat/pouch会在指定的Chubby单元内部解析。

和UNIX一样，每个目录包含子文件和子目录的列表，每个文件则包含一段未解析的字节序列。

由于Chubby的命名结构类似文件系统，我们既可以通过专属API提供服务，也可以通过谷歌其他文件系统（如GFS）使用的接口提供服务。这大幅降低了开发基础浏览和命名空间管理工具的成本，也减少了对普通Chubby用户的培训成本。

该设计在一些方面与UNIX不同，以适配分布式场景：

为了让不同目录下的文件可以由不同的Chubby主节点提供服务，我们不提供跨目录移动文件的操作，不维护目录修改时间，也不采用依赖路径的权限语义（即文件的访问权限由文件自身的权限控制，而非路径上的目录权限）。
为了更方便地缓存文件元数据，系统不暴露最后访问时间。

命名空间中仅包含文件和目录，二者统称为节点。每个节点在其单元内只有唯一名称；不存在符号链接或硬链接。

节点分为永久节点和临时节点。任何节点都可以被显式删除；而临时节点如果没有客户端打开（对于目录来说，还需要目录为空），也会被自动删除。临时文件可用作临时文件，也可用于向其他节点标识某个客户端处于存活状态。

任何节点都可以充当咨询型读写锁；锁的更多细节见2.4节。

每个节点都包含多种元数据，其中包括三组访问控制列表（ACL）的名称，分别控制节点的读取、写入和修改ACL权限。默认情况下，节点创建时会继承父目录的ACL名称。ACL本身也是存储在ACL目录下的文件，该目录是单元本地命名空间中一个固定的位置。这些ACL文件由简单的主体名称列表组成；读者可能会联想到Plan 9的用户组[21]。因此，如果文件F的写入ACL名称为foo，且ACL目录下的foo文件中包含条目bar，那么用户bar就拥有F的写入权限。用户身份通过RPC系统内置的机制进行认证。由于Chubby的ACL本身就是文件，其他需要类似访问控制机制的服务也可以直接使用它们。

每个节点的元数据包含4个单调递增的64位数字，方便客户端检测变更：

实例号：大于同名的任何历史节点的实例号。
内容生成号（仅文件）：文件内容被写入时递增。
锁生成号：节点的锁从空闲变为持有时递增。
ACL生成号：节点的ACL名称被写入时递增。

Chubby还提供64位的文件内容校验和，让客户端可以判断文件是否发生变化。

客户端通过打开节点获得句柄，类似于UNIX的文件描述符。句柄包含：

校验码：防止客户端伪造或猜测句柄，因此只需在创建句柄时执行完整的权限检查（对比UNIX：它在打开时检查权限位，但后续读写时不再检查，因为文件描述符无法被伪造）。
序列号：让主节点可以判断句柄是由自己生成的，还是由前任主节点生成的。
模式信息：打开时指定，让新重启的主节点可以重建旧句柄的状态。

2.4 锁与序列器

每个Chubby文件和目录都可以充当读写锁：要么一个客户端句柄以排他（写）模式持有锁，要么任意数量的客户端句柄以共享（读）模式持有锁。和大多数程序员熟悉的互斥锁一样，Chubby的锁是咨询性的。也就是说，锁仅与其他获取同一锁的请求产生冲突：持有名为F的锁，既不是访问文件F的必要条件，也不会阻止其他客户端访问该文件。

我们拒绝了强制锁方案——强制锁会让未持有锁的客户端无法访问被锁定的对象，原因如下：

Chubby锁通常保护的是其他服务实现的资源，而不仅仅是锁关联的文件本身。要实现有意义的强制锁，需要对这些服务做大量修改。
我们不希望用户在需要调试或管理访问被锁定的文件时，必须关闭应用程序。在复杂系统中，很难采用个人电脑上的常用方案——管理软件可以通过让用户关闭应用或重启系统来解除强制锁。
我们的开发者会通过常规方式做错误检查，比如编写“锁X已持有”这样的断言，因此强制检查带来的收益很小。有缺陷或恶意的进程有很多机会在未持有锁的情况下破坏数据，因此强制锁提供的额外防护并没有显著价值。

在Chubby中，以任意模式获取锁都需要写入权限，这样可以防止无权限的读者阻塞写者的执行。

分布式系统中的锁之所以复杂，是因为通信通常是不可靠的，并且进程可能独立发生故障。因此，持有锁L的进程可能发出请求R，随后发生故障。另一个进程可能获取锁L并执行某些操作，之后请求R才到达目的地。如果此时处理请求R，就会在没有锁L保护的情况下执行操作，可能导致数据不一致。消息乱序接收的问题已经被广泛研究；解决方案包括虚拟时间[11]和虚拟同步[1]，后者通过确保消息处理顺序与所有参与者的观测一致，从根本上避免了问题。

在现有复杂系统的所有交互中都引入序列号，成本很高。而Chubby提供了一种方案，只需要在使用锁的交互中引入序列号。在任何时候，锁持有者都可以请求一个序列器——一段不透明的字节串，描述获取锁之后锁的即时状态。它包含锁的名称、获取模式（排他或共享）以及锁生成号。

如果客户端希望某个操作受到锁的保护，就可以将序列器传递给服务器（比如文件服务器）。接收服务器需要校验序列器是否仍然有效、模式是否匹配；如果不满足，则拒绝请求。服务器可以通过自身的Chubby缓存校验序列器的有效性；如果服务器不想维持与Chubby的会话，也可以用它观测到的最新序列器进行校验。序列器机制只需要在相关消息中增加一个字符串，并且很容易向开发者解释清楚。

尽管我们认为序列器简单易用，但重要协议的演进通常很缓慢。因此Chubby还提供了一种不完美但更简单的机制，降低不支持序列器的服务器收到延迟或乱序请求的风险。

如果客户端正常释放锁，锁会立即可供其他客户端获取，这符合预期。但如果锁是因为持有者故障或不可达而释放，锁服务器会在一段称为锁延迟（lock-delay）的时间内，阻止其他客户端获取该锁。客户端可以指定不超过上限的锁延迟时间，目前上限为1分钟；该限制可以防止故障客户端导致某个锁（以及对应的资源）长时间不可用。虽然不够完美，但锁延迟可以保护未修改的服务器和客户端，免受消息延迟和重启带来的常见问题。

2.5 事件

Chubby客户端在创建句柄时，可以订阅一系列事件。这些事件通过Chubby库的回调，异步地推送给客户端。事件包括：

文件内容修改：常用于监控通过文件广播的服务地址。
子节点新增、删除或修改：用于实现镜像功能（见2.12节）。（除了可以发现新文件，子节点事件还让客户端可以监控临时文件，而不会影响它们的引用计数。）
Chubby主节点故障转移：提醒客户端可能丢失了其他事件，因此必须重新扫描数据。
句柄（及其锁）失效：通常意味着出现了通信问题。
锁获取成功：可用于判断主节点何时选举完成。
其他客户端发起冲突锁请求：可用于实现锁的缓存。

事件会在对应操作完成之后送达。因此，如果客户端收到文件内容变更的通知，那么它后续读取该文件时，保证能看到新数据（或者更新的数据）。

最后两个事件很少被使用，事后看来其实可以省略。例如，在主节点选举后，客户端通常需要与新主节点通信，而不仅仅是知道主节点已经选出；因此它们会等待文件修改事件，表明新主节点已经将自己的地址写入文件。

冲突锁事件理论上允许客户端缓存其他服务器上的数据，用Chubby锁维护缓存一致性。当收到冲突锁请求的通知时，客户端就可以停止使用与该锁关联的数据：完成待处理操作、将修改同步回源位置、丢弃缓存数据，然后释放锁。到目前为止，还没有开发者采用这种使用模式。

2.6 应用程序接口

在客户端视角，Chubby句柄是一个指向不透明结构体的指针，支持多种操作。句柄只能通过Open()创建，通过Close()销毁。

Open()：打开指定的文件或目录，返回一个句柄，类似于UNIX文件描述符。只有该调用接收节点名称；其他所有调用都基于句柄操作。
名称会相对于已有的目录句柄进行解析；客户端库提供了根目录/的句柄，且始终有效。使用目录句柄可以避免在多层抽象的多线程程序中，使用全局当前目录带来的问题[18]。

客户端可以指定多种选项：
- 句柄的使用方式（读取、写入加锁、修改ACL）；只有客户端拥有对应权限时，才会创建句柄。
- 需要接收的事件（见2.5节）。
- 锁延迟时间（见2.4节）。
- 是否需要创建新的文件或目录。如果创建文件，调用者可以提供初始内容和初始ACL名称。返回值会指示文件是否为新建。
Close()：关闭一个已打开的句柄。之后不允许再使用该句柄。该调用永远不会失败。
相关的Poison()调用会让该句柄上未完成和后续的操作都失败，但不会关闭句柄；这允许客户端取消其他线程发起的Chubby调用，而不用担心释放正在被访问的内存。

针对句柄的主要操作包括：

GetContentsAndStat()：返回文件的内容和元数据。文件内容是原子读取的，且一次性读取全部内容。我们刻意不支持部分读写，以避免文件过大。
相关的GetStat()仅返回元数据；ReadDir()返回目录下子节点的名称和元数据。
SetContents()：写入文件内容。客户端可以可选地提供一个内容生成号，实现文件的比较并交换（compare-and-swap）语义——只有当生成号与当前值匹配时，内容才会被修改。文件内容总是原子写入的，且一次性写入全部内容。
相关的SetACL()对节点关联的ACL名称执行类似操作。
Delete()：如果节点没有子节点，则删除该节点。
Acquire()、TryAcquire()、Release()：获取和释放锁。
GetSequencer()：返回一个序列器（见2.4节），描述该句柄持有的锁的状态。
SetSequencer()：将序列器与句柄关联。如果序列器不再有效，后续对该句柄的操作都会失败。
CheckSequencer()：校验序列器是否有效（见2.4节）。

如果句柄创建后节点被删除，哪怕之后又重新创建了同名节点，该句柄上的操作也会失败。也就是说，句柄关联的是文件的一个实例，而非文件名。Chubby可以在任意调用中执行权限检查，但Open()调用一定会检查（见2.3节）。

上述所有调用除了自身所需的参数外，都还接收一个操作参数。该参数包含与调用关联的数据和控制信息。特别是，通过操作参数，客户端可以：

提供回调函数让调用异步执行，等待异步调用完成，并且/或者获取详细的错误和诊断信息。

客户端可以通过这套API实现主节点选举，流程如下：
所有候选主节点打开锁文件，尝试获取锁。其中一个成功成为主节点，其余作为副本。主节点通过SetContents()将自身身份写入锁文件，这样客户端和副本就可以通过GetContentsAndStat()读取文件找到主节点——通常是响应文件修改事件（见2.5节）。
理想情况下，主节点通过GetSequencer()获取序列器，然后传递给与之通信的服务器；这些服务器应该通过CheckSequencer()确认主节点身份仍然有效。对于无法校验序列器的服务，可以使用锁延迟机制（见2.4节）。

2.7 缓存

为了减少读取流量，Chubby客户端会在内存中缓存文件数据和节点元数据（包括文件不存在的状态），采用一致性的写直达缓存策略。缓存通过下文所述的租约机制维护，并通过主节点发送的失效通知保持一致性；主节点会维护每个客户端可能缓存的内容列表。该协议保证客户端要么看到一致的Chubby状态，要么收到错误。

当需要修改文件数据或元数据时，修改操作会被阻塞，同时主节点向所有可能缓存了该数据的客户端发送失效通知；该机制基于保活（KeepAlive）RPC实现，下一节会详细说明。
收到失效通知后，客户端会清空失效的状态，并在下次保活调用中进行确认。只有当服务器确认所有客户端都已失效缓存（要么客户端确认失效，要么客户端的缓存租约过期）之后，修改操作才会继续执行。

只需要一轮失效通知即可，因为在缓存失效未被确认期间，主节点会将该节点标记为不可缓存。这种设计让读取操作始终可以无延迟处理；这一点很重要，因为读操作的数量远多于写操作。
另一种方案是在失效期间阻塞访问该节点的调用；这样可以减少失效期间客户端大量未缓存请求冲击主节点的情况，但代价是偶尔会产生延迟。如果这成为问题，可以采用混合方案，在检测到过载时切换策略。

缓存协议的逻辑很简单：数据变更时让缓存失效，而不是更新缓存。更新缓存和失效缓存的实现复杂度相近，但只更新的协议可能效率极低；一个访问过某个文件的客户端可能会持续收到更新，产生大量不必要的更新消息。

尽管提供严格一致性会带来额外开销，但我们还是拒绝了更弱的一致性模型，因为我们认为程序员更难理解和使用弱模型。同样，像虚拟同步这类要求客户端在所有消息中交换序列号的机制，在存在大量既有通信协议的环境中也不适用。

除了缓存数据和元数据，Chubby客户端还会缓存打开的句柄。因此，如果客户端打开一个之前打开过的文件，只有第一次Open()调用需要向主节点发起RPC。
这种缓存有一些小的限制，确保不会影响客户端观察到的语义：

临时文件的句柄如果被应用关闭，就不能继续持有。
支持加锁的句柄可以复用，但不能被多个应用句柄同时使用。这是因为客户端可能会用Close()或Poison()的副作用来取消未完成的Acquire()调用。

Chubby的协议允许客户端缓存锁——也就是说，持有锁的时间可以比实际需要的更长，期望后续可以再次使用。如果有其他客户端发起冲突的锁请求，会通过事件通知当前锁持有者，让持有者在其他地方需要锁时及时释放（见2.5节）。

2.8 会话与保活机制

Chubby会话是Chubby单元与Chubby客户端之间的一种关系，会持续一段时间，通过称为**保活（KeepAlive）**的周期性握手来维护。除非Chubby客户端主动通知主节点，否则只要会话保持有效，客户端的句柄、锁和缓存数据就都保持有效。（不过，会话维护协议可能要求客户端确认缓存失效，才能维持会话；见下文。）

客户端首次连接Chubby单元的主节点时，会请求创建新会话。会话会在客户端终止时显式结束，或者如果会话空闲（没有打开的句柄，也没有调用）达到一分钟，也会自动结束。

每个会话都关联一个租约——一段未来的时间区间，在此区间内主节点保证不会单方面终止会话。该区间的结束时间称为会话租约超时。主节点可以将超时时间向未来推移，但不能往回调整。

主节点会在三种情况下延长租约超时：会话创建时、主节点故障转移时（见下文），以及响应客户端的保活RPC时。
收到保活请求后，主节点通常会阻塞该RPC（不让它返回），直到客户端上一个租约区间即将到期。之后主节点才让RPC返回给客户端，通知客户端新的租约超时时间。主节点可以任意延长超时时间，默认延长12秒；但过载的主节点可以使用更大的值，减少需要处理的保活调用数量。
客户端在上一次保活回复返回后，会立即发起新的保活请求。这样，客户端确保几乎总有一个保活调用在主节点处处于阻塞状态。

除了延长客户端租约，保活回复还用于向客户端传递事件和缓存失效通知。当需要推送事件或失效通知时，主节点会让保活请求提前返回。
将事件搭载在保活回复上，既保证了客户端必须确认缓存失效才能维持会话，又让所有Chubby RPC都由客户端向主节点单向发起。这简化了客户端实现，并且让协议可以穿越只允许单向发起连接的防火墙。

客户端维护一个本地租约超时，是对主节点租约超时的保守估计。它和主节点的租约超时存在差异，因为客户端必须保守估计保活回复的网络传输时间，以及主节点时钟的推进速率；为了保证一致性，我们要求服务器时钟的推进速率，不能比客户端时钟快出一个已知的常数因子。

如果客户端的本地租约超时到期，客户端就无法确定主节点是否已经终止了会话。客户端会清空并禁用缓存，此时我们称会话处于危险状态（jeopardy）。
客户端会再等待一段称为宽限期的时间，默认45秒。如果在宽限期结束前，客户端与主节点成功完成了一次保活交互，客户端就会重新启用缓存。否则，客户端认为会话已经过期。
这样设计是为了避免Chubby单元不可达时，Chubby API调用无限阻塞；如果通信恢复前宽限期就结束，调用会返回错误。

Chubby库可以通过“危险状态事件”通知应用宽限期开始。当确认会话成功度过通信问题后，会发送“安全事件”让客户端继续；如果会话最终超时，则发送“过期事件”。
这些信息让应用程序可以在不确定会话状态时暂停自身运行，如果问题只是暂时的，就无需重启就能恢复。对于启动开销很大的服务，这对于避免服务中断非常重要。

如果客户端持有节点的句柄H，且关联的会话过期导致H上的某个操作失败，那么H上所有后续操作（除了Close()和Poison()）都会以同样的方式失败。客户端可以利用这一点，保证网络和服务器中断只会导致一系列操作的末尾部分失败，而不是随机中间的操作失败；这样就可以通过最后一次写入来标记复杂变更是否提交。

2.9 故障转移

当主节点发生故障或者失去主节点身份时，它会丢弃会话、句柄和锁的内存状态。会话租约的权威计时器运行在主节点上，因此在新主节点选出之前，会话租约计时器会停止；这是合法的，因为这等价于延长了客户端的租约。

如果主节点选举很快完成，客户端可以在本地（近似）租约计时器到期前联系上新主节点。如果选举耗时较长，客户端会清空缓存，在尝试找到新主节点的同时等待宽限期。因此，宽限期允许会话在超过正常租约超时的故障转移过程中保持有效。

图2展示了一次耗时较长的主节点故障转移的事件序列，客户端必须使用宽限期来保留会话。时间从左到右推进，但时间未按比例绘制。

图2：宽限期在主节点故障转移中的作用

客户端会话租约用粗箭头表示，分别从旧主节点、新主节点视角（上方M1-3）和客户端视角（下方C1-3）展示。向上的箭头表示保活请求，向下的箭头表示保活回复。
原主节点为客户端分配的会话租约为M1，客户端对应的保守估计为C1。主节点在通过第2次保活回复通知客户端之前，就已经承诺了租约M2；客户端得以将自身的租约视图延长到C2。
主节点在回复下一次保活之前发生故障，经过一段时间后新的主节点才被选出。最终，客户端对租约的估计值C2到期，客户端清空缓存并启动宽限期计时器。

在此期间，客户端无法确定自己的租约在主节点端是否已经过期。它不会销毁会话，但会阻塞所有API调用，防止应用程序观测到不一致的数据。
在宽限期开始时，Chubby库会向应用程序发送危险状态事件，让应用程序暂停运行，直到可以确认会话状态。

最终新主节点选举成功。新主节点最初会使用保守估计值M3，作为前任主节点可能为该客户端分配的会话租约时长。
客户端向新主节点发送的第一次保活请求（标记为4）会被拒绝，因为它使用了错误的主节点纪元号（下文会详细说明）。重试的请求（标记为6）成功，但通常不会进一步延长主节点租约，因为M3已经是保守估计了。不过回复（标记为7）让客户端可以再次延长自身的租约（C3），并且可以通知应用程序会话不再处于危险状态。
由于宽限期足够长，覆盖了从租约C2结束到租约C3开始的间隔，客户端只会感受到延迟，不会感知到故障。如果宽限期短于该间隔，客户端就会放弃会话，并向应用程序报告失败。

客户端联系上新主节点后，客户端库和主节点会协同工作，给应用程序造成没有发生故障的错觉。为此，新主节点必须重建出前任主节点内存状态的保守近似。它的信息来源包括：磁盘上稳定存储的数据（通过常规数据库复制协议同步）、从客户端获取的状态，以及保守假设。
数据库中记录了每个会话、持有的锁和临时文件。新当选的主节点会按以下步骤执行：

首先生成一个新的客户端纪元号，要求客户端在每次调用时都提供该编号。主节点会拒绝使用旧纪元号的客户端调用，并返回新的纪元号。这确保新主节点不会响应发送给前任主节点的旧数据包——哪怕前任主节点运行在同一台机器上。
新主节点可以响应主节点位置查询，但暂时不处理与会话相关的操作。
根据数据库中的记录，构建会话和锁的内存数据结构。会话租约会延长到前任主节点可能使用的最大值。
此时主节点允许客户端执行保活操作，但不允许其他会话相关操作。
向每个会话发送故障转移事件；这会让客户端清空缓存（因为可能遗漏了失效通知），并提醒应用程序可能丢失了其他事件。
主节点等待，直到每个会话都确认了故障转移事件，或者会话过期。
主节点允许所有操作继续执行。
如果客户端使用的是故障转移前创建的句柄（通过句柄中的序列号判断），主节点会重建该句柄的内存表示，并处理调用。如果重建的句柄被关闭，主节点会在内存中记录下来，确保在当前主节点纪元内不会被重建；这保证了延迟或重复的网络数据包，不会意外重建已关闭的句柄。有故障的客户端可能在未来的纪元中重建已关闭的句柄，但由于客户端本身已经故障，这种情况不会造成危害。
经过一段时间（比如1分钟）后，主节点会删除没有打开句柄的临时文件。客户端应当在故障转移后的这段时间内，刷新临时文件的句柄。这种机制带来了一个不太好的副作用：如果临时文件的最后一个客户端在故障转移期间丢失了会话，临时文件可能不会及时消失。

读者应该不会意外：故障转移相关代码的运行频率远低于系统其他部分，因此一直是各类有趣bug的来源。

2.10 数据库实现

Chubby的第一个版本使用Berkeley DB[20]的复制版本作为数据库。Berkeley DB提供B树结构，将字节串键映射到任意字节串值。我们实现了一个键比较函数，首先按路径名的组件数量排序；这样节点可以按路径名作为键，同时让同级节点在排序中相邻。由于Chubby不使用基于路径的权限，每次文件访问只需要一次数据库查询。

Berkeley DB使用分布式共识协议在多台服务器间复制数据库日志。加入主节点租约后，这与Chubby的设计相匹配，实现起来很直接。

尽管Berkeley DB的B树代码应用广泛、非常成熟，但它的复制代码是近期新增的，用户较少。软件维护者必须优先维护和改进最受欢迎的产品功能。虽然Berkeley DB的维护者解决了我们遇到的问题，但我们认为使用复制代码带来的风险超出了可接受范围。

因此，我们参考Birrell等人的设计[2]，实现了一个基于预写日志和快照的简易数据库。和之前一样，数据库日志通过分布式共识协议在副本间分发。Chubby只用到了Berkeley DB的很少一部分功能，因此这次重写让整个系统得到了大幅简化；例如，我们需要原子操作，但不需要通用事务。

2.11 备份

每隔几小时，每个Chubby单元的主节点都会将数据库快照写入另一栋建筑的GFS文件服务器[7]。使用不同建筑既保证了备份能在建筑损毁时幸存，也避免了系统中出现循环依赖；同一栋建筑内的GFS单元可能依赖该Chubby单元选举主节点。

备份既用于灾难恢复，也用于初始化新替换副本的数据库，避免给运行中的副本增加负载。

2.12 镜像

Chubby允许将一组文件从一个单元镜像到另一个单元。镜像速度很快，因为文件本身很小，并且事件机制（见2.5节）会在文件新增、删除或修改时立即通知镜像程序。如果没有网络问题，变更会在不到一秒的时间内同步到全球数十个镜像节点。如果某个镜像不可达，它会保持不变，直到连接恢复；之后通过比较校验和来识别更新的文件。

镜像最常用于将配置文件复制到全球各地的计算集群。有一个名为global的特殊单元，它包含子树/ls/global/master，该子树会被镜像到所有其他Chubby单元的/ls/cell/slave子树。
全局单元的特殊之处在于，它的5个副本分布在全球相距很远的位置，因此从公司绝大多数地方都几乎总能访问到。

从全局单元镜像的文件包括：Chubby自身的访问控制列表、Chubby单元和其他系统向监控服务上报自身状态的各类文件、客户端定位大数据集（比如Bigtable单元）的指针，以及其他系统的大量配置文件。

3 扩展机制

Chubby的客户端是独立的进程，因此Chubby需要处理的客户端数量比预期多得多；我们观测到最多有9万个客户端直接与单个Chubby主节点通信——远多于涉及的机器数量。
由于每个单元只有一个主节点，且主节点的机器配置与客户端机器相同，客户端很容易就会让主节点过载。因此，最有效的扩展技术是大幅减少与主节点的通信。只要主节点没有严重的性能bug，优化主节点的请求处理带来的提升很小。我们采用了多种方法：

我们可以创建任意数量的Chubby单元；客户端几乎总是使用就近的单元（通过DNS发现），避免依赖远程机器。我们的典型部署是，一个包含数千台机器的数据中心对应一个Chubby单元。
主节点在高负载时，可以将租约时长从默认的12秒增加到约60秒，这样需要处理的保活RPC就更少。（保活请求是绝对的主流请求类型，见4.1节；无法及时处理保活请求是服务器过载的典型故障模式；而客户端对其他调用的延迟变化基本不敏感。）
Chubby客户端会缓存文件数据、元数据、文件不存在的状态，以及打开的句柄，减少向服务器发起的调用次数。
我们使用协议转换服务器，将Chubby协议转换为更简单的协议，比如DNS等。下文会讨论其中一部分。

本节介绍两种常见的机制：代理和分区，我们预计它们可以让Chubby进一步扩展。我们尚未在生产环境中使用它们，但已经完成设计，可能很快就会投入使用。
我们目前不需要考虑超过5倍的扩展：首先，一个数据中心内可以容纳的机器数量是有限的，让太多机器依赖单个服务实例也不现实。其次，由于Chubby的客户端和服务器使用类似的硬件，单台机器客户端数量的提升，也会相应提升单台服务器的处理能力。

3.1 代理

Chubby协议可以通过可信进程进行代理（两端使用相同协议），代理将其他客户端的请求转发给Chubby单元。
代理可以通过处理保活请求和读取请求来降低服务器负载；它无法减少写流量，因为写请求需要穿透代理缓存。但即使客户端缓存做得很好，写流量也不到Chubby正常工作负载的1%（见4.1节），因此代理可以大幅增加支持的客户端数量。
如果一个代理服务N_proxy个客户端，保活流量就会降低为原来的1/N_proxy，这个系数可以达到1万甚至更高。代理缓存最多可以将读流量降低到原来的1/读共享系数——大约10倍（见4.1节）。但由于目前读操作占Chubby负载不到10%，保活流量的节省才是最主要的效果。

代理会让写入和首次读取多增加一次RPC。有人可能会认为，代理会让单元的临时不可用概率至少增加一倍，因为每个通过代理的客户端依赖两台可能故障的机器：代理本身和Chubby主节点。

细心的读者会注意到，2.9节描述的故障转移策略对于代理来说并不理想。我们会在4.4节讨论这个问题。

3.2 分区

如2.3节所述，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本身就是文件，因此一个分区可能需要访问另一个分区来做权限检查。不过ACL文件很容易缓存；只有Open()和Delete()调用需要ACL检查；而且大多数客户端读取的是公开可访问的文件，不需要ACL校验。
删除目录时，可能需要跨分区调用，确保目录为空。

由于每个分区都能独立处理绝大多数请求，我们预计这类通信对性能和可用性的影响很小。

除非分区数量N很大，否则每个客户端可能都会和大多数分区建立连接。因此，分区可以让每个分区的读写流量降低为原来的1/N，但不一定能减少保活流量。
如果未来Chubby需要支持更多客户端，我们的策略会是代理与分区相结合。

4 使用情况、意外问题与设计失误

4.1 使用情况与运行表现

下表是某个Chubby单元的快照统计数据；RPC速率是10分钟内的观测值，这些数据在谷歌的单元中具有代表性。

指标	数值
距上次故障转移时间	18天
故障转移持续时间	14秒
活跃直连客户端	2.2万
代理转发的额外客户端	3.2万
打开的文件数	1.2万
命名相关占比	60%
客户端缓存文件条目数	23万
缓存的不同文件数	2.4万
负缓存（文件不存在）条目数	3.2万
排他锁数量	1000
共享锁数量	0
存储的目录数	8000
临时目录占比	0.1%
存储的文件数	2.2万
0-1KB文件占比	90%
1KB-10KB文件占比	10%
>10KB文件占比	0.2%
命名相关占比	46%
镜像的ACL与配置信息占比	27%
GFS与Bigtable元数据占比	11%
临时文件占比	3%
RPC速率	1000-2000次/秒
保活请求占比	93%
GetStat占比	2%
Open占比	1%
CreateSession占比	1%
GetContentsAndStat占比	0.4%
SetContents占比	680ppm（百万分之680）
Acquire占比	31ppm（百万分之31）

从中可以看出几点规律：

大量文件用于命名服务，见4.3节。
配置、访问控制和元数据文件（类似文件系统的超级块）很常见。
负缓存的作用很显著。
平均每个缓存文件被约10个客户端使用（23万/2.4万≈10）。
持有锁的客户端很少，共享锁更是罕见；这与锁用于主节点选举和副本间数据划分的用途一致。
RPC流量以会话保活请求为主；读请求数量很少（都是缓存未命中）；写请求和锁获取则非常少。

接下来简要介绍单元故障的典型原因。
如果乐观地将“可用”定义为存在主节点并可以提供服务，在我们的单元样本中，数周内共记录了61次故障，对应总计700个单元·天的数据。我们排除了数据中心停机维护导致的故障，包含了其他所有原因：网络拥塞、运维、过载，以及操作、软件、硬件导致的错误。
大多数故障持续时间不超过15秒，其中52次少于30秒；对于我们的绝大多数应用，30秒以内的Chubby故障不会造成显著影响。
剩下的9次故障原因分别是：网络维护（4次）、疑似网络连通性问题（2次）、软件错误（2次）、过载（1次）。

在数十年的单元运行总时长中，我们共发生过6次数据丢失，原因分别是数据库软件错误（4次）和操作失误（2次）；没有一次是硬件错误导致的。讽刺的是，那几次操作失误恰恰是为了升级以避免软件错误。我们还两次修复了非主节点副本中由软件导致的数据损坏。

Chubby的数据可以完全放在内存中，因此大多数操作开销很低。生产服务器的平均请求延迟始终在亚毫秒级别，和单元负载关系不大；直到单元接近过载，延迟才会急剧上升，并且会话开始被丢弃。
过载通常发生在活跃会话超过9万个的时候，但也可能由特殊情况触发：比如客户端同时发起数百万次读请求（见4.3节），或者客户端库的某个bug导致部分读取无法缓存，造成每秒数万次请求。
由于绝大多数RPC都是保活请求，服务器可以通过延长会话租约周期，在大量活跃客户端的情况下仍保持较低的平均请求延迟（见第3节）。
当写入请求突发到来时，组提交可以降低每个请求的实际开销，但这种情况很少见。

客户端侧的RPC读取延迟受RPC系统和网络限制；本地单元的延迟在1毫秒以内，但跨半球的延迟可达250毫秒。
写入操作（包括锁操作）会因为数据库日志更新额外增加5-10毫秒延迟；但如果最近故障的客户端缓存了该文件，延迟可能高达数十秒。
不过由于写入非常少，这种写入延迟的波动对服务器平均请求延迟的影响很小。

只要会话不被丢弃，客户端对延迟波动的容忍度相当高。我们曾经为了遏制滥用客户端，在Open()调用中加入人工延迟；直到延迟超过10秒并且反复出现，开发者才注意到异常。

我们发现，扩展Chubby的关键不在于服务器性能；减少与服务器的通信能带来大得多的提升。我们没有在读写服务代码路径的调优上投入太多精力；在确认没有明显bug之后，我们就将重点放在了效果更显著的扩展机制上。
另一方面，如果性能bug影响到了客户端本地的Chubby缓存——客户端可能每秒读取数千次——开发者确实会察觉到。

4.2 Java客户端

谷歌的基础设施大多使用C++开发，但越来越多的系统开始使用Java[8]。这一趋势给Chubby带来了意料之外的问题——Chubby的客户端协议比较复杂，客户端库也有一定的实现难度。

Java鼓励整个应用的可移植性，但代价是增量接入的成本较高，因为与其他语言链接相当麻烦。Java访问非原生库的标准机制是JNI[15]，但普遍认为它速度慢、使用繁琐。我们的Java开发者非常排斥JNI，为了避免使用JNI，他们更愿意将大型库翻译成Java版本，并投入精力维护。

Chubby的C++客户端库有7000行代码（和服务器端相当），并且客户端协议非常精细。用Java维护这套库需要投入大量精力和成本；而如果实现不带缓存的版本，又会给Chubby服务器带来沉重负担。
因此，我们的Java用户会运行协议转换服务器，对外提供与Chubby客户端API高度对应的简易RPC协议。现在回头看，我们也很难想到有什么办法能避免编写、运行和维护这一额外服务器的成本。

4.3 作为命名服务的使用

尽管Chubby是作为锁服务设计的，但我们发现它最广泛的用途是作为命名服务器。

传统互联网命名系统DNS的缓存基于时间机制。DNS条目有生存时间（TTL），超过该时间未刷新就会被丢弃。通常选择合适的TTL值并不难，但如果要求故障服务能被快速替换，TTL就需要设置得很小，以至于DNS服务器会过载。

例如，我们的开发者经常运行包含数千个进程的任务，每个进程都要和其他所有进程通信，这就产生了平方级的DNS查询量。
我们可能希望使用60秒的TTL；这既能让故障客户端被及时替换，在我们的环境中也不算太短。在这种情况下，仅一个3000个客户端的任务，维持DNS缓存就需要每秒15万次查询。（作为对比，一台2CPU、2.6GHz的至强DNS服务器每秒大约能处理5万次请求。）更大的任务问题更严重，而且可能同时运行多个任务。在Chubby推出之前，DNS负载的波动一直是谷歌的一个严重问题。

相比之下，Chubby的缓存使用显式失效机制，因此只要没有变更，客户端只需以固定速率发送会话保活请求，就可以无限期维护任意数量的缓存条目。
我们观测到，一台2CPU、2.6GHz的至强Chubby主节点，可以直接承载9万个客户端（无代理）；其中包括具备上述通信模式的大型任务。
Chubby能够快速更新名称、无需逐个轮询每个名称，这一优势极具吸引力，因此现在它已经成为公司绝大多数系统的命名服务。

尽管Chubby的缓存机制让单个单元可以支撑大量客户端，但负载尖峰仍然可能造成问题。
我们刚部署基于Chubby的命名服务时，启动一个3000进程的任务（会产生900万次请求）就可能让Chubby主节点瘫痪。为了解决这个问题，我们选择将名称条目分组，这样一次查询就可以返回并缓存一个任务内大量（通常100个）相关进程的名称映射。

Chubby提供的缓存语义比命名服务需要的更强；名称解析只需要及时通知，不需要完全一致性。因此，本来有机会通过引入专门用于名称查询的简易协议转换服务器，来降低Chubby的负载。
如果我们当初预见到Chubby会被用作命名服务，可能会更早实现完整的代理功能，也就不需要这个简单但额外的服务器了。

还有一个协议转换服务器：Chubby DNS服务器。它将Chubby中存储的命名数据提供给DNS客户端。这个服务器非常重要，既可以平滑从DNS名称到Chubby名称的过渡，也可以兼容浏览器等难以改造的现有应用。

4.4 故障转移相关问题

主节点故障转移的原始设计（见2.9节）要求主节点在创建会话时，就将会话写入数据库。在基于Berkeley DB的锁服务器版本中，当大量进程同时启动时，创建会话的开销会成为问题。
为了避免过载，服务器做了修改：会话不在首次创建时写入数据库，而是在第一次执行修改操作、获取锁或者打开临时文件时才写入。此外，活跃会话会在每次保活时以一定概率写入数据库。这样，只读会话的写入操作就被分散到了不同时间。

尽管这是避免过载的必要优化，但它也带来了副作用：新建的只读会话可能不会被记录在数据库中，因此发生故障转移时可能会被丢弃。
虽然这些会话不持有锁，但这仍然是不安全的；如果所有已记录的会话都在被丢弃会话的租约到期前，向新主节点完成了签到，那么被丢弃的会话就可能在一段时间内读取到过期数据。
这种情况在实践中很少发生；在大型系统中，几乎必然会有某个会话无法及时签到，从而迫使新主节点等待最长租约时间。
尽管如此，我们还是修改了故障转移设计，既避免了这个问题，也解决了当前方案给代理带来的复杂度。

在新设计下，我们完全不在数据库中记录会话，而是采用主节点重建句柄的方式（见2.9节第8条）来重建会话。
新主节点现在必须等待完整的最坏情况租约超时，之后才能允许操作继续，因为它无法确认是否所有会话都已签到（见2.9节第6条）。同样，这在实践中影响很小，因为本来就不太可能所有会话都能及时签到。

当会话可以无需磁盘状态重建后，代理服务器就可以管理主节点感知不到的会话。代理专属的额外操作允许它们变更锁关联的会话。这使得当某个代理故障时，另一个代理可以接管它的客户端。
主节点只需要额外保证：在新代理有机会接管之前，不会释放代理会话关联的锁或临时文件句柄。

4.5 异常客户端行为

谷歌的项目团队可以自行搭建Chubby单元，但这样会增加他们的维护负担，也会消耗额外的硬件资源。因此很多服务都使用共享的Chubby单元，这就使得隔离客户端异常行为的影响变得很重要。
Chubby的定位是在公司内部运行，因此恶意的拒绝服务攻击很少见。然而，开发者的失误、误解，以及不同的预期，还是会造成类似攻击的效果。

我们的一些应对措施比较直接。例如，我们会审核项目团队使用Chubby的方案，在审核通过前，不允许他们使用共享的Chubby命名空间。
这种方式的问题在于，开发者往往无法预测他们的服务未来会如何使用，以及使用规模会如何增长。读者应该能感受到其中的讽刺：我们自己都没能预测到Chubby本身的使用方式。

我们审核的核心是判断Chubby资源（RPC速率、磁盘空间、文件数量）的使用是否会随用户数量或数据处理量线性（甚至更差）增长。任何线性增长都必须通过可调参数来缓解，将Chubby的负载控制在合理范围内。尽管如此，我们早期的审核还是不够全面。

另一个相关问题是，大多数软件文档都缺少性能建议。一个团队编写的模块，一年后可能被另一个团队复用，造成灾难性的后果。有时候很难向接口设计者解释：必须修改接口不是因为接口本身不好，而是因为其他开发者可能意识不到RPC的成本。

下面列举我们遇到的一些典型问题：

缓存使用不充分
最初，我们没有意识到缓存文件不存在状态、复用打开的文件句柄至关重要。尽管做了培训，我们的开发者还是经常写出这样的代码：文件不存在时就无限循环重试，或者通过反复打开关闭文件来轮询，而不是只打开一次文件。

一开始，我们通过引入指数退避延迟来应对这种重试循环——如果应用在短时间内多次尝试打开同一个文件，延迟会不断增加。在某些情况下，这暴露出了开发者承认的bug，但更多时候还是需要我们花时间做培训。最终，让重复的Open()调用变得更廉价，才是更简单的解决方案。

缺少配额
Chubby从来就不是设计用来存储大量数据的，因此没有设置存储配额。事后看来，这太天真了。

谷歌的一个项目编写了一个跟踪数据上传的模块，将一些元数据存储在Chubby中。这类上传很少发生，并且只面向少数用户，因此空间占用是可控的。
然而，另外两个服务也开始使用同一个模块，用来跟踪更广泛用户的上传。最终，这些服务的规模增长到了极端程度：一个1.5MB的文件，每次用户操作都会被完整重写；该服务占用的总空间，超过了其他所有Chubby客户端的空间需求总和。

我们引入了256KB的文件大小限制，并推动这些服务迁移到更合适的存储系统。但要对繁忙人员维护的生产系统做重大修改非常困难——数据花了大约一年才全部迁移出去。

发布/订阅模式滥用
曾有多次尝试将Chubby的事件机制用作Zephyr[6]风格的发布/订阅系统。
Chubby的强一致性保证，以及它通过失效而非更新来维护缓存一致性的方式，使得它对于除了最简单场景之外的发布/订阅来说，既慢又低效。幸运的是，这类使用都在应用改造成本过高之前被及时制止了。

4.6 经验教训

这里我们总结了经验教训，以及如果有机会会做出的一些设计调整：

开发者很少考虑可用性
我们发现，开发者很少考虑故障概率，倾向于将Chubby这类服务视为永远可用。
例如，我们的开发者曾经搭建过一个包含数百台机器的系统，当Chubby选举新主节点时，系统会启动长达数十分钟的恢复流程。这将单次故障的影响，在时间和受影响机器数量上都放大了一百倍。
我们更希望开发者为短时的Chubby故障做好预案，让这类事件对应用几乎没有影响。这也是我们主张粗粒度锁的原因之一，见2.1节。

开发者还容易混淆两个概念：服务本身正常运行，与服务对他们的应用可用。
例如，全局Chubby单元（见2.12节）几乎总是正常运行的，因为两个以上相距遥远的数据中心同时故障的概率很低。然而，对于特定客户端来说，它的观测可用性通常低于本地Chubby单元。
原因有二：首先，本地单元与客户端发生网络分区的概率更低；其次，尽管本地单元可能因为维护而停机，但维护本身会直接影响客户端，因此客户端并不会感知到Chubby不可用。

我们的API设计也会影响开发者处理Chubby故障的方式。例如，Chubby提供事件让客户端检测主节点故障转移。初衷是让客户端检查可能的变更，因为可能丢失了其他事件。
但不幸的是，很多开发者选择在收到该事件时直接让应用崩溃，反而大幅降低了自身系统的可用性。
我们或许应该改为发送冗余的“文件变更”事件，或者干脆确保故障转移期间不会丢失任何事件。

目前我们通过三种机制，防止开发者对Chubby（尤其是全局单元）的可用性过于乐观：
第一，如前所述（见4.5节），我们审核项目团队的Chubby使用方案，建议他们不要采用将自身可用性与Chubby过度绑定的技术。
第二，我们现在提供封装了高层任务的库，自动将开发者与Chubby故障隔离开。
第三，我们对每次Chubby故障做复盘，不仅修复Chubby本身和运维流程中的bug，也降低应用对Chubby可用性的敏感度——两者都能提升整体系统的可用性。

细粒度锁并非刚需
在2.1节末尾，我们概述了一种客户端可以自行运行的细粒度锁服务器设计。有点意外的是，到目前为止我们都不需要开发这样的服务器；我们的开发者通常发现，为了优化应用，必须减少不必要的通信，而这往往意味着采用粗粒度锁。

糟糕的API设计会带来意外影响
总体来说，我们的API演进得不错，但有一个失误很突出。
我们取消长耗时调用的方式是Close()和Poison() RPC，它们同时也会丢弃句柄的服务器状态。这导致可以获取锁的句柄无法被多个线程共享。我们可能会新增Cancel() RPC，让打开的句柄可以更多地被共享。

RPC使用影响传输协议选择
保活请求既用于刷新客户端的会话租约，也用于从主节点向客户端传递事件和缓存失效通知。这种设计带来了一个自然而然的理想结果：客户端必须确认缓存失效，才能刷新会话租约。

这看起来很完美，直到它在协议选择上带来了矛盾。TCP的退避策略不会考虑Chubby租约这类高层超时，因此基于TCP的保活请求在网络高拥塞时，会导致大量会话丢失。
我们被迫改用UDP发送保活RPC；但UDP没有拥塞避免机制，我们只在必须满足高层时间限制的场景下才愿意使用UDP。

我们可能会给协议增加一个基于TCP的GetEvent() RPC，用于正常情况下传递事件和失效通知，用法和保活请求类似。保活回复中仍然会包含未确认的事件列表，确保事件最终必须被确认。

5 相关工作对比

Chubby建立在诸多成熟思想的基础之上。
Chubby的缓存设计源自分布式文件系统的相关研究[10]。它的会话和缓存令牌在行为上与Echo[17]中的类似；会话则降低了V系统中租约[9]的开销。
提供通用锁服务的思路在VMS[23]中就已出现，不过该系统最初使用专用高速互联网络，实现了低延迟交互。
和缓存模型一样，Chubby的API也基于文件系统模型，包括“类文件系统的命名空间不止适合存储文件”这一思想[18,21,22]。

Chubby与Echo、AFS[10]这类分布式文件系统的区别在于性能和存储定位：
客户端不会读写、存储大量数据，也不追求高吞吐量甚至低延迟——除非数据已经被缓存。他们更看重一致性、可用性和可靠性，而当性能要求不高时，这些属性更容易实现。
由于Chubby的数据库很小，我们可以在线存储多份副本（通常5个副本加几份备份）。我们每天会执行多次全量备份，并且每隔几小时就通过数据库状态校验和对比副本之间的数据。
通过弱化常规文件系统的性能和存储要求，我们可以用单个Chubby主节点服务数万个客户端。通过提供一个让众多客户端共享信息、协调活动的中心节点，我们解决了系统开发者面临的一类共性问题。

文献中描述了大量文件系统和锁服务器，无法逐一对比，因此我们选取一个进行详细对比：我们选择Boxwood锁服务[16]，因为它是近期设计的，同样面向松耦合环境，且设计与Chubby存在多方面差异——有些是本质差异，有些是附带差异。

Chubby在单个服务中实现了锁、可靠小文件存储系统，以及会话/租约机制。相比之下，Boxwood将这三者拆分为三个独立组件：锁服务、Paxos服务（可靠状态存储库）和故障检测服务。Boxwood系统本身将这三个组件结合使用，但其他系统可以独立使用这些构建块。
我们怀疑这种设计差异源于目标用户的不同。Chubby面向多样化的用户和应用场景：用户既包括构建新型分布式系统的专家，也包括编写管理脚本的新手。对于我们的环境，提供一个拥有熟悉API的大规模共享服务更具吸引力。
相比之下，Boxwood提供的是一套工具集（至少在我们看来），更适合少数经验更丰富的开发者，他们的项目可能共享代码，但不需要统一使用。

在很多方面，Chubby提供的接口比Boxwood更高层。例如，Chubby将锁和文件命名空间合二为一，而Boxwood的锁名称只是简单的字节序列。Chubby客户端默认缓存文件状态；Boxwood的Paxos服务客户端也可以通过锁服务实现缓存，但通常会直接使用Boxwood自身提供的缓存。

两个系统的默认参数差异显著，对应了不同的预期：
每个Boxwood故障检测器每200毫秒就会被客户端访问一次，超时时间为1秒；而Chubby的默认租约时长是12秒，保活每7秒交互一次。
Boxwood的子组件使用2到3个副本来实现可用性，而我们每个单元通常使用5个副本。
不过，这些选择本身并不代表深层的设计差异，只是说明这类系统的参数必须根据客户端机器数量、与其他项目共享机架的不确定性等因素进行调整。

一个更有意思的差异是Chubby的宽限期，这是Boxwood没有的。（回顾一下：宽限期让客户端可以度过较长的Chubby主节点中断，而不会丢失会话或锁。Boxwood的“宽限期”等价于Chubby的“会话租约”，是完全不同的概念。）
同样，这种差异源于两个系统对规模和故障概率的不同预期。尽管主节点故障转移很少见，但丢失Chubby锁对客户端来说代价很高。

最后，两个系统中锁的设计用途不同。Chubby的锁更“重”，需要配合序列器才能安全保护外部资源；而Boxwood的锁更“轻”，主要用于Boxwood内部。

6 总结

Chubby是一款分布式锁服务，旨在为谷歌分布式系统内的活动提供粗粒度同步；它还被更广泛地用作命名服务和配置信息存储库。

它的设计基于诸多经典思想，并且结合得非常好：通过少量副本间的分布式共识实现容错，通过一致性客户端缓存减少服务器负载同时保持简单语义，通过事件及时通知更新，以及提供熟悉的文件系统接口。
我们使用缓存、协议转换服务器和简单的负载自适应机制，让每个Chubby实例可以扩展到支持数万个客户端进程。未来我们预计通过代理和分区进一步扩展。

Chubby已经成为谷歌首要的内部命名服务；它是MapReduce[4]等系统通用的协调机制；GFS和Bigtable等存储系统用Chubby从冗余副本中选举主节点；它也是访问控制列表等需要高可用性文件的标准存储库。

7 致谢

许多人为Chubby系统做出了贡献：
Sharon Perl编写了基于Berkeley DB的复制层；
Tushar Chandra和Robert Griesemer编写了替代Berkeley DB的复制数据库；
Ramsey Haddad将API接入了谷歌的文件系统接口；
Dave Presotto、Sean Owen、Doug Zongker和Praveen Tamara分别编写了Chubby DNS、Java客户端、命名协议转换器，以及完整的Chubby代理；
Vadim Furman增加了打开句柄缓存和文件不存在状态缓存；
Rob Pike、Sean Quinlan和Sanjay Ghemawat提供了宝贵的设计建议；
还有众多谷歌开发者发现了早期的缺陷。

参考文献

[1] BIRMAN, K. P., AND JOSEPH, T. A. Exploiting virtual synchrony in distributed systems. In 11th SOSP (1987), pp. 123–138.
[2] BIRRELL, A., JONES, M. B., AND WOBBER, E. A simple and efficient implementation for small databases. In 11th SOSP (1987), pp. 149–154.
[3] CHANG, F., DEAN, J., GHEMAWAT, S., HSIEH, W. C., WALLACH, D. A., BURROWS, M., CHANDRA, T., FIKES, A., AND GRUBER, R. Bigtable: A distributed structured data storage system. In 7th OSDI (2006).
[4] DEAN, J., AND GHEMAWAT, S. MapReduce: Simplified data processing on large clusters. In 6th OSDI (2004), pp. 137–150.
[5] FISCHER, M. J., LYNCH, N. A., AND PATERSON, M. S. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382.
[6] FRENCH, R. S., AND KOHL, J. T. The Zephyr Programmer’s Manual. MIT Project Athena, Apr. 1989.
[7] GHEMAWAT, S., GOBIOFF, H., AND LEUNG, S.-T. The Google file system. In 19th SOSP (Dec. 2003), pp. 29–43.
[8] GOSLING, J., JOY, B., STEELE, G., AND BRACHA, G. Java Language Spec. (2nd Ed.). Addison-Wesley, 2000.
[9] GRAY, C. G., AND CHERITON, D. R. Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. In 12th SOSP (1989), pp. 202–210.
[10] HOWARD, J., KAZAR, M., MENEES, S., NICHOLS, D., SATYANARAYANAN, M., SIDEBOTHAM, R., AND WEST, M. Scale and performance in a distributed file system. ACM TOCS 6, 1 (Feb. 1988), 51–81.
[11] JEFFERSON, D. Virtual time. ACM TOPLAS, 3 (1985), 404–425.
[12] LAMPORT, L. The part-time parliament. ACM TOCS 16, 2 (1998), 133–169.
[13] LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (2001), 18–25.
[14] LAMPSON, B. W. How to build a highly available system using consensus. In Distributed Algorithms, vol. 1151 of LNCS. Springer–Verlag, 1996, pp. 1–17.
[15] LIANG, S. Java Native Interface: Programmer’s Guide and Reference. Addison-Wesley, 1999.
[16] MACCORMICK, J., MURPHY, N., NAJORK, M., THEKKATH, C. A., AND ZHOU, L. Boxwood: Abstractions as the foundation for storage infrastructure. In 6th OSDI (2004), pp. 105–120.
[17] MANN, T., BIRRELL, A., HISGEN, A., JERIAN, C., AND SWART, G. A coherent distributed file cache with directory write-behind. TOCS 12, 2 (1994), 123–164.
[18] MCJONES, P., AND SWART, G. Evolving the UNIX system interface to support multithreaded programs. Tech. Rep. 21, DEC SRC, 1987.
[19] OKI, B., AND LISKOV, B. Viewstamped replication: A general primary copy method to support highly-available distributed systems. In ACM PODC (1988).
[20] OLSON, M. A., BOSTIC, K., AND SELTZER, M. Berkeley DB. In USENIX (June 1999), pp. 183–192.
[21] PIKE, R., PRESOTTO, D. L., DORWARD, S., FLANDRENA, B., THOMPSON, K., TRICKEY, H., AND WINTERBOTTOM, P. Plan 9 from Bell Labs. Computing Systems 8, 2 (1995), 221–254.
[22] RITCHIE, D. M., AND THOMPSON, K. The UNIX timesharing system. CACM 17, 7 (1974), 365–375.
[23] SNAMAN, JR., W. E., AND THIEL, D. W. The VAX/VMS distributed lock manager. Digital Technical Journal 1, 5 (Sept. 1987), 29–44.
[24] YIN, J., MARTIN, J.-P., VENKATARAMANI, A., ALVISI, L., AND DAHLIN, M. Separating agreement from execution for byzantine fault tolerant services. In 19th SOSP (2003), pp. 253–267.

【转载】面向松耦合分布式系统的Chubby锁服务（The Chubby Lock Service for Loosely-Coupled Distributed Systems）