译 The Chubby lock service

继续翻译论文，Chubby 是 Google 内部很多分布式系统依赖的重要组件之一，这里看原文

Design#

Rationale#

首先比较了 client Paxos library 和 centralized lock serivce 两种方式的差异。

client Paxos library 不依赖其他服务，而且可以提供标准的编程框架，但是在开发早期原型阶段不会充分考虑高可用性，且不适用于一致性协议。使用锁可以更方便的维护现有的程序结构和通信模式，不需要维护一定数量的 client 来保证达成共识，减少了实现可靠客户端系统所需的服务器数量。基于这些原因，作者选择了锁服务，并允许存储小文件以实现选举主节点和广告传播等功能。此外，作者还介绍了一些预期使用和环境方面的决策，包括支持大量客户端观察文件、事件通知机制、文件缓存和安全机制等。

System structure#

Chubby 主要包含两个通过 RPC 通信的组件: server 以及客户端链接库。客户端和服务端之间的所有 RPC 通信都是通过客户端库来协调。

一个 Chubby cell 是由多个 (一般是五个) server (副本) 组成的集合，这些副本被放置在不同的位置 (如不同的机架) 以降低相关故障的可能性。副本使用分布式共识算法进行选举 master 必须获得大多数副本的投票和一段时间 (master 租约) 内不会选举另外一个 master 的承诺。只要主节点继续赢得副本的多数选票，租约会周期性的进行续期。

每个副本维护了一个简单数据库的拷贝，但是只有 master 能够对数据库进行读写操作，其他副本通过共识协议从 master 拷贝更新。客户端通过向 DNS 中列出的副本发送 master location 请求来找到 master 非 master 节点收到请求后会返回 master 的标识。一旦客户端定位到 master 之后所有的请求都会向其发送，直到节点停止响应，或者其标识自己不再是 master。

写请求会通过共识协议广播到所有副本，只有请求到达 call 中的大多数副本才能被确认。读请求由 master 节点独自处理，在 master 租约未过期期间这样是安全的，因为同时不可能有其他 master 存在。

如果一个 master 失效，其他副本会在他们的 master 租约过期时执行选择协议，一般几秒钟以后新的 master 就会选举出来。

如果一个副本失效，并且在几个小时内没有恢复，有一个简单的替换系统会在空闲池中选一个新的机器来启动 lock server 进程并且更新 DNS 表中对应副本的 IP 当前的 master 节点会周期性的轮询 DNS 并且最终能够发现这个变更，然后会在数据库中更新 cell 成员列表，这个列表会通过普通的复制协议在所有成员间保持一致。同时新的副本会通过文件服务器中的备份和其他活跃副本中的更新获取最近的数据库拷贝。一旦新副本处理了一个当前 master 等待提交的请求，就可以在新的 master 选举中进行投票。

Files, directories, and handles#

Chubby 提供了一个类似于文件系统的接口，但是比 UNIX 接口更简单，整个系统由斜杠分割的名字组成一个树的结构，比如 /ls/foo/wombat/pouch 其中 /ls 是所有名字的公共前缀，表示 lock service 第二部分 foo 是 Chubby cell 的名字，通过 DNS 查询解析成一个或多个 Chubby servers 一个特殊的 cell 名称 local 表示客户端应该使用本地的 cell 通常这个 cell 是跟客户端在同一建筑内的。剩下的部分 /wombat/pouch 是客户端自行定义的。

使用这种类似于文件系统的结构，无需实现基础的浏览和命名空间操作工具，并且减少了教育用户的成本。

Chubby 和传统的 UNIX 文件系统设计不同以便于分发。为了允许不同目录的文件 (不同的 cell) 服务于不同的 master Chubby 不支持将文件从一个目录移动到另一个目录的操作，也不维护目录的修改时间，并且避免路径依赖权限 (即每个文件的权限由文件自身控制，与其所在的目录无关)

为了简化文件元数据缓存，系统并不显示最后访问时间。命名空间仅包含文件和目录，统称为节点。每个节点在其 cell 中仅有一个名字，也不适用符号链接或者硬链接。

节点可以是永久的或者是临时的，所有节点都可以显式的删除，临时节点会在没有客户端将其打开 (或目录为空) 时删除，临时节点可以用作临时文件，用于向其他节点表明表明一个客户端是活跃的。

所有节点都可以用作读 / 写咨询锁。每个节点有各种元数据，包括三个 ACLs (access control lists) 名称用于：读取控制，写入控制，更改节点 ACL 名称。

在非覆盖情况下，一个节点在创建时会继承其父目录的 ACL 名称 ACL 本身也是在 ACL 目录下的文件，属于 cell 本地命名空间的一部分。这些 ACL 文件包含一个简单的负责人名字的列表。因此如果一个文件 F 的写入 ACL 名字是 foo 并且 ACL 目录包含一个名为 foo 的文件，此文件中包含条目 bar 则用户 bar 被允许写入 foo 文件，用户通过 RPC 系统内置的机制进行验证。

由于 Chubby 的 ACLs 是简单的文件，对于其他想要使用类似权限控制机制的服务来说是自动可用的。

每个节点的元数据包含四个单调递增的 64 位数字允许客户端简单的检查变更:

实例编号：大于具有相同名称的示例编号 (删除，创建相同节点)
内容生成编号 (仅文件): 在写入文件内容时递增
锁产生编号：当节点锁从空闲转换到被持有时递增
ACL 生成编号：当节点的 ACL 名称被写入时递增

Chubby 也提供了 64 位的文件内容校验和客户端就可以知道文件是否有变更。客户端打开文件获取 handle 类似于 UNIX 的文件描述符 handle 包含:

校验位，预防客户端创建或者猜测 handle 因此只需要在 handle 创建时执行完整的访问控制检查。（类似于 UNIX 只在打开文件时检查权限位）
一个序列号，允许 master 判断这个 handle 是自己还是之前的 master 节点生成的
在打开文件时提供的模式信息，允许在出现旧的 handle 时新启动的 master 也能够重建其状态

Locks and sequencers#

每个 Chubby 的文件和目录都表现得像是一个读写锁：一个客户端 handle 以互斥模式持有锁，或者多个客户端 handle 以共享模式持有锁。

这里的锁是一种咨询锁：只会跟其他试图获取相同锁的操作产生冲突，持有锁 F 并不是访问文件 F 所必须的，也不会阻塞其他客户端访问此文件。相对而言，强制性所锁住对象后会导致没有持有这个锁的其他所有客户端无法访问：

Chubby 锁保护的资源是其他服务实现的，而不仅仅是锁相关的文件，如果需要强制实施强制锁需要对这些服务进行修改
我们不希望当用户出于 debug 或者管理的目的需要访问被锁住的文件时，强制他们关闭应用 (为了移除锁)
执行错误检查更简单，进行类似 lock X is held 的断言即可
bug 或者恶意操作有很多机会在没有持有锁时损坏数据，所以我们发现强制锁提供的额外保证并没有太大的价值

在 Chubby 中无论获取什么类型的锁都需要写的权限，这样没有权限的 reader 就不能阻止 writer 的操作。

分布式系统中的锁是很复杂的，因为通信一般是不确定的，且进程可能会独立失败。因此一个持有锁 L 的进程可能会发出 R 请求然后自己失效了，同时另外一个进程可能会获取到锁 L 然后在 R 请求没有到达目的地之前执行一些操作，如果 R 稍后到达，可能会在没有锁 L 的保护下，使用不一致的数据执行操作。接收消息顺序混乱的问题已经有很多研究了，解决方案包括 virtual time, virtual synchrony 通过确保消息以所有参与者观察到的一致的顺序处理，来避免这个问题。

在现有复杂系统中给所有交互引入序列号成本很高，而 Chubby 提供了一种方法，只在使用锁的交互中引入序列号。在任何时间，一个锁的持有者请求 sequencer (序列控制器) 产生一个非透明字节字符串来描述锁在获取后的即时状态：包含锁的名字，锁模式 (互斥或共享)，锁生成编号。

如果客户端想要在 server 上执行一些需要受到保护的操作会将 sequencer 传递到 server 接收到的 server 会检查 sequencer 是否依然有效且处于合适的模式，否则会拒绝请求。一个 sequencer 可以通过服务器的 Chubby 缓存进行有效性验证，如果服务器不想维持一个与 Chubby 的会话，也可以使用服务器最后观察到的 sequencer 进行验证 sequencer 机制仅需要在消息上附加一个字符串，这也很容易跟开发者解释。

尽管 sequencers 用起来很简单，但是对于一些比较重要的协议进展很慢。因此 Chubby 还给不支持 sequencers 的服务提供了一种不完美但是更简单的机制来降低延迟或者乱序请求的风险。

如果一个客户端正常释放了一个锁，其他客户端立即可以获得这个锁。然后如果一个锁因为持有者崩溃或者无法访问而释放，则 lock server 会阻止其他客户端在一段时间内获得这个锁称为 lock-delay 客户端可以指定延迟时间，但上限是一分钟，这个上限是为了避免崩溃的客户端导致锁 (及其关联的资源) 在任意长的时间不可用。虽然不完美，但是 lock-delay 保护了未经修改的服务器和客户端免受消息延迟和重启导致的日常问题。

Events#

Chubby 客户端在创建 handle 时可以订阅一系列的事件，这些事件会通过 Chubby 库的上层调用异步的派发给客户端。事件包括：

文件内容修改：经常用于监控通过文件广播的 service location (服务发现)
子节点新增，移除或修改：用于实现 mirroring
Chubby master 故障转移：警告客户端其他事件可能会丢失，所以需要重新扫描数据
一个 handle 及其关联的锁失效：一般表明通信存在问题
锁获取：用于确定是否已经选举出了一个 primary
其他客户端的冲突锁请求：允许锁缓存

事件是在对应的行为发生后派发的，因此如果一个客户端被告知文件内容变更，能够保证之后读取的数据都是新的。上述的后两个事件很少使用，回过头来看可以被省略。比如选举后客户端通常需要和新的 primary 进行通信，而不仅仅是只知道有一个 primary 存在，因此他们等待一个表明新的 primary 将其地址写入到了文件的修改事件。

冲突锁事件理论上允许客户端缓存被其他 server 持有的数据，使用 Chubby 锁维护缓存一致性。一个锁冲突请求通知向客户端表明应该完成未处理的操作 flush 修改，丢弃缓存数据然后释放锁 (锁冲突意味着有另外一个客户端要修改数据)。但是到目前位置还没有任何人采用这种方式。

API#

客户端将 Chubby handle 视作一个支持各种操作的非透明指针 handle 只能通过 Open 创建，通过 Close 销毁。

Open 打开一个指定名称的文件或目录产生一个 handle 类似于 UNIX 的文件描述符，也只有 Open 使用名字，所有其他的操作都基于 handle 这里使用的名字是相对于一个已经存在的目录 handle (相对路径) 然后库中提供了一个永远有效的 handle / 即根目录，目录 handle 避免了在多层抽象的多线程程序内全局使用 current directory 会产生的问题。

客户端提供了多种选项:

将会如何使用 handle (读 / 写 / 锁 / 修改 ACL) client 拥有合适的权限 handle 才能创建成功
应该派发的事件
是否应该 (必须) 立即创建一个文件或目录，如果创建了文件，调用者可以提供初始内容和初始 ACL 名称，返回值会表明是否创建了文件

Close () 关闭一个打开的 handle 此后 handle 不允许被使用，这个调用永远不会失败。一个相关的调用 Poison () 会导致 handle 在不需要 close handle 的情况下，使得所有未完成的和后续的操作都失败。这种方式允许一个客户端可以取消其他线程执行的 Chubby 调用而无需担心释放这些调用访问的内存。

在一个 handle 上主要执行的调用是:

GetContentsAndStat () 返回文件的内容和元数据，文件内容被原子性的完整读取。我们避免部分读取和写入，来阻止使用大文件。有一个相关的调用 GetStat () 仅仅返回文件的元数据而 ReadDir () 返回目录下子节点的名字和元数据
SetContents () 向文件中写入内容，客户端可以提供一个文件生成编号来模拟文件的 compare-and-swap 只有生成编号和当前一致才会修改内容。写入操作也是具有原子性的整体写入。类似还有一个 SetACL () 调用在节点关联的 ACL 名称上执行类似的操作
Delete () 调用在节点没有子节点时将其删除
Acquire (), TryAcquire (), Release () 申请和释放锁
GetSequencer () 返回一个描述当前 handle 持有的所有锁的 sequencer
SetSequencer () 将 handle 和一个 sequencer 关联在一起，如果 sequencer 已经失效则相关所有的 sequencer 操作都会失败
CheckSequencer () 检查 sequencer 是否有效

如果 handle 创建之后节点被删除则调用会失败，即使后续文件被重新创建。因为 handle 总是和一个文件实例相关联而不是一个名字 Chubby 虽然可以对所有调用执行访问控制检查，但是实际上只会检查 Open 调用。

以上所有调用除了本身所使用的参数以外，都会附带一个操作参数保存可能与任何调用相关的数据和控制信息，具体来说通过操作参数，客户端可以：

提供一个回调函数来使调用异步
等待一个调用结束
获取扩展错误和诊断信息

客户端可以使用这些 API 执行 primary 选举：所有潜在的 primary 打开锁文件然后尝试获取锁，其中一个成功且成为 primary 其他则成为副本。然后 primary 使用 SetContents () 调用将自己的标识写入锁文件，这样就可以被其他客户端和副本通过 GetContentsAndStat () 读取文件发现 (可能是作为文件修改事件的响应)。理想情况下 primary 通过 GetSequencer () 获取一个 sequencer 在后续通信时传递到 server 上，他们会执行 CheckSequencer () 确认其依然是 primary 对于无法检查 sequencer 的服务，可以使用之前提到过的延迟锁

Caching#

为了减少读流量 Chubby 客户端在内存中缓存文件数据和节点的元数据。缓存由一个租约机制维护，通过 master 发送的失效请求保持一致，这个协议保证客户端要么看到一个一致的 Chubby 状态，要么发生错误。

当文件数据或元数据改变时，修改操作会阻塞到 master 给所有可能缓存数据的客户端发送失效请求，这个机制位于 KeepAlive RPCs 之上。当接收到失效请求后，客户端清除无效状态，并且在下一次 KeepAlive 调用中进行确认。修改流程会持续到 server 知道每个客户端都将其缓存失效：要么是因为客户端确认了失效消息，要么是客户端允许其缓存的租约过期。

只需要一轮无效化是因为，当缓存无效化一直无法确认时 master 会将节点认为是不可缓存的。这种方式允许读请求不会被延迟处理，在读操作远超过写操作的情况下这样很有用。一种替代方案是在无效化期间阻塞所有访问对应节点调用，这将会减少一些热点客户端在无效化期间对 master 进行的轰炸式的非缓存访问，代价是偶尔的延迟。如果这是一个问题，可以想象采用混合方案，一旦检测到超载就切换策略。

缓存协议很简单，在有变更时直接将其失效，从不更新缓存。更新可能比无效化更简单，但是仅更新的协议可能会非常低效，客户端访问一个文件时可能会收到无限多的更新，导致无限多的非必要的更新 (失效后直接获取最新的就可以了)。

尽管提供严格一致性的开销很高，我们也拒接使用弱一致性的模型因为这种对程序员来说很难用。类似的，比如虚拟同步机制，在一个预先存在多样化通信协议的环境中，需要客户端在所有消息中交换序列号是不合适的。

除了缓存数据和元数据 Chubby 客户端还缓存打开的 handle 因此如果一个客户端打开之前已经已经打开过的文件，只有第一个 Open 请求需要发送到 master 这种缓存受到一些小的限制，以确保不会对客户端观察到的语义产生影响：临时文件上的 handle 在应用将其关闭以后不能保持打开状态，允许加锁的 handle 可以被重用但是不能同时被多个 handle 使用。后一条限制存在是因为客户端可能会使用 Close () 或者 Poison () 取消向 master 未完成的 Acquire () 调用并产生副作用。

Chubby 协议允许客户端缓存锁，即超出所需的时间更长的持有锁，可以在同一个客户端上重用。当其他客户端请求锁冲突时会通知锁的持有者一个事件，允许持有者在其他地方需要锁时释放。

Sessions and KeepAlives#

Chubby 会话指的是一个 Chubby cell 和一个客户端的关系，其存在一段事件，通过称为 KeepAlives 的周期性握手来维护。除非客户端主动通知 master 否则客户端的 handle 锁和缓存数据在会话保持有效期间都是保持有效的 (会话维护消息可能会需要客户端确认缓存无效化来保证会话有效)

客户端在第一次和 Chubby cell 联系时会请求一个新的会话，而会话结束是隐式的，可能是客户端自己终止或者会话被闲置 (挂起)(在一分钟内没有打开 handle 和任何调用)。

每个会话有一个关联的租约 (一个续期的间隔时间)，保证未来的一段时间内 master 不会单方面的终止会话，这个时间间隔的结束称为会话租约超时 master 可以自由的将超时时间进一步推迟到未来，但是不能移到过去。

master 会在以下三种情形下推迟租约超时时间：会话创建时，master 发生故障转移时，响应客户端 KeepAlive RPC 时。收到 KeepAlive 请求时 master 一般会将 RPC 阻塞到客户端的前一个租约间隔快过期，然后才允许 RPC 返回给客户端并且告知客户端新的租约超时时间 master 可能会将超时时间延长任意时长，默认的延长时间是 12s 但是负载高的 master 可能会使用更长的时间以减少需要处理的 KeepAlive 的调用的数量。客户端收到前一个响应后会立即发起一个新的 KeepAlive 因此客户端可以保证几乎总是有一个 KeepAlive 阻塞在 master 上。

除了延长租约 KeepAlive 的响应还可以用来传输事件和失效缓存 master 允许在派发事件或者无效化时提早返回 KeepAlive 在响应中搭载事件确保客户端在确认缓存失效前无法维持会话，并且使得所有的 Chubby RPCs 从客户端流向 master 这简化了客户端并且允许协议在只允许单向连接初始化的防火墙上运行。

客户端在本地维护一个相对于 master 较为保守的租约超时时间，因为客户端需要考虑到响应消息在返回过程中花费的时间和 master 上时钟超前的可能性，为了保持一致，我们需要保证 server 的时钟不能比客户端的时钟超过一个已知的常数因子。

如果客户端本地租约超时，它没办法确定是否 master 已经终止了此会话，客户端会禁用和清空缓存，并处于一个不确定的状态。客户端等待一个宽限期的间隔时间 (默认 45s) 如果在此间隔结束之前成功交换了 KeepAlive 则客户端再一次启用缓存，否则客户端假设会话已经过期。这样做的为了当 Chubby cell 无法访问时 Chubby API 调用不会无限期的阻塞，在宽限期结束之前如果通信没有重新建立，调用会返回一个错误。

当宽限期开始时 Chubby 库可以通知应用一个危险事件，当会话通信问题恢复后会发送一个安全事件，反之如果会话超时则发送一个超时事件。这些信息能够使应用在不确定自己会话的状态时保持安静，当遇到暂时性的问题时也无需重启即可恢复。对一些启动开销很大的服务来说防止中断很重要。

如果一个客户端持有一个节点的 handle H 并且由于关联的会话过期所有在 H 上的操作都失败了，后续的所有请求 (除了 Close) 都会以相同的方式失败。客户端可以以此来保证，网络和服务中断只会导致操作序列的某个后缀部分丢失，而非任意的子序列，因此可以使用最终的写入来将复杂的变更标记为已经提交 (只要最终写入的是成功，前面的所有操作一定是成功的)

Fail-overs#

当 master 产生故障或失去主控权，会丢弃掉所有的内存状态包括：会话 handle 和锁。会话租约的权威定时器运行在 master 上，所在在新的 master 被选举出来之前租约定时器是停止的，这样等效于延长了客户端的租约。如果 master 选举很快，客户端可以在本地 (宽松) 租约定时器过期之前，连接到新的 master 而如果租约花费了较长的事件，客户端会清除本地的缓存并在宽限期内等待新的 master 因此宽限期允许在超过正常租约超时的故障转移过程中维持会话。

故障转移

上图显示了在漫长的 master 故障转移事件过程中的一系列事件，客户端必须使用其宽限期保护其会话。初始 master 有一个客户端租约 M1 然后客户端有一个相对保守估计的 C1 接着 master 提交了 M2 租约，客户端延续租约到 C2 然后在响应下一条 KeepAlive 之前 master 宕机，在一个 master 选举出来之前过去了一些时间，最终客户端租约 C2 到期，然后客户端清除缓存并开启了一个新的宽限期定时器。

在这个时期内，客户端无法确认是否其租约在 master 上过期，客户端不会立即销毁会话，但是会阻塞所有应用层的 API 调用避免应用层观察到不一致的数据。在宽限期的开始 Chubby library 发送一个危险事件到应用层让其监听发送请求，直到能够确认会话状态。

最终一个新的 master 被选举出来 master 给之前可能持有的租约初始化一个保守估计的租约 M3 从客户端发送到新的 master 的第一个 KeepAlive 请求会被拒绝因为包含错误的 master 周期编号，重试请求 (6) 能够成功但是一般不会延长 master 租约因为 M3 本身就是保守估计的 (延长了) 然而响应 (7) 允许客户端再次延续其本身的租约到 C3 并且可以通知应用层会话不再处于危险中。由于宽限期足够长覆盖了 C2 的结束到 C3 的开始的间隔，客户端只能感知到一段延迟，而如果宽限期比这个间隔小，客户端会放会话然后向应用层报告错误。

一旦客户端连接到新的 master 客户端 library 和 master 协作给应用层提供一个错觉好像从来没有发生过故障，为了达到这个目标新的 master 必须重新构造一个相对于之前的 master 保守估计的内存状态，部分通过读取稳定存储在磁盘上的数据 (通过普通的数据库复制协议备份)，部分通过获取从客户端获取到的状态，部分通过保守的估计。数据库记录每个会话，持有锁和临时文件。

被选举出的新的 master 执行以下步骤：

master 选取一个新的 epoch number 客户端需要在每个调用中传入 master 会拒绝低于此 epoch number 的请求并且提供当前最新的编号，确保新的 master 不会响应发给之前的 master 的数据包，即使是运行在相同的机器上。
master 可能会响应 master-location 请求，但是一开始不会处理传入的与会话相关的请求。
master 在内存中重建记录在数据库中的会话和锁的数据结构，会话租约会被延期到上个 master 可能会使用的最大时长
master 开始让客户端执行 KeepAlives 但不执行其他会话相关的操作。
master 向所有的会话发送一条 fail-over 事件，这会使客户端清除他们的缓存 (因为他们可能会错过一些缓存无效化的通知) 并且警告应用层一些事件可能已经丢失了。
master 等待所有会话确认 fail-over 事件或者使其过期。
master 允许处理所有操作
如果一个客户端使用一个在故障转移之前创建的 handle (通过 handle 中的 sequence number 确定) master 会重新创建这个 handle 在内存中的表示然后响应调用。如果这个新创建的 handle 被关闭 master 会在内存中记录，这样在当前的 epoch 内就不会被重新创建，这样能够保证一个延迟或者重复的网络包不会意外的重新创建一个已经关闭的 handle 故障的客户端可以在以后的 opoch 中重新创建一个已经关闭的 handle 由于客户端已经故障，这样是无害的。
在一段时间后 master 删除已经没有被打开的 handle 的临时文件，客户端也应该在故障转移一段时间以后刷新临时文件上的 handle 这种机制的不幸效果是，如果最后一个使用该文件的客户端在故障转移期间丢失了会话，临时文件可能无法及时消失。

Database implementation#

第一版的 Chubby 使用带复制版本的 Berkeley DB 的作为其数据库 Berkeley DB 提供了 B-trees 将 bytestring key 映射到任意 bytestring value 我们使用了一个 key 比较函数：首先比较路径中层级的数目，将所有节点按照路径名划分成 key 还能保证兄弟节点在在排序中相邻。由于 Chubby 不使用基于路径的权限，每次文件访问只需要在数据库中查找一次就够了。

Berkeley DB 使用一个分布式共识协议在多个 server 之间复制数据库日志，一旦添加了 master 租约，这就和 Chubby 的设计相匹配，使得实现变得简单直接。

Berkeley DB 的 B-tree 代码已经被广泛使用且非常成熟，但是复制的代码是最近新加的并且用户很少。软件维护者必须优先考虑维护和改进他们最流程的产品功能 Berkeley DB 的维护者解决了我们的问题，我们觉得使用复制代码会使我们面临比我们愿意承担更多的风险。最终我们使用 WAL 和快照技术写了一个简单的数据库。和之前一样，数据库日志通过一个分布式共识协议在所有副本间分发 Chubby 使用了 Berkeley DB 很少一部分的特性，因此这次重写允许我们极大简化了整个系统，比如当我们需要原子操作，不需要事务。

Backup#

每几个小时每个 Chubby cell 的 master 将其数据库快照写入到不同建筑的 GFS server 上。使用分开的建筑确保建筑物损坏时备份能够存活，且副本不会在系统内引入循环依赖，因为同一建筑内的 GFS cell 可能会依赖其选举出来的 Chubby cell

备份提供了灾难恢复，和一种不会给正在运行中的服务增加负载的初始化新的替代副本的数据库的方法。

Mirroring#

Chubby 允许将一组文件从一个 cell 镜像到另一个 cell 镜像操作很快，因为文件很小，而且事件机制可以在添加 / 删除 / 修改文件时立即通知镜像代码。假设没有网络问题，变更会在不到一秒内反映到事件范围内的数十个镜像中。如果一个镜像不可到达，其会保持不变直到连接恢复，文件更新通过比较他们的校验和来标识。

镜像最经常用于拷贝配置文件到分布在世界各地的不同的计算集群上。一个名为 global 的特殊 cell 包含一个子树 /ls/global/master 被镜像到所有其他 cell 上的子树 /ls/cell/slave global cell 是特殊的，因为其五个副本分布在世界各地相距较远的地方，所以它基本上在大多数地方能被访问到。

在 global cell 镜像文件中包含 Chubby 自身的权限控制列表，以及 Chubby cell 和其他服务向监控服务告知其存在的文件，允许客户端定位类似 Bigtable cells 的大数据集的指针，和许多其他系统的配置文件。

Mechanisms for scaling#

Chubby 的客户端是独立的进程，因此 Chubby 必须处理比预期更多的客户端，我们已经见过超过 90000 个客户端直接和一个 Chubby master 直接相连，涉及到比这个数量更多的机器。由于每个 cell 中仅有一个 master 并且其机器和客户端是相同的，客户端数据远超其处理能力。因此最有效的扩容技术通过显著减少与 master 的通信来实现，假设 master 没有严重的性能 bug 在 master 对请求处理上的微小改进对其影响很小，我们使用了几种方法：

我们可以创建任意数量的 Chubby cell 但客户端几乎总是使用一个最近的 cell 来避免依赖远程机器，我们典型的部署方式是在一个数千台机器的数据中心中使用一个 Chubby cell
master 可以在处于高负载时，将其租约时间从 12s 提高到最多 60s 这样可以处理更少的 KeepAlive RPCs (KeepAlive 是主要的请求类型，无法及时处理请求是负载过重服务器的典型故障模式，客户端对其他调用的延迟变化很不敏感)
Chubby 客户端缓存文件数据，元数据，缺失文件和打开的 handle 来减少向服务器发起的调用
使用协议转换服务器将 Chubby 协议转换成更简单的协议比如 DNS 等。

这里，我们描述两种熟悉的机制：代理和分区，我们期望这些能够使 Chubby 进一步扩展。我们还没有在生产环境中使用，但是已经被设计好，可能很快就用上。我们目前无需考虑超过五倍的扩展：首先，我们放在一个数据中心上的机器或者依赖于单个服务的实例都有数量限制；其次，由于我们在 Chubby 客户端和服务器上使用相似的机器，硬件优化在每台机器上增加客户端的数量，也会增加每个 server 的容量。

Proxies#

Chubby 的协议可以被信任的进程代理，代理可以通过处理 KeepAlive 和读取请求来降低服务器的负载，但是不能通过代理缓存减少写流量，不过即使使用了积极的客户端缓存策略，写入流程也只占 Chubby 正常工作负载的不到百分之一。所以使用代理可以极大增加客户端的数量。

如果一个代理处理 N 个客户端 KeepAlive 流量就减少了 N 可能是 10k 或更多，代理缓存最多可以减少的读取流量大约是读共享的平均值，大约是 10 倍的因素。但是由于读取只占 Chubby 负载的不到 10% 节省 KeepAlive 流量的效果更重要。另外代理添加了写入和首次读取的额外 RPC 调用。人们可能会期望代理使得 cell 临时不可用性相比之前增加了一倍，因为每个代理客户端依赖两台可能会故障的机器：代理服务器和 Chubby master 服务器。敏锐的读者可能会注意到之前描述的故障转移策略对于代理服务器并不理想。

Partitioning#

Chubby 的接口被设计成一个 cell 的命名空间可以被分区到不同的 server 上，尽管我们现在还不需要，代码可以通过目录将命名空间分区。如果开启，一个 Chubby cell 可以由 N 个分区组成，每个分区都有一个副本集合和一个 master 每个目录 D 中的节点 D/C 会被存储在分区 P(D/C) = hash(D) mod N 上，注意 D 的元数据可能会存储子啊不同的分区上 P(D) = hash(D0) mod N 这里 D0 是 D 的父目录。

分区旨在实现区分之间只有少量通信的大型 Chubby cell 尽管 Chubby 缺少硬链接，目录修改时间，和跨目录的重命名操作，少部分操作仍然需要跨分区的通信：

ACLs 本身就是文件，因此一个分区可能会使用其他分区进行权限检查，然而 ACL 文件很容易缓存，只有 Open () 和 Delete () 调用需要 ACL 检查，并且大多数客户端读取的是公开可访问的文件，不需要 ACL
当一个目录被删除，跨分区调用可能需要确认这个目录是空的

由于每个每个分区处理的调用大部分不依赖其他分区，我们预期分区间通信对性能和可用性的影响有限。尽管分区的数量 N 很大，可以预期每个客户端都会联系大多数的分区，因此分区能够将给分区上的读写流量减少 N 倍但是并不一定会 KeepAlive 流量。

如果有必要让 Chubby 处理更多的客户端，我们的策略包括使用代理和分区的组合。

Use, surprises and design errors#

... 省略相关数据和使用情况

Use as a name service#

尽管 Chubby 被设计成一个锁服务，我们发现它最常见的用途是作为一个 name server 常见的互联网 name system 使用基于时间的缓存 DNS 条目有一个存活时间 TTL 如果在这个时期内没有刷新则 DNS 数据会被丢弃。通常如果选择一个合适的 TTL 值是很直观的，但是如果希望快速替换失败的服务 TTL 可能会足够小以至于拖垮 DNS 服务器。

例如，对我们的开发者来说，运行一个涉及到上千个进程的作业是很普遍的，每个进程都要和其他进程通信，导致平方级别的 DNS 查询。我们可能希望使用 60s 的 TTL 这会使得行为不当的客户端可以在没有过多延迟的情况下被替换，而且在我们的环境中不被认为是一个过于短暂的替换时间。

在这种情况下，为了维护一个将近 3000 个客户端的作业，每秒需要 150k 次查询 DNS 缓存，更大型的作业会带来更严重的问题，而且许多作业可能会同时进行。在引入 Chubby 之前我们的 DNS 负载的变化一直是 Google 的一个严重问题。

作为对比 Chubby 的缓存使用显示的无效化，因此在没有变化的情况下，以一个恒定的速率请求会话 KeepAlive 可以在客户端上无限期的维护任意数量的缓存条目。一个 2 核 2.6GHz 的 Chubby master 可以处理与其直连的 90k 个客户端，其中包括上面提到过的大型作业的客户端。不需要逐个轮询每个名称，就能够提供快速名称更新的能力是非常吸引人的，以至于现在 Chubby 为公司的许多系统提供 name service

尽管 Chubby 的缓存允许一个 cell 支撑大量的客户端，但是负载峰值仍然是一个问题。当我们首次部署基于 Chubby 的 name service 开了 3k 个进程 (产生了 9m 的请求) 就可以把 master 打跪。为了解决这个问题，我们选择将一组名称查询组成批处理，这样单个查询就可以返回和缓存大量 (一般是 100 个) 作业中相关进程的名称映射。

Chubby 提供的缓存语义比 name service 更精确，名称解析只需要及时通知而非完全一致性。通过引入一个专门用于名称查询的简单的协议转换服务器，有机会减轻对 Chubby 的负载。如果我们预见到 Chubby 作为 name service 的使用，我们可能会更早的实现完全代理，以避免对这个简单的需求的需要。

还存在一个进一步的协议转换服务器：Chubby DNS server 存储在 Chubby 上的名称数据对 DNS 客户端可用。这个服务对简化从 DNS 名称到 Chubby 名称的过渡和适应无法轻松转化的现有应用 (如浏览器) 都很重要。

Lessons learned#

开发者很少考虑可用性，我们发现我们的开发者很少考虑故障的可能性，并且倾向于将 Chubby 这样的服务视为始终可用。比如，我们的开发者曾构建过一个系统，使用了数百台机器，当 Chubby 选举出一个 master 后，这个程序会启动恢复程序，需要几十分钟的时间。这不仅将单个故障在时间上放大了一百倍，而且影响了数百台机器。我们更希望开发者对 Chubby 的短暂中断做好计划，这样这种事件对他们的应用程序几乎没有任何影响。

开发者们也没能理解 service 启动和 service 对他们的应用可用的区别，比如 global cell 基本上总是在运行，因为很少见到地理上相距较远的两个或以上数据中心同时宕机。然而对于客户端所观察到的可用性总是低于客户端本地的 local cell 首先客户端与 local cell 分开的概率较低，并且尽管 local cell 可能会经常因为维护宕机，同样的维护也会直接影响到客户端，所以 Chubby 的不可用性不会被客户端观察到。

我们的 API 选择也会影响到开发者处理 Chubby 中断的方式，比如 Chubby 提供了事件允许客户端发现 master 故障转移，原本的目的是让客户端检查可能的变更，因为其他事件可能丢失了。不幸的是，许多开发者在收到这个事件时会直接崩溃他们的应用，由此显著的降低了他们系统的可用性。我们可能更好还是发送冗余的文件变更事件，或者确保在故障转移期间没有事件丢失。

当前我们使用了三种机制避免开发者对于 Chubby 的可用性过于乐观，特别是 global cell 首先，像之前提到过的，我们检查工程团队如何计划使用 Chubby 并且建议他们不要使用那些将他们系统的可用性与 Chubby 紧密联系在一起的技术。其次，我们现在提供 libraries 执行一些高层次的任务将开发者和 Chubby 的中断自动隔离开来。第三，我们对每次 Chubby 中断进行事后分析，不仅用于消除 Chubby 和我们操作程序中的 bug 还减少了应用对于 Chubby 可用性的敏感性，这两者都可以提高整个系统的可用性。

细粒度的锁可以被忽略，前面章节描述过一个可以使客户端使用细粒度锁的服务的设计。令人惊讶的是，目前为止我们不需要实现这样一个服务。我们的开发者发现，为了优化应用程序，他们必须移除不必要的通信，而这通常意味着找到了一个使用粗粒度锁的方式。

糟糕的 API 选择会产生意想不到的影响，总体而言我们的 API 发展良好，但是出现了一个突出的错误。我们意图取消长时间运行调用的 API 是 Close () 和 Poison () RPCs 这也会丢弃 handle 在服务器上的状态。这避免了 handle 这会阻止可以获取锁的 handle 被共享，例如被多个线程共享。我们可以添加一个 Cancel () RPC 允许打开的 handle 被共享。

RPC 的使用会影响传输协议 KeepAlives 同时用于刷新客户端的会话，传递事件和 master 下发的缓存无效化。这种设计使得客户端无法确认缓存无效化时无法刷新其会话，这看起来是很理想的，但是会使我们在设计协议时小心谨慎 TCP 的退避策略不关心上层的超时比如 Chubby 的租约，因此基于 TCP 的 KeepAlives 在网络拥堵时产生了非常多的会话丢失。我们被迫使用 UDP 而非 TCP 发送 KeepAlive RPCs UDP 没有拥塞避免机制，所以当上层时间限制需要考虑时我们更倾向于使用 UDP。

在正常情况下，我们可以通过一个额外的基于基于 TCP 的 GetEvent () RPC 扩充协议，用于传递事件和无效化，用法和 KeepAlive 相同 KeepAlive 响应依然包含一个未确认事件的列表，这样可以确保事件最终得到确认。