第2章 Google云计算原理 正是考虑到以上几个问题，Google设计了Chubby，而不是单独地维护一个函数库（实际上，Google有这样一个独立于Chubby的函数库，不过一般情况下并不会使用）。在设计的过程中有一些细节问题也值得我们关注，比如在Chubby系统中采用了建议性的锁而没有采用强制性的锁。两者的根本区别在于用户访问某个被锁定的文件时，建议性的锁不会阻止这种行为，而强制性的锁则会，实际上这是为了便于系统组件之间的信息交互行为。另外Chubby还采用了粗粒度（Coarse-Grained）锁服务而没有采用细粒度（Fine-Grained）锁服务，两者的差异在于持有锁的时间。细粒度的锁持有时间很短，常常只有几秒甚至更少，而粗粒度的锁持有的时间可长达几天，做出如此选择的目的是减少频繁换锁带来的系统开销。当然用户也可以自行实现细粒度锁，不过建议还是使用粗粒度 的锁。
图2-9[13]就是Chubby的基本架构。很明显，Chubby被划分成两个部分：客户端和服务器端，客户端和服务器端之间通过远程过程调用（RPC）来连接。在客户这一端每个客户应用程序都有一个Chubby程序库（Chubby Library），客户端的所有应用都是通过调用这个库中的相关函数来完成的。服务器一端称为Chubby单元，一般是由五个称为副本（Replica）的服务器组成的，这五个副本在配置上完全一致，并且在系统刚开始时处于对等地位。这些副本通过quorum机制选举产生一个主服务器（Master），并保证在一定的时间内有且仅有一个主服务器，这个时间就称为主服务器租约期（Master Lease）。如果某个服务器被连续推举为主服务器的话，这个租约期就会不断地被更新。租续期内所有的客户请求都是由主服务器来处理的。客户端如果需要确定主服务器的位置，可以向DNS发送一个主服务器定位请求，非主服务器的副本将对该请求做出回应，通过这种方式客户端能够快速、准确地对主服务器做出定位。
客户端应 用程序 ? Chubby 程序库 远程过程调用 Chubby 程序库 主服务器 Chubby单元的 五个服务器 客户端应 用程序 客户端进程
图2-9 Chubby的基本架构
2.3.3 Chubby文件系统
Chubby系统本质上就是一个分布式的、存储大量小文件的文件系统，它所有的操作都是在文件的基础上完成的。例如在Chubby最常用的锁服务中，每一个文件就代表了一个锁，用户通过打开、关闭和读取文件，获取共享（Shared）锁或独占（Exclusive）锁。选举主服务器的过程中，符合条件的服务器都同时申请打开某个文件并请求锁住该文件。成功获得锁的服务器自动成为主服务器并将其地址写入这个文件夹，以便其他服务器和用户可以获知主服务器的地址信息。
21 2 云计算
Chubby的文件系统[13]和UNIX类似。例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，这是所有Chubby文件系统的共有前缀；foo是某个单元的名称；/wombat/pouch则是foo这个单元上的文件目录或者文件名。由于Chubby自身的特殊服务要求，Google对Chubby做了一些与UNIX不同的改变。例如Chubby不支持内部文件的移动；不记录文件的最后访问时间；另外在Chubby中并没有符号连接（Symbolic Link，又叫软连接，类似于Windows系统中的快捷方式）和硬连接（Hard Link，类似于别名）的概念。在具体实现时，文件系统由许多节点组成，分为永久型和临时型，每个节点就是一个文件或目录。节点中保存着包括ACL（Access Control List，访问控制列表，将在2.3.5节讲解）在内的多种系统元数据。为了用户能够及时了解元数据的变动，系统规定每个节点的元数据都应当包含以下四种单调递增的64位编号[13]。
1）实例号（Instance Number）：新节点实例号必定大于旧节点的实例号。 2）内容生成号（Content Generation Number）：文件内容修改时该号增加。 3）锁生成号（Lock Generation Number）：锁被用户持有时该号增加。 4）ACL生成号（ACL Generation Number）：ACL名被覆写时该号增加。
用户在打开某个节点时就会获取一个类似于UNIX中文件描述符（File Descriptor）的句柄[13]（Handles），这个句柄由以下三个部分组成。
1）校验数位（Check Digit）：防止其他用户创建或猜测这个句柄。 2）序号（Sequence Number）：用来确定句柄是由当前还是以前的主服务器创建的。 3）模式信息（Mode Information）：用于新的主服务器重新创建一个旧的句柄。
在实际的执行中，为了避免所有的通信都使用序号带来的系统开销增长，Chubby引入了sequencer的概念。sequencer实际上就是一个序号，只不过这个序号只能由锁的持有者在获取锁时向系统发出请求来获得。这样一来Chubby系统中只有涉及锁的操作才需要序号，其他一概不用。在文件操作中，用户可以将句柄看做一个指向文件系统的指针。这个指针支持一系列的操作，常用的句柄操作函数如表2-1所示。
表2-1 常用句柄函数及其作用
函数名称 Open() Close() Poison() GetContentsAndStat() GetStat() ReadDir() SetContents() SetACL() Delete() Acquire() Release() GetSequencer() SetSequencer() CheckSequencer() 作 用 打开某个文件或者目录来创建句柄 关闭打开的句柄，后续的任何操作都将中止 中止当前未完成及后续的操作，但不关闭句柄 返回文件内容及元数据 只返回文件元数据 返回子目录名称及其元数据 向文件中写入内容 设置ACL名称 如果该节点没有子节点的话则执行删除操作 获取锁 释放锁 返回一个sequencer 将sequencer和某个句柄进行关联 检查某个sequencer是否有效 22 2
第2章 Google云计算原理 2.3.4 通信协议
客户端和主服务器之间的通信是通过KeepAlive握手协议来维持的，图2-10[13]就是这一通信过程的简单示意图。
旧的主服 务器故障 旧的主 服务器 租约期M2 租约期M1 1 3 KeepAlives 4 6 租约期M3 8 无主服务器 选出新的 主服务器 新的主 服务器 2 租约期C1 5 宽限期 7 租约期C3 客户端 租约期C2 危险状态临界点 安全状态临界点
图2-10 Chubby客户端与服务器端的通信过程
图2-10中从左到右时间在增加，斜向上的箭头表示一次KeepAlive请求，斜向下的箭头则是主服务器的一次回应。M1、M2、M3表示不同的主服务器租约期。C1、C2、C3则是客户端对主服务器租约期时长做出的一个估计。KeepAlive是周期发送的一种信息，它主要有两方面的功能：延迟租约的有效期和携带事件信息告诉用户更新。主要的事件包括文件内容被修改、子节点的增加、删除和修改、主服务器出错、句柄失效等。正常情况下，通过KeepAlive握手协议租约期会得到延长，事件也会及时地通知给用户。但是由于系统有一定的失效概率，引入故障处理措施是很有必要的。通常情况下系统可能会出现两种故障：客户端租约期过期和主服务器故障，对于这两种情况系统有着不同的应对方式。
1．客户端租约过期
刚开始时，客户端向主服务器发出一个KeepAlive请求（图2-10中的1），如果有需要通知的事件时则主服务器会立刻做出回应，否则主服务器并不立刻对这个请求做出回应，而是等到客户端的租约期C1快结束的时候才做出回应（图2-10中的2），并更新主服务器租约期为M2。客户端在接到这个回应后认为该主服务器仍处于活跃状态，于是将租约期更新为C2并立刻发出新的KeepAlive请求（图2-10中的3）。同样的，主服务器可能不是立刻回应而是等待C2接近结束，但是在这个过程中主服务器出现故障停止使用。在等待了一段时间后C2到期，由于并没有收到主服务器的回应，系统向客户端发出一个危险（Jeopardy）事件，客户端清空并暂时停用自己的缓存，从而进入一个称为宽限期（Grace Period）的危险状态。这个宽限期默认是45秒。在宽限期内，客户端不会立刻断开其与服务器端的联系，而是不断地做探询。图2-10中新的主服务器很快被重新选出，当它接到客户端的第一个KeepAlive请求（图2-10中的4）时会拒绝（图2-10中的5），因为这个请求的纪元号（Epoch Number）错误。不同主服务器的纪元号不相同，客户端的每次请求都需要这个号来保证处理的请求是针对当前的主服务器。客户端在主服务器拒绝之后会使用新的纪元号来发送KeepAlive请求（图2-10中的6）。新的主服务器接受这个请求并立刻做出回应（图2-10中的7）。如果客户端接收到这个回应的时间仍处于宽限期
23 2 云计算
内，则系统会恢复到安全状态，租约期更新为C3。如果在宽限期未接到主服务器的相关回应，则客户端终止当前的会话。
2．主服务器出错
在客户端和主服务器端进行通信时可能会遇到主服务器故障，图2-10就出现了这种情况。正常情况下旧的主服务器出现故障后系统会很快地选举出新的主服务器，新选举的主服务器在完全运行前需要经历以下九个步骤[13]。
1）产生一个新的纪元号以便今后客户端通信时使用，这能保证当前的主服务器不必处理针对旧的主服务器的请求。
2）只处理主服务器位置相关的信息，不处理会话相关的信息。 3）构建处理会话和锁所需的内部数据结构。
4）允许客户端发送KeepAlive请求，不处理其他会话相关的信息。 5）向每个会话发送一个故障事件，促使所有的客户端清空缓存。 6）等待直到所有的会话都收到故障事件或会话终止。 7）开始允许执行所有的操作。
8）如果客户端使用了旧的句柄则需要为其重新构建新的句柄。 9）一定时间段后（1分钟），删除没有被打开过的临时文件夹。
如果这一过程在宽限期内顺利完成，则用户不会感觉到任何故障的发生，也就是说新旧主服务器的替换对于用户来说是透明的，用户感觉到的仅仅是一个延迟。使用宽限期的好处正是如此。
在系统实现时，Chubby还使用了一致性客户端缓存（Consistent Client-Side Caching）技术，这样做的目的是减少通信压力，降低通信频率。在客户端保存一个和单元上数据一致的本地缓存，这样需要时客户可以直接从缓存中取出数据而不用再和主服务器通信。当某个文件数据或者元数据需要修改时，主服务器首先将这个修改阻塞；然后通过查询主服务器自身维护的一个缓存表，向所有对修改的数据进行了缓存的客户端发送一个无效标志（Invalidation）；客户端收到这个无效标志后会返回一个确认（Acknowledge），主服务器在收到所有的确认后才解除阻塞并完成这次修改。这个过程的执行效率非常高，仅仅需要发送一次无效标志即可，因为主服务器对于没有返回确认的节点就直接认为其是未缓存的。
2.3.5 正确性与性能
1．一致性
前面提到过每个Chubby单元是由五个副本组成的，这五个副本中需要选举产生一个主服务器，这种选举本质上就是一个一致性问题。在实际的执行过程中，Chubby使用Paxos算法来解决这个问题。
主服务器产生后客户端的所有读写操作都是由主服务器来完成的。读操作很简单，客户直接从主服务器上读取所需数据即可，但是写操作就涉及数据一致性的问题了。为了保证客户的写操作能够同步到所有的服务器上，系统再次利用了Paxos算法。因此，可以看出Paxos算法在分布式一致性问题中的作用是巨大的。
2．安全性
Chubby采用的是ACL形式的安全保障措施。系统中有三种ACL名[13]，分别是写ACL名（Write ACL Name）、读ACL名（Read ACL Name）和变更ACL名（Change ACL
24 2
第2章 Google云计算原理 Name）。只要不被覆写，子节点都是直接继承父节点的ACL名。ACL同样被保存在文件中，它是节点元数据的一部分，用户在进行相关操作时首先需要通过ACL来获取相应的授权。图2-11是一个用户成功写文件所需经历的过程。
⑤成功写入 ②读取写 ACL名 CLOUD ④成功查到 允许写入 fun ?? ③查询 chinacloud ?? chinacloud ①请求写文件 图2-11 Chubby的ACL机制
用户chinacloud请求向文件CLOUD中写入内容。CLOUD首先读取自身的写ACL名是fun，接着在fun中查到了chinacloud这一行记录，于是返回信息允许chinacloud对文件进行写操作，此时chinacloud才被允许向CLOUD写入内容。其他的操作和写操作类似。
3．性能优化
为了满足系统的高可扩展性，Chubby目前已经采取了一些措施[13]。比如提高主服务器默认的租约期、使用协议转换服务将Chubby协议转换成较简单的协议。还有就是使用上面提到的客户端一致性缓存。除此之外，Google的工程师们还考虑使用代理（Proxy）和分区（Partition）技术，虽然目前这两种技术并没有实际使用，但是在设计的时候还是被包含进系统，不排除将来使用的可能。代理可以减少主服务器处理KeepAlive以及读请求带来的服务器负载，但是它并不能减少写操作带来的通信量。不过根据Google自己的数据统计表明，在所有的请求中，写请求仅占极少的一部分，几乎可以忽略不计。使用分区技术的话可以将一个单元的命名空间（Name Space）划分成N份。除了少量的跨分区通信外，大部分的分区都可以独自地处理服务请求。通过分区可以减少各个分区上的读写通信量，但不能减少KeepAlive请求的通信量。因此，如果需要的话，将代理和分区技术结合起来使用才可以明显提高系统同时处理的服务请求量。
2.4 分布式结构化数据表Bigtable
Bigtable是Google开发的基于GFS和Chubby的分布式存储系统。Google的很多数据，包括Web索引、卫星图像数据等在内的海量结构化和半结构化数据，都是存储在Bigtable中的。从实现上来看，Bigtable并没有什么全新的技术，但是如何选择合适的技术并将这些技术高效、巧妙地结合在一起恰恰是最大的难点。Google的工程师通过研究以及大量的实践，完美实现了相关技术的选择及融合。Bigtable在很多方面和数据库类似，但它并不是真正意义上的数据库。通过本节的学习，读者将会对Bigtable的数据模型、系统架构、实现以及它使用的一些数据库技术有一个全面的认识。
2.4.1 设计动机与目标
Google设计Bigtable的动机主要有如下三个方面。
1）需要存储的数据种类繁多。Google目前向公众开放的服务很多，需要处理的数据
25 2