B i g t a b l e结构化数据的分布式存储系统上Bigtable 结构化数据的分布式存储系统上转载请注明：作者phylips@bmy摘要Bigtable是设计用来管理那些可能达到很大大小(比如可能是存储在数千台服务器上的数PB的数据)的结构化数据的分布式存储系统。

Google的很多项目都将数据存储在Bigtable中，比如网页索引，google地球，google金融。

这些应用对Bigtable提出了很多不同的要求，无论是数据大小(从单纯的URL到包含图片附件的网页)还是延时需求。

尽管存在这些各种不同的需求，Bigtable成功地为google的所有这些产品提供了一个灵活的，高性能的解决方案。

在这篇论文中，我们将描述Bigtable所提供的允许客户端动态控制数据分布和格式的简单数据模型，此外还会描述Bigtable的设计和实现。

1.导引在过去的2年半时间里，我们设计,实现,部署了一个称为Bigtable的用来管理google的数据的分布式存储系统。

Bigtable的设计使它可以可靠地扩展到成PB的数据以及数千台机器上。

Bigtable成功的实现了这几个目标：广泛的适用性，可扩展性，高性能以及高可用性。

目前，Bigtable已经被包括Google分析，google金融，Orkut，个性化搜索，Writely和google地球在内的60多个google产品和项目所使用。

这些产品使用Bigtable用于处理各种不同的工作负载类型，从面向吞吐率的批处理任务到时延敏感的面向终端用户的数据服务。

这些产品所使用的Bigtable集群也跨越了广泛的配置规模，从几台机器到存储了几百TB数据的上千台服务器。

在很多方面，Bigtable都类似于数据库：它与数据库采用了很多相同的实现策略。

目前的并行数据库和主存数据库已经成功实现了可扩展性和高性能，但是Bigtable提供了与这些系统不同的接口。

Bigtable并不支持一个完整的关系数据模型，而是给用户提供了一个可以动态控制数据分布和格式的简单数据模型，允许用户将数据的局部性属性体现在底层的数据存储上。

数据使用可以是任意字符串的行列名称进行索引。

Bigtable将数据看做是未经解释的字符串，尽管用户经常将各种形式的结构化或半结构化的数据存储到这些字符串里。

用户可以通过在schema中的细心选择来控制数据的locality。

最后，Bigtable的schema参数还允许用户选择从磁盘还是内存获取数据。

第2节更加详细的描述了该数据模型。

第3节提供了关于用户API的概览。

第4节简要描述了Bigtable所依赖的底层软件。

第5节描述了Bigtable 的基本实现。

第6节描述了我们为提高Bigtable的性能使用的一些技巧。

第7节提供了一些对于Bigtable的性能测量数据。

第8节展示了几个Google内部的Bigtable的使用实例。

第9节讨论了我们在设计支持Bigtable所学到的一些经验教训。

最后第10节描述了相关工作，第11节进行了总结。

2.数据模型Bigtable是一个稀疏的，分布式的一致性多维有序map。

这个map是通过行关键字，列关键字以及时间戳进行索引的；map中的每个值都是一个未经解释的字节数组。

(row：string,column：string,time：int64)-string我们在对于这种类Bigtable系统的潜在使用场景进行了大量考察后，最终确定了这个数据模型。

举一个影响到我们的某些设计决策的具体例子，比如我们想保存一份可以被很多工程使用的一大集网页及其相关信息的拷贝。

我们把这个表称为webtable，在这个表中，我们可以使用URL作为行关键字，网页的各种信息作为列名称，将网页的内容作为表的内容存储：获取的时候还需要在列上加上时间戳，如图1所示。

表中的行关键字是大字符串(目前最大可以到64KB，尽管对于大多数用户来说最常用的是10-100字节)。

在一个行关键字下的数据读写是原子性的(无论这一行有多少个不同的列被读写)，这个设计使得用户在对相同行的并发更新出现时，更容易理解系统的行为。

Bigtable按照行关键字的字典序来维护数据。

行组{row range，将它翻译为行组，一个row range可能由多个行组成}是可以动态划分的。

每个行组叫做一个tablet，是数据存放以及负载平衡的单位。

这样，对于一个短的行组的读就会很有效，而且只需要与少数的机器进行通信。

客户端可以通过选择行关键字来利用这个属性，这样它们可以为数据访问得到好的局部性。

比如，在webtable里，相同域名的网页可以通过将URL中的域名反转而使他们放在连续的行里来组织到一块。

比如我们将网页/index.html的数据存放在关键字com.google.maps/index.html下。

将相同域名的网页存储在邻近位置可以使对主机或域名的分析更加有效。

列族不同的列关键字可以被分组到一个集合，我们把这样的一个集合称为一个列族，它是基本的访问控制单元。

存储在同一个列族的数据通常是相同类型的(我们将同一列族的数据压缩在一块)。

在数据能够存储到某个列族的列关键字下之前，必须首先要创建该列族。

我们假设在一个表中不同列族的数目应该比较小(最多数百个)，而且在操作过程中这些列族应该很少变化。

与之相比，一个表的列数目可以没有限制。

一个列关键字是使用如下的字符来命名的：family：qualifier。

列族名称必须是可打印的，但是qualifier可能是任意字符串。

比如webtable有一个列族是language，它存储了网页所使用的语言。

在language列族里，我们只使用了一个列关键字，里面存储了每个网页的language id。

该表的另一个列族是anchor，在该列族的每个列关键字代表一个单独的anchor，如图1所示。

Qualifier是站点的名称，里面的内容是链接文本。

访问控制以及磁盘的内存分配都是在列族级别进行的。

在webtable这个例子中，这些控制允许我们管理不同类型的应用：一些可能会添加新的基础数据，一些可能读取这些基础数据来创建新的列族，一些可能只需要查看现有数据(甚至可能因为隐私策略不需要查看所有现有数据)。

时间戳Bigtable里的每个cell可以包含相同数据的多个版本；这些不同的版本是通过时间戳索引的。

Bigtable的时间戳是一个64位的整数。

它们可以由Bigtable来赋值，在这种情况下它们以毫秒来代表时间。

也可以由客户端应用程序显式分配。

应用程序为了避免冲突必须能够自己生成唯一的时间戳。

一个cell的不同版本是按照时间戳降序排列，这样最近的版本可以被首先读到。

为了使不同版本的数据管理更简单，我们支持2个针对每个列族的设定来告诉Bigtable可以对cell中的数据版本进行自动的垃圾回收。

用户可以指定最近的哪几个版本需要保存，或者保存那些足够新的版本(比如只保存那些最近7天写的数据)。

在我们的webtable中，我们将爬取的网页的时间戳存储在内容里：这些时间说明了这些网页的不同版本分别是在何时被抓取的。

前面描述的垃圾回收机制，使我们只保存每个网页最新的三个版本。

3.API Bigtable API提供了一些函数用于表及列族的创建和删除。

它也提供了一些用于改变集群，表格及列族元数据的函数，比如访问控制权限。

客户端应用程序可以写或者删除Bigtable里的值，从行里查找值或者在表中的一个数据子集中进行迭代。

图2展示了使用RowMutation执行一系列更新的C++代码(为了保持简单省略了不相关的细节)。

Apply调用对webtable执行了一个原子性的变更操作：给增加一个anchor，然后删除另一个anchor。

图3展示的c++代码使用Scanner来在一个特殊行上的所有anchor进行迭代，用户可以在多个列族上进行迭代，存在几种机制来对扫描到的行，列，时间戳进行过滤。

比如我们可以限制只扫描那些与正则表达式"anchor：*"匹配的列，或者那些时间戳距离当前时间10天以内的anchor。

Bigtable提供了几种其他的feature允许用户使用更复杂的方式熟练控制数据。

首先，Bigtable支持单行事务，能够支持对存储在一个行关键字上的执行原子性的读写修改序列。

Bigtable当前并不支持跨行的事务，尽管它提供了一个多个用户的跨行写的接口。

其次，Bigtable允许用户将cell作为一个整数计数器来使用。

最后，Bigtable支持在服务器地址空间内执行一个客户端脚本。

这些脚本是使用google内部开发的数据处理语言sawzall编写的。

当前，我们基于Sawzall的API不允许客户端脚本向Bigtable中写回，但是它允许进行各种形式的数据转换，基于各种表达式的过滤以及大量的统计操作符。

Bigtable可以与MapReduce(google内部开发的一个运行大规模并行程序的框架)一起使用。

我们写了很多wrapper它允许将Bigtable作为输入源或者输出目标。

4.基础构件Bigtable是建立在google的其他几个设施之上。

Bigtable使用GFS来存储日志和数据文件。

Bigtable集群通常运行在一个运行着大量其他分布式应用的共享机器池上。

Bigtable依赖于一个集群管理系统进行job调度，共享机器上的资源管理，处理机器失败以及监控机器状态。

Bigtable内部采用Google SSTable文件格式来存储数据。

一个SSTable 提供了一个一致性的，有序的从key到value的不可变map，key和value都是任意的字节串。

操作通常是通过一个给定的key来查找相应的value，或者在一个给定的key range上迭代所有的key/value对。

每个SSTable内部包含一系列的块(通常每个块是64KB大小，但是该大小是可配置的)。

一个块索引(保存在SSTable的尾部)是用来定位block的，当SSTable打开时该索引会被加载到内存。

一次查找可以通过一次磁盘访问完成：首先通过在内存中的索引进行一次二分查找找到相应的块，然后从磁盘中读取该块。

另外，一个SSTable可以被完全映射到内存，这样就不需要我们接触磁盘就可以执行所有的查找和扫描。

{关于SSTable(StaticSearchTable)的具体格式可以参考YunTable开发日记(4)-BigTable的存储模型，中对HBASE的HFile的介绍} Bigtable依赖于一个高可用的一致性分布式锁服务Chubby。

Chubby由5个活动副本组成，其中的一个选为master处理请求。

当大部分的副本运行并且可以相互通信时，该服务就是活的。