Chubby论文

这个谷歌 Chubby 的论文
The Chubby lock service for loosely-coupled distributed systems

背景

Chubby 是谷歌开发的锁服务，提供粗粒度的锁服务，以实现松耦合的分布式系统
Chubby提供了类似分布式文件系统的接口，以及锁服务
它的设计目标是高可靠、高可用，而不是高性能，它是由很多普通机器组成
目前已有很多部门在使用了，可以为1W个4C机器提供服务，网络为1G带宽
Chubby是部署在单机房内的，不过也能让一个实例跨机房部署

Chubby提供的功能：

• 允许客户端同步他们的活跃状态
• 就他们环境的基本信息达成一致
• 提供高可用、高可靠 并服务大量客户端
• 提供易于理解的语义
• 吞吐量和存储容量不是设计的主要目标
• 提供了类似文件系统的接口，可以对整个文件读、写
• 提供了锁查询服务、文件修改的各种事件的通知服务

Chubby可以为开发者提供粗粒度的锁服务，以及领导者选举功能
BigTable、GFS用Chubby选举master，BigTable的master用Chuuby管理slaver，让客户端查找master
GFS和BigTable用Chubby存储一些少量的元数据信息，他们把Chubby当做分布式数据结构
一些服务提供了锁划分，将不同的服务做区分

在使用Chubby之前，大多数分布式系统都使用了特殊方法处理，使得选举时不会造成危害；而其他一些非常重要的操作则需要人为干预
而Chubby则可以省去人工干预的成本，它提在可用性方面提供了重要的改进，使得系统失败时不再需要人为进行干预
Chubby的核心是基于Paxos的，并不是重新发明什么算法，而是基于已有的算法做工程上的实现
目的是为了满足上述的高可用需求，论文中也省略了一些细节，如RPC何共识算法

设计

Chubby的作者并非设计了一个paxos的库，而是提供了一个客户端，这个客户端是独立于paxos服务的
并且什么服务也不依赖(除了DNS)，这样的做法有这么一些优势：

• 像插件一样增加到现有系统中
  • 很多服务一开始只是一个原型、不需要共识、不需要高可靠，随着服务成熟、用户增多才会考虑这些
  • 这时候提供一个锁服务，像插件一样增加到现有服务中，使的设计就变得很简单了
  • 比如选举只需要增加一些简单的代码，向一个服务写RPC然后变成主，其他服务因为编号低就会拒绝写入
  • 通过提供客户端的方式让使用者变得简单，比让用户的服务加入到共识服务中心要简单多了
• 提供锁服务，而不是name service
  • 用户需要发布选举、分区数据这些信息，也就是客户端需要读、写一些小量的文件
  • 使用 name service是可以的，但用锁服务更合适
  • 这样可以减少客户端依赖的服务数量；协议的一致性也是通用的
  • 客户端没有使用像DNS那样的缓存时间策略，这样的超时时间设置不好，会导致DNS负载很高；或者过期时间很长
  • 而基于锁服务的一致性客户端缓存，效果是更好的
• 程序员对锁服务更熟悉
  • 大部分程序员对使用锁服务来说，就像顺序编程那样
  • 不过很少有人能真正认识到分布式锁的难点
  • 而提供了基于锁的接口，让程序员在使用分布式系统就更有信心了
• 减少了客户端需要的服务器数量
  • 共识算法需要一组机器来完成服务，那样的话客户端依赖的服务就会很多
  • 而作为锁服务嵌入到客户端，只需要一个机器，就能达到共识
  • 这个客户端，其实就相当于多数派的共识算法

总结一下设计的关键点：

• 选择一个锁服务，而不是设计一个共识算法库
• 选择服务一些小文件，允许选举的主可以发布它自身，以及它的参数；而不是维护第二套服务

这些设计决定，是根据用户需求，以及我们的环境来决定的：

• 发布主服务，是通过chubby的文件来实现的，并且要被几千个客户端访问
• 客户端和副本服务，都想要知道主服务什么时候变更了，所以需要提供一种 通知机制
• 即使客户端不需要定期抓取文件，提供文件缓存机制也是可取的
• 开发人员对不一致的缓存语义使用起来会困惑，所以要提供一致性的语义
• 为避免经济损失，也提供了安全机制，如访问控制

Chubby使用的不是细粒度的锁，那样的话就需要锁住很短的时间
Chubby使用的是粗粒度的锁，比如用户只需要锁住一个选举的主，然后访问所有数据，这个动作可能会持续几个小时甚至几天

比较下这两种方案：

• 粗粒度
  • 对服务的负载压力较小，跟客户端事务增长的比例关系不大
  • 短暂的中断也不会影响服务
  • 将锁状态从客户端转移到另一个客户端 需要很大代价，但粗粒度锁允许锁失败
  • 这样做实现起来就简单了，而且影响也不大
• 细粒度
  • 即使短暂的不可用，也会影响到客户端
  • 随着新机器的增加，客户端的事务数量增加，锁服务的压力也会增大
  • 在锁失败时，可以减少维护锁负载的压力
  • 客户端要主动预防在网络分区中引发的锁丢失，而服务的故障恢复也不会使锁自动恢复

用户可以使用粗粒度锁，完成一些系列度锁的工作
比如将锁分配给一组机器，每组机器都管理一个锁，这样的维护成本很低，对锁服务压力也不大
这样的实现，等于是赋予用户一些使用权利，由他们自主决定使用锁的方式
从而降低了共识服务器的实现难度

基本结构

包含两个基本组件，客户端和服务端，客户端可以内嵌到用户的应用中
服务端是一个master和多个slaver，本质是一个 分布式共识协议
master通过选举产生，master也会定期向slaver广播租约，证明自己还是leader
master自己维护了一个本地数据库，所有的读写都到这个数据库上，并将所有的更新发往其他的slaver，其他的slaver通过共识算法实现一致性
客户端通过 DNS 找到master，如果非mater，就重定向到master，之后客户端都跟master交互
一旦master宕机，其他slaver就会感知到，从而触发选举机制

Chubby的下面可能还有其他的调度系统
论文中提到了，当一个副本挂了几个小时，就会有调度机制从空闲的机器池中选取一个机器，然后将数据分配给它
然后更新 DNS信息，替换IP地址，而master会定期跟DNS交互，最终会得到这些变更信息
master随后会更新的自己的数据库，将成员列表信息更新，并广播给其他slaver
新的机器从 backup机器上取得base数据，从活跃机器上取得delta数据，将两者合并就得到最新数据了

文件、目录、句柄

采用类似 unix 文件目录的形式

1

/ls/foo/wombat/pouch

ls 是所有的 chubby的共同前缀，foo是通过DNS查询的 后面的 /wombat/pouch 则是 chubby目录的名称，每个节点要不是一个目录，或者是一个文件
由于 chubby的名称结构类似文件系统，所以使用起来很方便，也容易跟现有的分布式文件系统GFS集成
通过不同的目录名，就可以区分不同的chubby的master
访问文件控制权限是由文件本身控制的，而不是由目录层级控制的
另外也不支持从一个目录导出到另一个目录，不支持目录的时间修改
节点分为两种

• 持久的，需要显示的删除
• 临时的，当客户端不再引用后悔自动删除，可以用于做临时目录，实现读写锁机制
  每个节点都包含元数据，以及ACL，ACL控制了读、写、修改三个权限，权限由子集成父目录，也可以显示的覆盖
  ACL是一套认证机制
  节点包含了一个单调递增的64位整数
• 当目录发现变更后，这个整数就会递增
• 当生成一个锁后，如果锁状态变化了，如无锁变成锁定，则也会递增
• 当内容发生变化，比如有写入，则会递增
• ACL内容发生变化，值也会递增

客户端也会获得一个类似UNIX的句柄

• 通过句柄数字，防止在创建期间的操作，至于在创建节点时才会检查，而unix是在打开时检查，读/写不检查
• 允许master判断当前的句柄是他生成的，还是由其他master生成的
• 如果旧的句柄出现在新的master 打开节点时，则master会重新创建这个句柄

锁和序列器

chubby提供了两种锁

• 写锁，排斥模式
• 读锁，共享模式

强制锁使的未持有锁的对象，无法访问锁定对象

• chubby经常保护由其他服务实现的资源，而不仅仅是与锁关联的文件
• 当用户需要对文件做调试、或者管理时，不希望用户关闭应用，因为复杂系统跟本地实现不同
• 开发人员以传统的断言方式检查： 是否持有锁，这样从强制检查中没有什么价值

持有L锁的进程，发送了一个R请求，但是这个R请求但失败了；另一个进程获取了L锁，发送了R请求
这会导致数据不一致，目前可以通过 虚拟时间、虚拟同步来解决
直接在所有的交互中引入 序号代价很高，chubby是在持有锁期间使用序列器
任何时候，持有锁的进程都可以发送一个不透明的 字节串，它描述了在获得锁之后的状态
包含了锁的名称、模式(排斥/共享)，锁的编号
如果客户端希望操作的资源被保护，就会将这个序号发给服务端，服务端会检查其序号是否有效
也可以通过这个序号来检查chubby的缓存有效性
可能由于时间为题，chubby未提供一个完美的解决方案，提供了一个失效的锁机制
当客户端挂掉后，锁服务会继续持有这个锁，直到超时，这样就包含了这个锁不会被其他人抢占

事件

chubby的客户端可以订阅时间，当创建一个句柄后，就会异步的触发这个事件

• 文件内容修改
• 子节点的增加、删除、修改
• master失败
• 句柄、或者锁变得无效了，比如通讯失败
• 锁获取成功
• 锁获取冲突

后面两个操作，是跟选举有关的，比如通过排斥锁选举了一个主服务
锁冲突后就会卡住

API

类似 unix的各种操作 比如，open()是打开一个文件描述符，close()是关闭
句柄与文件的实例相关联，而不是跟文件名关联 客户端的各种操作：

• 读、写、枷锁、修改ACL等
• 事件通知
• 锁延迟
• Poison()，导致后续的操作终止和失效，但不会释放资源
• GetContentsAndStat()，获取内容以及元数据
• SetContents()，设置内容
• GetStat()、ReadDir()、SetACL()
• Delete() 如果没有子节点，则删除
• Acquire(), TryAcquire(), Release() 获取和释放锁
• GetSequencer()、SetSequencer()、CheckSequencer() 设置、获取以及检查序列号

所有的调用都可以传递一些参数

• 支持回调函数
• 等待一段时间
• 获取错误和相关调试信息

应用使用这个客户端做选举，只有一个机器能当选为主，获得了文件锁，其他为副本
主会写文件内容，而其他节点通过读取或者事件通知，就知道谁是主了

缓存

为了减少网络I/O，chubby的客户端使用了缓存，可以缓存文件数据和元数据
写入到内层中，底层是通过RPC协议维持了keep-alive
客户端会定期跟master通讯，这样就保证了数据一致性，如果通讯失败，则缓存失效
当文件或者元数据被修改后，master会通知所有的客户端，让其缓存的数据失效
尽管需要提供严格的一致性，但我们拒绝了较弱的模型，因为我们觉得程序员会发现它们更难使用。类似地
要求客户端在所有消息中交换序列号的虚拟同步等机制也被认为在具有不同的预先存在的通信协议的环境中是不合适的
chubby的客户端允许让其缓存锁，使其可以超过严格限制的时间，可以让一个客户端反复使用
如果出现锁冲突了，则会有通知机制提醒

session和keep-alive

chubby的服务端和客户端会一致维持一个会话，通过keep-alive方式实现
在缓存未失效时，客户端的句柄，锁，缓存数据都是有效的
每个session都会关联一个租约时间
以下情况会使session提前超时

• 创建一个新会话时
• master故障转移时
• 当收到客户端的keep-avlie消息时

master会阻塞RCP，不允许它返回，直到客户端段之前的租约接近到期
通过keep-alive将事件通知、缓存失效返回给客户端
在故障转移的情况下，如果客户端 和master一致支持通讯，之后master挂了
此时session不会立马断开，会维持默认45秒，等待新的master，如果在45秒能连接上新的master则sessin继续有效
否则session就失效了，master挂到，到重新选举这段时间，称为 危险期
会由事件通知给客户端，可以让客户端在这段时间主动终止会话

故障转移

一旦master挂了，在内存中的句柄、锁、状态都没了；认证超时也会导致失败
客户端会在一段周期内尝试连接新的master，如果能成功就会继续持有这个锁
当老的master挂了之后，客户端会发送keep-alive，此时失败了，没有收到响应
于是客户端等待一段时间继续发送，这时候新的master选举成功了，客户端向新的master发送keep-alive
第一次请求不会成功，但是携带的 term是老的，所以失败了
但第二次会成功，而此时新master会判断出这个是一个安全的状态
因为其周期 小于 上一次租约结束，大于新租约的开始
于是在又一轮的keep-alive后，连接就建立起来了
此时新的master会根据磁盘上的状态，在内存中建立一个新的句柄，和状态信息，这些信息跟老master的一样
另一部分是从客户端那里获取的
新master处理过程：

1. 使用一个新的 epoch 编号并返回给客户端，拒绝掉老编号的客户端请求
2. 新的master可以响应master定位请求，但不会马上处理请求响应
3. 从数据库中重建会话状态，锁信息等，并延长最大的会话时间，也就是故障转移
4. 接受客户端的keep-alive，但不响应其他操作
5. 向所有的客户度发出 故障转移事件，这些客户端就会清空缓存(因为可能过期了)，跟客户端绑定的应用也会收到这个事件
6. master等待每个每个session的响应，或者他们超时
7. master开始接受请求
8. 如果客户端使用旧的句柄，则新master在内存中重建新句柄；如果重建的句柄已经关闭，则master会保存这个句柄，这样延迟和旧的客户端就不能再使用这个句柄了
9. 经过一段时间，master删除了不再打开的临时文件，客户端在故障转移后客户端可以重刷新临时文件；如果文件上的最后一个客户端在故障转移丢失，则此文件不会立刻消失

跟系统其他组件相比，故障转移部分的代码不多，但是更容易产生bug

数据库实现

chubby最早是采用 berkeley db作为存储的
berkeley db采用了b+树的机制，key是字节string，value可以是任意的二进制
在berkeley db之上，增加了一个比较函数，用于排序路径上的名称数量，这样就把相邻的节点紧挨着了
berkeley db使用分布式共识算法，然后复制数据库日志
berkeley db的b+代码很成熟，但是复制功能是最近增加的，而且chubby只使用berkeley db很少的一些特性，比如原子性；而用不到它的事务特性
再加上复制特性可能有风险，于是chubby基于 WAL的方式重写了一个简单的数据库
这样就是基于 WAL的方式复制日志

备份和镜像

备份提供了灾备以及初始化新副本数据库的方式，而不会影响到现有的服务
每过一个小时，chubby就会往GFS上写一个备份文件，每个备份文件都是独立的

chubby允许将文件集合从一个镜像到另一个，在CUD时会通知镜像的代码
修改的文件会在不到一秒内反馈到世界范围内的各个镜像中，如果网络有问题则保持不变，等网络恢复后继续重连
更新文件是通过比较文件标识符和校验码实现的
镜像可以将配置的文件复制到全世界各个范围
一个特殊的单元，global，包含一个子树 /ls/global/master 镜像到每个 /ls/global/slave
全局镜像是特殊的，有5个副本，分散在全球各地，所有可以从大多数组织中获取

从全局单元镜像的文件包括 查比自己的访问控制列表，各种文件 Chubby cell和其他系统向我们的监控服务发布它们的存在，允许客户端定位大数据集(如Bigtable cell)的指针，以及其他系统的许多配置文件

扩展机制

单个master可以服务 9W个客户端

• 可以创建任意数量的chubby机器，按照地域分布部署，这样用户基于DNS可以就近查找，一个chubby可以服务
• 调大keep-alive时间，可以减少master负载
• 客户端可以缓存文件、元数据、缺失的文件、打开的句柄，这样可以减少master负载
• 使用协议转换，把chubby的协议转为不太复杂的协议，如DNS这样的

后面描述了两种实现方式，代理、分区，这两种方式还没有在生产环境部署过
单个机房容纳的机器数量是有限的
客户端和服务端使用了类似的机器配置，所以增加客户端机器的硬件数量，也会增加服务端的处理能力

代理

• chubby的协议可以被代理，代理连接了客户端和chubby master，两边保持协议一致即可
• 的代理可以减少keep-alive，减少了chubby的负载，可以支持读，这样更能减少master负载
• 但对写不管用，写的时候，proxy还是要写到chubby的，不过写流量大概只有 1%
• 如果proxy能处理N个客户端，keep-alive流量就可以减少 1/N
• proxy增加了写，第一次连接的延迟，但是提高了可用性
• 故障转移的场景下，proxy就不管用了

分区

• 选择chubby的接口是为了在服务器之间划分 名称空间，可以按目录对名称空间划分
• 可以将chubby划分为 N 个分区，每个分区都是一个master + N个副本
• D目录下的每个节点 D/C 按照 hash(D) % N，存储分区 P(D/C)
• 元数据不会划分，分区的目的是支持更大的集群，而分区之间几乎没有什么通讯
• chubby缺少硬链接、目录修改时间、跨目录重命名操作
• ACL本身是文件，因此一个访问一个分区需要依靠另一个分区做检查，而ACL很容易缓存，只有open和delete需要ACL
• 当目录被删除时，需要跨分区删除里面的文件
• 每个客户端都可以跟大多数分区联系，这也大大减少了流量
• 如果要支持更多客户端，策略是 组合 代理 + 分区

使用、惊喜、错误的设计

使用行为

相关统计信息如下

几周时间大概有61次停机，包含了 700天的数据
排查了机房维护的停机，剩下的故障包括：

• 网络拥塞、连接问题
• 正常维护
• 高负载
• 操作错误
• 软件、硬件bug

大部分故障在 15秒内可以恢复
出现过 6 次丢数据，包括 数据库软件错误、操作错误，但没有涉及到硬件问题
讽刺的是，操作错误是因为想升级软件，避免软件错误
还修复了 2次 非master部分的损坏
当会话数量超过 9W，就变成的负载很高了，可能是客户端库的一些错误导致的，比如错误的禁用了缓存
导致大量的会话连向服务端
设计者甚至故意在 open的时候增加了一些延迟

其他问题

java clent

• chubby的服务端大概 7K+代码
• java在谷歌也很受欢迎，但是要链接其他语言就要用 JNI，这个则很不受欢迎
• java客户端使用协议转换服务连接的，有点像一个代理的server
• 不过这样就要额外的维护一套server

名字服务

• dns是使用TTL，如果在过期前没有刷新，则会超时
• dns替换一个服务需要把过期时间设置很短，但是太短会对DNS服务器造成压力
• chubby除了锁，也充当名字服务
• 在chubby没出现之前，都是访问DNS的，但大量的临时程序会对DNS造成很大压力
• 单个master就可以提供9W个客户端，而需要代理
• 因为大多数客户端都做了缓存，除非显示更新，否则客户端会一致缓存，直到失效
• 所以chubby在谷歌内部也充当了名字服务器
• 设计者们还搞了 chubby dns server，将dns客户端的数据存储到chubby中

失败转移

• 最开始的设计是，每创建一个session，就往 berkeley db中写数据
• 后来改成延迟写入，只有修改、或者锁、创建临时文件时才会写入
• 但是只读session就不会存到数据库中，如果出现故障转移，则客户端会读到过期数据
• 解决办法是，新master上任后，需要等待一个最大过期时间
• 新的master需要等待一个最大超时后，再以相同的方式重建这些会话
• 客户端联系的一个proxy如果挂了，新的proxy可以继续维持这个会话
• 只要master没有丢弃之前客户端的锁、临时文件，那么新的proxy就可以获得这些，从而继续提供服务

滥用的客户端

• 谷歌的项目团队可以自己申请资源，自己维护机器，来搭建chubby，不过这样很麻烦，一般都是共享的
• 一些对行为不理解，滥用的几乎等同于攻击行为了
• 很多软件都缺乏文档，一个团队可能开发了一个模块，然后另一个团队使用了它，带来了灾难后果
• 缺乏主动的缓存
  • 一开始对于不存在的文件、重用open都没有考虑
  • 开发人员使用无限循环来确认文件文件是否存在
  • 通过反复的open、close来实现poll，而他们可能只希望打开一次
  • 最终将open做改造，使的其打开不会引起多大开销
• 缺乏配额
  • chubby不是用来做存储系统的，也不时候存储大文件
  • 但有的项目人员，用chubby来存储用户上传行为数据，导致一个文件超过了1.5M，每次都要覆盖写
  • chubby团队的人修改了配额，限制到最大265K，但需要那个团队的人修改代码
  • 结果花了一年的时间，才把数据迁移走
• 发布/订阅
  • 有人就拿chubby的事件通知，当做发布/订阅使用
  • 但chubby需要维护很重的锁保证，使用无效而不是更新来维护缓存一致性
  • 这样就导致发布订阅这种方式很慢
  • 好在使用这种方式的人后来都发现问题，并重构了项目

学习到的经验

• 开发人员很少考虑到 可用性
  • 开发人员曾经申请了几百台机器，然后选举master初始化时花费了几十分钟
  • chubby的全球部署时，同时有两个地理位置很远的机房同时宕掉极为罕见
  • chubby对于故障转移提供了事件通知，不过很多开发人员得到这个通知后，就直接关闭应用了
  • chubby的改进建议是，重新评审这个项目，不要把它们项目的可用性跟chubby的可用性 联系在一起，它们两是不相关的
  • 提供更高级的API，让其调用跟chubby的可用性独立开来
  • 事后复盘，总结操作问题、chubby的bug
• 忽略细粒度的锁
  • 开发人员通常会优化它们的应用，消除不必要的通讯
  • 这样的结果是，它们需要一种粗粒度的锁