Chubby的锁服务

最近在完成Zeppelin的中心节点重构的过程中，反思了我们对分布式锁的实现和使用。因此重读了Chubby论文The Chubby lock service for loosely-coupled distributed systems，收益良多的同时也对其中的细节有了更感同身受的理解，论文中将众多的设计细节依次罗列，容易让读者产生眼花缭乱之感。本文希望能够更清晰的展现Chubby的设计哲学和实现方式，以及带给我们的思考和启发。首先介绍Chubby的定位和设计初衷，这也是Chubby众多细节的目标和本质；之后从一致性、锁的实现和锁的使用三个方面介绍Chubby作为分布式锁的设计和实现；最后总结一些Chubby对我们设计开发分布式系统的一般性的经验和启发。

定位

Chubby的设计初衷是为了解决分布式系统中的一致性问题，其中最常见的就是分布式系统的选主需求及一致性的数据存储。Chubby选择通过提供粗粒度锁服务的方式实现：

Chubby provide coarse-grained locking as well as reliable storage for a loosely-coupled distributed system.

这里的粗粒度(Coarse-grained)锁服务相对于细粒度(Fine-grained)锁服务，指的是应用加锁时间比较长的场景，达到几个小时或者几天。Chubby的三个重要的设计目标是：可靠性(reliability)、可用性(availability)、易于理解(easy-to-understand)，除此之外，一致性当然也是锁服务的立命之本。这些就是稍后会提到的各种设计细节所追求的目标。对于为什么选择锁服务，而不是一致性库或者一致性服务的问题，作者总结了如下几点：

• 用户系统可能并不会在开发初期考虑高可用，而锁服务使得这些系统在后期需要一致性保证的时候能够以最小的代价接入；
• 分布式系统在选主的同时需要存储少量数据供集群其他节点读取，而锁服务本身就可以很好的提供这个功能；
• 开发者更熟悉锁接口的使用；
• 锁服务使得需要一致性或互斥的应用节点数不受quorum数的限制。

分布式锁

分布式锁是Chubby的设计初衷，我们这里就以分布式锁来展开其设计实现，Chubby的结构如下图所示：

• Chubby包括客户端和服务端两个部分；
• 客户端通过一个Chubby Library同服务端进行交互；
• 服务端由多个节点组成集群的方式提供高可用的服务。

我们认为分布式锁的问题其实包含三个部分，分别是一致性协议、分布式锁的实现、分布式锁的使用。三个部分自下而上完成了在分布式环境中对锁需求，下面我们就将从这三个方面介绍Chubby的设计。

1， 一致性协议

一致性协议其实并不是锁需求直接相关的，假设我们有一个永不宕机的节点和永不中断的网络，那么一个单点的存储即可支撑上层的锁的实现及使用。但这种假设在互联网环境中是不现实的，所以才引入了一致性协议，来保证我们可以通过副本的方式来容忍节点或网络的异常，同时又不引起正确性的风险，作为一个整体对上层提供高可用的服务。

Chubby采用的是一个有强主的Multi-Paxos，其概要实现如下：

• 多个副本组成一个集群，副本通过一致性协议选出一个Master，集群在一个确定的租约时间内保证这个Master的领导地位；
• Master周期性的向所有副本刷新延长自己的租约时间；
• 每个副本通过一致性协议维护一份数据的备份，而只有Master可以发起读写操作；
• Master挂掉或脱离集群后，其他副本发起选主，得到一个新的Master；

具体的Paxos实现可以参考论文Paxos Made Simple，在这里我们只需要把它近似看做一个不会宕机不会断网的节点，能保证所有成功写入的操作都能被后续成功的读取读到。

2，分布式锁的实现

这部分是Chubby实现的重点，为了更好的梳理这部分的脉络，我们先看看Chubby提供的API以及给Client的使用机制，他们一起组成了Chubby对外的接口；之后介绍锁的实现；最后结合Chubby对读写请求比例，可用性，Corase-Lock等定位引出的Cache，Session及故障恢复等内部机制。

接口

Chubby的对外接口是外部使用者直接面对的使用Chubby的方式，是连接分布式锁的实现及使用之间的桥梁：

• Chubby提供类似UNIX文件系统的数据组织方式，包括Files和Directory来存储数据或维护层级关系，统称Node；提供跟Client同生命周期的Ephemeral类型Node来方便实现节点存活监控；通过类似于UNIX文件描述符的Handle方便对Node的访问；Node除记录数据内容外还维护如ACL、版本号及Checksum等元信息。
• 提供众多方便使用的API，包括获取及关闭Handle的Open及Close接口；获取释放锁的Aquire，Release接口；读取和修改Node内容的GetContentAndStat，SetContent，Delete接口；以及其他访问元信息、Sequencer，ACL的相关接口。
• 提供Event的事件通知机制来避免客户端轮训的检查数据或Lock的变化。包括Node内容变化的事件；子Node增删改的事件；Chubby服务端发生故障恢复的事件；Handle失效事件。客户端收到事件应该做出对应的响应。

锁实现

每一个File或者Directory都可以作为读写锁使用，接受用户的Aquire，Release等请求。锁依赖下层的一致性服务来保证其操作顺序。Chubby提供的是Advisory Lock的实现，相对于Mandatory Lock，由于可以访问加锁Node的数据而方便数据共享及管理调试。分布式锁面对的最大挑战来自于客户端节点和网络的不可靠，Chubby提供了两种锁实现的方式：

1)，完美实现：

• Aquire Lock的同时，Master生成一个包含Lock版本号和锁类型的Sequencer；
• Chubby Server在Lock相关节点的元信息中记录这个版本号，Lock版本号会在每次被成功Aquire时加一；
• 成功Aquire Lock的Handle中也会记录这个Sequencer；
• 该Handle的后续操作都可以通过比较元信息中的Lock版本号和Sequencer判断锁是否有效，从而接受或拒绝；
• 用户直接调用Release或Handle由于所属Client Session过期而失效时，锁被释放并修改对应的元信息。

2)，简易实现：

• Handle Aquire Lock的同时指定一个叫做lock-delay的时长；
• 获得Lock的Handle可以安全的使用锁功能，而不需要获得Sequencer；
• 获得Lock的Handle失效后，Server会在lock-delay的时间内拒绝其他加锁操作。
• 而正常的Release操作释放的锁可以立刻被再次获取；
• 注意，用户需要保证在指定的lock-delay时间后不会再有依赖锁保护的操作；

对比两种实现方式，简易版本可以使用在无法检查Sequencer的场景从而更一般化，但也因为lock-delay的设置牺牲了一定的可用性，同时需要用户在业务层面保证lock-delay之后不会再有依赖锁保护的操作。

Cache

从这里开始要提到的Chubby的机制是对Client透明的了。Chubby对自己的定位是需要支持大量的Client，并且读请求远大于写请求的场景，因此引入一个对读请求友好的Client端Cache，来减少大量读请求对Chubby Master的压力便十分自然，客户端可以完全不感知这个Cache的存在。Cache对读请求的极度友好体现在它牺牲写性能实现了一个一致语义的Cache：

• Cache可以缓存几乎所有的信息，包括数据，数据元信息，Handle信息及Lock；
• Master收到写请求时，会先阻塞写请求，通过返回所有客户端的KeepAlive来通知客户端Invalid自己的Cache；
• Client直接将自己的Cache清空并标记为Invalid，并发送KeepAlive向Master确认；
• Master收到所有Client确认或等到超时后再执行写请求。

Session and KeepAlive

Session可以看做是Client在Master上的一个投影，Master通过Session来掌握并维护Client：

• 每个Session包括一个租约时间，在租约时间内Client是有效的，Session的租约时间在Master视角和Client视角由于网络传输时延及两端的时钟差异可能略有不同；
• Master和Client之间通过KeepAlive进行通信，Client发起KeepAlive，会被Master阻塞在本地，直到Session租约临近过期，此时Master会延长租约时间，并返回阻塞的KeepAlive通知Client。除此之外，Master还可能在Cache失效或Event发生时返回KeepAlive；
• Master除了正常的在创建连接及租约临近过期时延长租约时间外，故障恢复也会延长Session的租约；
• Client的租约过期会先阻塞本地的所有请求，进入jeopardy状态，等待额外的45s，以期待与Master的通信恢复。如果事与愿违，则返回用户失败。

Session及KeepAlive给了Chubby Server感知和掌握Client存活的能力，这对锁的实现也是非常重要的，因为这给了Master一个判断是否要释放失效Lock的时机。最后总结下，这些机制之间的关系，如下图：

故障恢复

Master发生故障或脱离集群后，它锁维护的Session信息会被集群不可见，一致性协议会选举新的Master。由于Chubby对自己Corase Lock的定位，使用锁的服务在锁的所有权迁移后会有较大的恢复开销，这也就要求新Master启动后需要恢复必要的信息，并尽量减少集群停止服务过程的影响：

• 选择新的epoch；
• 根据持久化的副本内容恢复Session及Lock信息，并重置Session租约到一个保守估计的时长；
• 接受并处理Client的KeepAlive请求，第一个KeepAlive会由于epoch错误而被Maser拒绝，Client也因此获得了最新的epoch；之后第二个KeepAlive直接返回以通知Client设置本地的Session租约时间；接着Master Block第三个KeepAlive，恢复正常的通信模式。
• 从新请求中发现老Master创建的Handle时，新Master也需要重建，一段时间后，删除没有Handle的临时节点。

3， 分布式锁的使用

锁的使用跟上面提到的锁的实现是紧密相关的，由于客户端节点及网络的不可靠，即使Chubby提供了直观如Aquire，Realease这样的锁操作，使用者仍然需要做出更多的努力来配合完成锁的语义，Chubby论文中以一个选主场景对如何使用锁给出了详细的说明，以完美方案为例：

• 所有Primary的竞争者，Open同一个Node，之后用得到的Handle调用Aquire来获取锁；
• 只有一个成功获得锁，成为Primary，其他竞争者称为Replicas；
• Primary将自己的标识通过SetContent写入Node；
• Replicas调用GetContentsAndStat获得当前的Primary标识，并注册该Node的内容修改Event，以便发现锁的Release或Primary的改变；
• Primary调用GetSequencer从当前的Handle中获得sequencer，并将其传递给所有需要锁保护的操作的Server；
• Server通过CheckSequencer检查其sequencer的合法性，拒绝旧的Primary的请求。

如果是简单方案，则不需要Sequencer，但需要在Aquire操作时指定lock-delay，并保证所有需要锁保护的操作会在最后一次Session刷新后的lock-delay时间内完成。

启发

暂且抛开Chubby对分布式锁的实现，本质上Chubby是一个在分布式环境中提供服务的系统。其在复杂性控制，可用性，可靠性，可扩展性等方面作出的努力和思考对我们其他系统的设计开发也是很有指导和借鉴意义的，下面列举一些进行说明。

1，责任分散

分布式系统中，通常都会有多个角色进行协作共同完成某个目标，有时候合理的将某些功能的责任分散到不同角色上去，分散到不同时间去，会起到降低复杂度，减少关键节点压力的效果。比如Chubby中发生写事件需要更新Client Cache时，Master并没有尝试自己去更新所有的Client，而是简单的Invalid所有Client的Cache，这样就将更新所有Client Cache这项任务分散到所有的客户端上，分散到后边一次次的请求时机中去。这种推变拉的做法也是Zeppelin中大量使用的。

2，考虑可扩展时，减少通信次数有时候比优化单次请求处理速度更有效

Chubby作为一个为大量Client提供服务的中心节点，并没有花过多的精力在优化单条请求路径上，而是努力地寻找可以减少Client与Master通信的机制：

• 分散多个Cell负责不同地域的Client；

• 负载较重时，Master可以将Session的租约从12s最多延长到60s来减少通信频次；

• 通过Client的Cache缓存几乎所有需要的信息；

• 进一步的采用Proxy或Partition的方式。

  ​

3，限制资源的的线性增长

论文中提到对Chubby使用资源情况的检查，包括RPC频率、磁盘空间、打开文件数等。任何可能随着用户数量或数据量的增加而线性增加的资源都应该有机制通过降级操作限制在一个合理的范围内，从而提供更加健壮的服务。负载较重时延长Session租约时间及存储配额的设置应该就是这方面的努力。

Any linear growth must be mitigated by a compensating parameter that can be adjusted to reduce the load on Chubby to reasonable bounds

4，故障恢复时的数据恢复

为了性能或负载，Master不可能将所有需要的信息全部通过一致性协议同步到所有副本。其内存维护的部分会在故障发生时丢失，新的Master必须能尽可能的恢复这些数据来让外部使用者尽量少的感知到故障的发生。恢复的数据来源方面，Chubby做了一个很好的范例：

• 部分来源于持久化的一致性数据部分，这也是最主要的；
• 部分来源于客户端，如Handle会记录一些信息供新主读取并重新创建。论文中也提到在Chubby的进化中，这种方式也变得越来越重要；
• 部分来源于保守估计，如Session的Timeout。

参考

The Chubby lock service for loosely-coupled distributed systems

Talk about consensus algorithm and distributed lock

Paxos Made Simple

Qihoo360 Zeppelin