【译】Bigtable: A Distributed Storage System for Structured Data

本文翻译了论文《Bigtable: A Distributed Storage System for Structured Data》的全部内容，原论文“科学”下载。作为谷歌的三驾马车之一，是谷歌早期（2005年）在大数据领域的精华作品，对后来的大数据领域其他产品的孵化有深远的影响。同样的，在工程化方面也有很多可以借鉴的地方。阅读愉快，欢迎在留言区勘误和提出意见。

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

摘要

Bigtable 是一个分布式存储系统，用于管理结构化数据，旨在扩展到非常大的规模：跨越数千台商用服务器的 PB 级数据。Google 的许多项目都将数据存储在 Bigtable 中，包括网络索引、Google 地球和 Google 财经等。这些应用程序对 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 节中描述了 Google 如何使用 Bigtable 的几个示例，并在第 9 节中讨论了我们在设计和支持 Bigtable 中学到的一些经验教训。最后，第 10 节描述了业界类似的工作，第 11 节给出了我们的结论。

2 数据模型

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

(row:string, column:string, time:int64) → string

在检查了类似 Bigtable 这种系统的各种潜在用途后，我们确定了这个数据模型。作为推动我们做出一些设计决策的一个具体示例是，假设我们想要保留一份可供许多不同项目使用的大量网页和相关信息的副本；让我们称这个特殊的表为 Webtable。在 Webtable 中，我们将使用 URL 作为行键，使用网页的各个方面作为列名，并将网页的内容存储在 contens这个列中：对应于获取它们时的那个时间戳下，如图 1 所示。

图 1

图 1：存储网页的示例表的一部分。行名称是反向的 URL。内容列contens族包含页面内容，锚列anchor族包含引用页面的任何锚的文本。CNN 的主页被 Sports Illustrated 和 MY-look 主页引用，因此该行包含名为 ```anchor:cnnsi.com``` 和 ```anchor:my.look.ca``` 的列。每个锚单元有一个版本；内容列具有三个版本，分别位于时间戳 t3、t5 和 t6

行

表中的行键是任意字符串（目前最大为 64KB，尽管 10-100 字节是我们大多数用户的典型大小）。在单个行键下的每次读取或写入数据都是原子性的（无论在行中读取或写入的不同列的数量如何），这种设计决策使客户端更容易在存在并发的情况下推断系统的行为，更新到同一行。

Bigtable 按行键的字典顺序维护数据。表的行范围是动态分区的。每个行范围称为一个片（tablet），它是分配和负载均衡的最小单位。因此，短行范围的读取是高效的，并且通常只需要与少量机器进行通信。客户端可以利用通过选择自己的行键，使他们获得良好的局部性数据访问。例如，在 Webtable 中，通过反转 URL 的主机名组件，同一域中的页面被组合成连续的行。例如，我们将 maps.google.com/index.html 的数据存储在键 com.google.maps/index.html 下。将来自同一域的页面彼此靠近存储可以使某些主机和域分析更有效。

列族

列键被分组为称为列族的集合，它们构成了访问控制的基本单元。存储在列族中的所有数据通常是相同的类型（我们将同一列族中的数据压缩在一起）。必须先创建列族，然后才能将数据存储在该族中的任何列键下；创建族后，可以使用族内的任何列键。我们的意图是表中不同列族的数量很少（最多数百个），并且族在操作期间很少发生变化。相比之下，一个表可能有无限数量的列。

列键使用以下语法命名：family: qualifier。列族名称必须是可打印的，但限定符可以是任意字符串。Webtable 的一个示例列族是语言，它存储着编写网页的语言。我们在语言族中只使用一个列键，它存储了每个网页的语言 ID。这个表的另一个有用的列族是锚；该系列中的每个列键代表一个锚点，如图 1 所示。限定符是引用站点的名称；单元格内容是链接文本。

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

时间戳

Bigtable 中的每个单元格都可以包含相同数据的多个版本；这些版本按时间戳索引。Bigtable 时间戳是 64 位整数。它们可以由 Bigtable 分配，在这种情况下，它们表示以微秒为单位的“实时”，或者由客户端应用程序显式分配。需要避免冲突的应用程序必须自己生成唯一的时间戳。单元格的不同版本按时间戳递减顺序存储，以便可以首先读取最新版本。

为了让版本化数据的管理更轻松，我们支持两种 per-column-family 设置，告诉 Bigtable 自动对单元格版本进行垃圾收集。客户端可以指定仅保留单元格的最后 n 个版本，或者仅保留足够新的版本（例如，仅保留最近 7 天内写入的值）。

在我们的 Webtable 示例中，我们将存储在contents内容列中的已爬取页面的时间戳设置为实际爬取这些页面版本的时间。上面描述的垃圾收集机制让我们只保留每个页面的最新三个版本。

3 API

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

客户端应用程序可以写入或删除 Bigtable 中的值、从单个行中查找值或迭代表中的数据子集。下面的这段代码（论文中的图2）显示了使用 RowMutation 抽象来执行一系列更新的 C++ 代码。（省略了不相关的细节以保持示例简短。）调用 Apply 对 Webtable 执行原子性更改：它将一个锚点添加到 www.cnn.com 并删除另一个锚点。

1
2
3
4
5
6
7
8
// 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 匹配的锚点，或者仅生成时间戳在当前时间的十天内的锚点。

1
2
3
4
5
6
7
8
9
10
11
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 支持在服务器的地址空间中执行客户端提供的脚本。这些脚本是用谷歌开发的一种语言编写的，用于处理称为 Sawzall [28] 的数据。目前，我们基于 Sawzall 的 API 不允许客户端脚本写回 Bigtable，但它允许各种形式的数据转换、基于任意表达式的过滤以及通过各种运算符进行汇总。

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

4 构成要素

Bigtable 建立在 Google 基础架构的其他几个部分之上。Bigtable 使用分布式 Google 文件系统 (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 片位置

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

图 4

第一级是存储在 Chubby 中的文件，其中包含根片的位置。根片包含特殊 METADATA 表中所有片的位置。每个 METADATA 片都包含一组用户片的位置。根片只是 METADATA 表中的第一个片，但被特殊对待（它从不拆分）以确保片位置层次结构不超过三个级别。

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

客户端程序库(lib)会缓存片的位置。如果客户端不知道片的位置，或者它发现缓存的位置信息不正确，则它会在片位置的层次结构递归地向上移动。如果客户端的缓存为空，则定位算法需要 3 次网络往返，包括一次从 Chubby 读取。如果客户端的缓存是陈旧的，则位置算法可能需要多达六次往返，因为陈旧的缓存条目仅在未命中时才被发现（假设 METADATA 片不经常移动）。尽管片位置存储在内存中，因此不需要 GFS 访问，但我们在常见情况下通过让客户端库预取片位置进一步降低了这一成本：每当读取 METADATA 表时，它都会读取多个片的元数据。

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

5.2 片分配

每个片一次分配给一个片服务器。主服务器会跟踪一组活动的片服务器，以及片到片服务器的当前分配，包括哪些片是未分配的。当一个片没有被分配，并且有一个片服务器有足够的空间给片使用时，主服务器通过向片服务器发送一个片加载请求来分配片。

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

主服务器负责检测片服务器何时不再为它的片提供服务，并尽快重新分配这些片。为了检测片服务器何时不再为它的片提供服务，主服务器会定期询问每个片服务器的锁定状态。如果一个片服务器报告它已经失去了它的锁，或者如果主服务器在最后几次尝试中无法访问服务器，主服务器会尝试获取服务器文件上的排他锁。如果主服务器能够获得锁，那么 Chubby 是活动的，片服务器要么挂了，要么无法访问 Chubby，所以主服务器 通过删除它的服务器文件来确保片服务器永远不会再次服务。一旦服务器的文件被删除，主服务器就可以将之前分配给该服务器的所有片移动到未分配片的集合中。为了确保 Bigtable 集群不会受到主服务器和 Chubby 之间网络问题的影响，如果其 Chubby 会话过期，主服务器会自行终止。然而，如上所述，主机故障不会改变片到片服务器的分配。

当集群管理系统启动主服务器时，它需要先发现当前的片分配，然后才能更改它们。主服务器在启动时执行以下步骤。(1) 主服务器在 Chubby 中获取唯一的主服务器锁，防止并发主服务器实例化。(2) 主服务器扫描Chubby中的服务器目录，找到存活的服务器。(3) 主服务器与每个活跃的片服务器通信，以发现哪些片已经分配给每个服务器。（4）主服务器扫描METADATA表，了解片集合。每当此扫描遇到尚未分配的片时，主设备都会将该片添加到未分配的片集合中，这使得该片有资格进行片分配。

一种复杂情况是，在分配了 METADATA 片之前，无法对 METADATA 表进行扫描。因此，在开始此扫描（第 4 步）之前，如果在第 3 步期间未发现对根片的分配，则主服务器将根片添加到未分配的片集合中。此添加确保将分配根片。由于根片包含所有 METADATA 片的名称，因此主服务器在扫描根片后就知道所有这些名称。

只有在创建或删除表、两个现有的片合并形成一个更大的片或一个现有的片拆分为两个较小的片时，现有片的集合才会发生变化。主服务器能够跟踪这些更改，因为它初始化了除最后一个之外的所有更改。片拆分会被特殊对待，因为它们是由片服务器启动的。片服务器通过在 METADATA 表中记录新片的信息来提交拆分。提交拆分后，它会通知主服务器。如果拆分通知丢失（因为片服务器或主服务器终止），主服务器会在请求片服务器加载现在已拆分的片时检测到新的片。片服务器将通知主服务器拆分，因为它在 METADATA 表中找到的片条目将仅指定主服务器要求它加载的一部分片。

5.3 片服务

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

图 5

当写操作到达片服务器时，服务器会检查它的格式是否正确以及发送者是否有权执行更改。授权是通过从 Chubby 文件中读取允许写入的列表来执行的（这几乎总是在 Chubby 客户端缓存中命中）。一个有效的变更被写入提交日志。组提交用于提高大量小变动的吞吐量 [13] [16]。写入提交后，其内容被插入到内存表中。

当读取操作到达片服务器时，同样会检查它的格式是否正确和正确的授权。在 SSTable 和 memtable 序列的合并视图上执行有效的读取操作。由于 SSTables 和 memtable 是按字典顺序排序的数据结构，因此可以有效地形成合并视图。

当片被拆分和合并时，传入的读写操作可以继续。

5.4 压缩

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

每次非主要压缩都会创建一个新的 SSTable。如果此行为继续未选中，则读取操作可能需要合并来自任意数量 SSTable 的更新。相反，我们通过在后台定期执行合并压缩来限制此类文件的数量。合并压缩读取一些 SSTable 和 memtable 的内容，并写出一个新的 SSTable。压缩完成后，输入 SSTables 和 memtable 可以被丢弃。
将所有 SSTable 重写为一个 SSTable 的合并压缩称为主要压缩。由非主要压缩生成的 SSTable 可以包含特殊的删除条目，这些条目可以抑制仍然存活的旧 SSTable 中已删除的数据。另一方面，主要压缩会产生一个不包含删除信息或已删除数据的 SSTable。Bigtable 循环遍历它的所有片，并定期对它们应用主要压缩。这些主要压缩允许 Bigtable 回收被删除数据使用的资源，并允许它确保删除的数据及时从系统中消失，这对于存储敏感数据的服务很重要。

6 改进

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

局部性组

客户端可以将多个列族组合到一个局部组中。为每个片中的每个局部组生成一个单独的 SSTable。将通常不会一起访问的列族分离到单独的局部组中可以实现更高效的读取。例如，Webtable 中的页面元数据（如语言和校验和）可以在一个局部组中，页面的内容可以在不同的组中：想要读取元数据的应用程序不需要通读所有页面内容。

此外，可以在每个局部组的基础上指定一些有用的调整参数。例如，可以将局部组声明在内存中。内存中局部组的 SSTable 被延迟加载到片服务器的内存中。加载后，可以在不访问磁盘的情况下读取属于此类局部组的列族。这个特性对于经常访问的小块数据很有用：我们在内部将它用于 METADATA 表中的位置列族。

压缩

客户端可以控制是否压缩局部组的 SSTable，如果压缩，使用哪种压缩格式。 用户指定的压缩格式应用于每个 SSTable 块（其大小可通过特定于局部组的调整参数进行控制）。 虽然单独压缩每个块会损失一些空间，但我们的收获是可以在不解压缩整个文件的情况下读取 SSTable 的一小部分。 许多客户端使用两遍自定义压缩方案。 第一遍使用 Bentley 和 McIlroy 的方案 [6]，它在一个大窗口中压缩长公共字符串。 第二遍使用快速压缩算法，在数据的 16 KB 小窗口中查找重复项。 这两个压缩通道都非常快——它们以 100-200 MB/s 的速度编码，在现代机器上以 400-1000 MB/s 的速度解码。

尽管我们在选择压缩算法时强调速度而不是空间减少，但这种两遍压缩方案的效果出奇地好。例如，在Webtable 中，我们使用这种压缩方案来存储网页内容。在一个实验中，我们将大量文档存储在一个压缩的局部组中。出于实验的目的，我们将自己限制为每个文档的一个版本，而不是存储我们可用的所有版本。该方案实现了 10 比 1 的空间缩减。由于 Webtable 行的布局方式，这比典型的 3 对 1 或 4 对 1 HTML 页面的 Gzip 缩减要好得多：来自单个主机的所有页面都彼此靠近存储。这允许 Bentley-McIlroy 算法识别来自同一主机的页面中的大量共享样板。许多应用程序，不仅仅是 Webtable，选择它们的行名称，以便类似的数据最终聚集在一起，从而实现非常好的压缩率。当我们在 Bigtable 中存储相同值的多个版本时，压缩率会变得更好。

缓存提升读取性能

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

布隆过滤器

如第 5.3 节所述，读取操作必须从构成片状态的所有 SSTable 中读取。 如果这些 SSTable 不在内存中，我们最终可能会进行多次磁盘访问。 我们通过允许客户端指定应为特定局部组中的 SSTable 创建布隆过滤器 [7] 来减少访问次数。 布隆过滤器允许我们询问 SSTable 是否可能包含指定行/列对的任何数据。 对于某些应用程序，用于存储布隆过滤器的少量片服务器内存会大大减少读取操作所需的磁盘搜索次数。 我们对布隆过滤器的使用也意味着对不存在的行或列的大多数查找不需要接触磁盘。

日志提交的实现

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

使用一个日志可以在正常操作期间提供显著的性能优势，但会使恢复复杂化。 当一个片服务器宕机时，它所服务的片将被转移到大量其他片服务器上：每个服务器通常会加载少量原始服务器的片s。 要恢复片的状态，新的片服务器需要从原始片服务器写入的提交日志中重新应用该片的更改。 但是，这些片的变动混合在同一个物理日志文件中。 一种方法是让每个新的片服务器读取这个完整的提交日志文件，并只应用它需要恢复的片所需的条目。 然而，在这样的方案下，如果 100 台机器每台被分配一个来自故障片服务器的片，那么日志文件将被读取 100 次（每个服务器一次）。

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

将提交日志写入 GFS 有时会由于各种原因导致性能出现问题（例如，涉及写入崩溃的 GFS 服务器机器，或者到达特定的三个 GFS 服务器组的网络路径正在遭受网络拥塞，或者负载过重 ）。 为了保护 GFS 延迟峰值的变动，每个片服务器实际上有两个日志写入线程，每个写入自己的日志文件； 一次只有这两个线程中的一个在使用中。 如果对活动日志文件的写入性能不佳，则将日志文件写入切换到另一个线程，并且提交日志队列中的变动由新的活动日志写入线程写入。 日志条目包含序列号，以允许恢复过程消除由此日志切换过程产生的重复条目。

加速片恢复

如果主服务器将一个片从一个片服务器移动到另一个片服务器，源片服务器首先在那个片上做一个非主要压缩。 这种压缩通过减少片服务器 提交日志中未压缩状态的数量来减少恢复时间。 完成此压缩后，片服务器将停止为该片提供服务。 在它实际卸载片之前，片服务器进行另一次（通常非常快）非主要压缩，以消除片服务器日志中任何剩余的未压缩状态，这些状态是在执行第一次非主要压缩时到达的。 在第二次非主要压缩完成后，片可以加载到另一个片服务器上，而无需恢复任何日志条目。

利用不变性

除了 SSTable 缓存之外，由于我们生成的所有 SSTable 都是不可变的，Bigtable 系统的其他各个部分也得到了简化。 例如，从 SSTables 读取时，我们不需要对文件系统的任何同步访问。 因此，可以非常有效地实现对行的并发控制。 读取和写入都可以访问的唯一可变数据结构是内存表。 为了减少内存表读取期间的争用，我们使每个内存表行在写时复制，并允许读取和写入并行进行。

由于 SSTables 是不可变的，永久删除已删除数据的问题转化为垃圾收集过时的 SSTables。 每个片的 SSTable 都注册在 METADATA 表中。 主服务器 删除过时的 SSTables 作为标记和清除垃圾收集 [25] 在 SSTables 集上，其中 METADATA table 包含一组根。

最后，SSTables 的不变性使我们能够快速拆分片。 我们不是为每个子片生成一组新的 SSTable，而是让子片共享父片的 SSTable。

7 性能评估

我们建立了一个包含 N 个片服务器的 Bigtable 集群，以衡量 Bigtable 在 N 变化时的性能和可扩展性。 片服务器配置为使用 1GB 内存并写入由 1786 台机器组成的 GFS 单元，每台机器带有两个 400 GB IDE 硬盘。 N 台客户端机器生成用于这些测试的 Bigtable 负载。 （我们使用与片服务器相同数量的客户端，以确保客户端永远不会成为瓶颈。）每台机器都有两个双核 Opteron 2 GHz 芯片，足够的物理内存来容纳所有正在运行的进程的工作集，以及一个千兆位 以太网链接。 这些机器被安排在一个两级树形交换网络中，在根部有大约 100-200 Gbps 的总带宽可用。 所有机器都在同一个托管设施中，因此任何一对机器之间的往返时间都小于一毫秒。

片服务器和主、测试客户端和 GFS 服务器都在同一组机器上运行。 每台机器都运行一个 GFS 服务器。 一些机器还运行片服务器或客户端进程，或在这些实验的同时使用池的其他作业的进程.

R 是测试中涉及的 Bigtable 行键的不同数量。 选择 R 是为了让每个基准测试在每个片服务器上读取或写入大约 1 GB 的数据。

顺序写入基准使用名称为 0 到 R − 1 的行键。这个行键空间被划分为 10N 个相等大小的范围。 这些范围由中央调度器分配给 N 个客户端，一旦客户端完成处理分配给它的前一个范围，中央调度器就会将下一个可用范围分配给客户端。 这种动态分配有助于减轻由在客户端计算机上运行的其他进程引起的性能变化的影响。 我们在每个行键下写了一个字符串。 每个字符串都是随机生成的，因此是不可压缩的。 此外，不同行键下的字符串是不同的，因此无法进行跨行压缩。 随机写入基准是相似的，除了行键在写入之前立即以 R 为模进行散列，以便在基准的整个持续时间内写入负载大致均匀地分布在整个行空间中。

顺序读取基准以与顺序写入基准完全相同的方式生成行键，但不是在行键下写入，而是读取存储在行键下的字符串（由顺序写入基准的较早调用写入） . 类似地，随机读取基准测试影响了随机写入基准的操作。

扫描基准测试类似于顺序读取基准测试，但使用 Bigtable API 提供的支持来扫描行范围内的整体值。 使用扫描减少了基准执行的 RPC 数量，因为单个 RPC 从片服务器获取大量值。

随机读取 (mem) 基准测试类似于随机读取基准测试，但包含基准数据的局部组被标记为内存中，因此读取是从片服务器的内存中满足的，而不需要 GFS 读取。 对于这个基准测试，我们将每台片服务器的数据量从 1 GB 减少到 100 MB，以便它可以轻松地放入片服务器可用的内存中。

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

图6

单个片服务器性能

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

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

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

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

扫描速度甚至更快，因为 片 服务器可以返回大量值以响应单个客户端 RPC，因此 RPC 开销会在大量值上分摊。

扩缩容

当我们将系统中的片服务器数量从 1 增加到 500 时，总吞吐量急剧增加了 100 多倍。例如，从内存中随机读取的性能增加了近 300 倍，因为 片服务器增加了 500 倍。出现这种情况是因为此基准测试的性能瓶颈是单个片服务器 CPU。

但是，性能不会线性增加。 对于大多数基准测试，当从 1 台片服务器增加到 50 台片服务器时，每台服务器的吞吐量会显着下降。 这种下降是由多个服务器配置中的负载不平衡引起的，通常是由于其他进程争用 CPU 和网络。 我们的负载平衡算法尝试处理这种不平衡，但由于两个主要原因而不能完美地完成工作：重新平衡被限制以减少片移动的次数（片在短时间内不可用，通常不到一秒） 移动），并且我们的基准测试产生的负载随着基准测试的进行而移动

随机读取基准测试显示最差的扩展（对于服务器数量增加 500 倍，总吞吐量仅增加 100 倍）。 出现这种情况是因为（如上所述）我们每读取 1000 字节就通过网络传输一个 64KB 大块。 这种传输使我们网络中的各种共享 1GB 链接饱和，因此，随着机器数量的增加，每台服务器的吞吐量显着下降。

8 实际应用

截至 2006 年 8 月，有 388 个非测试 Bigtable 集群在各种 Google 机器集群中运行，总共约有 24,500 个片服务器。 表 1 显示了每个集群的片服务器的粗略分布。 其中许多集群用于开发目的，因此在很长一段时间内处于空闲状态。 一组 14 个繁忙的集群，共有 8069 个片服务器，每秒的总请求量超过 120 万个，传入的 RPC 流量约为 741 MB/s，传出的 RPC 流量约为 16 GB/s。

表 1

表 2 提供了有关当前使用的一些表的一些数据。 一些表存储提供给用户的数据，而另一些表存储用于批处理的数据； 这些表在总大小、平均单元格大小、内存提供的数据百分比以及表模式的复杂性方面范围很广。 在本节的其余部分，我们将简要介绍三个产品团队如何使用 Bigtable。

表 2

8.1 Google Analytics

Google Analytics (analytics.google.com) 是一项帮助网站管理员分析其网站流量模式的服务。 它提供汇总统计数据，例如每天唯一访问者的数量和每天每个 URL 的页面浏览量，以及站点跟踪报告，例如购买的用户百分比，前提是他们之前查看了特定页面 .

为了启用该服务，网站管理员在他们的网页中嵌入了一个小的 JavaScript 程序。 每当访问页面时都会调用此程序。 它在 Google Analytics 中记录有关请求的各种信息，例如用户标识符和有关正在获取的页面的信息。 Google Analytics 会汇总这些数据并提供给网站管理员。

我们简要介绍了 Google Analytics 使用的两个表。 原始点击表 (~200 TB) 为每个最终用户会话维护一行。 行名称是一个包含网站名称和会话创建时间的元组。 此架构可确保访问同一网站的会话是连续的，并按时间顺序排序。 该表压缩到其原始大小的 14%。

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

8.2 Google Earth

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

预处理管道使用一张表来存储原始图像。 在预处理期间，图像被清理并合并为最终的服务数据。 该表包含大约 70 TB 的数据，因此由磁盘提供。 图像已被有效压缩，因此禁用 Bigtable 压缩。

影像表中的每一行对应一个地理段。 命名行以确保相邻的地理段彼此靠近存储。 该表包含一个列族，用于跟踪每个段的数据源。 这个列族有大量的列：基本上每个原始数据图像一个。 由于每个段仅由几个图像构建，因此该列族非常稀疏。

预处理管道严重依赖 MapReduce 而不是 Bigtable 来转换数据。 在其中一些 MapReduce 作业期间，整个系统每台片服务器处理超过 1 MB/秒的数据。

服务系统使用一张表来索引存储在 GFS 中的数据。 该表相对较小（约 500 GB），但它必须以低延迟为每个数据中心每秒处理数万次查询。 因此，该表托管在数百台片服务器上，并包含内存中的列族。

个性化搜索 (www.google.com/psearch) 是一项选择加入的服务，用于记录用户在各种 Google 属性（例如网络搜索、图像和新闻）中的查询和点击。 用户可以浏览他们的搜索历史以重新访问他们的旧查询和点击，并且他们可以根据他们的历史 Google 使用模式请求个性化的搜索结果。

个性化搜索将每个用户的数据存储在 Bigtable 中。 每个用户都有一个唯一的用户 ID，并分配有一个以该用户 ID 命名的行。 所有用户操作都存储在一个表中。 为每种类型的操作保留一个单独的列族（例如，有一个列族存储所有 Web 查询）。 每个数据元素使用相应用户操作发生的时间作为它的 Bigtable 时间戳。 个性化搜索在 Bigtable 上使用 MapReduce 生成用户配置文件。 这些用户配置文件用于个性化实时搜索结果。

个性化搜索数据跨多个 Bigtable 集群复制，以提高可用性并减少由于与客户端的距离而导致的延迟。 Personalized Search 团队最初在 Bigtable 之上构建了一个客户端复制机制，以确保所有副本的最终一致性。 当前系统现在使用内置于服务器中的复制子系统。

个性化搜索存储系统的设计允许其他组在他们自己的列中添加新的每用户信息，并且该系统现在被许多其他需要存储每用户配置选项和设置的 Google 属性使用。 在许多组之间共享一个表导致异常大量的列族。 为了支持共享，我们在 Bigtable 中添加了一个简单的配额机制，以限制共享表中任何特定客户端的存储消耗； 这种机制在使用该系统的各个产品组之间提供了一些隔离，用于每个用户的信息存储。

9 经验教训

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

我们学到的一个教训是，大型分布式系统容易受到多种类型的故障的影响，而不仅仅是许多分布式协议中假设的标准网络分区和故障停止故障。 例如，我们已经看到由于以下所有原因引起的问题：内存和网络损坏、时钟偏差大、机器挂起、扩展和非对称网络分区、我们正在使用的其他系统中的错误（例如 Chubby）、GFS 溢出 配额，以及计划内和计划外的硬件维护。 随着我们在这些问题上获得更多经验，我们通过更改各种协议来解决这些问题。 例如，我们在 RPC 机制中添加了校验和。 我们还通过消除系统的一部分对另一部分所做的假设来处理一些问题。 例如，我们不再假设给定的 Chubby 操作只能返回一组固定错误中的一个。

我们学到的另一个教训是，推迟添加新功能直到明确如何使用新功能是很重要的。 例如，我们最初计划在我们的 API 中支持通用事务。 然而，因为我们没有立即使用它们，所以我们没有实现它们。 现在我们在 Bigtable 上运行了许多真实的应用程序，我们已经能够检查它们的实际需求，并且发现大多数应用程序只需要单行事务。 在人们请求分布式事务的地方，最重要的用途是维护二级索引，我们计划添加专门的机制来满足这种需求。 新机制将不如分布式事务通用，但会更高效（特别是对于跨越数百行或更多行的更新），并且还将与我们的乐观跨数据中心复制方案更好地交互。

我们从支持 Bigtable 中学到的一个实际教训是适当的系统级监控的重要性（即监控 Bigtable 本身以及使用 Bigtable 的客户端进程）。 例如，我们扩展了我们的 RPC 系统，以便对于 RPC 样本，它可以详细跟踪代表该 RPC 完成的重要操作。 此功能使我们能够检测并修复许多问题，例如片数据结构上的锁争用、提交 Bigtable 突变时对 GFS 的写入缓慢，以及当 METADATA 片不可用时对 METADATA 表的访问卡住。 另一个有用的监控示例是每个 Bigtable 集群都在 Chubby 中注册。 这使我们能够追踪所有集群，发现它们有多大，查看它们正在运行我们的软件的哪些版本，它们接收了多少流量，以及是否存在任何问题，例如意外的大延迟。

我们学到的最重要的一课是简单设计的价值。考虑到我们系统的大小（大约 100,000 行非测试代码），以及代码以意想不到的方式随时间演变的事实，我们发现代码和设计清晰度对代码维护和调试有很大帮助。这方面的一个例子是我们的片服务器会员协议。我们的第一个协议很简单：主节点定期向片服务器发布租约，如果租约到期，片服务器会自行终止。不幸的是，该协议在出现网络问题时显着降低了可用性，并且对主恢复时间也很敏感。我们多次重新设计了协议，直到我们有了一个表现良好的协议。然而，由此产生的协议过于复杂，并且依赖于其他应用程序很少使用的 Chubby 功能的行为。我们发现我们花费了过多的时间来调试晦涩难懂的极端情况，不仅在 Bigtable 代码中，而且在Chubby 代码中。最终，我们废弃了这个协议，转而使用一个更新的更简单的协议，它完全依赖于广泛使用的 Chubby 特性。

10 相关类似的工作

Boxwood 项目 [24] 的组件在某些方面与 Chubby、GFS 和 Bigtable 重叠，因为它提供了分布式协议、锁、分布式块存储和分布式 B 树存储。 在存在重叠的每种情况下，似乎 Boxwood 的组件的目标级别都比相应的 Google 服务低一些。 Boxwood 项目的目标是为构建更高级别的服务（例如文件系统或数据库）提供基础设施，而 Bigtable 的目标是直接支持希望存储数据的客户端应用程序。

最近的许多项目都解决了通过广域网提供分布式存储或更高级别服务的问题，通常是“互联网规模”。 这包括从 CAN [29]、Chord [32]、Tapestry [37] 和 Pastry [30] 等项目开始的分布式哈希表工作。 这些系统解决了 Bigtable 不会出现的问题，例如高度可变的带宽、不受信任的参与者或频繁的重新配置； 去中心化控制和拜占庭容错不是Bigtable的目标。

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

一些数据库供应商开发了可以存储大量数据的并行数据库。 Oracle 的 Real Application Cluster 数据库 [27] 使用共享磁盘存储数据（Bigtable 使用 GFS）和分布式锁管理器（Bigtable 使用 Chubby）。 IBM 的 DB2 Parallel Edition [4] 基于类似于 Bigtable 的无共享 [33] 架构。 每个 DB2 服务器负责存储在本地关系数据库中的表中行的子集。 这两种产品都提供了一个完整的事务关系模型。

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

Bigtable 使用 memtables 和 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 存储结构化数据的分布式系统。 Bigtable 集群自 2005 年 4 月以来一直在生产中使用，在那之前我们花了大约 7 人年的时间进行设计和实施。 截至 2006 年 8 月，已有 60 多个项目在使用 Bigtable。 我们的用户喜欢 Bigtable 实现提供的性能和高可用性，并且他们可以通过简单地向系统添加更多机器来扩展集群的容量，因为他们的资源需求会随着时间的推移而变化。

鉴于 Bigtable 的不寻常界面，一个有趣的问题是我们的用户很难适应使用它。 新用户有时不确定如何最好地使用 Bigtable 接口，特别是如果他们习惯于使用支持通用事务的关系数据库。 尽管如此，许多 Google 产品成功使用 Bigtable 的事实表明我们的设计在实践中运作良好。

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

最后，我们发现在 Google 构建自己的存储解决方案具有显著优势。 通过为 Bigtable 设计我们自己的数据模型，我们获得了很大的灵活性。 此外，我们对 Bigtable 的实施以及 Bigtable 所依赖的其他 Google 基础设施的控制意味着我们可以在瓶颈和低效出现时消除它们。

致谢

我们感谢匿名审稿人 David Nagle 和我们的牧羊人 Brad Calder 对本文的反馈。 Bigtable 系统从 Google 内部许多用户的反馈中受益匪浅。 此外，我们感谢以下人员对 Bigtable 的贡献：Dan Aguayo、Sameer Ajmani、Zhifeng Chen、Bill Coughran、Mike Epstein、Healfdene Goguen、RobertGriesemer、Jeremy Hylton、Josh Hyman、Alex Khesin、Joanna Kulik、Alberto Lerner、Sherry Listgarten , MikeMaloney, Eduardo Pinheiro, Kathy Polizzi, Frank Yellin, 和 Arthur Zwiegincew。

参考

  1. ABADI, D. J., MADDEN, S. R., AND FERREIRA, M. C. Integrating compression and execution in column oriented database systems. Proc. of SIGMOD (2006). ↩
  2. AILAMAKI, A., DEWITT, D. J., HILL, M. D., AND SK-OUNAKIS, M. Weaving relations for cache performance. In The VLDB Journal (2001), pp. 169–180. ↩
  3. BANGA, G., DRUSCHEL, P., AND MOGUL, J. C. Resource containers: A new facility for resource management in server systems. In Proc. of the 3rd OSDI (Feb. 1999), pp. 45–58. ↩
  4. BARU, C. K., FECTEAU, G., GOYAL, A., HSIAO, H., JHINGRAN, A., PADMANABHAN, S., COPELAND, G. P., AND WILSON, W. G. DB2 parallel edition. IBM Systems Journal 34, 2 (1995), 292–322. ↩
  5. BAVIER, A., BOWMAN, M., CHUN, B., CULLER, D., KARLIN, S., PETERSON, L., ROSCOE, T., SPALINK, T., AND WAWRZONIAK, M. Operating system support for planetary-scale network services. In Proc. of the 1st NSDI (Mar. 2004), pp. 253–266. ↩
  6. BENTLEY, J. L., AND MCILROY, M. D. Data compression using long common strings. In Data Compression Conference (1999), pp. 287–295. ↩
  7. BLOOM, B. H. Space/time trade-offs in hash coding with allowable errors. CACM 13, 7 (1970), 422–426. ↩
  8. BURROWS, M. The Chubby lock service for looselycoupled distributed systems. In Proc. of the 7th OSDI (Nov. 2006). ↩
  9. CHANDRA, T., GRIESEMER, R., AND REDSTONE, J. Paxos made live — An engineering perspective. In Proc. of PODC (2007). ↩
  10. COMER, D. Ubiquitous B-tree. Computing Surveys 11, 2 (June 1979), 121–137. ↩
  11. COPELAND, G. P., ALEXANDER, W., BOUGHTER, E. E., AND KELLER, T. W. Data placement in Bubba. In Proc. of SIGMOD (1988), pp. 99–108. ↩
  12. DEAN, J., AND GHEMAWAT, S. MapReduce: Simplifified data processing on large clusters. In Proc. of the 6th OSDI (Dec. 2004), pp. 137–150. ↩
  13. DEWITT, D., KATZ, R., OLKEN, F., SHAPIRO, L., STONEBRAKER, M., AND WOOD, D. Implementation techniques for main memory database systems. In Proc. of SIGMOD (June 1984), pp. 1–8. ↩
  14. DEWITT, D. J., AND GRAY, J. Parallel database systems: The future of high performance database systems. CACM 35, 6 (June 1992), 85–98. ↩
  15. FRENCH, C. D. One size fifits all database architectures do not work for DSS. In Proc. of SIGMOD (May 1995), pp. 449–450. ↩
  16. GAWLICK, D., AND KINKADE, D. Varieties of concurrency control in IMS/VS fast path. Database Engineering Bulletin 8, 2 (1985), 3–10. ↩
  17. GHEMAWAT, S., GOBIOFF, H., AND LEUNG, S.-T. The Google fifile system. In Proc. of the 19th ACM SOSP (Dec. 2003), pp. 29–43. ↩
  18. GRAY, J. Notes on database operating systems. In Operating Systems — An Advanced Course, vol. 60 of Lecture Notes in Computer Science. Springer-Verlag, 1978. ↩
  19. GREER, R. Daytona and the fourth-generation language Cymbal. In Proc. of SIGMOD (1999), pp. 525–526. ↩
  20. HAGMANN, R. Reimplementing the Cedar fifile system using logging and group commit. In Proc. of the 11th SOSP (Dec. 1987), pp. 155–162. ↩
  21. HARTMAN, J. H., AND OUSTERHOUT, J. K. The Zebra striped network fifile system. In Proc. of the 14th SOSP (Asheville, NC, 1993), pp. 29–43. ↩
  22. KX.COM. kx.com/products/database.php. Product page. ↩
  23. LAMPORT, L. The part-time parliament. ACM TOCS 16, 2 (1998), 133–169. ↩
  24. MACCORMICK, J., MURPHY, N., NAJORK, M., THEKKATH, C. A., AND ZHOU, L. Boxwood: Abstractions as the foundation for storage infrastructure. In Proc. of the 6th OSDI (Dec. 2004), pp. 105–120. ↩
  25. MCCARTHY, J. Recursive functions of symbolic expressions and their computation by machine. CACM 3, 4 (Apr. 1960), 184–195. ↩
  26. O’NEIL, P., CHENG, E., GAWLICK, D., AND O’NEIL, E. The log-structured merge-tree (LSM-tree). Acta Inf. 33, 4 (1996), 351–385. ↩
  27. ORACLE.COM. www.oracle.com/technology/products/database/clustering/index.html. Product page. ↩
  28. PIKE, R., DORWARD, S., GRIESEMER, R., AND QUIN- LAN, S. Interpreting the data: Parallel analysis with Sawzall. Scientifific Programming Journal 13, 4 (2005), 227–298. ↩
  29. RATNASAMY, S., FRANCIS, P., HANDLEY, M., KARP, R., AND SHENKER, S. A scalable content-addressable network. In Proc. of SIGCOMM (Aug. 2001), pp. 161– 172. ↩
  30. ROWSTRON, A., AND DRUSCHEL, P. Pastry: Scalable, distributed object location and routing for largescale peer-to-peer systems. In Proc. of Middleware 2001 (Nov. 2001), pp. 329–350. ↩
  31. SENSAGE.COM. sensage.com/products-sensage.htm. Product page. ↩
  32. STOICA, I., MORRIS, R., KARGER, D., KAASHOEK, M. F., AND BALAKRISHNAN, H. Chord: A scalable peer-to-peer lookup service for Internet applications. In Proc. of SIGCOMM (Aug. 2001), pp. 149–160. ↩
  33. STONEBRAKER, M. The case for shared nothing. Database Engineering Bulletin 9, 1 (Mar. 1986), 4–9. ↩
  34. STONEBRAKER, M., ABADI, D. J., BATKIN, A., CHEN, X., CHERNIACK, M., FERREIRA, M., LAU, E., LIN, A., MADDEN, S., O’NEIL, E., O’NEIL, P., RASIN, A., TRAN, N., AND ZDONIK, S. C-Store: A columnoriented DBMS. In Proc. of VLDB (Aug. 2005), pp. 553– 564. ↩
  35. STONEBRAKER, M., AOKI, P. M., DEVINE, R., LITWIN, W., AND OLSON, M. A. Mariposa: A new architecture for distributed data. In Proc. of the Tenth ICDE (1994), IEEE Computer Society, pp. 54–65. ↩
  36. SYBASE.COM. www.sybase.com/products/databaseservers/sybaseiq. Product page. ↩
  37. ZHAO, B. Y., KUBIATOWICZ, J., AND JOSEPH, A. D. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Tech. Rep. UCB/CSD-01-1141, CS Division, UC Berkeley, Apr. 2001. ↩
  38. ZUKOWSKI, M., BONCZ, P. A., NES, N., AND HEMAN, S. MonetDB/X100 — A DBMS in the CPU cache. IEEE Data Eng. Bull. 28, 2 (2005), 17–22. ↩