【论文阅读笔记】The Chubby Lock Service for Loosely-Coupled Distributed Systems

1 简介

Chubby是一个面向松耦合分布式系统的锁服务，被广泛应用于Google内部的多个关键系统中，如GFS（Google文件系统）和Bigtable。在GFS中，Chubby用于指定主服务器；而在Bigtable中，它不仅支持主服务器选举、帮助主服务器发现其所管理的子服务器以及协助客户端定位主服务器，还充当了少量元数据存储的角色。 Chubby允许客户端同步活动并就环境基本信息达成一致。主要目标包括可靠性、对大量客户端的可用性以及易于理解的语义，吞吐量和存储容量是次要考虑因素。 值得注意的是，Chubby并非基于全新的算法理论构建而成，而是将已有的Paxos一致性算法作为实现基础，通过工程上的优化来满足实际应用场景下的需求。 Chubby向用户暴露了一套类似于UNIX文件系统的API接口，应用不仅能对Chubby服务器上的整个文件进行读写操作，还可以添加对文件节点的锁控制。此外，Chubby还引入了事件订阅机制，允许客户端注册监听某些类型的数据变更通知，一旦相关文件或目录发生更新，则会立即接收到由服务端推送的通知消息。

2 设计目标

Chubby最初的设计者并没有将它实现为一个包含Paxos算法的协议库，而是将Chubby设计成一个需要访问中心节点（Master）的分布式锁服务，这一决策基于以下几个优势： 能像插件一样增加到现有系统中。开发者一开始可能未对高可用性做规划，锁服务器更易维护现有程序结构和通信模式。 许多服务需要一种机制来公布选举主服务器或划分数据的结果，想比name service，基于所服务的一致性客户端缓存更适合存储和获取少量数据。 基于锁的接口对程序员更熟悉。 分布式共识算法需多个副本实现高可用性，而锁服务嵌入到客户端，只需要一个机器，就能达成共识。 为了满足实际需求，Chubby设定了以下设计目标： 提供一个完整的、独立运作的分布式锁服务，而不仅仅是一个一致性协议的客户端实现。 提供粗粒度的锁服务。 除了基本的锁服务外，还支持对小文件进行读写操作。 具备高可用性和可靠性，保证即使在网络分区或硬件故障的情况下也能持续稳定运行。 引入了一种高效的事件订阅模型，允许客户端实时接收关于所关注文件变更的通知信息。这样不仅增强了系统的响应速度，也使得应用程序能够更好地适应动态变化的环境。

3 Chubby设计

3.1 系统结构

Chubby包含两个基本组件，一个服务器和客户端应用链接的库，通过 RPC 通信，还有第三个可选组件——代理服务器。Chubby 单元由少量服务器（通常为 5 个）组成，这些服务器称为副本，使用分布式共识协议选举Master。

集群中每个服务器都维护一份服务端数据库的副本，但只有Master负责读写数据库，其他副本复制主服务器的更新。客户端通过 DNS 找到Master，Master故障时其他副本重新选举。副本故障可由替换系统选择新机器替换。

3.2 文件、目录、句柄

Chubby 的文件系统接口类似 UNIX 但更简单，是严格的文件和目录树结构，有特定命名规则。与 UNIX 不同之处在于便于分布，不暴露某些操作，不维护部分时间信息，命名空间只有文件和目录（节点），无符号或硬链接。

节点分永久（需显式删除）和临时（无引用则删，可检测 client 存活），可作读写锁，有相关元数据和访问控制列表（ACLs），用于控制节点的读、写和更改ACL权限。除非被覆盖，否则节点在创建时将继承其父目录的ACL名称。每个节点的元数据包含四个单调递增的 64 位数字，便于客户端轻松检测变化：

• 实例编号：用于标识创建该数据节点的顺序

• 文件内容编号：用于标识文件内容的变化情况，该编号会在文件内容被写入时增加

• 锁编号：用于标识节点锁状态变更情况，该编号会在节点锁从自由状态转换到被持有状态时增加

• ACL编号：用于标识节点的ACL信息变更情况，该编号会在节点的ACL配置信息被写入时增加

同时，Chubby还会标识一个64位的文件内容校验码，以便客户端能够识别出文件是否变更。

客户端打开节点可获取类似 UNIX 文件描述符的句柄，具有以下特点：

• 通过句柄数字，防止在创建期间的操作，只有在创建节点时才会检查，而UNIX是在打开时检查，读/写不检查
• 允许master 能够判断句柄是自身生成还是其他 master 生成。
• 若旧句柄在新 master 打开节点时出现，master 会重新创建该句柄。

3.3 锁和序列器

Chubby 提供两种锁：写锁（排斥模式）和读锁（共享模式）。强制锁会使未持有锁的对象无法访问锁定对象，但 Chubby 未采用，而是使用建议锁，也就是说，它们只与获取同一把锁的其他尝试发生冲突：持有一个名为F的锁既不是访问文件F所必需的，也不会阻止其他客户端这样做。因为 Chubby 经常保护其他服务实现的资源，不只是与锁关联的文件，且在用户调试或管理文件时，不希望强制用户关闭应用，同时开发人员可以通过传统断言检查锁持有情况，强制检查价值不大。

在分布式系统中，由于网络通信的不确定性，导致在分布式系统中锁机制变得非常复杂，消息的延迟或是乱序都有可能会引起锁的失效。目前可通过虚拟时间、虚拟同步解决，但 Chubby 未采用这些复杂方式。

Chubby采用了序列器和锁延迟两种机制来解决上述问题，序列器指锁的持有者向Chubby服务端请求一个序列器（是一个不透明的字节串，包括锁的名称、锁的模式以及锁的生成号），然后之后在需要使用锁的时候将该序列器一并发给 Chubby 服务器，服务端检查序列器的有效性。虽然序列器机制只需要向受影响的消息添加字符串，但重要的协议发展缓慢。

而延迟就是客户端在非正常情况下释放锁的话，那么Chubby服务器会允许该客户端在锁延迟时间内一直持有不释放这个锁，在这段时间内，其他客户端无法获取到这个锁，可以减少由网络延迟造成的问题。

3.4 事件通知机制和缓存

为了避免大量客户端轮询Chubby服务端状态所带来的压力，Chubby提供了事件通知机制。客户端可以向服务端注册事件通知，当触发这些事件时，服务端就会异步地向客户端发送对应的事件通知。常见的Chubby事件如下：

• 文件内容变更：监视通过文件发布的服务的位置。
• 节点的增加、删除、修改：用于实现镜像，发现新文件以及监视临时文件。
• Master失败：警告客户端其他事件可能已经丢失，因此需要重新扫描数据。
• 句柄、或者锁变得无效了：这通常表明存在通信问题。
• 锁获取成功：可用于确定Master何时被选举。
• 锁获取冲突：允许锁缓存。

为了减少网络I/O，Chubby的客户端使用了缓存，可以缓存文件数据和元数据。Chubby借助租约来保证客户端和服务端缓存的一致性，每个客户端的缓存都有一个租约，一旦该租约到期，客户端就需要向服务端续订租约才能够保证缓存的有效性。

当文件数据或者元数据被修改时，Chubby服务端首先会阻塞该修改操作，然后由Master通知所有缓存了该信息的客户端，等到Master收到了客户端对该过期消息的应答后，再进行修改操作。Chubby通过缓存机制保证了数据的强一致性，在缓存机制下，Chubby就能够保证可回单要么从缓存中会总访问到一致的数据，要么访问出错。

3.5 Session 和 KeepAlive

一个Chubby Session是Chubby Cell和客户端通过定期的KeepAlive握手维护的一个关系，当Session有效时，除非客户端通知Master，客户端的句柄、锁、缓存都是有效的。

Master在收到一个KeepAlive RPC时，通常会阻塞该RPC直到该Client的前一个租约接近过期，然后Master再允许该RPC返回给客户端，同时告知客户端新的租约过期时间。Master可以任意地延长过期时间，默认的演唱时间时12s。

但是一个负载过高的Master可能会使用一个更高的值来减少它所需要处理的KeepAlive RPC调用。客户端在收到响应后，就会马上发起一个新的KeepAlive，因此几乎总是有一个KeepAlive被阻塞在Master。这个KeepAlive 回复也可以用来给客户端传递事件和过期缓存，如果事件或者缓存失效发生了，Master则允许KeepAlive立即返回，同时客户端维护了一个本地租约过期时间，是Master租约过期时间的近似（为了防止Master已经关闭Session了），如果客户端本地缓存租约过期了，但此时无法确定Master是否已经结束了这个Session，客户端就需要清空并禁用它的缓存，此时Session处于jeopardy状态，客户端则会继续等待一个称为宽限期的时长，默认为45s。如果在宽限期结束之前，客户端和Master又完成了一次成功的KeepAlive交互，那么客户端就会再次使它的缓存有效，否则，客户端就假设Session已过期。

3.6 故障转移

一旦Master挂了或者失去Master身份时，它就会丢掉关于它的Session，在内存中的句柄、锁、状态都没了， 转而运行一个Session本地租约计时器，等待新的Master选举出来，如果一个Master选举很快完成，客户端就可以在租约计时器过期之前联系新的Master，否则，客户端的本地超时过期后，客户端可以利用宽限期来让Session在故障转移期间得到维持，其宽限期增加了客户端的租约超时时间。

新的Master需重建其前任Master的内存状态，这一过程部分通过硬盘上存储的数据实现，部分从客户端获取状态，还有部分通过保守估计完成。数据库会记录每个Session、持有的锁以及临时文件。新当选的Master需按以下流程操作：

1. 采用一个新的epoch编号并反馈给客户端，拒绝来自旧epoch编号的客户端请求，以防新Master对发送给旧Master的陈旧数据包做出响应。
2. 新Master可响应Master定位请求，但不会处理与Session相关的请求。
3. 依据数据库重建Session状态和锁信息等，并延长最大的Session时间，即进行故障转移。
4. 接收客户端的KeepAlive，但不响应其他操作。
5. 向所有客户端发送故障转移事件，客户端会因此清空缓存（因可能已过期），并警示应用程序可能丢失了其他事件。
6. Master等待每个客户端确认故障转移事件，或者客户端Session超时。
7. Master允许所有操作正常进行。
8. 若客户端使用旧句柄，新Master会在内存中重建新句柄；若重建的句柄已关闭，Master会保存该句柄，确保在其任期内无法再次重建相同句柄。
9. 经过一段时间，Master会删除无句柄打开的临时文件，所以客户端需在此期间刷新临时文件的句柄。若文件上最后一个客户端在故障转移过程中丢失Session，则该文件不会立即被删除。

3.7 数据库实现

最初使用的是Berkeley DB的复制版本，它采用B +树机制，其中键为字节字符串，值可以是任意二进制数据。在Berkeley DB之上，添加了一个用于对路径名称数量进行排序的比较函数，从而使相邻节点紧密排列。Berkeley DB使用分布式共识算法来复制数据库日志。

后来由于维护风险等因素，自行编写了简单数据库，运用了预写日志（WAL）和快照技术。

3.8 备份和镜像

每个 Chubby 单元的主服务器每隔几小时将数据库快照写入不同建筑的 GFS 文件服务器，用于灾难恢复和初始化新替换副本的数据库。

Chubby允许文件集合从一个单元镜像到另一个单元，利用事件机制快速更新，常用于复制配置文件到全球各地的计算集群。

4 扩展机制

单个Master可以服务9W个客户端，因为每个单元只有一个Master，所以Master的压力会很大。因此，最有效的扩展机制在很大程序上能减少与主机的通信，有以下几种方法：

• 可创建任意数量的 Chubby 单元，客户端通常使用附近单元，减少对远程机器的依赖。

• 主服务器在负载重时可增加租约时间，减少需处理的KeepAlive RPC 数量。

• Chubby客户端缓存文件数据、元数据、文件缺失情况和打开句柄，减少对服务器的调用。

• 使用协议转换服务器将 Chubby 协议转换为较简单的协议，如 DNS 等。

还有以下两种机制，代理和分区。

4.1 代理

可由受信任进程代理 Chubby 协议，代理连接了客户端和Chubby Master，两边保持一致即可。这样可以减少服务器负载，主要处理KeepAlive和读请求，对写流量影响小。代理增加了写和首次读的 RPC，但可显著增加客户端数量，同时也带来一些潜在问题，如增加单元不可用的频率，原故障转移策略对代理不理想。

4.2 分区

Chubby 的接口设计允许按目录对单元的命名空间进行分区，每个分区有自己的副本和主服务器。但元数据不会划分，分区旨在实现大型 Chubby 单元且分区之间通信少，虽有一些操作需跨分区通信，但影响预计不大。

分区可减少给定分区上的读写流量，但不一定减少KeepAlive流量。如果要支持更多客户端，策略是代理、分区一起使用。