云计算
类型也非常多。包括URL、网页内容、用户的个性化设置在内的数据都是Google需要经常处理的。
2）海量的服务请求。Google运行着目前世界上最繁忙的系统，它每时每刻处理的客户服务请求数量是普通的系统根本无法承受的。
3）商用数据库无法满足Google的需求。一方面现有商用数据库的设计着眼点在于其通用性，面对Google的苛刻服务要求根本无法满足，而且在数量庞大的服务器上根本无法成功部署普通的商用数据库。另一方面对于底层系统的完全掌控会给后期的系统维护、升级带来极大的便利。
在仔细考察了Google的日常需求后，Bigtable开发团队确定了Bigtable设计所需达到的如下几个基本目标。
1）广泛的适用性。Bigtable是为了满足一系列Google产品而并非特定产品的存储要求。
2）很强的可扩展性。根据需要随时可以加入或撤销服务器。
3）高可用性。对于客户来说，有时候即使短暂的服务中断也是不能忍受的。Bigtable设计的重要目标之一就是确保几乎所有的情况下系统都可用。
4）简单性。底层系统的简单性既可以减少系统出错的概率，也为上层应用的开发带来便利。
在目标确定之后，Google开发者就在现有的数据库技术中进行了大规模的筛选，希望各种技术之间能够扬长避短，巧妙地结合起来。最终实现的系统也确实达到了原定的目标。下面就开始详细讲解Bigtable。
2.4.2 数据模型
Bigtable是一个分布式多维映射表，表中的数据是通过一个行关键字（Row Key）、一个列关键字（Column Key）以及一个时间戳（Time Stamp）进行索引的。Bigtable对存储在其中的数据不做任何解析，一律看做字符串，具体数据结构的实现需要用户自行处理。Bigtable的存储逻辑可以表示为：
(row:string, column:string, time:int64)→string
Bigtable数据的存储格式如图2-12所示[8]。
“内容：” “锚点：cnnsi.com” “锚点：my..look.ca” “com.cnn.www” “…” t3 “…” t5 “…” t6 “CNN” t9 “CNN.com” t8
图2-12 Bigtable数据模型
1．行
Bigtable的行关键字可以是任意的字符串，但是大小不能够超过64KB。Bigtable和传统的关系型数据库有很大不同，它不支持一般意义上的事务，但能保证对于行的读写操作具有原子性（Atomic）。表中数据都是根据行关键字进行排序的，排序使用的是词典序。
26 2
第2章 Google云计算原理 图2-12是Bigtable数据模型的一个典型实例，其中com.cn.www就是一个行关键字。不直接存储网页地址而将其倒排是Bigtable的一个巧妙设计。这样做至少会带来以下两个好处。
1）同一地址域的网页会被存储在表中的连续位置，有利于用户查找和分析。 2）倒排便于数据压缩，可以大幅提高压缩率。
单个的大表由于规模问题不利于数据的处理，因此Bigtable将一个表分成了很多子表（Tablet），每个子表包含多个行。子表是Bigtable中数据划分和负载均衡的基本单位。有关子表的内容会在稍后详细讲解。
2．列
Bigtable并不是简单地存储所有的列关键字，而是将其组织成所谓的列族（Column Family），每个族中的数据都属于同一个类型，并且同族的数据会被压缩在一起保存。引入了列族的概念之后，列关键字就采用下述的语法规则来定义：
族名：限定词（family：qualifier）
族名必须有意义，限定词则可以任意选定。在图2-12中，内容（Contents）、锚点（Anchor，就是HTML中的链接）都是不同的族。而cnnsi.com和my.look.ca则是锚点族中不同的限定词。通过这种方式组织的数据结构清晰明了，含义也很清楚。族同时也是Bigtable中访问控制（Access Control）的基本单元，也就是说访问权限的设置是在族这一级别上进行的。
3．时间戳
Google的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分。图2-12中内容列的t3、t5和t6表明其中保存了在t3、t5和t6这三个时间获取的网页。Bigtable中的时间戳是64位整型数，具体的赋值方式可以采取系统默认的方式，也可以用户自行定义。
为了简化不同版本的数据管理，Bigtable目前提供了两种设置：一种是保留最近的N个不同版本，图2-12中数据模型采取的就是这种方法，它保存最新的三个版本数据。另一种就是保留限定时间内的所有不同版本，比如可以保存最近10天的所有不同版本数据。失效的版本将会由Bigtable的垃圾回收机制自动处理。
2.4.3 系统架构
Bigtable是在Google的另外三个云计算组件基础之上构建的，其基本架构如图2-13所示[11]。
图中WorkQueue是一个分布式的任务调度器，它主要被用来处理分布式系统队列分组和任务调度，关于其实现Google并没有公开。在前面已经讲过，GFS[9]是Google的分布式文件系统，在Bigtable中GFS主要用来存储子表数据以及一些日志文件。Bigtable还需要一个锁服务的支持，Bigtable选用了Google自己开发的分布式锁服务Chubby。在Bigtable中Chubby主要有以下几个作用[10]。
1）选取并保证同一时间内只有一个主服务器（Master Server）。 2）获取子表的位置信息。
3）保存Bigtable的模式信息及访问控制列表。
27 2 云计算
Bigtable客户端 Bigtable客户端 程序库 () 执行Open 操作 Bigtable子表服务器 处理数据 Bigtable主服务器 执行元数据操作及 负载平衡 Bigtable子表服务器 处理数据 Bigtable子表服务器 处理数据 Google WorkQueue 负责故障处理及监控 GFS 保存子表数据及日志 Chubby 负责元数据存储及 主服务器的选择
图2-13 Bigtable基本架构
另外在Bigtable的实际执行过程中，Google的MapReduce和Sawzall也被使用来改善其性能，不过需要注意的是这两个组件并不是实现Bigtable所必需的。
Bigtable主要由三个部分组成：客户端程序库（Client Library）、一个主服务器（Master Server）和多个子表服务器（Tablet Server），这三个部分在图2-13中都有相应的表示。从图2-13中可以看出，客户需要访问Bigtable服务时首先要利用其库函数执行Open()操作来打开一个锁（实际上就是获取了文件目录），锁打开以后客户端就可以和子表服务器进行通信了。和许多具有单个主节点的分布式系统一样，客户端主要与子表服务器通信，几乎不和主服务器进行通信，这使得主服务器的负载大大降低。主服务主要进行一些元数据的操作以及子表服务器之间的负载调度问题，实际的数据是存储在子表服务器上的。客户程序库的概念比较简单，这里不做讲解，下面对主服务器和子表服务器展开讲解。
2.4.4 主服务器
主服务的主要作用如图2-14所示。
新子表分配 子表服务器 状态监控 主服务器 子服务器之间 的负载均衡 图2-14 主服务器的主要作用
28 2
第2章 Google云计算原理 当一个新的子表产生时，主服务器通过一个加载命令将其分配给一个空间足够的子表服务器。创建新表、表合并以及较大子表的分裂都会产生一个或多个新子表。对于前面两种，主服务器会自动检测到，因为这两个操作是由主服务器发起的，而较大子表的分裂是由子服务发起并完成的，所以主服务器并不能自动检测到，因此在分割完成之后子服务器需要向主服务发出一个通知。由于系统设计之初就要求能达到良好的扩展性，所以主服务器必须对子表服务器的状态进行监控，以便及时检测到服务器的加入或撤销。Bigtable中主服务器对子表服务器的监控是通过Chubby来完成的，子表服务器在初始化时都会从Chubby中得到一个独占锁。通过这种方式所有的子表服务器基本信息被保存在Chubby中一个称为服务器目录（Server Directory）的特殊目录之中。主服务器通过检测这个目录就可以随时获取最新的子表服务器信息，包括目前活跃的子表服务器，以及每个子表服务器上现已分配的子表。对于每个具体的子表服务器，主服务器会定期向其询问独占锁的状态。如果子表服务器的锁丢失或没有回应，则此时可能有两种情况，要么是Chubby出现了问题（虽然这种概率很小，但的确存在，Google自己也做过相关测试），要么是子表服务器自身出现了问题。对此主服务器首先自己尝试获取这个独占锁，如果失败说明Chubby服务出现问题，需等待Chubby服务的恢复。如果成功则说明Chubby服务良好而子表服务器本身出现了问题。这种情况下主服务器会中止这个子表服务器并将其上的子表全部移至其他子表服务器。当在状态监测时发现某个子表服务器上负载过重时，主服务器会自动对其进行负载均衡操作。
基于系统出现故障是一种常态的设计理念（Google几乎所有的产品都是基于这个设计理念），每个主服务器被设定了一个会话时间的限制。当某个主服务器到时退出后，管理系统就会指定一个新的主服务器，这个主服务器的启动需要经历以下四个步骤[8]。
1）从Chubby中获取一个独占锁，确保同一时间只有一个主服务器。 2）扫描服务器目录，发现目前活跃的子表服务器。
3）与所有的活跃子表服务器取得联系以便了解所有子表的分配情况。 4）通过扫描元数据表（Metadata Table），发现未分配的子表并将其分配到合适的子表服务器。如果元数据表未分配，则首先需要将根子表（Root Tablet）加入未分配的子表中。由于根子表保存了其他所有元数据子表的信息，确保了扫描能够发现所有未分配的 子表。
在成功完成以上四个步骤后主服务器就可以正常运行了。
2.4.5 子表服务器
Bigtable中实际的数据都是以子表的形式保存在子表服务器上的，客户一般也只和子表服务器进行通信，所以子表以及子表服务器是我们重点讲解的概念。子表服务器上的操作主要涉及子表的定位、分配以及子表数据的最终存储问题。其中子表分配在前面已经有了详细介绍，这里略过不讲。在讲解其他问题之前我们首先介绍一下SSTable的概念以及子表的基本结构。
1．SSTable及子表基本结构
SSTable是Google为Bigtable设计的内部数据存储格式。所有的SSTable文件都是存储在GFS上的，用户可以通过键来查询相应的值，图2-15是SSTable格式的基本示意图。
29 2 云计算
SSTable 64KB 块 ?? 64KB 块 索引
图2-15 SSTable结构
SSTable中的数据被划分成一个个的块（Block），每个块的大小是可以设置的，一般来说设置为64KB。在SSTable的结尾有一个索引（Index），这个索引保存了SSTable中块的位置信息，在SSTable打开时这个索引会被加载进内存，这样用户在查找某个块时首先在内存中查找块的位置信息，然后在硬盘上直接找到这个块，这种查找方法速度非常快。由于每个SSTable一般都不是很大，用户还可以选择将其整体加载进内存，这样查找起来会更快。
从概念上来讲子表是表中一系列行的集合，它在系统中的实际组成如图2-16所示。
日志 SSTable 64KB 块 ... 64KB 块 索引 ... 64KB 块 ... 64KB 块 索引 SSTable
图2-16 子表实际组成
每个子表都是由多个SSTable以及日志（Log）文件构成的。有一点需要注意，那就是不同子表的SSTable可以共享，也就是说某些SSTable会参与多个子表的构成，而由子表构成的表则不存在子表重叠的现象。Bigtable中的日志文件是一种共享日志，也就是说系统并不是对子表服务器上每个子表都单独地建立一个日志文件，每个子表服务器上仅保存一个日志文件，某个子表日志只是这个共享日志的一个片段。这样会节省大量的空间，但在恢复时却有一定的难度，因为不同的子表可能会被分配到不同的子表服务器上，一般情况下每个子表服务器都需要读取整个共享日志来获取其对应的子表日志。Google为了避免这种情况出现，对日志做了一些改进。Bigtable规定将日志的内容按照键值进行排序，这样不同的子表服务器都可以连续读取日志文件了。一般来说每个子表的大小在100MB到200MB之间。每个子表服务器上保存的子表数量可以从几十到上千不等，通常情况下是100个左右。
2．子表地址
子表地址的查询是经常碰到的操作。在Bigtable系统的内部采用的是一种类似B+树的三层查询体系。子表地址结构如图2-17所示[8]。
所有的子表地址都被记录在元数据表中，元数据表也是由一个个的元数据子表（Metadata tablet）组成的。根子表是元数据表中一个比较特殊的子表，它既是元数据表的第一条记录，也包含了其他元数据子表的地址，同时Chubby中的一个文件也存储了这个根子表的信息。这样在查询时，首先从Chubby中提取这个根子表的地址，进而读取
30 3