翻译:Google大表(BigTable)
大表(Bigtable):结构化数据的分布存储系统

http://labs.google.com/papers/bigtable-osdi06.pdf
｛中是译者评论,程序除外｝

{本文的翻译可能有不准确的地方,详细资料请参考原文.}
摘要
bigtable是设计来分布存储大规模结构化数据的，从设计上它可以扩展到上２^50字节，分布存储在几千个普通服务器上．Ｇoogle的很多项目使用ＢＴ来存储数据，包括网页查询，google earth和google金融．这些应用程序对ＢＴ的要求各不相同：数据大小（从URL到网页到卫星图象）不同，反应速度不同（从后端的大批处理到实时数据服务）．对于不同的要求，ＢＴ都成功的提供了灵活高效的服务．在本文中，我们将描述ＢＴ的数据模型．这个数据模型让用户动态的控制数据的分布和结构．我们还将描述ＢＴ的设计和实现．

１．介绍

在过去两年半里，我们设计，实现并部署了ＢＴ．ＢＴ是用来分布存储和管理结构化数据的．ＢＴ的设计使它能够管理2^50 bytes(petabytes)数据，并可以部署到上千台机器上．ＢＴ完成了以下目标：应用广泛，可扩展，高性能和高可用性（high availability）. 包括google analytics, google finance, orkut, personalized search, writely和google earth在内的60多个项目都使用BT.这些应用对ＢＴ的要求各不相同，有的需要高吞吐量的批处理，有的需要快速反应给用户数据．它们使用的ＢＴ集群也各不相同，有的只有几台机器，有的有上千台，能够存储2^40字节(terabytes)数据．

ＢＴ在很多地方和数据库很类似：它使用了很多数据库的实现策略．并行数据库［１４］和内存数据库［１３］有可扩展性和高性能，但是ＢＴ的界面不同．ＢＴ不支持完全的关系数据模型；而是为客户提供了简单的数据模型，让客户来动态控制数据的分布和格式{就是只存储字串，格式由客户来解释}，并允许客户推断底层存储数据的局部性｛以提高访问速度｝．数据下标是行和列的名字，数据本身可以是任何字串．ＢＴ的数据是字串，没有解释｛类型等｝．客户会在把各种结构或者半结构化的数据串行化｛比如说日期串｝到数据中．通过仔细选择数据表示，客户可以控制数据的局部化．最后，可以使用ＢＴ模式来控制数据是放在内存里还是在硬盘上．｛就是说用模式，你可以把数据放在离应用最近的地方．毕竟程序在一个时间只用到一块数据．在体系结构里，就是：locality, locality, locality｝

第二节描述数据模型细节．第三节关于客户ＡＰＩ概述．第四节简介ＢＴ依赖的google框架．第五节描述ＢＴ的实现关键部分．第6节叙述提高ＢＴ性能的一些调整．第7节提供ＢＴ性能的数据．在第8节，我们提供ＢＴ的几个使用例子，第9节是经验教训．在第10节，我们列出相关研究．最后是我们的结论．

２．数据模型
ＢＴ是一个稀疏的，长期存储的｛存在硬盘上｝，多维度的，排序的映射表．这张表的索引是行关键字，列关键字和时间戳．每个值是一个不解释的字符数组．｛数据都是字符串，没类型，客户要解释就自力更生吧｝．

(row:string, column:string,time:int64)->string {能编程序的都能读懂，不翻译了}

//彼岸翻译的第二节

我们仔细查看过好些类似bigtable的系统之后定下了这个数据模型。举一个具体例子（它促使我们做出某些设计决定）， 比如我们想要存储大量网页及相关信息，以用于很多不同的项目；我们姑且叫它Webtable。在Webtable里，我们将用URL作为行关键字，用网页的某些属性作为列名，把网页内容存在contents:列中并用获取该网页的时间戳作为标识，如图一所示。



图一：一个存储Web网页的范例列表片断。行名是一个反向URL｛即com.cnn.www｝。contents列族｛原文用 family，译为族，详见列族｝存放网页内容，anchor列族存放引用该网页的锚链接文本。CNN的主页被Sports Illustrater｛即所谓SI，CNN的王牌体育节目｝和MY-look的主页引用，因此该行包含了名叫“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每个锚链接只有一个版本｛由时间戳标识，如t9，t8｝；而contents列则有三个版本，分别由时间 戳t3，t5，和t6标识。

行

表中的行关键字可以是任意字符串（目前支持最多64KB，多数情况下10－100字节足够了）。在一个行关键字下的每一个读写操作都是原子操作（不管读写这一行里多少个不同列），这是一个设计决定，这样在对同一行进行并发操作时，用户对于系统行为更容易理解和掌控。

Bigtable通过行关键字的字典序来维护数据。一张表可以动态划分成多个连续行。连续行在这里叫做“子表”｛tablet｝，是数据分布和负载均衡的单位。这样一来，读较少的连续行就比较有效率，通常只需要较少机器之间的通信即可。用户可以利用这个属性来选择行关键字，从而达到较好数据访问地域性｛locality｝。举例来说，在Webtable里，通过反转URL中主机名的方式，可以把同一个域名下的网页组织成连续行。具体来说，可以把maps.google.com/index.html中的数据存放在关键字com.google.maps/index.html下。按照相同或属性相近的域名来存放网页可以让基于主机和基于域名的分析更加有效。

列族

一组列关键字组成了“列族”，这是访问控制的基本单位。同一列族下存放的所有数据通常都是同一类型（同一列族下的数据可压缩在一起）。列族必须先创建，然后在能在其中的列关键字下存放数据；列族创建后，族中任何一个列关键字均可使用。我们希望，一张表中的不同列族不能太多（最多几百个），并且列族在运作中绝少改变。作为对比，一张表可以有无限列。

列关键字用如下语法命名：列族：限定词。 列族名必须是看得懂｛printable｝的字串，而限定词可以是任意字符串。比如，Webtable可以有个列族叫language，存放撰写网页的语言。我们在language列族中只用一个列关键字，用来存放每个网页的语言标识符。该表的另一个有用的列族是anchor；给列族的每一个列关键字代表一个锚链接，如图一所示。而这里的限定词则是引用该网页的站点名；表中一个表项存放的是链接文本。

访问控制，磁盘使用统计，内存使用统计，均可在列族这个层面进行。在Webtable举例中，我们可以用这些控制来管理不同应用：有的应用添加新的基本数据，有的读取基本数据并创建引申的列族，有的则只能浏览数据（甚至可能因为隐私权原因不能浏览所有数据）。

时间戳

Bigtable表中每一个表项都可以包含同一数据的多个版本，由时间戳来索引。Bigtable的时间戳是64位整型。可以由Bigtable来赋值，表示准确到毫秒的“实时”；或者由用户应用程序来赋值。需要避免冲突的应用程序必须自己产生具有唯一性的时间戳。不同版本的表项内容按时间戳倒序排列，即最新的排在前面。

为了简化对于不同数据版本的数据的管理，我们对每一个列族支持两个设定，以便于Bigtable对表项的版本自动进行垃圾清除。用户可以指明只保留表项的最后n个版本，或者只保留足够新的版本（比如，只保留最近7天的内容）。

在Webtable举例中，我们在contents:列中存放确切爬行一个网页的时间戳。如上所述的垃圾清除机制可以让我们只保留每个网页的最近三个版本。

//我开始翻译3,4节

3.API
BT的ＡＰＩ提供了建立和删除表和列族的函数．还提供了函数来修改集群，表和列族的元数据，比如说访问权限．

// 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);
图 2: 写入Bigtable.

在ＢＴ中，客户应用可以写或者删除值，从每个行中找值，或者遍历一个表中的数据子集．图2的Ｃ＋＋代码是使用RowMutation抽象表示来进行一系列的更新（为保证代码精简，没有包括无关的细节）．调用Apply函数，就对Ｗ