没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
Bigtable:一个分布式的结构化数据存储系统
译者:alex [出处链接] 整理:cxw
摘要 .................................................................................................................................................1
1 介绍..............................................................................................................................................1
2 数据模型 ......................................................................................................................................1
行 .....................................................................................................................................................2
列族 .................................................................................................................................................3
时间戳..............................................................................................................................................3
3 API.................................................................................................................................................3
4 BIGTABLE 构件...............................................................................................................................5
5 介绍..............................................................................................................................................5
5.1 TABLET 的位置 .............................................................................................................................6
5.2 TABLET 分配 .................................................................................................................................7
5.3 TABLET 服务 .................................................................................................................................8
5.4 COMPACTIONS................................................................................................................................9
6 优化..............................................................................................................................................9
局部性群组....................................................................................................................................10
压缩 ...............................................................................................................................................10
通过缓存提高读操作的性能........................................................................................................10
BLOOM 过滤器 ................................................................................................................................11
COMMIT 日志的实现.......................................................................................................................11
TABLET 恢复提速.............................................................................................................................12
利用不变性....................................................................................................................................12
7 性能评估 ....................................................................................................................................12
单个 TABLET 服务器的性能 ............................................................................................................13
性能提升........................................................................................................................................14
8 实际应用 ....................................................................................................................................14
8.1 GOOGLE ANALYTICS.......................................................................................................................15
8.2 GOOGLE EARTH ............................................................................................................................16
8.3 个性化查询 .............................................................................................................................16
9 经验教训 ....................................................................................................................................17
10 相关工作 ..................................................................................................................................18
11 结论..........................................................................................................................................19
ACKNOWLEDGEMENTS ...................................................................................................................19
REFERENCES....................................................................................................................................19
1 / 22
摘要
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 数据模型
2 / 22
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 下。把相同的域中的网页存储在连续的区
域可以让基于主机和域名的分析更加有效。
3 / 22
列族
列关键字组成的集合叫做“列族“,列族是访问控制的基本单位。存放在同一列族下的所
有数据通常都属于同一个类型(我们可以把同一个列族下的数据压缩在一起)。列族在使用
之前必须先创建,然后才能在列族中任何的列关键字下存放数据;列族创建后,其中的任何
一个列关键字下都可以存放数据。根据我们的设计意图,一张表中的列族不能太多(最多几
百个),并且列族在运行期间很少改变。与之相对应的,一张表可以有无限多个列。
列关键字的命名语法如下:
列族:限定词
。 列族的名字必须是可打印的字符串,而限
定词的名字可以是任意的字符串。比如,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,比如修改访问权限。
4 / 22
// 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 可以作为
剩余21页未读,继续阅读
资源评论
lihuaidong1989
- 粉丝: 20
- 资源: 12
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功