原文地址

摘要

Bigtable是一个用于管理结构化数据的分布式存储系统，旨在扩展到非常大的规模：跨数千台通用服务器的数据达到了几十PB。

许多Google项目都在Bigtable中存储数据，包括网页索引、Google Earth和Google Finance。这些应用对Bigtable提出了不同的需求，包括数据大小（从URL到网页再到卫星图像）和延迟要求（从后端批量处理到实时数据服务）。尽管有这些多样化的需求，Bigtable成功为所有这些Google产品提供了灵活、高性能的解决方案。

在本文中，我们描述了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还将数据视为未解释的字符串，尽管客户端通常将各种形式的结构化和半结构化数据序列化到这些字符串中。客户端可以通过在其模式中进行谨慎选择来控制其数据的局部性。最后，Bigtable模式参数允许客户端动态控制是从内存还是从磁盘提供数据。

第2节更详细地描述了数据模型，

第3节概述了客户端API。

第4节简要描述了Bigtable依赖的底层Google基础设施。

第5节描述了Bigtable实现的基本原理，第6节描述了我们为提高Bigtable性能而进行的一些改进。

第7节提供了Bigtable性能的测量结果。

我们在第8节描述了Bigtable在Google中的使用示例，并在第9节中讨论了我们在设计和支持Bigtable过程中学到的一些经验教训。

最后，第10节描述了相关工作，第11节总结了我们的结论。

2 数据模型

Bigtable是一种稀疏、分布式、持久的多维有序映射。该映射由行键、列键和时间戳索引；映射中的每个值都是一个未解释的字节数组。

（行：字符串，列：字符串，时间：int64）→ 字符串

我们在检查类似Bigtable系统的各种潜在用途后，最终确定了这个数据模型。作为驱动我们一些设计决策的一个具体示例，假设我们想要保存一个大量的网页副本和相关信息，供许多不同的项目使用；我们将这个特定的表称为Webtable。

在Webtable中，我们将使用URL作为行键，将网页的各个方面作为列名，并将网页内容存储在contents:列下，以在抓取时的时间戳为索引，如图1所示。

  • 图 1

F1

2.1 行 Rows

表中的行键是任意字符串（目前最大为64KB，尽管对于大多数用户，典型大小为10-100字节）。

对于单个行键下的数据的每次读取或写入都是原子的（无论在该行中读取或写入的不同列的数量），这是一个设计决策，使得客户端更容易推断在同一行的并发更新存在的情况下系统的行为。

Bigtable按行键的字典顺序维护数据。表的行范围是动态划分的。每个行范围称为一个tablet，这是分布和负载平衡的单位。

因此，对短行范围的读取是高效的，通常只需要与少量的机器通信。客户端可以通过选择其行键以获得其数据访问的良好局部性来利用此属性。

例如，在Webtable中，相同域中的页面通过反转URL的主机名组合在一起形成连续的行。

例如，我们将maps.google.com/index.html的数据存储在键com.google.maps/index.html下。将来自同一域的页面存储在一起使得一些主机和域分析更加高效。

2.2 列族 Column Families

列键被分组到称为列族的集合中，列族形成了访问控制的基本单元。

存储在列族中的所有数据通常是相同类型的（我们将同一列族中的数据进行压缩）。必须在可以在该列族中的任何列键下存储数据之前创建列族；创建列族后，可以使用该列族内的任何列键。我们的意图是表中不同列族的数量很小（最多数百个），并且在运行过程中列族很少更改。相比之下，表可以有无限数量的列。

列键的命名采用以下语法：family:qualifier。列族的名称必须是可打印的，但限定符可以是任意字符串。

Webtable的一个示例列族是language，它存储了网页所使用的语言。我们在language列族中只使用一个列键，它存储了每个网页的语言ID。对于这个表的另一个有用的列族是anchor；该列族中的每个列键代表一个单一的锚点，如图1所示。限定符是引用站点的名称；单元格内容是链接文本。

访问控制以及磁盘和内存的计量都是在列族级别执行的。在我们的Webtable示例中，这些控制允许我们管理几种不同类型的应用程序：一些应用程序添加新的基础数据，一些读取基础数据并创建派生列族，还有一些只被允许查看现有数据（可能甚至不允许查看所有现有列族，出于隐私原因）。

2.3 时间戳

Bigtable中的每个单元格可以包含相同数据的多个版本；这些版本是按时间戳索引的。

Bigtable时间戳是64位整数。它们可以由Bigtable分配，此时它们代表微秒级的“实时”；或者可以由客户端应用程序显式分配。需要避免冲突的应用程序必须自己生成唯一的时间戳。单元格的不同版本按照时间戳递减的顺序存储，以便首先读取最近的版本。

为了减轻版本数据的管理负担，我们支持两个每列族的设置，告诉Bigtable自动进行单元格版本的垃圾回收。

客户端可以指定只保留单元格的最后n个版本，或者只保留足够新的版本（例如，只保留在过去七天内写入的值）。

在我们的Webtable示例中，我们将存储在contents:列中的抓取页面的时间戳设置为实际抓取这些页面版本的时间。

上述的垃圾回收机制让我们只保留每个页面的最近三个版本。

3 API

Bigtable API提供了用于创建和删除表以及列族的函数。它还提供了用于更改集群、表和列族元数据的函数，例如访问控制权限。

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

图2显示了使用RowMutation抽象执行一系列更新的C++代码（为了保持示例简短，省略了不相关的细节）。对Apply的调用执行对Webtable的原子突变：它向www.cnn.com添加一个锚点并删除另一个锚点。

  • 图 2
// 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);

图3显示了使用Scanner抽象在特定行中迭代所有锚点的C++代码。客户端可以迭代多个列族，并且有几种机制来限制扫描生成的行、列和时间戳。

例如，我们可以限制上述扫描仅生成列匹配正则表达式anchor:*.cnn.com的锚点，或者仅生成时间戳在当前时间的十天内的锚点。

  • 图3
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());
}

Bigtable支持几个其他功能，允许用户以更复杂的方式操作数据。

首先，Bigtable支持单行事务，可用于在单个行键下执行原子读取-修改-写入序列的操作。目前，Bigtable不支持跨行键的通用事务，尽管它在客户端提供了跨行键批量写入的接口。其次，Bigtable允许将单元格用作整数计数器。最后，Bigtable支持在服务器的地址空间中执行客户端提供的脚本。这些脚本使用Google用于处理数据的一种称为Sawzall的语言编写[28]。

目前，我们基于Sawzall的API不允许客户端脚本写回到Bigtable，但允许进行各种形式的数据转换、基于任意表达式的过滤以及通过各种运算符进行摘要。

Bigtable可以与MapReduce [12]一起使用，这是Google开发的用于运行大规模并行计算的框架。我们编写了一组包装器，允许Bigtable既用作MapReduce作业的输入源，又用作输出目标。

4 构建模块

Bigtable构建在谷歌基础设施的几个其他组件之上。Bigtable使用分布式谷歌文件系统（GFS）[17]存储日志和数据文件。Bigtable集群通常在运行各种其他分布式应用程序的共享机器池中运行，并且Bigtable进程经常与其他应用程序的进程共享相同的机器。Bigtable依赖于集群管理系统来调度作业、管理共享机器上的资源、处理机器故障并监控机器状态。

内部使用Google SSTable文件格式存储Bigtable数据。SSTable提供了从键到值的持久、有序、不可变映射，其中键和值都是任意的字节字符串。提供了查找与指定键关联的值以及迭代在指定键范围内的所有键值对的操作。在内部，每个SSTable包含一个块序列（通常每个块的大小为64KB，但这是可配置的）。块索引（存储在SSTable的末尾）用于定位块；在打开SSTable时，索引加载到内存中。可以执行单个磁盘查找的查找：首先通过在内存中的索引中执行二进制搜索找到适当的块，然后从磁盘读取适当的块。可选地，SSTable可以完全映射到内存中，这允许我们在不触及磁盘的情况下执行查找和扫描。

Bigtable依赖于一种高可用和持久的分布式锁服务，称为Chubby [8]。Chubby服务由五个活动副本组成，其中之一被选为主服务器并主动服务请求。当大多数副本正在运行并能够相互通信时，服务是活动的。Chubby使用Paxos算法[9, 23]在面对故障时保持其副本的一致性。Chubby提供一个由目录和小文件组成的命名空间。每个目录或文件都可以用作锁，对文件的读写是原子的。Chubby客户端库提供Chubby文件的一致缓存。每个Chubby客户端与Chubby服务保持会话。如果客户端无法在租约到期时间内续订其会话租约，则客户端的会话将过期。当客户端的会话过期时，它将失去任何锁和打开的句柄。Chubby客户端还可以在Chubby文件和目录上注册回调，以通知更改或会话过期。

Bigtable在各种任务中使用Chubby：确保任何时候最多只有一个活动的主服务器；存储Bigtable数据的引导位置（请参见第5.1节）；发现平板服务器并完成平板服务器的故障（请参见第5.2节）；存储Bigtable模式信息（每个表的列族信息）；以及存储访问控制列表。如果Chubby在长时间内不可用，Bigtable也会变得不可用。我们最近在涵盖11个Chubby实例的14个Bigtable集群中测量了这种影响。由于Chubby不可用（由Chubby宕机或网络问题引起），导致Bigtable中的一些数据在Bigtable服务器小时中不可用的平均百分比为0.0047%。受Chubby不可用影响最严重的单个集群的百分比为0.0326%。

5 实现

Bigtable的实现有三个主要组件：一个被链接到每个客户端的库，一个主服务器和许多平板服务器。平板服务器可以动态添加（或删除）到集群中以适应工作负载的变化。

主服务器负责将平板分配给平板服务器，检测平板服务器的添加和过期，平衡平板服务器的负载以及对GFS中的文件进行垃圾回收。此外，它处理模式更改，例如表和列族的创建。

每个平板服务器管理一组平板（通常每个平板服务器有十到一千个平板）。平板服务器处理对其已加载的平板的读写请求，并在表格增长过大时拆分平板。

与许多单主分布式存储系统[17, 21]一样，客户端数据不通过主服务器传输：客户端直接与平板服务器通信进行读写。由于Bigtable客户端不依赖主服务器获取平板位置信息，大多数客户端实际上不会与主服务器通信。因此，在实践中主服务器的负载较轻。

Bigtable集群存储多个表。每个表由一组平板组成，每个平板包含与行范围相关联的所有数据。

最初，每个表只包含一个平板。随着表的增长，它会自动拆分成多个平板，每个平板默认大小约为100-200 MB。

5.1 平板位置 Tablet Location

我们使用类似于B+树的三级层次结构[10]来存储平板位置信息（图4）。

  • 图4

F4

第一级是存储在Chubby中的一个文件，包含根平板的位置。根平板包含一个特殊的METADATA表中所有平板的位置。每个METADATA平板包含一组用户平板的位置。根平板只是METADATA表中的第一个平板，但被特殊处理，它永远不会被拆分，以确保平板位置层次结构不超过三级。

METADATA表存储平板的位置，其中行键是平板的表标识符和其结束行的编码。每个METADATA行在内存中存储约1KB的数据。通过设置128 MB的METADATA平板的适度限制，我们的三级位置方案足以处理2^34个平板（或128 MB平板中的2^61字节）。

客户端库缓存平板位置。如果客户端不知道平板的位置，或者发现缓存的位置信息不正确，那么它会递归地上溯平板位置层次结构。如果客户端的缓存为空，则位置算法需要三次网络往返，包括从Chubby读取一次。如果客户端的缓存过期，位置算法可能需要多达六次往返，因为仅在未命中时才发现过期的缓存条目（假设METADATA平板不会经常移动）。

尽管平板位置存储在内存中，因此不需要GFS访问，但在常见情况下，我们通过客户端库预取平板位置进一步降低了这个成本：每当读取METADATA表时，它都会读取多个平板的元数据。

我们还在METADATA表中存储次要信息，包括与每个平板相关的所有事件的日志（例如服务器何时开始为其提供服务）。这些信息对于调试和性能分析非常有帮助。

5.2 平板分配 Tablet Assignment

每个平板一次只能分配给一个平板服务器。主服务器跟踪一组活动的平板服务器，以及平板分配到平板服务器的当前情况，包括哪些平板未分配。当一个平板未分配，并且有足够空间容纳该平板的平板服务器可用时，主服务器通过向平板服务器发送平板加载请求来分配该平板。

Bigtable使用Chubby来跟踪平板服务器。当平板服务器启动时，它在特定的Chubby目录中创建并获取一个唯一命名的文件的独占锁。主服务器监视这个目录（名为servers的目录）以发现平板服务器。如果平板服务器失去其独占锁，例如由于导致服务器失去其Chubby会话的网络分区，则平板服务器停止为其提供服务。（Chubby提供了一种有效的机制，允许平板服务器检查它是否仍然持有锁，而不会产生网络流量。）只要文件仍然存在，平板服务器将尝试重新获取其文件上的独占锁。如果文件不再存在，则平板服务器将永远无法再提供服务，因此它会终止自身。每当平板服务器终止（例如，因为集群管理系统正在从集群中删除平板服务器的机器时），它都会尝试释放其锁，以便主服务器更快地重新分配其平板。

主服务器负责检测平板服务器何时不再为其平板提供服务，并在尽快重新分配这些平板。为了检测平板服务器何时不再为其平板提供服务，主服务器定期询问每个平板服务器其锁的状态。如果平板服务器报告已失去锁定，或者如果主服务器在最后几次尝试期间无法与服务器通信，则主服务器会尝试获取平板服务器文件的独占锁。如果主服务器能够获取锁定，则Chubby是活动的，而平板服务器要么已经死亡要么无法与Chubby通信，因此主服务器通过删除其服务器文件确保平板服务器再也不能提供服务。一旦服务器的文件被删除，主服务器就可以将之前分配给该服务器的所有平板移动到未分配的平板集中。为了确保Bigtable集群不容易受到主服务器和Chubby之间的网络问题的影响，如果其Chubby会话到期，主服务器将自己终止。

然而，如上所述，主服务器故障不会改变平板分配到平板服务器的情况。

当由集群管理系统启动主服务器时，它需要在更改平板分配之前发现当前的平板分配情况。主服务器在启动时执行以下步骤。

（1）主服务器在Chubby中获取唯一的主锁，防止并发主实例化。

（2）主服务器扫描Chubby中的servers目录，找到活动的服务器。

（3）主服务器与每个活动的平板服务器通信，以发现每个服务器已经分配了哪些平板。

（4）主服务器扫描METADATA表，了解平板的集合。每当此扫描遇到尚未分配的平板时，主服务器将该平板添加到未分配的平板集中，从而使该平板有资格进行平板分配。

一个复杂之处在于在扫描METADATA表（步骤4）之前，不能进行METADATA平板的分配。

因此，在开始此扫描之前，如果在步骤3中未发现根平板的分配，主服务器将根平板添加到未分配的平板集中。此添加确保根平板将被分配。由于根平板包含所有METADATA平板的名称，所以主服务器在扫描根平板后知道所有METADATA平板。现有平板的集合只有在创建或删除表时，两个现有平板合并成一个较大的平板，或者将一个现有平板拆分为两个较小的平板时才会更改。主服务器能够跟踪这些更改，因为它启

动了所有这些更改，除了最后一个。

平板拆分是特殊处理的，因为它们是由平板服务器启动的。平板服务器通过在METADATA表中记录新平板的信息来提交拆分。

拆分提交后，它会通知主服务器。如果拆分通知丢失（无论是因为平板服务器还是主服务器死亡），主服务器在请求平板服务器加载现在已拆分的平板时会检测到新平板。

平板服务器将通知主服务器已拆分，因为它在METADATA表中找到的平板条目将仅指定主服务器要求其加载的平板的一部分。

5.3 平板提供服务 Tablet Serving

平板的持久状态存储在GFS中，如图5所示。

  • 图 5

F5

更新被提交到一个存储重做记录的提交日志中。其中，最近提交的更新存储在内存中的一个称为memtable的排序缓冲区中；而较旧的更新则存储在一系列SSTable中。为了恢复平板，平板服务器从METADATA表中读取其元数据。此元数据包含组成平板的SSTable列表和一组重做点，这些重做点是指向可能包含平板数据的任何提交日志的指针。服务器读取SSTable的索引到内存中，并通过应用自重做点以来已提交的所有更新来重建memtable。

当写操作到达平板服务器时，服务器会检查其是否格式良好，并且发送方是否被授权执行变异。授权是通过从Chubby文件中读取允许写入者的列表来执行的（这几乎总是在Chubby客户端缓存中命中）。有效的变异被写入提交日志。使用组提交来提高大量小型变异的吞吐量[13, 16]。在写操作已提交后，其内容将插入到memtable中。

当读操作到达平板服务器时，同样会检查其是否格式良好且是否得到适当授权。有效的读操作在SSTable序列和memtable的合并视图上执行。由于SSTable和memtable都是按字典顺序排序的数据结构，因此可以有效地形成合并视图。

在进行平板的拆分和合并时，可以继续进行传入的读写操作。

5.4 合并 Compactions

随着写操作的执行，memtable的大小会增加。当memtable大小达到阈值时，memtable会被冻结，创建一个新的memtable，并将冻结的memtable转换为SSTable并写入GFS。这个小的合并过程有两个目标：它缩小了平板服务器的内存使用，并减少了在此服务器死机时在恢复期间从提交日志中读取的数据量。在进行合并时，传入的读写操作可以继续进行。

每个小的合并都会创建一个新的SSTable。如果这种行为继续不受检查，读操作可能需要从任意数量的SSTable中合并更新。相反，我们通过定期在后台执行合并合并来限制这类文件的数量。合并合并读取几个SSTable和memtable的内容，并写出一个新的SSTable。一旦合并完成，可以立即丢弃输入SSTable和memtable。

将所有SSTable重写为一个SSTable的合并合并称为主合并。由非主合并生成的SSTable可以包含特殊的删除条目，以抑制仍然有效的旧SSTable中的已删除数据。

另一方面，主要合并生成的SSTable不包含删除信息或已删除的数据。 Bigtable循环遍历其所有平板并定期对其进行主合并。

这些主合并允许Bigtable回收被删除数据使用的资源，并且还允许它确保已删除的数据及时从系统中消失，这对于存储敏感数据的服务非常重要。

6 优化 Refinements

前一节中描述的实现需要进行一些优化，以实现我们的用户所需的高性能、可用性和可靠性。本节将更详细地描述实现的部分内容，以突出这些优化。

6.1 局部组 Locality groups

客户端可以将多个列族组合到一个局部组中。每个平板中都为每个局部组生成一个单独的SSTable。将通常不一起访问的列族分隔到单独的局部组中可以实现更高效的读取。

例如，Webtable中的页面元数据（如语言和校验和）可以在一个局部组中，而页面的内容可以在另一个组中：想要读取元数据的应用程序不需要读取所有页面内容。

此外，一些有用的调整参数可以在每个局部组的基础上指定。例如，可以声明一个局部组为内存中的。内存中的局部组的SSTable被惰性地加载到平板服务器的内存中。

加载后，属于这些局部组的列族可以在不访问磁盘的情况下读取。这个功能对于经常访问的小数据块非常有用：我们在METADATA表的location列族中内部使用它。

6.2 压缩 Compression

客户端可以控制局部组的SSTable是否压缩，如果是的话，使用哪种压缩格式。

用户指定的压缩格式应用于每个SSTable块（其大小可通过局部组特定的调整参数进行控制）。

虽然通过单独压缩每个块会损失一些空间，但在可以在不解压整个文件的情况下读取SSTable的小部分时，我们会受益。许多客户端使用两遍的自定义压缩方案。第一遍使用Bentley和McIlroy的方案[6]，它在一个大窗口内压缩长的公共字符串。第二遍使用一种快速的压缩算法，在数据的一个小的16 KB窗口中查找重复项。

两个压缩通道都非常快 - 它们在现代计算机上的编码速度为100-200 MB/s，解码速度为400-1000 MB/s。

即使在选择压缩算法时我们强调了速度而不是空间减少，这种两遍的压缩方案表现得出奇的好。

例如，在Webtable中，我们使用这种压缩方案存储Web页面内容。

在一个实验中，我们在一个压缩的局部组中存储了大量文档。为了实验的目的，我们限制了自己只存储每个文档的一个版本，而不是存储我们拥有的所有版本。

该方案实现了10:1的空间减小。这比HTML页面上典型的Gzip减小3:1或4:1要好得多，这是因为Webtable行的布局方式：来自单个主机的所有页面都存储在彼此附近。

这使得Bentley-McIlroy算法能够识别来自同一主机的页面中的大量共享样板。

许多应用程序，不仅仅是Webtable，都选择它们的行名称，以便相似的数据最终聚集在一起，因此实现了非常好的压缩比。当我们在Bigtable中存储同一值的多个版本时，压缩比甚至更好。

6.3 读性能的缓存 Caching for read performance

为了提高读性能，tablet服务器使用两个级别的缓存。扫描缓存是一个更高级别的缓存，它缓存了由SSTable接口返回给tablet服务器代码的键值对。块缓存是一个更低级别的缓存，它缓存了从GFS中读取的SSTable块。扫描缓存对于倾向于重复读取相同数据的应用程序非常有用。块缓存对于倾向于读取与它们最近读取的数据接近的数据的应用程序也很有用（例如，顺序读取，或在热行中同一局部组内的不同列的随机读取）。

6.4 布隆过滤器 Bloom filters

如第5.3节所述，读操作必须从组成tablet状态的所有SSTables中读取。如果这些SSTables不在内存中，我们可能会进行许多磁盘访问。

我们通过允许客户端指定为特定局部组的SSTables创建Bloom过滤器[7]来减少访问次数。

Bloom过滤器允许我们询问一个SSTable是否可能包含指定行/列对的任何数据。对于某些应用程序，用于存储Bloom过滤器的少量tablet服务器内存可以大大减少读取操作所需的磁盘寻道次数。

我们使用Bloom过滤器还意味着大多数查找不存在的行或列的操作不需要触及磁盘。

6.5 实现日志提交 Commit-log implementation

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

使用一个日志在正常操作期间提供了显著的性能优势，但它复杂化了恢复过程。当一个tablet服务器宕机时，它所服务的tablets将移至许多其他tablet服务器：每个服务器通常加载原始服务器的少量tablets。要恢复一个tablet的状态，新的tablet服务器需要从原始tablet服务器写入的提交日志中重新应用该tablet的突变。然而，这些tablet的突变在同一个物理日志文件中混合。一种方法是让每个新的tablet服务器读取这个完整的提交日志文件，并仅应用它需要恢复的tablets的条目。然而，在这样的方案下，如果有100台机器每台分配了一个从失败的tablet服务器恢复的tablet，那么该日志文件将被读取100次（每个服务器读取一次）。

我们通过首先按键htable、行名、日志序列号的顺序对提交日志条目进行排序来避免重复读取日志。在排序后的输出中，特定tablet的所有突变是连续的，因此可以通过一个磁盘寻道后的顺序读取进行高效读取。为了并行化排序，我们将日志文件划分为64MB的段，并在不同的tablet服务器上并行对每个段进行排序。这个排序过程由master协调，并在tablet服务器指示需要从某个提交日志文件中恢复突变时启动。

将提交日志写入GFS有时会因为各种原因导致性能波动（例如，参与写入的GFS服务器机器崩溃，或者用于到达特定的三个GFS服务器集合的网络路径遭受网络拥塞或负载过重）。为了保护突变免受GFS延迟峰值的影响，每个tablet服务器实际上有两个日志写入线程，每个线程写入自己的日志文件；其中一个线程每次只有一个是活跃的。如果写入活跃日志文件的性能差，将日志文件写入切换到另一个线程，然后由新激活的日志写入线程写入提交日志队列中的突变。日志条目包含序列号，以允许恢复过程省略由于这个日志切换过程而导致的重复条目。

6.6 加速tablet恢复 Speeding up tablet recovery

如果master将一个tablet从一个tablet服务器移动到另一个，源tablet服务器首先对该tablet执行一次小合并。这个合并通过减少tablet服务器提交日志中的未合并状态的数量，减少了恢复时间。在完成这次合并之后，tablet服务器停止服务该tablet。在实际卸载tablet之前，tablet服务器执行另一次（通常非常快速的）小合并，以消除在执行第一次小合并时到达的tablet服务器日志中的任何剩余未合并状态。完成这第二次小合并后，该tablet可以在另一个tablet服务器上加载，而无需恢复日志条目。

6.7 利用不可变性 Exploiting immutability

除了SSTable缓存之外，Bigtable系统的各个部分都因为我们生成的所有SSTables都是不可变的而变得简化。

例如，当从SSTables读取数据时，我们不需要对文件系统的访问进行同步。因此，可以非常高效地实现对行的并发控制。唯一一个被读写访问的可变数据结构是内存表。为了在读取内存表时减少争用，我们使每个内存表行都是写时复制的，并允许读和写并行进行。

由于SSTables是不可变的，永久删除已删除数据的问题转变为垃圾收集过时的SSTables。每个tablet的SSTables都在METADATA表中注册。master通过对SSTables集合执行标记和扫描的垃圾收集[25]，其中METADATA表包含根集，删除过时的SSTables。

最后，SSTables的不可变性使我们能够快速地分割tablet。我们不是为每个子tablet生成一个新的SSTables集合，而是让子tablet共享父tablet的SSTables。

7 性能评估

我们搭建了一个包含 N 个平板服务器的 Bigtable 集群，以测量 Bigtable 在 N 变化时的性能和可伸缩性。平板服务器配置为使用 1GB 内存，并写入一个由 1786 台机器组成的 GFS 存储单元，每台机器都配备两个 400GB 的 IDE 硬盘。N 个客户端机器生成了用于这些测试的 Bigtable 负载。（我们使用了与平板服务器相同数量的客户端，以确保客户端永远不会成为瓶颈。）每台机器配备两个双核 Opteron 2 GHz 处理器，足够的物理内存可容纳所有运行进程的工作集，并具有单个千兆以太网连接。

这些机器被布置在一个两级树形结构的交换网络中，根节点处的带宽约为 100-200 Gbps。所有机器都位于同一托管设施，因此任意两台机器之间的往返时间都不到一毫秒。

平板服务器、主节点、测试客户端和 GFS 服务器都在相同的机器组上运行。每台机器都运行一个 GFS 服务器。其中一些机器还运行平板服务器、客户端进程或同时使用池的其他作业的进程。

R 是测试中涉及的 Bigtable 行键的不同数量。R 被选择得足够大，以便每个基准读取或写入约 1GB 的数据到每个平板服务器。

顺序写基准使用名称为 0 到 R - 1 的行键。这些行键的空间被分成 10N 个相等大小的范围。这些范围由一个中央调度器分配给 N 个客户端，该调度器在客户端完成其分配给它的先前范围的处理后，立即分配下一个可用范围。这种动态分配有助于减轻由于客户端机器上运行的其他进程导致的性能变化的影响。我们在每个行键下写入一个字符串。每个字符串都是随机生成的，因此不可压缩。此外，不同行键下的字符串是不同的，因此无法进行跨行的压缩。随机写基准类似，只是在写入之前，行键被模 R 哈希，以便在整个行空间中均匀分布写入负载。

顺序读基准生成的行键方式与顺序写基准完全相同，但是与在行键下写入不同，它读取存储在行键下的字符串（由顺序写基准的先前调用写入）。类似地，随机读基准复制了随机写基准的操作。

扫描基准类似于顺序读基准，但使用 Bigtable API 提供的支持，以在行范围内扫描所有值。使用扫描减少了基准执行的 RPC 数量，因为单个 RPC 可以从平板服务器获取一个大的值序列。

随机读取（内存）基准类似于随机读取基准，但包含基准数据的局部组被标记为内存，因此读取可以从平板服务器的内存中满足，而不需要 GFS 读取。仅针对此基准，我们将每个平板服务器的数据量从 1GB 减少到 100MB，以确保它可以轻松适应平板服务器可用的内存。

图 6 展示了在读写 1000 字节值到 Bigtable 时我们基准的性能的两个视图。表格显示了每个平板服务器每秒的操作数；图表显示了每秒操作的总数。

  • 图 6

F6

7.1 单个平板服务器性能

首先考虑只有一个平板服务器的性能。随机读取比所有其他操作都慢一个数量级或更多。每个随机读取涉及从 GFS 将一个 64KB 的 SSTable 块通过网络传输到平板服务器，其中仅使用单个 1000 字节的值。平板服务器每秒执行约 1200 次读取，这相当于从 GFS 读取的数据约为 75 MB/s。由于我们的网络堆栈、SSTable 解析和 Bigtable 代码中的开销，这个带宽足以饱和平板服务器的 CPU，并且几乎足以饱和我们系统中使用的网络链路。大多数具有这种访问模式的 Bigtable 应用程序将块大小减小为更小的值，通常为 8KB。

由于每个 1000 字节读取都可以从平板服务器的本地内存中满足，随机读取从内存中读取的速度要快得多，而不需要从 GFS 中获取一个大的 64 KB 块。

随机和顺序写入的性能优于随机读取，因为每个平板服务器将所有传入的写入附加到单个提交日志，并使用组提交将这些写入有效地流式传输到 GFS。随机写入和顺序写入的性能之间没有显著的差异；在这两种情况下，所有写入平板服务器的操作都记录在同一个提交日志中。

由于从 GFS 检索的每个 64 KB SSTable 块都存储在我们的块缓存中，用于为下一个 64 个读取请求提供服务，因此顺序读取的性能要优于随机读取。

扫描的性能甚至更快，因为平板服务器可以在单个客户端 RPC 的响应中返回大量值，因此 RPC 开销被摊销在大量值上。

7.2 扩展性

随着系统中平板服务器数量从 1 增加到 500，总吞吐量呈现显著增加，增长超过一百倍。例如，随机读取内存的性能在增加 500 倍的平板服务器数量时几乎提高了 300 倍。这种行为发生的原因是这个基准测试性能的瓶颈是单个平板服务器的 CPU。

然而，性能并非线性增加。对于大多数基准测试，从 1 到 50 个平板服务器时，每个服务器的吞吐量会显著下降。这个下降是由于在多服务器配置中负载不平衡造成的，通常是由于其他进程争夺 CPU 和网络资源。我们的负载平衡算法试图解决这种不平衡，但由于两个主要原因，它不能完美地完成这项工作：重新平衡受到限制，以减少平板移动的数量（移动平板时，平板在短时间内不可用，通常不到一秒），并且我们的基准测试生成的负载在基准测试进行时会发生变化。

随机读取基准测试显示了最差的扩展性（对于服务器数量增加了 500 倍，总吞吐量仅增加了 100 倍）。

这种行为发生的原因是（如上所述），对于每次 1000 字节的读取，我们通过网络传输一个大的 64KB 块。这种传输饱和了我们网络中的各种共享 1 千兆比特链路，因此随着机器数量的增加，每个服务器的吞吐量显著下降。

8 实际应用

截至 2006 年 8 月，谷歌各个机器集群中运行着 388 个非测试的 Bigtable 集群，总计约有 24,500 个平板服务器。表 1 展示了每个集群中平板服务器的大致分布。

这些集群中的许多用于开发目的，因此在相当长的时间内处于空闲状态。一组包含 14 个繁忙集群的总平板服务器数为 8069 台，其总请求数超过每秒 120 万次，入站 RPC 流量约为 741 MB/s，出站 RPC 流量约为 16 GB/s。

表 2 提供了目前正在使用的一些表格的一些数据。

一些表存储为用户提供的数据，而其他表存储用于批处理的数据，其中包括从内存提供的数据的百分比以及表模式的复杂性。在本节的其余部分，我们简要描述了三个产品团队如何使用 Bigtable。

8.1 Google Analytics

Google Analytics（analytics.google.com）是一个帮助网站管理员分析其网站流量模式的服务。它提供聚合统计信息，如每天的独立访问者数量和每天每个 URL 的页面浏览量，以及站点跟踪报告，如在先前查看特定页面的情况下进行购买的用户百分比。

为了启用该服务，网站管理员需要在其网页中嵌入一个小的 JavaScript 程序。该程序在每次访问页面时调用，记录有关请求的各种信息，如用户标识符和正在获取的页面的信息。Google Analytics对这些数据进行汇总，并向网站管理员提供可用的信息。

我们简要描述了 Google Analytics 使用的两个表。原始点击表（约200 TB）为每个最终用户会话维护一行。行名是包含网站名称和创建会话的时间的元组。这个模式确保访问相同网站的会话是连续的，并且按时间顺序排序。该表的压缩比为原始大小的14%。

摘要表（约20 TB）包含每个网站的各种预定义摘要信息。此表是通过定期安排的 MapReduce 作业从原始点击表生成的。每个 MapReduce 作业从原始点击表中提取最近的会话数据。整个系统的吞吐量受到 GFS 吞吐量的限制。该表的压缩比为原始大小的29%。

8.2 Google Earth

Google运营一系列服务，为用户提供通过基于Web的Google地图界面（maps.google.com）和Google Earth（earth.google.com）定制客户端软件访问世界表面高分辨率卫星图像的功能。这些产品允许用户在世界表面上导航：他们可以在许多不同分辨率级别上平移、查看和注释卫星图像。该系统使用一个表来预处理数据，并使用一组不同的表来提供客户端数据。

预处理流水线使用一个表来存储原始图像。在预处理过程中，图像被清理并整合为最终的服务数据。这个表包含大约70 TB 的数据，因此从磁盘提供服务。图像已经被高效压缩，因此禁用了Bigtable的压缩功能。

图像表中的每一行对应一个单一的地理段。为了确保相邻的地理段存储在彼此附近，对行进行了命名。该表包含一个列族，用于跟踪每个段的数据源。这个列族有大量的列：基本上是每个原始数据图像的一列。由于每个段只是由少量图像构建而成，因此这个列族非常稀疏。

预处理流水线在Bigtable上广泛使用MapReduce来转换数据。在某些MapReduce作业期间，整个系统每秒处理超过1 MB 的数据量每个平板服务器。

服务系统使用一个表来索引存储在GFS中的数据。这个表相对较小（约500 GB），但必须以低延迟为每个数据中心每秒提供数万次的查询。因此，该表分布在数百个平板服务器上，并包含内存列族。

8.3 个性化搜索

个性化搜索（www.google.com/psearch）是一个选择加入的服务，记录用户在各种Google属性（如网络搜索、图像和新闻）上的查询和点击。

用户可以浏览他们的搜索历史，重新查看他们以前的查询和点击，并可以根据他们的历史Google使用模式请求个性化的搜索结果。

个性化搜索将每个用户的数据存储在Bigtable中。每个用户都有一个唯一的用户ID，并分配一个以该用户ID命名的行。所有用户操作都存储在一个表中。为每种类型的操作保留一个单独的列族（例如，有一个列族存储所有网络查询）。每个数据元素使用其对应用户操作发生的时间作为其Bigtable时间戳。个性化搜索使用Bigtable上的MapReduce生成用户配置文件。这些用户配置文件用于个性化实时搜索结果。个性化搜索数据在多个Bigtable集群之间复制，以提高可用性并减少与客户端距离相关的延迟。个性化搜索团队最初在Bigtable之上构建了一个客户端复制机制，确保所有副本最终一致。当前系统现在使用内置于服务器中的复制子系统。

个性化搜索存储系统的设计允许其他团队在其自己的列中添加新的每用户信息，该系统现在被许多其他需要存储每用户配置选项和设置的Google属性使用。

在多个团队之间共享一个表导致了异常数量的列族。为了支持共享，我们向Bigtable添加了一个简单的配额机制，以限制共享表中任何特定客户端的存储消耗；这个机制在使用该系统进行每用户信息存储的各种产品组之间提供了一些隔离。

9 教训

在设计、实施、维护和支持Bigtable的过程中，我们积累了有用的经验并学到了一些有趣的教训。

我们学到的一课是大型分布式系统容易受到许多类型的故障的影响，不仅仅是许多分布式协议中假设的标准网络分区和故障停止。例如，我们曾经因为以下原因遇到问题：

内存和网络损坏、大时钟偏移、挂起的机器、扩展和不对称的网络分区、我们正在使用的其他系统中的错误（例如Chubby），GFS配额溢出，以及计划和非计划的硬件维护。随着我们对这些问题的经验增加，我们通过改变各种协议来解决这些问题。例如，我们为我们的RPC机制添加了校验和。我们还通过消除系统的一部分对另一部分的假设来处理一些问题。例如，我们停止假设给定的Chubby操作只能返回固定一组错误之一。

另一个我们学到的教训是，在确切知道新功能将如何使用之前，推迟添加新功能是很重要的。例如，我们最初计划在API中支持通用事务。

然而，由于我们没有对它们的即时使用，我们没有实施它们。现在我们有许多在Bigtable上运行的真实应用程序，我们已经能够研究它们的实际需求，并发现大多数应用程序只需要单行事务。在人们要求分布式事务的情况下，最重要的用途是维护次要索引，我们计划添加一种专门的机制来满足这种需求。这种新机制将比分布式事务更为专用，但将更为高效（特别是对于跨越数百行或更多的更新），并且还将更好地与我们的乐观的跨数据中心复制方案进行交互。

Bigtable支持的一个实际教训是正确的系统级监控的重要性（即监控Bigtable本身以及使用Bigtable的客户端进程）。例如，我们扩展了我们的RPC系统，以便对RPC的样本进行详细跟踪，记录为该RPC执行的重要操作。这个特性使我们能够检测和修复许多问题，比如对tablet数据结构的锁争用、在提交Bigtable变更时对GFS的慢写以及在METADATA表不可用时对METADATA表的访问被阻塞。另一个有用的监控例子是，每个Bigtable集群都在Chubby中注册。这使我们能够追踪所有集群，了解它们有多大，它们运行哪个版本的软件，它们接收多少流量，以及是否存在任何问题，比如意外的大延迟。

我们学到的最重要的教训是简单设计的价值。考虑到我们系统的规模（大约有10万行非测试代码）以及代码随时间以意想不到的方式演变的事实，我们发现代码和设计的清晰度在代码维护和调试方面是巨大的帮助。其中一个例子是我们的tablet服务器成员协议。我们的第一个协议很简单：主节点定期向tablet服务器发放租约，如果租约过期，tablet服务器就会自杀。不幸的是，这个协议在存在网络问题时显著降低了可用性，而且对主节点恢复时间也很敏感。我们多次重新设计该协议，直到找到性能良好的协议。然而，由此产生的协议过于复杂，并依赖于很少被其他应用程序使用的Chubby功能的行为。我们发现我们花费了大量时间调试Bigtable代码和Chubby代码中的晦涩角落。

最终，我们放弃了该协议，转而使用一种更简单的协议，仅依赖于广泛使用的Chubby功能。

10 Related Work

The Boxwood项目[24]的一些组件在某些方面与Chubby、GFS和Bigtable重叠，因为它提供了分布式协议、锁定、分布式块存储和分布式B树存储。

在每个重叠的情况下，似乎Boxwood的组件针对的目标略低于相应的Google服务。Boxwood项目的目标是提供构建更高级服务（如文件系统或数据库）的基础设施，而Bigtable的目标是直接支持希望存储数据的客户端应用程序。

许多最近的项目都致力于解决在广域网络上提供分布式存储或更高级服务的问题，通常在“互联网规模”上。这包括以CAN [29]、Chord [32]、Tapestry [37]和Pastry [30]为代表的分布式哈希表的研究。这些系统解决了Bigtable不涉及的问题，如高度可变的带宽、不受信任的参与者或频繁的重配置；去中心化控制和拜占庭容错不是Bigtable的目标。

在提供给应用程序开发人员的分布式数据存储模型方面，我们认为分布式B树或分布式哈希表提供的键值对模型过于受限。键值对是一个有用的构建块，但它们不应该是向开发人员提供的唯一构建块。我们选择的模型比简单的键值对更丰富，并支持稀疏的半结构化数据。尽管如此，它仍然足够简单，使其适合非常高效的平面文件表示，并且通过局部性组的透明性，允许我们的用户调整系统的重要行为。

一些数据库供应商已经开发了可以存储大量数据的并行数据库。甲骨文的Real Application Cluster数据库[27]使用共享磁盘存储数据（Bigtable使用GFS），并使用分布式锁管理器（Bigtable使用Chubby）。IBM的DB2 Parallel Edition [4]基于类似于Bigtable的共享无物理架构。

每个DB2服务器负责存储在本地关系数据库中的表中的一部分行。这两个产品都提供完整的关系模型和事务。

Bigtable的局部性组实现了在磁盘上使用基于列而不是基于行的存储组织数据的其他系统所观察到的类似的压缩和磁盘读取性能优势，包括C-Store [1, 34]以及商业产品如Sybase IQ [15, 36]、SenSage [31]、KDB+ [22]和MonetDB/X100中的ColumnBM存储层 [38]。另一个对数据进行垂直和水平数据分区并实现良好数据压缩比率的系统是AT&T的Daytona数据库 [19]。局部性组不支持CPU缓存级别的优化，例如Ailamaki [2]所描述的那些。

Bigtable使用内存表和SSTables存储对表格的更新的方式类似于Log-Structured Merge Tree [26]存储索引数据的方式。在这两个系统中，排序数据在写入磁盘之前被缓冲在内存中，读取必须从内存和磁盘中合并数据。

C-Store和Bigtable共享许多特征：两个系统都使用共享无物理架构，并有两种不同的数据结构，一种用于最近的写入，一种用于存储长寿命的数据，并有将数据从一种形式移动到另一种形式的机制。这两个系统的API存在显著的差异：C-Store的行为类似于关系数据库，而Bigtable提供了一个更低级别的读写接口，并设计成支持每秒数千次此类操作。C-Store还是一个“以读为优化的关系型DBMS”，而Bigtable在读密集型和写密集型应用上都提供了良好的性能。

Bigtable的负载平衡器必须解决与共享无物理数据库面临的一些相同类型的负载和内存平衡问题（例如[11, 35]）。

我们的问题略微简单：

（1）我们不考虑相同数据的多个副本的可能性，可能由于视图或索引而以不同的形式存在；

（2）我们让用户告诉我们哪些数据应该存储在内存中，哪些数据应该保留在磁盘上，而不是尝试动态确定这一点；

（3）我们没有需要执行或优化的复杂查询。

11 结论

我们已经描述了Bigtable，这是Google用于存储结构化数据的分布式系统。

自2005年4月以来，Bigtable集群已经投入生产使用，我们在此日期之前花费了大约七个人年的时间进行设计和实现。

截至2006年8月，有超过六十个项目在使用Bigtable。我们的用户喜欢Bigtable实现提供的性能和高可用性，以及他们可以通过简单地向系统添加更多机器来随时间改变的资源需求来扩展他们集群的容量。考虑到Bigtable的不寻常接口，一个有趣的问题是我们的用户适应使用它的难度有多大。新用户有时不确定如何最好地使用Bigtable接口，特别是如果他们习惯于使用支持通用事务的关系数据库。尽管如此，许多Google产品成功地使用Bigtable表明我们的设计在实践中运作良好。

我们正在实施一些额外的Bigtable功能，例如支持二级索引和构建具有多个主副本的跨数据中心复制Bigtable的基础设施。我们还已经开始将Bigtable部署为服务提供给产品组，因此个别组不需要维护自己的集群。随着我们的服务集群扩展，我们将需要处理Bigtable本身的更多资源共享问题 [3, 5]。

最后，我们发现在Google构建自己的存储解决方案有着重大的优势。通过为Bigtable设计我们自己的数据模型，我们获得了相当大的灵活性。

此外，我们对Bigtable实现及其依赖的其他Google基础架构的掌控意味着我们可以在问题出现时消除瓶颈和低效。

致谢

我们感谢匿名审稿人、David Nagle以及我们的协作编辑Brad Calder，感谢他们对本文的反馈。Bigtable系统受益于Google内部众多用户的反馈。

此外，我们感谢以下人员对Bigtable的贡献：Dan Aguayo、Sameer Ajmani、Zhifeng Chen、Bill Coughran、Mike Epstein、Healfdene Goguen、Robert Griesemer、Jeremy Hylton、Josh Hyman、Alex Khesin、Joanna Kulik、Alberto Lerner、Sherry Listgarten、Mike Maloney、Eduardo Pinheiro、Kathy Polizzi、Frank Yellin和Arthur Zwiegincew。

参考资料

https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/bigtable-osdi06.pdf