Bigtable:一个分布式的结构化数据存储系统
译者:alex
摘要
Bigtable是一个分布式的结构化数据存储系统,它被设计用来处理海量数据:通常是分布在数千台普通服
务器上的PB级的数据。Google的很多项目使用Bigtable存储数据,包括Web索引、Google Earth、
Google Finance。这些应用对Bigtable提出的要求差异非常大,无论是在数据量上(从URL到网页到卫星
图像)还是在响应速度上(从后端的批量处理到实时数据服务)。尽管应用需求差异很大,但是,针对
Google的这些产品,Bigtable还是成功的提供了一个灵活的、高性能的解决方案。本论文描述了Bigtable
提供的简单的数据模型,利用这个模型,用户可以动态的控制数据的分布和格式;我们还将描述Bigtable
的设计和实现。
1 介绍
在过去两年半时间里,我们设计、实现并部署了一个分布式的结构化数据存储系统 — 在Google,我们称
之为Bigtable。Bigtable的设计目的是可靠的处理PB级别的数据,并且能够部署到上千台机器上。
Bigtable已经实现了下面的几个目标:适用性广泛、可扩展、高性能和高可用性。Bigtable已经在超过60
个Google的产品和项目上得到了应用,包括Google Analytics、Google Finance、Orkut、
Personalized Search、Writely和Google Earth。这些产品对Bigtable提出了迥异的需求,有的需要高
吞吐量的批处理,有的则需要及时响应,快速返回数据给最终用户。它们使用的Bigtable集群的配置也有
很大的差异,有的集群只有几台服务器,而有的则需要上千台服务器、存储几百TB的数据。
在很多方面,Bigtable和数据库很类似:它使用了很多数据库的实现策略。并行数据库【14】和内存数据
库【13】已经具备可扩展性和高性能,但是Bigtable提供了一个和这些系统完全不同的接口。Bigtable不
支持完整的关系数据模型;与之相反,Bigtable为客户提供了简单的数据模型,利用这个模型,客户可以
动态控制数据的分布和格式(alex注:也就是对BigTable而言,数据是没有格式的,用数据库领域的术语
说,就是数据没有Schema,用户自己去定义Schema),用户也可以自己推测(alex注:reason
about)底层存储数据的位置相关性(alex注:位置相关性可以这样理解,比如树状结构,具有相同前缀的数
据的存放位置接近。在读取的时候,可以把这些数据一次读取出来)。数据的下标是行和列的名字,名字可
以是任意的字符串。Bigtable将存储的数据都视为字符串,但是Bigtable本身不去解析这些字符串,客户
程序通常会在把各种结构化或者半结构化的数据串行化到这些字符串里。通过仔细选择数据的模式,客户可
以控制数据的位置相关性。最后,可以通过BigTable的模式参数来控制数据是存放在内存中、还是硬盘
上。
第二节描述关于数据模型更多细节方面的东西;第三节概要介绍了客户端API;第四节简要介绍了
BigTable底层使用的Google的基础框架;第五节描述了BigTable实现的关键部分;第6节描述了我们为了
提高BigTable的性能采用的一些精细的调优方法;第7节提供了BigTable的性能数据;第8节讲述了几个
Google内部使用BigTable的例子;第9节是我们在设计和后期支持过程中得到一些经验和教训;最后,在
第10节列出我们的相关研究工作,第11节是我们的结论。
2 数据模型
Bigtable是一个稀疏的、分布式的、持久化存储的多维度排序Map(alex注:对于程序员来说,Map应该
不用翻译了吧。Map由key和value组成,后面我们直接使用key和value,不再另外翻译了)。Map的索
引是行关键字、列关键字以及时间戳;Map中的每个value都是一个未经解析的byte数组。
(row:string, column:string,time:int64)->string
我们在仔细分析了一个类似Bigtable的系统的种种潜在用途之后,决定使用这个数据模型。我们先举个具
体的例子,这个例子促使我们做了很多设计决策;假设我们想要存储海量的网页及相关信息,这些数据可以
用于很多不同的项目,我们姑且称这个特殊的表为Webtable。在Webtable里,我们使用URL作为行关键
字,使用网页的某些属性作为列名,网页的内容存在“contents:”列中,并用获取该网页的时间戳作为标
识(alex注:即按照获取时间不同,存储了多个版本的网页数据),如图一所示。
图一:一个存储Web网页的例子的表的片断。行名是一个反向URL。contents列族存放的是网页的内容,anchor列族存放引用该网页的锚链
接文本(alex注:如果不知道HTML的Anchor,请Google一把)。CNN的主页被Sports Illustrater和MY-look的主页引用,因此该行包含了
名为“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每个锚链接只有一个版本(alex注:注意时间戳标识了列的版本,t9和t8分别标
识了两个锚链接的版本);而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列族用来存放写网页的语言。我们在
language列族中只使用一个列关键字,用来存放每个网页的语言标识ID。Webtable中另一个有用的列族
是anchor;这个列族的每一个列关键字代表一个锚链接,如图一所示。Anchor列族的限定词是引用该网页
的站点名;Anchor列族每列的数据项存放的是链接文本。
访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的Webtable的例子中,上述的控制权限
能帮助我们管理不同类型的应用:我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并
创建继承的列族、一些应用则只允许浏览数据(甚至可能因为隐私的原因不能浏览所有数据)。
时间戳
在Bigtable中,表的每一个数据项都可以包含同一份数据的不同版本;不同版本的数据通过时间戳来索
引。Bigtable时间戳的类型是64位整型。Bigtable可以给时间戳赋值,用来表示精确到毫秒的“实时”时
间;用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突,那么它必须自己生成具有唯一性
的时间戳。数据项中,不同版本的数据按照时间戳倒序排序,即最新的数据排在最前面。
为了减轻多个版本数据的管理负担,我们对每一个列族配有两个设置参数,Bigtable通过这两个参数可以
对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后n个版本的数据,或者只保存“足够新”的版
本的数据(比如,只保存最近7天的内容写入的数据)。
在Webtable的举例里,contents:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾
收集机制可以让我们只保留最近三个版本的网页数据。
3 API
Bigtable提供了建立和删除表以及列族的API函数。Bigtable还提供了修改集群、表和列族的元数据的
API,比如修改访问权限。
// Open the table
Table *T = OpenOrDie(“/bigtable/web/webtable”);
// Write a new anchor and delete an old anchor
RowMutation r1(T, “com.cnn.www”);
r1.Set(“anchor:www.c-span.org”, “CNN”);
r1.Delete(“anchor:www.abc.com”);
Operation op;
Apply(&op, &r1);
Figure 2: Writing to Bigtable.
客户程序可以对Bigtable进行如下的操作:写入或者删除Bigtable中的值、从每个行中查找值、或者遍历
表中的一个数据子集。图2中的C++代码使用RowMutation抽象对象进行了一系列的更新操作。(为了保
持示例代码的简洁,我们忽略了一些细节相关代码)。调用Apply函数对Webtable进行了一个原子修改操
作:它为www.cnn.com增加了一个锚点,同时删除了另外一个锚点。
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily(“anchor”);
stream->SetReturnAllVersions();
scanner.Lookup(“com.cnn.www”);
for (; !stream->Done(); stream->Next()) {
printf(“%s %s %lld %s\n”,
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
Figure 3: Reading from Bigtable.
图3中的C++代码使用Scanner抽象对象遍历一个行内的所有锚点。客户程序可以遍历多个列族,有几种
方法可以对扫描输出的行、列和时间戳进行限制。例如,我们可以限制上面的扫描,让它只输出那些匹配正
则表达式*.cnn.com的锚点,或者那些时间戳在当前时间前10天的锚点。
Bigtable还支持一些其它的特性,利用这些特性,用户可以对数据进行更复杂的处理。首先,Bigtable支
持单行上的事务处理,利用这个功能,用户可以对存储在一个行关键字下的数据进行原子性的读-更新-写操
作。虽然Bigtable提供了一个允许用户跨行批量写入数据的接口,但是,Bigtable目前还不支持通用的跨
行事务处理。其次,Bigtable允许把数据项用做整数计数器。最后,Bigtable允许用户在服务器的地址空
间内执行脚本程序。脚本程序使用Google开发的Sawzall【28】数据处理语言。虽然目前我们基于的
Sawzall语言的API函数还不允许客户的脚本程序写入数据到Bigtable,但是它允许多种形式的数据转换、
基于任意表达式的数据过滤、以及使用多种操作符的进行数据汇总。
Bigtable可以和MapReduce【12】一起使用,MapReduce是Google开发的大规模并行计算框架。我们
已经开发了一些Wrapper类,通过使用这些Wrapper类,Bigtable可以作为MapReduce框架的输入和输
出。
4 BigTable构件
Bigtable是建立在其它的几个Google基础构件上的。BigTable使用Google的分布式文件系统(GFS)
【17】存储日志文件和数据文件。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【8】。一个Chubby服务包括
了5个活动的副本,其中的一个副本被选为Master,并且处理请求。只有在大多数副本都是正常运行的,
并且彼此之间能够互相通信的情况下,Chubby服务才是可用的。当有副本失效的时候,Chubby使用
Paxos算法【9,23】来保证副本的一致性。Chubby提供了一个名字空间,里面包括了目录和小文件。每个
目录或者文件可以当成一个锁,读写文件的操作都是原子的。Chubby客户程序库提供对Chubby文件的一
致性缓存。每个Chubby客户程序都维护一个与Chubby服务的会话。如果客户程序不能在租约到期的时间
内重新签订会话的租约,这个会话就过期失效了(alex注:又用到了lease。原文是:A client’s session
expires if it is unable to renew its session lease within the lease expiration time.)。当一个会话
失效时,它拥有的锁和打开的文件句柄都失效了。Chubby客户程序可以在文件和目录上注册回调函数,当
文件或目录改变、或者会话过期时,回调函数会通知客户程序。
Bigtable使用Chubby完成以下的几个任务:确保在任何给定的时间内最多只有一个活动的Master副本;
存储BigTable数据的自引导指令的位置(参考5.1节);查找Tablet服务器,以及在Tablet服务器失效时
进行善后(5.2节);存储BigTable的模式信息(每张表的列族信息);以及存储访问控制列表。如果
Chubby长时间无法访问,BigTable就会失效。最近我们在使用11个Chubby服务实例的14个BigTable集
群上测量了这个影响。由于Chubby不可用而导致BigTable中的部分数据不能访问的平均比率是0.0047%
(Chubby不能访问的原因可能是Chubby本身失效或者网络问题)。单个集群里,受Chubby失效影响最
大的百分比是0.0326%(alex注:有点莫名其妙,原文是: The percentage for the single cluster
that was most affected by Chubby unavailability was 0.0326%.)。
5 介绍
Bigtable包括了三个主要的组件:链接到客户程序中的库、一个Master服务器和多个Tablet服务器。针对
系统工作负载的变化情况,BigTable可以动态的向集群中添加(或者删除)Tablet服务器。
Master服务器主要负责以下工作:为Tablet服务器分配Tablets、检测新加入的或者过期失效的Table服务
器、对Tablet服务器进行负载均衡、以及对保存在GFS上的文件进行垃圾收集。除此之外,它还处理对模
式的相关修改操作,例如建立表和列族。
每个Tablet服务器都管理一个Tablet的集合(通常每个服务器有大约数十个至上千个Tablet)。每个
Tablet服务器负责处理它所加载的Tablet的读写操作,以及在Tablets过大时,对其进行分割。
和很多Single-Master类型的分布式存储系统【17.21】类似,客户端读取的数据都不经过Master服务
器:客户程序直接和Tablet服务器通信进行读写操作。由于BigTable的客户程序不必通过Master服务器来
获取Tablet的位置信息,因此,大多数客户程序甚至完全不需要和Master服务器通信。在实际应用中,
Master服务器的负载是很轻的。
一个BigTable集群存储了很多表,每个表包含了一个Tablet的集合,而每个Tablet包含了某个范围内的行
的所有相关数据。初始状态下,一个表只有一个Tablet。随着表中数据的增长,它被自动分割成多个
Tablet,缺省情况下,每个Tablet的尺寸大约是100MB到200MB。
5.1 Tablet的位置
我们使用一个三层的、类似B+树[10]的结构存储Tablet的位置信息(如图4)。
第一层是一个存储在Chubby中的文件,它包含了Root Tablet的位置信息。Root Tablet包含了一个特殊
的METADATA表里所有的Tablet的位置信息。METADATA表的每个Tablet包含了一个用户Tablet的集
合。Root Tablet实际上是METADATA表的第一个Tablet,只不过对它的处理比较特殊 — Root Tablet永
远不会被分割 — 这就保证了Tablet的位置信息存储结构不会超过三层。
在METADATA表里面,每个Tablet的位置信息都存放在一个行关键字下面,而这个行关键字是由Tablet所
在的表的标识符和Tablet的最后一行编码而成的。METADATA的每一行都存储了大约1KB的内存数据。在
一个大小适中的、容量限制为128MB的METADATA Tablet中,采用这种三层结构的存储模式,可以标识
2^34个Tablet的地址(如果每个Tablet存储128MB数据,那么一共可以存储2^61字节数据)。
客户程序使用的库会缓存Tablet的位置信息。如果客户程序没有缓存某个Tablet的地址信息,或者发现它
缓存的地址信息不正确,客户程序就在树状的存储结构中递归的查询Tablet位置信息;如果客户端缓存是
空的,那么寻址算法需要通过三次网络来回通信寻址,这其中包括了一次Chubby读操作;如果客户端缓存
的地址信息过期了,那么寻址算法可能需要最多6次网络来回通信才能更新数据,因为只有在缓存中没有查
到数据的时候才能发现数据过期(alex注:其中的三次通信发现缓存过期,另外三次更新缓存数据)(假设
METADATA的Tablet没有被频繁的移动)。尽管Tablet的地址信息是存放在内存里的,对它的操作不必访
问GFS文件系统,但是,通常我们会通过预取Tablet地址来进一步的减少访问的开销:每次需要从
METADATA表中读取一个Tablet的元数据的时候,它都会多读取几个Tablet的元数据。
在METADATA表中还存储了次级信息(alex注:secondary information),包括每个Tablet的事件日志
(例如,什么时候一个服务器开始为该Tablet提供服务)。这些信息有助于排查错误和性能分析。
5.2 Tablet分配
在任何一个时刻,一个Tablet只能分配给一个Tablet服务器。Master服务器记录了当前有哪些活跃的
Tablet服务器、哪些Tablet分配给了哪些Tablet服务器、哪些Tablet还没有被分配。当一个Tablet还没有
被分配、并且刚好有一个Tablet服务器有足够的空闲空间装载该Tablet时,Master服务器会给这个Tablet
服务器发送一个装载请求,把Tablet分配给这个服务器。
BigTable使用Chubby跟踪记录Tablet服务器的状态。当一个Tablet服务器启动时,它在Chubby的一个
指定目录下建立一个有唯一性名字的文件,并且获取该文件的独占锁。Master服务器实时监控着这个目录
(服务器目录),因此Master服务器能够知道有新的Tablet服务器加入了。如果Tablet服务器丢失了
Chubby上的独占锁 — 比如由于网络断开导致Tablet服务器和Chubby的会话丢失 — 它就停止对Tablet
提供服务。(Chubby提供了一种高效的机制,利用这种机制,Tablet服务器能够在不增加网络负担的情况
下知道它是否还持有锁)。只要文件还存在,Tablet服务器就会试图重新获得对该文件的独占锁;如果文
件不存在了,那么Tablet服务器就不能再提供服务了,它会自行退出(alex注:so it kills itself)。当
Tablet服务器终止时(比如,集群的管理系统将运行该Tablet服务器的主机从集群中移除),它会尝试释
放它持有的文件锁,这样一来,Master服务器就能尽快把Tablet分配到其它的Tablet服务器。
Master服务器负责检查一个Tablet服务器是否已经不再为它的Tablet提供服务了,并且要尽快重新分配它
加载的Tablet。Master服务器通过轮询Tablet服务器文件锁的状态来检测何时Tablet服务器不再为Tablet
提供服务。如果一个Tablet服务器报告它丢失了文件锁,或者Master服务器最近几次尝试和它通信都没有
得到响应,Master服务器就会尝试获取该Tablet服务器文件的独占锁;如果Master服务器成功获取了独占
锁,那么就说明Chubby是正常运行的,而Tablet服务器要么是宕机了、要么是不能和Chubby通信了,因
此,Master服务器就删除该Tablet服务器在Chubby上的服务器文件以确保它不再给Tablet提供服务。一
旦Tablet服务器在Chubby上的服务器文件被删除了,Master服务器就把之前分配给它的所有的Tablet放
入未分配的Tablet集合中。为了确保Bigtable集群在Master服务器和Chubby之间网络出现故障的时候仍
然可以使用,Master服务器在它的Chubby会话过期后主动退出。但是不管怎样,如同我们前面所描述
的,Master服务器的故障不会改变现有Tablet在Tablet服务器上的分配状态。
当集群管理系统启动了一个Master服务器之后,Master服务器首先要了解当前Tablet的分配状态,之后才
能够修改分配状态。Master服务器在启动的时候执行以下步骤:(1)Master服务器从Chubby获取一个
唯一的Master锁,用来阻止创建其它的Master服务器实例;(2)Master服务器扫描Chubby的服务器文
件锁存储目录,获取当前正在运行的服务器列表;(3)Master服务器和所有的正在运行的Tablet表服务
器通信,获取每个Tablet服务器上Tablet的分配信息;(4)Master服务器扫描METADATA表获取所有的
Tablet的集合。在扫描的过程中,当Master服务器发现了一个还没有分配的Tablet,Master服务器就将这
个Tablet加入未分配的Tablet集合等待合适的时机分配。
可能会遇到一种复杂的情况:在METADATA表的Tablet还没有被分配之前是不能够扫描它的。因此,在开
始扫描之前(步骤4),如果在第三步的扫描过程中发现Root Tablet还没有分配,Master服务器就把
Root Tablet加入到未分配的Tablet集合。这个附加操作确保了Root Tablet会被分配。由于Root Tablet
包括了所有METADATA的Tablet的名字,因此Master服务器扫描完Root Tablet以后,就得到了所有的
METADATA表的Tablet的名字了。
保存现有Tablet的集合只有在以下事件发生时才会改变:建立了一个新表或者删除了一个旧表、两个
Tablet被合并了、或者一个Tablet被分割成两个小的Tablet。Master服务器可以跟踪记录所有这些事件,
因为除了最后一个事件外的两个事件都是由它启动的。Tablet分割事件需要特殊处理,因为它是由Tablet
服务器启动。在分割操作完成之后,Tablet服务器通过在METADATA表中记录新的Tablet的信息来提交这
个操作;当分割操作提交之后,Tablet服务器会通知Master服务器。如果分割操作已提交的信息没有通知
到Master服务器(可能两个服务器中有一个宕机了),Master服务器在要求Tablet服务器装载已经被分割
的子表的时候会发现一个新的Tablet。通过对比METADATA表中Tablet的信息,Tablet服务器会发现
Master服务器要求其装载的Tablet并不完整,因此,Tablet服务器会重新向Master服务器发送通知信息。
5.3 Tablet服务
如图5所示,Tablet的持久化状态信息保存在GFS上。更新操作提交到REDO日志中(alex注:Updates
are committed to a commit log that stores redo records)。在这些更新操作中,最近提交的那些
存放在一个排序的缓存中,我们称这个缓存为memtable;较早的更新存放在一系列SSTable中。为了
复一个Tablet,Tablet服务器首先从METADATA表中读取它的元数据。Tablet的元数据包含了组成这个
Tablet的SSTable的列表,以及一系列的Redo Point(alex注:a set of redo points),这些Redo
Point指向可能含有该Tablet数据的已提交的日志记录。Tablet服务器把SSTable的索引读进内存,之后通
过重复Redo Point之后提交的更新来重建memtable。
当对Tablet服务器进行写操作时,Tablet服务器首先要检查这个操作格式是否正确、操作发起者是否有执
行这个操作的权限。权限验证的方法是通过从一个Chubby文件里读取出来的具有写权限的操作者列表来进
行验证(这个文件几乎一定会存放在Chubby客户缓存里)。成功的修改操作会记录在提交日志里。可以采
用批量提交方式(alex注:group commit)来提高包含大量小的修改操作的应用程序的吞吐量【13,
16】。当一个写操作提交后,写的内容插入到memtable里面。
当对Tablet服务器进行读操作时,Tablet服务器会作类似的完整性和权限检查。一个有效的读操作在一个
由一系列SSTable和memtable合并的视图里执行。由于SSTable和memtable是按字典排序的数据结
构,因此可以高效生成合并视图。
当进行Tablet的合并和分割时,正在进行的读写操作能够继续进行。
5.4 Compactions
(alex注:这个词简单,但是在这节里面难翻译的。应该是空间缩减的意思,但是似乎又不能完全概括
它在上下文中的意思,干脆,不翻译了)