Bigtable：结构化数据的分布式存储系统（一）

译自Bigtable_A Distributed Storage System for Structured Data

作者：Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C.Hsieh, Deborah A. Wallach Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E.Gruber

摘要

Bigtable是海量结构化数据的分布式存储系统，用于处理分布在几千台普通服务器上的PB级的数据。

Google的很多项目都使用Bigtable存储数据，包括Web索引、Google Earth以及GoogleFinance。不管是从数据量层面（从URL到网页到卫星图像）还是从响应速度层面（从后端的批量处理到实时数据服务），这些应用都对Bigtable提出了各种各样的要求。针对千差万别的需求，Bigtable成功提供了灵活的高性能解决方案。

本文介绍了Bigtable的简单数据模型。利用该模型，客户端可以动态地控制数据的分布和格式。本文还介绍了Bigtable的设计和实现。

1 引言

过去两年，我们设计、实现并部署了结构化数据的分布式存储系统Bigtable，用于处理分布在几千台机器上的PB级的数据。Bigtable具有适用性广、可扩展性强、高性能和高可用性的优点。

Bigtable已经用于Google的60多个产品和项目，包括GoogleAnalytics、Google Finance、Orkut、Personalized Search、Writely以及Google Earth。这些产品对Bigtable的要求各不相同：有的需要高吞吐量的批处理；有的则需要及时响应，快速将数据返回给终端用户。这些产品使用Bigtable 集群时的配置方式也有很大差异：有的集群只有几台服务器，而有的则需要上千台服务器，存储几百TB的数据。

Bigtable的很多实现策略都与数据库类似。并行数据库和内存数据库已经具备可扩展性和高性能，但Bigtable提供的接口与这些系统完全不同。Bigtable不支持完整的关系数据模型；相反，它提供了简单的数据模型。客户端可利用这个模型动态控制数据的分布和格式，也可以自己推测底层存储数据的位置。数据的下标是行和列的名称，名称可以是任意字符串。虽然客户端程序一般会对各种结构化或者半结构化的数据进行串行化处理，但Bigtable依然会将这些数据视为未解析的字符串。通过仔细选择数据模式，客户端可以控制数据的位置；然后通过BigTable的模式参数来决定将数据存放在内存中还是硬盘上。

第2节详细介绍了数据模型，第3节概述了客户端API。第4节简要介绍了Bigtable所依赖的底层Google基础框架。第5节介绍了Bigtable实现的关键部分，第6节介绍了改善Bigtable性能的调优方法。第7节介绍了Bigtable的性能。第8节介绍了Bigtable在Google的应用情况，第9节介绍了在Bigtable的设计和后期支持过程中得出的经验和教训。第10节介绍了相关研究工作，第11节为本文结论。

2 数据模型

Bigtable是一个稀疏的分布式持久化存储的多维度排序Map。Map的索引是行关键字、列关键字以及时间戳；Map中的每个value都是一个未经解析的byte数组。

(row:string,column:string, time:int64) → string

认真分析了一个类似于Bigtable系统的各种潜在功能后，我们决定使用这个数据模型。举个例子：假设我们需要存储海量网页及相关信息，这些数据可以用于很多不同的项目。我们暂且称该表为Webtable。在Webtable中，我们以URL为行关键字，以网页的某些属性为列名，网页内容放在“contents:”列中，并以时间戳标记该网页的获取时间，如图1所示。

图1：存储Web页面的样表的片段行名为反向URL contents列族为网页内容，anchor列族为引用该网页的锚链接文本。CNN的主页被SportsIllustrator和MY-look的主页引用，因此该行包含了名为“ anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每个锚链接只有一个版本；而contents 列则有三个版本，分别由时间戳t3、t5和t6标识。

行

表中的行关键字是任意字符串（目前支持最大64KB的字符串，但是大多数用户仅需要10-100个字节）。对同一个行关键字的读或者写操作都是原子的（不受读或者写这一行中的列数影响），这种设计便于用户理解程序在对同一个行进行并发更新操作时的行为。

Bigtable通过行关键字的字母顺序组织数据。表中的每个行都可以动态分区。每个分区叫做一个”Tablet”，Tablet是数据分布和负载均衡调整的最小单位。当操作只读取行中很少几列的数据时，效率很高，通常只需要机器间的少数几次通信即可完成。用户可以利用该特点，选择合适的行关键字，更加合理地安排数据位置。举例来说，在Webtable中，通过反转URL中主机名，可以把同一个域名下的网页聚集起来组织成连续的行。例如，我们可以把maps.google.com/index.html的数据存放在关键字com.google.maps/index.html下。把相同域中的网页存储在连续的区域能够提高基于主机和域名的分析效率。

列族

列关键字组成的集合叫做“列族“，列族是访问控制的基本单位。存放在同一列族下的所有数据通常属于同一类型（可以把同一列族下的数据压缩在一起）。必须先创建列族，然后才能在列族中的任何列关键字下存放数据；列族创建后，其中的任何一个列关键字下都可以存放数据。一张表中的列族不能太多（最多几百个），且列族在运行期间几乎不发生改变；但一张表中可以有无限多个列。

列关键字的命名语法为列族：限定词。列族的名称必须是可打印的字符串，而限定词的名字则可以是任意字符串。例如，Webtable中有个列族language，该列族用来存放撰写网页的语言。我们在language 列族中只使用一个列关键字，用来存放每个网页的语言标识 ID。在Webtable中，另一个有用的列族是anchor；该列族的每一个列关键字代表一个锚链接，如图1所示。Anchor列族的限定词为引用该网页的站点名，每列的数据项存放的是链接文本。

访问控制、磁盘和内存的使用统计都是在列族层面进行的。在Webtable中，控制权限能够实现对不同类型应用的管理：有些应用可以添加新的基本数据，有些应用可以读取基本数据并创建继承的列族，有些应用则只允许浏览数据（甚至可能因为隐私的原因不能浏览所有数据）。

时间戳

在Bigtable中，表的每一个数据项都可以包含同一份数据的不同版本；不同版本的数据通过时间戳来索引。Bigtable时间戳的类型是64位整型。Bigtable可以给时间戳赋值，时间可以精确到毫秒；用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突，则必须生成唯一的时间戳。在数据项中，不同版本的数据按照时间戳倒序排序，即最新的数据排在最前面。

为了便于管理不同版本的数据，我们对每一个列族配置了两个设置参数，Bigtable可以通过这两个参数自动对废弃版本的数据进行垃圾收集。客户端程序可以指定只保存最后n个版本的数据，也可以指定只保存最近版本的数据（比如，只保存最近7天写入的数据）。

在Webtable中，contents:列存储的时间戳信息是网络爬虫实际抓取页面的时间。前文提及的垃圾收集机制支持仅保留最新三个版本的网页数据。

3 API

Bigtable API提供了创建和删除表以及列族的函数。Bigtable还提供了修改集群、表和列族元数据（例如访问权限）的函数。

客户端程序可以对Bigtable进行如下的操作：写入或删除Bigtable中的值、从每个行中查找值、或者遍 历表中的一个数据子集。图2中，C++代码使用RowMutation抽象对象进行了一系列的更新操作。（为了保证示例代码简洁，我们省略了一些细节相关代码。）调用Apply函数对Webtable 进行了一次原子修改操作：为www.cnn.com增加了一个锚点，同时删除了另外一个锚点。

图2：向Bigtable写入值

图3中的C++代码使用Scanner抽象对象遍历一个行内的所有锚点。客户端程序可以遍历多个列族，可以通过多种方法对扫描输出的行、列和时间戳进行限制。例如，我们可以限制上述扫描只输出匹配正则表达式*.cnn.com的锚点，或者时间戳在当前时间10天内的锚点。

图3：从Bigtable中读值

Bigtable还支持更加复杂的数据处理。首先，Bigtable支持单行上的事务处理。利用这个功能，用户可以对存储在一个行关键字下的数据进行原子读-更新-写操作。Bigtable虽然提供了跨行批量写入数据的接口，但目前还不支持通用的跨行事务处理。其次，Bigtable允许把数据项用做整数计数器。最后，Bigtable允许在服务器的地址空间内执行客户端脚本程序。脚本程序使用Google开发的Sawzall数据处理语言。虽然基于Sawzall语言的API目前不支持客户端脚本程序向Bigtable写入数据，但它支持多种形式的数据转换、基于任意表达式的数据过滤以及基于多种操作符的数据汇总。

Bigtable可以和MapReduce一起使用。MapReduce是Google开发的大规模并行计算框架。我们已经开发了一些Wrapper类。通过这些类，Bigtable可以作为MapReduce框架的输入和输出。

4 构件

Bigtable基于Google的其他几个基础构件。Bigtable使用Google的分布式文件系统（GFS）存储日志文件和数据文件。Bigtable集群一般运行在共享的机器池中，池中的机器还会运行其它各种分布式应用程序。Bigtable的进程往往需要和其它应用的进程共享机器。Bigtable 依赖集群管理系统调度任务、管理共享的机器上的资源、处理机器故障、监视机器状态。

Bigtable内部存储数据文件是Google SSTable格式的。SSTable是有序的持久化Map结构，不可更改；Map是key-value映射的数据结构，key和value的值都是任意的Byte串。SSTable支持查询与key值相关的value，或遍历某个key值范围内的所有key-value对。

从内部结构来看，SSTable是一系列的数据块（每个块的大小可以自由配置，一般是64KB）。SSTable使用块索引（存储在SSTable的最后）来定位数据块；打开SSTable时，索引被加载到内存。每次查找都可以通过一次磁盘搜索完成：首先使用二分查找法在内存中的索引里找到数据块的位置，然后再从硬盘读取相应的数据块；也可以把整个SSTable都放在内存中，这样就不必访问硬盘了。

Bigtable还依赖高可用的持久化分布式锁服务组件Chubby。一个Chubby服务包含5个活动副本，其中一个副本为Master，负责处理请求。只有当大多数副本处于正常运行状态且彼此之间能够互相通信时，Chubby服务才是可用的。出现副本失效的情况时，Chubby使用Paxos算法来保证副本的一致性。Chubby的命名空间包括目录和小文件。每个目录或者文件可以当做一个锁，读写文件的操作都是原子的。Chubby客户端程序库提供Chubby文件的一致性缓存。每个Chubby客户端程序都维护一个与Chubby服务的会话。如果客户端程序不能在租约到期时重新签订会话租约，会话便会过期失效。会话失效后，其锁和打开的文件句柄都会失效。Chubby客户端程序可以在文件和目录上注册回调函数，当文件或目录改变、或者会话过期时，回调函数会通知客户端程序。

Bigtable使用Chubby处理以下几类任务：

• 确保最多只有一个活动的Master副本；
• 存储Bigtable数据的自引导指令的位置（见第5.1节）；
• 查找Tablet服务器，负责处理失效的Tablet服务器（见第5.2节）；
• 存储Bigtable的模式信息（每张表的列族信息）；
• 存储访问控制列表。

如果Chubby长时间无法访问，Bigtable就会失效。最近我们在使用了11个Chubby服务实例的14个BigTable集群上测量了这种影响。由于Chubby不可用导致BigTable中的部分数据不能访问的平均几率是0.0047%。（不能访问的原因可能是Chubby本身失效或者网络问题）。单个集群受Chubby失效影响的最大几率是0.0326%。

参考资料

1. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C.Hsieh, Deborah A. Wallach Mike Burrows, Tushar Chandra, Andrew Fikes and Robert E.Gruber. Bigtable_A Distributed Storage System for Structured Data

2. Yan Wei. Google Bigtable中文版