英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料

Bigtable：一个分布式的结构化数据存储系统

1介绍

在过去两年半时间里，我们在谷歌设计、实现并部署了一个分布式的结构化数据存储系统，该系统被称之为Bigtable。Bigtable的设计目的是可靠的处理PB级别的数据，并且能够部署到上千台机器上。Bigtable已经实现了下面的几个目标：适用性广泛、可扩展、高性能和高可用性。Bigtable已经在超过60个Google的产品和项目上得到了应用，这些产品对Bigtable提出了迥异的需求，有的需要高吞吐量的批处理，有的则需要及时响应，快速返回数据给最终用户。它们使用的Bigtable集群的配置也有很大的差异。

在很多方面，Bigtable和数据库很类似：它使用了很多数据库的实现策略。并行数据库【14】和内存数据库【13】已经具备可扩展性和高性能，但是Bigtable提供了一个和这些系统完全不同的接口。Bigtable不支持完整的关系数据模型；与之相反，Bigtable为客户提供了简单的数据模型，利用这个模型，客户可以动态控制数据的分布和格式，用户也可以自己推测底层存储数据的位置相关性。最后，可以通过Bigtable的模式参数来控制数据是存放在内存中，还是硬盘上。

2数据模型

Bigtable是一个稀疏的、分布式的、持久化存储的多维度排序Map。Map的索引是行关键字、列关键字以及时间戳；Map中的每个value都是一个未经解析的byte数组。

我们在仔细分析了一个类似Bigtable的系统的种种潜在用途之后，决定使用这个数据模型。我们先举个具体的例子，这个例子促使我们做了很多设计决策。假设我们想要存储海量的网页及相关信息，这些数据可以用于很多不同的项目，我们姑且称这个特殊的表为Webtable。在Webtable里，我们使用URL作为行关键字，使用网页的某些属性作为列名，网页的内容存在“contents:”列中，并用获取该网页的时间戳作为标识，如图一所示。

行

表中的行关键字可以是任意的字符串（目前支持最大64KB的字符串，但是对大多数用户，10-100个字节就足够了）。对同一个行关键字的读或者写操作都是原子的（不管读或者写这一行里多少个不同列），这个设计决策能够使用户很容易的理解程序在对同一个行进行并发更新操作时的行为。

列族

列关键字组成的集合叫做“列族”，列族是访问控制的基本单位。存放在同一列族下的所有数据通常都属于同一个类型（我们可以把同一个列族下的数据压缩在一起）。列族在使用之前必须先创建，然后才能在列族中任何的列关键字下存放数据；列族创建后，其中的任何一个列关键字下都可以存放数据。根据我们的设计意图，一张表中的列族不能太多，并且列族在运行期间很少改变。与之相对应的，一张表可以有无限多个列。

访问控制、磁盘和内存的使用统计都是在列族层面进行的。在我们的Webtable的例子中，上述的控制权限能帮助我们管理不同类型的应用：我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并创建继承的列族、一些应用则只允许浏览数据（甚至可能因为隐私的原因不能浏览所有数据）。

时间戳

在Bigtable中，表的每一个数据项都可以包含同一份数据的不同版本；不同版本的数据通过时间戳来索引。Bigtable时间戳的类型是64位整型。Bigtable可以给时间戳赋值，用来表示精确到毫秒的“实时”时间；用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突，那么它必须自己生成具有唯一性的时间戳。数据项中，不同版本的数据按照时间戳倒序排序，即最新的数据排在最前面。

为了减轻多个版本数据的管理负担，我们对每一个列族配有两个设置参数，Bigtable通过这两个参数可以对废弃版本的数据自动进行垃圾收集。用户可以指定只保存最后n个版本的数据，或者只保存“足够新”的版本的数据。

在Webtable的举例里，contents:列存储的时间戳信息是网络爬虫抓取一个页面的时间。上面提及的垃圾收集机制可以让我们只保留最近三个版本的网页数据。

3 API

Bigtable提供了建立和删除表以及列族的API函数。Bigtable还提供了修改集群、表和列族的元数据的API，比如修改访问权限。

图3中的C 代码使用Scanner抽象对象遍历一个行内的所有锚点。客户程序可以遍历多个列族，有几种方法可以对扫描输出的行、列和时间戳进行限制。例如，我们可以限制上面的扫描，让它只输出那些匹配正则表达式*.cnn.com的锚点，或者那些时间戳在当前时间前10天的锚点。

Bigtable可以和MapReduce【12】一起使用，MapReduce是Google开发的大规模并行计算框架。我们已经开发了一些Wrapper类，通过使用这些Wrapper类，Bigtable可以作为MapReduce框架的输入和输出。

4 Bigtable构件

Bigtable是建立在其它的几个Google基础构件上的。Bigtable使用Google的分布式文件系统(GFS)【17】存储日志文件和数据文件。Bigtable集群通常运行在一个共享的机器池中，池中的机器还会运行其它的各种各样的分布式应用程序，Bigtable的进程经常要和其它应用的进程共享机器。Bigtable依赖集群管理系统来调度任务、管理共享的机器上的资源、处理机器的故障、以及监视机器的状态。

5介绍

Bigtable包括了三个主要的组件：链接到客户程序中的库、一个Master服务器和多个Tablet服务器。针对系统工作负载的变化情况，Bigtable可以动态的向集群中添加（或者删除）Tablet服务器。

Master服务器主要负责以下工作：为Tablet服务器分配Tablets、检测新加入的或者过期失效的Table服务器、对Tablet服务器进行负载均衡、以及对保存在GFS上的文件进行垃圾收集。除此之外，它还处理对模式的相关修改操作，例如建立表和列族。

每个Tablet服务器都管理一个Tablet的集合（通常每个服务器有大约数十个至上千个Tablet）。每个Tablet服务器负责处理它所加载的Tablet的读写操作，以及在Tablets过大时，对其进行分割。

5.1 Tablet的位置

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

第一层是一个存储在Chubby中的文件，它包含了root tablet的位置信息。root tablet包含了一个特殊的METADATA表里所有的Tablet的位置信息。METADATA表的每个Tablet包含了一个用户Tablet的集合。root tablet实际上是METADATA表的第一个Tablet，只不过对它的处理比较特殊—root tablet永远不会被分割—这就保证了Tablet的位置信息存储结构不会超过三层。

5.2 Tablet分配

在任何一个时刻，一个Tablet只能分配给一个Tablet服务器。Master服务器记录了当前有哪些活跃的Tablet服务器、哪些Tablet分配给了哪些Tablet服务器、哪些Tablet还没有被分配。当一个Tablet还没有被分配、并且刚好有一个Tablet服务器有足够的空闲空间装载该Tablet时，Master服务器会给这个Tablet服务器发送一个装载请求，把Tablet分配给这个服务器。Bigtable使用Chubby跟踪记录Tablet服务器的状态。

5.3 Tablet服务

如图5所示，Tablet的持久化状态信息保存在GFS上。更新操作提交到REDO日志中。在这些更新操作中，最近提交的那些存放在一个排序的缓存中，我们称这个缓存为memtable；较早的更新存放在一系列SSTable中。

当对Tablet服务器进行写操作时，Tablet服务器首先要检查这个操作格式是否正确、操作发起者是否有执行这个操作的权限。权限验证的方法是通过从一个Chubby文件里读取出来的具有写权限的操作者列表来进行验证（这个文件几乎一定会存放在Chubby客户缓存里）。成功的修改操作会记录在提交日志里。

当进行Tablet的合并和分割时，正在进行的读写操作能够继续进行。

5.4空间缩减

随着写操作的执行，memtable的大小不断增加。当memtable的尺寸到达一个门限值的时候，这个memtable就会被冻结，然后创建一个新的memtable，被冻结住memtable会被转换成SSTable，然后写入GFS。Minor Compaction过程有两个目的：压缩Tablet服务器使用的内存，以及在服务器灾难恢复过程中，减少必须从提交日志里读取的数据量。

6 优化

上一节中描述的实现需要进行许多改进才能实现用户所需的高性能、可用性和可靠性。 本节更详细地描述了部分实现，以突出这些改进。

局部性群组

客户端可以将多个列族组合到一个位置组中。为每tablet中的每个locality group生成一个单独的SSTable。将通常不一起访问的列族分隔到单独的位置组中，可以提高读取效率。例如，Webtable中的页面元数据（例如语言和校验和）可以在一个locality组中，而页面的内容可以在不同的组中：想要读取元数据的应用程序不需要读取所有页面内容

压缩

客户端可以控制一个位置组的SSTables是否被压缩，如果是，使用哪种压缩格式。用户指定的压缩格式应用于每个SSTable块。虽然我们通过单独压缩每个块而损失了一些空间，但我们受益于可以读取SSTable的一小部分而无需解压缩整个文件。

通过缓存提高读操作的性能

为了提高读取性能，tablet服务器使用两级缓存。Scan Cache是更高级别的缓存，将SSTable接口返回的键值对缓存到tablet server代码中。块缓存是一个较低级别的缓存，用于缓存从GFS读取的SSTables块。扫描缓存对于倾向于重复读取相同数据的应用程序最有用。块缓存对于倾向于读取与他们最近读取的数据接近的数据的应用程序很有用。

Bloom过滤器

如5.3节所述，读取操作必须从构成tablet状态的所有SSTable中读取。如果这些SSTables不在内存中，我们最终可能会进行许多磁盘访问。我们通过允许客户端指定应该为特定位置组中的SSTables创建Bloom过滤器[7]来减少访问次数。

Commit日志的实现

如果我们将每个tablet的提交日志保存在一个单独的日志文件中，大量文件将同时写入GFS。根据每个GFS服务器上的底层文件系统实现，这些写入可能会导致大量磁盘搜索写入不同的物理日志文件。此外，每个tablet拥有单独的日志文件也会降低组提交优化的有效性，因为组往往更小。为了解决这些问题，我们将突变附加到每个Tablet服务器的单个提交日志中，将不同Tablet服务器的突变混合在同一个物理日志文件中[18,20]。

Tablet回复提速

如果master将一个tablet从一个tablet server移动到另一个tablet server，源tablet server首先对该tablet进行一次次压缩。这种压缩通过减少Tablet服务器提交日志中未压缩状态的数量来减少恢复时间。完成此压缩后，tablet服务器将停止为tablet提供服务。

利用不变性

除了SSTable缓存之外，Bigtable系统的其他各个部分都得到了简化，因为我们生成的所有SSTable都是不可变的。为了减少读取memtable期间的争用，我们使每个memtable行在写入时复制，并允许读取和写入并行进行。

7 性能评估

我们建立了一个包含N个tablet server的Bigtable集群，进行衡量Bigtable的性能和可扩展性，因为N是变化的。Tablet服务器被配置为使用1GB内存并写入由1786台机器组成的GFS单元，每台机器有两个400GBIDE硬盘驱动器。N台客户端机器生成了用于这些测试的Bigtable负载。这些机器被安排在一个两级树形交换网络中，在根处可用的聚合带宽约为100-200Gbps。所有机器都在同一个托管设施中，因此任何一对机器之间的往返时间都小于一毫秒。

图6显示了我们的基准在读取和写入Bigtable 1000字节值时的性能的两个视图。该表显示了每台Tablet服务器每秒的操作数；该图显示了每秒的操作总数。

单个Tablet服务的性能

让我们首先考虑仅使用一台Tablet服务器的性能。随机读取比所有其他操作慢一个数量级或更多。每次随机读取都涉及通过网络将64KB SSTable块从GFS传输到Tablet服务器，其中仅使用一个1000字节的值。Tablet服务器每秒执行大约1200次读取，这相当于从GFS读取大约75MB/s的数据。

从内存中随机读取要快得多，因为从Tablet服务器的本地内存中满足每个1000字节读取，而无需从GFS获取大的64KB块。

随机和顺序写入的性能优于随机读取，因为每个tablet server将所有传入的写入附加到单个提交日志并使用组提交将这些写入有效地流式传输到GFS。

顺序读取比随机读取执行得更好，因为从GFS获取的每个64 KB SSTable块都存储到我们的块缓存中，用于为接下来的64个读取请求提供服务。

扫描速度更快，因为tablet server可以返回大量值来响应单个客户端RPC，因此RPC开销分摊到大量值上。

性能提升

随着我们将系统中的tablet server数量

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[603223]，资料为PDF文档或Word文档，PDF文档可免费转换为Word