The Chubby lock service for loosely-coupled distributed systems

论文阅读系列

Posted by ChenJY on July 20, 2018 | Viewed times

开篇作者主要介绍了谷歌内部的分布式锁服务 Chubby,可以在分布式环境下提供粗粒度的锁服务,可在大规模小型机器组成的松耦合分布式系统中实现同步、存储元数据、拓扑结构或者配置信息等功能。

谈到如何实现异步的一致性,Chubby 的解决方案是引入 Paxos,作者也提到当时的普遍情况是,只要涉及到实现异步一致性的系统其内部实现或多或少都有 Paxos 算法的影子。作者强调这篇论文并不涉及新提出的算法,而只是聚焦于工程实现和后续优化提升。事实上整篇论文并不涉及一致性算法。

中心化锁服务

第二部分作者叙述了为什么他们选择做一个中心化的锁服务,开发者使用本地客户端去访问这个 lock service,而不是创建一个 Paxos 算法库供给开发人员使用。作者阐述这样的原因既是由开发者需求决定的,也是由于中心锁服务能减少应用依赖的服务个数。这样的设计要求客户端能够主动发现中心服务的数据变更,同时客户端需要能缓存信息,减少对服务器的压力,当然还需要做一些访问限制。

接下来作者叙述为什么他们选择提供粗粒度的锁服务而不是细粒度的,因为这样可以使得锁的持有时间较长,减少服务器压力;细粒度的锁服务即使是遇到小规模不可用也会导致大量 client 停止工作;应用开发者可以自己对业务内部实现细粒度的锁。

系统架构

在系统结构这部分,Chubby 主要有两个组成部分,server 和 client library。Chubby 内部有一个 Chubby Cell 的概念,一般一个 Cell 中有五台 Server 组成一个集群,其中一个 master,其他为副本(replica)。五台机器按照分布式一致性协议(Paxos)选举出 master,要想成为 master 必须得到五台中大多数的投票(至少三台,换句话说只要这个 Cell 中三台机器在正常运行那么这个 Cell 就能保证正常的对外服务)。

其中 master 会以租约的形式运行,只要它能得到副本的同意(即续租),那么租约便能定时更新然后延长 master 的运行时间,可以保证当 master 正常运作时,短时间内不会再选举新的 master。并且Chubby支持通过小文件的读写方式进行 master 选举结果的发布与订阅,因此Chubby实际应用中,必须能支撑成百上千个客户端对同一个文件进行监听和读取。

客户端如何定位到哪台是 master 的呢?这里客户端会向 DNS 请求 Chubby 服务器列表,然后随机发起访问,非master服务器会依据自身的存储的集群信息向客户端反馈哪台是master,然后客户端重定向到master。

副本(replica)是 copy master 的数据库来保持状态一致的,但是只有 master 才会读写,其更新传播给副本,当过半数的replica回复收到请求之后master才会向客户端反馈正常。读请求不需要广播直接 master 处理。

Chubby 的 client 接口设计类似于 Unix 文件系统结构,通过该客户端不仅能对Chubby服务器上的整个文件进行读写,还能添加对文件节点的锁控制,并且通过事件机制订阅服务器端对文件内容变更的通知。

目录与文件

紧接着作者开始介绍 Chubby 的文件、目录和句柄,大致上和 Unix File System 很像,后面也说了 API 就是类似于文件系统,于是一个文件的地址会由目录和斜杠分隔,这样的地址指向称为一个 Node,Node 有永久和临时两种类型,每个 Node 除了数据还有一些元数据。每个 Chubby 的文件和目录都可以作为读写锁,其中写锁是独占的,读锁是共享的。如何实现锁提到了 sequence number。

锁与 sequence number

分布式环境中锁机制是很复杂的,原因是网络通信的不确定性。例如客户端C1获取互斥锁L,并在持有L的期间发出request R,但是由于网络问题 R 延迟了未到达服务端,此时应用程序认为客户端C1进程挂了,为C2重新分配了锁L,然后重新发起之前失踪的Request R,但是之后前一个失踪的R又到达了服务器端,这是在非幂等的条件下服务器端就可能再次响应R导致数据出现不一致。

Chubby采用了 delay 和 sequence number 两种机制来优化(我认为不算是解决)上述问题,delay 很简单就是客户端在非正常情况下释放锁的话,那么Chubby服务器会允许该客户端在 delay 时间内一直持有不释放这个锁,这样其他客户端无法得到这个锁,可以减少由于网络延迟造成的问题。

sequence number 指锁的持有者向Chubby服务端请求一个序号(包括几个属性),然后之后在需要使用锁的时候讲该序号一并发给 Chubby 服务器,服务端检查序号的合法性,包括 number 是否有效等。

事件通知机制和缓存

接下来转到客户端作者介绍了事件通知机制,在 server 端发生部分事件时对客户端进行通知,使得客户端可以感知到数据改变或者刷新、禁用自己的本地 Cache。

客户端会有自己的本地缓存,这样可以减少对 Chubby 的读压力。如何保证客户端和服务端缓存的一致性呢?答案是借助租约,缓存时效由租约把持,并且由协议保证客户端见到的是和 Chubby 一致的状态,否则会报错。一旦租约到期客户端要向服务端续订才能继续保持缓存的有效性,否则只能过期缓存。如果 file data 或者 meta-data 将被改变了,master 会通知所有缓存了该信息的客户端,期间这部分更改会被阻塞,等到 master 收到了客户端确认本地缓存无效或者是过期了缓存租约,那么这部分更改才会生效。

本地缓存还可以重用句柄,或者是更长时间地 hold lock 期待客户端将来会再使用这把锁,如果期间发生了其他客户端请求这把锁的情况,那么在 master 通知它后就释放。

Session、KeepAlive

一个 Chubby session 是在 Chubby cell 和客户端之间的一种关系,它存在于某个时间间隔内,通过周期性的称为 KeepAlives 的心跳来保持 session 的活性。响应来自客户端的 KeepAlive RPC 调用时。在收到一个KeepAlive RPC 时,master 通常会阻塞该 RPC(不允许它返回)到该 client 的前一个租约接近过期。然后 master 允许该 RPC 返回给客户端,同时告知客户端新的租约过期时间。Master 可以任意的延长过期时间。默认的延长时间是12s,但是一个负载过高的 master 可能使用一个更高的值来减少它所需要处理的 KeepAlives RPC 调用。收到上一个 KeepAlives 调用的回复后,客户端会初始化一个新的 KeepAlives 调用。因此客户端可以保证通常只有一个KeepAlives 调用阻塞在 master 端。这个 KeepAlives 的回复也可以用来给客户端传递时间和过期缓存。同时客户端维护了一个本地租约过期时间,如果客户端的本地缓存租约过期了,由于此时它就无法确定 master 是否已经结束了这个 session,客户端就需要清空并禁用它的缓存,此时 session 处于 jeopardy 状态。客户端会继续等待一个称为 grace period 的时长,默认是45秒。如果在grace period 结束之前,客户端和 master 又完成了一次成功的 KeepAlive 交互,那么客户端就会再次使它的缓存有效。否则,客户端就假设 session 已过期。

当 master 挂了或者失去 master 身份的时候,它会丢掉它的关于 session,句柄及锁的所有内存状态,转而运行一个 session 租约计时器。等待新的 master 选举出来,如果一个 master 选举很快完成,那么客户端就可以在他们的 local 租约计时器过期之前联系新的 master。如果选举花了很长时间,客户端 grace period 使得会话可以超越正常的租约过期时间而能够在故障恢复期间仍能得以维护。新的 master 需要重建它的前任 master 内存状态,这里一部分通过读取保存在硬盘上的数据来完成,一部分通过从客户端获取状态,一部分再通过保守的估计来完成。数据库会记录每个会话,持有的锁及临时文件。

论文剩下的部分主要是一些工程上的演进和使用改良。

License


这是一个不定时更新的、披着程序员外衣的文青小号。

在这里,既分享极客技术,也记录人间烟火,欢迎关注。


Comment