英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
Bigtable：一个分布式的结构化数据存储系统
摘要
Bigtable 是一个分布式的结构化数据存储系统，它被设计用来处理海量数据：通常是
分布在数千台普通服务器上的 PB 级的数据。
Google 的很 多项目使用Bigtable 存储数据， 包括 Web 索引、Google Earth、Google
Finance。这些应用对 Bigtable 提出的要求差异非常大，无论是在数据量上（从 URL 到网页到卫星图像）还是在响应速度上（从后端的批量处理到 实时数据服务）。尽管应用需求差异很大，但是，针对 Google 的这些产品，Bigtable 还是成功的提供了一个灵活的、高性能的解决方案。本论文描述 了
Bigtable 提供的简单的数据模型，利用这个模型，用户可以动态的控制数据的分布和格式；我们还将描述 Bigtable 的设计和实现。
介绍
在过去两年半时间里，我们设计、实现并部署了一个分布式的结构化数据存储系统 — 在 Google，我们称之为 Bigtable。Bigtable
的设计目的是可靠的处理 PB 级别的数据， 并且能够部署到上千台机器上。Bigtable 已经实现了下面的几个目标：适用性广泛、可扩展、高性能和高可用性。Bigtable 已经在超过 60 个 Google 的产品和项目上得到了应用，包括 Google Analytics、Google
Finance、Orkut、PersonalizedSearch、
Writely 和 Google Earth。这些产品对
Bigtable 提出了迥异的需求，有的需要高吞吐量的批处理，有的则需要及时响应，快速返回数据给最终用户。它们使用的
Bigtable 集群的配置也有很大的差异，有的集群只有几台服务器，而有的则需要上千台服务器、存储几百 TB 的数据。
在很多方面，Bigtable 和数据库很类似：它使用了很多数据库的实现策略。并行数据库
【14】和内存数据库【13】已经具备可扩展性和高性能， 但是 Bigtable 提供了一个和这些系统完全不同的接口。Bigtable 不支持
完整的关系数据模型；与之相反，Bigtable 为客户提供了简单的数 据模型，利用这个模型，客户可以动态控制数据的分布和格式
（alex 注：也就是对 BigTable 而言，数据是没有格式的，用数据库领域的术语说，就是数据没有 Schema，用户自己去定义
Schema），用户也可以自己推测(alex 注：
reasonabout)底层存储数据的位置相关性
(alex 注： 位置相关性可以这样理解，比如 树状结构，具有相同前缀的数据的存放位置 接近。在读取的时候，可以把这些数据一次 读取出来)。数据的下标是行和列的名字， 名 字可以是任意的字符串。Bigtable 将存 储的数据都视为字符串，但是 Bigtable 本 身不去解析这些字符串，客户程序通常会在 把各种结构化或者半结 构化的数据串行化到这些字符串里。通过仔细选择数据的模式， 客户可以控制数据的位置相关性。最后，可
以通过 BigTable 的模式参数来控制数据是存放在 内存中、还是硬盘上。
第二节描述关于数据模型更多细节方面的东西；第三节概要介绍了客户端 API；第四节简要介绍了 BigTable 底层使用的 Google 的基础框架； 第五节描述了 BigTable 实现的关键部分；第 6 节描述了我们为了提高
BigTable 的性能采用的一些精细的调优方法；第 7 节提供了 BigTable 的性能数据； 第 8 节讲述了几个 Google 内部使用
BigTable 的例子；第 9 节是我们在设计和后期支持过程中得到一些经验和教训；最后， 在第 10 节列 出我们的相关研究工作，第 11 节是我们的结论。
数据模型
Bigtable 是一个稀疏的、分布式的、持久化存储的多维度排序 Map（alex 注：对于程序员来说，Map 应该不用翻译了吧。Map 由 key 和 value 组成，后面我们直接使用 key 和
value，不再另外翻译了）。Map 的索引是行关键字、列关键字以及时间戳；Map 中的每个 value 都是一个未经解析的 byte 数组。
(row:string,column:string,time:int64)
-gt;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:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾收集机制可以让我们只保留最近三个版本的网页数据。
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(amp;op, amp;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-gt;SetReturnAllVersions(); scanner.Lookup(“com.cnn.www”);
for (; !stream-gt;Done(); stream-gt;Next())
{
printf(“%s %s %lld %s ”,
scanner.RowName(), stream-gt;ColumnName(),
stream-gt;MicroTimestamp(), stream-gt;Value());
}
Figure3: Reading from Bigtable.
图 3 中的 C 代码使用 Scanner 抽象对象遍历一个行内的所有锚点。客户程序可以遍历 多个列族，有几种方法可以对扫描输出的行、列和时间戳进行 限制。例如，我们可以限 制上面的扫描，让它只输出那些匹配正则表
达式*.cnn.com 的锚点，或者那些时间戳在当前时间前 10 天的锚点。
Bigtable 还支持一些其它的特性，利用这些特性，用户可以对数据进行更复杂的处理。首先，Bigtable 支持单行上的事务处理，利用这个功 能，用户可以对存储在一个行关键字下的数据进行原子性的读-更新-写操 作。虽然 Bigtable 提供了一个允许用户跨行批量写入数据的接口，但 是，Bigtable 目前还不支持通用的跨行事务处理。其次，
Bigtable 允许把数据项用做整数计数器。最后，Bigtable 允许用户在服务器的地 址空间内执行脚本程序。脚本程序使用 Google 开发的 Sawzall【28】数据处理语言。虽然目前我们基于的 Sawzall 语言的 API 函数还不允许 客户的脚本程序写入数
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[409598]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
