Google_三大论文中文版资源-CSDN文库

Google_三大论文

需积分: 44 125 浏览量 2010-09-15 16:41:00 上传评论收藏 2.41MB PDF 举报

资源推荐

资源详情

资源评论

Alex && OpenCould

又一个 Ixiezi.com 博客

首页

About

Google论文

小道消息

未分类

请输入关键字...

Bigtable：一个分布式的结构化数据存储系统[中文版]

2010年3月27日 blademaster 没有评论

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

注：注意时间戳标识了列的版本，

和

分别标识了两个锚链接的版本）；

而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中的Ｃ++代码使用RowMutation抽象对象进行了一系列的更新操作。（为了

保持示例代码的简洁，我们忽略了一些细节相关代码）。调用Apply函数对Ｗebtable进行了一个原子修改

操作：它为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 aﬀected 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的位置

我们使用一个三层的、类似Ｂ+树[10]的结构存储Tablet的位置信息(如图4)。

第一层是一个存储在Chubby中的文件，它包含了Root Tablet的位置信息。Root Tablet包含了一个特殊

的METADATA表里所有的Tablet的位置信息。METADATA表的每个Tablet包含了一个用户Tablet的集合。

Root Tablet实际上是METADATA表的第一个Tablet，只不过对它的处理比较特殊 — Root Tablet永远不会

被分割 — 这就保证了Tablet的位置信息存储结构不会超过三层。

在METADATA表里面，每个Tablet的位置信息都存放在一个行关键字下面，而这个行关键字是由Tablet所

剩余59页未读，继续阅读

评论收藏

内容反馈

Apolloxiaoxuye

粉丝: 1
资源: 1

Google_三大论文中文版

Google 三大论文中文版

Google三大论文中文版

Google三大论文_中文版

Google_三大论文中文版2.pdf

Google文件系统(Google_File_System)论文中文版

The_Google_File_System_中文版论文

Google_云计算三大论文_中文版

google三大论文中文版

Google大数据三大论文中文版下载 Google论文MapReduce、GFS、Bigtable论文下载

Google_file_system-论文-中文版

Google三大论文WORD版

Google大数据必看三篇论文中文版

大数据Google的三大论文——中文版

Google三大论文

google云计算三大论文中文版

Google大数据三大论文中文版

Google云计算三大论文中文版

Google三大论文之Mapreduce中文版（转）

最新资源