Appearance
Bigtable：一个结构化数据的分布式存储系统
摘要
Bigtable 是一个用于管理结构化数据的分布式存储系统，其设计目标是扩展到非常大的规模：跨越数千台商用服务器的 PB 级数据。Google 的许多项目将数据存储在 Bigtable 中，包括网页索引、Google Earth 和 Google Finance。这些应用对 Bigtable 提出了非常不同的需求，无论是在数据大小（从 URL 到网页再到卫星图像）还是延迟要求（从后端批量处理到实时数据服务）方面。尽管需求各异，Bigtable 已成功地为所有这些 Google 产品提供了灵活、高性能的解决方案。在本文中，我们描述了 Bigtable 提供的简单数据模型，该模型赋予客户端对数据布局和格式的动态控制权，并详细描述了 Bigtable 的设计与实现。
1 引言
在过去两年半的时间里，我们设计、实现并部署了一个名为 Bigtable 的分布式存储系统，用于在 Google 管理结构化数据。Bigtable 设计用于可靠地扩展到 PB 级数据和数千台机器。Bigtable 已实现多个目标：广泛的适用性、可扩展性、高性能和高可用性。Bigtable 被超过六十个 Google 产品和项目所使用，包括 Google Analytics、Google Finance、Orkut、个性化搜索、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 是一个稀疏的、分布式的、持久化的多维排序映射。该映射由行键 (row key)、列键 (column key) 和时间戳 (timestamp) 索引；映射中的每个值都是一个未解释的字节数组。 (row:string, column:string, time:int64) → string
在研究了各种使用类似 Bigtable 系统的潜在用途后，我们确定了这个数据模型。作为一个推动我们部分设计决策的具体例子，假设我们想要保留一个大型网页集合的副本以及相关信息，供许多不同的项目使用；我们将这个特定的表称为 Webtable。在 Webtable 中，我们会将 URL 用作行键，将网页的各个方面用作列名，并将网页内容存储在 contents: 列下，时间戳为它们被抓取的时间，如图 1 所示。
行 (Rows)
表中的行键是任意字符串（目前最大为 64KB，但对于我们的大多数用户来说，10-100 字节是典型大小）。在单个行键下对数据的每次读取或写入都是原子的（无论该行中读取或写入的列数有多少），这一设计决策使得客户端在存在对同一行的并发更新时更容易推理系统的行为。
Bigtable 按行键的字典序维护数据。表的行范围是动态分区的。每个行范围称为一个片 (tablet)，它是数据分布和负载平衡的基本单位。因此，读取短行范围是高效的，通常只需要与少量机器通信。客户端可以通过选择其行键来利用此属性，从而为其数据访问获得良好的局部性。例如，在 Webtable 中，通过反转 URL 的主机名部分，将同一域中的页面分组到连续的行中。例如，我们将 maps.google.com/index.html 的数据存储在键 com.google.maps/index.html 下。将来自同一域的页面存储在一起使得某些主机和域分析更加高效。
列族 (Column Families)
列键被分组为称为列族 (column families) 的集合，它们构成访问控制的基本单位。存储在列族中的所有数据通常是相同类型的（我们对同一列族中的数据一起进行压缩）。在列族中任何列键下存储数据之前，必须先创建该列族；列族创建后，该族内的任何列键都可以使用。我们的意图是，一个表中不同的列族数量要少（最多数百个），并且在操作期间族很少更改。相比之下，一个表可以有无限数量的列。
列键使用以下语法命名：family:qualifier。列族名称必须是可打印的，但限定符 (qualifier) 可以是任意字符串。Webtable 的一个列族示例是 language，它存储网页所使用的语言。我们在 language 族中只使用一个列键，它存储每个网页的语言 ID。该表的另一个有用的列族是 anchor,如图 1 所示,该族中的每个列键代表一个锚点。限定符是引用站点的名称,单元格内容是链接文本。
访问控制以及磁盘和内存核算都在列族级别执行。在我们的 Webtable 示例中，这些控制允许我们管理几种不同类型的应用程序：一些添加新的基础数据，一些读取基础数据并创建派生的列族，还有一些只允许查看现有数据（甚至可能出于隐私原因无法查看所有现有族）。
时间戳 (Timestamps)
Bigtable 中的每个单元格可以包含同一数据的多个版本；这些版本由时间戳索引。Bigtable 时间戳是 64 位整数。它们可以由 Bigtable 分配，此时它们代表微秒级的“真实时间”，也可以由客户端应用程序显式分配。需要避免冲突的应用程序必须自己生成唯一的时间戳。单元格的不同版本按时间戳递减顺序存储，因此可以首先读取最新版本。
为了减轻版本化数据管理的负担，我们支持两个针对按列族的设置项，告诉 Bigtable 自动对单元格版本进行垃圾回收。客户端可以指定只保留单元格的最后 n 个版本，或者只保留足够新的版本（例如，只保留最近七天内写入的值）。
在我们的 Webtable 示例中，我们将爬取的页面存储于 contents: 列中，并把这些页面的的时间戳设置为对应版本实际被爬取的时间。上面描述的垃圾回收机制让我们只保留每个页面的最近三个版本。
3 API
Bigtable API 提供了创建和删除表及列族的函数。它还提供了更改集群、表和列族元数据的函数，例如访问控制权限。
客户端应用程序可以在 Bigtable 中写入或删除值，从单个行中查找值，或迭代表中的数据子集。图 2 显示了使用 RowMutation 抽象执行一系列更新的 C++ 代码。（为了保持示例简短，省略了不相关的细节。）对 Apply 的调用对 Webtable 执行一个原子变更：它为 www.cnn.com 添加一个锚点并删除另一个不同的锚点。
c++
// 打开表
Table* T = OpenOrDie("/bigtable/web/webtable");
// 写入一个新锚点并删除一个旧锚点
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。
图 3 显示了使用 Scanner 抽象迭代特定行中所有锚点的 C++ 代码。客户端可以迭代多个列族，并且有几种机制可以限制扫描产生的行、列和时间戳。例如，我们可以将上述扫描限制为仅生成列匹配正则表达式 anchor:*.cnn.com 的锚点，或者仅生成时间戳在当前时间十天内（fall within ten days）的锚点。
c++
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());
}图 3：从 Bigtable 读取。
Bigtable 支持其他一些特性，允许用户以更复杂的方式操作数据。首先，Bigtable 支持单行事务，可用于对存储在单个行键下的数据执行原子读-修改-写序列。Bigtable 目前不支持跨行键的通用事务，但它提供了一个接口用于在客户端对跨行键的写入进行批处理。其次，Bigtable 允许将单元格用作整数计数器。最后，Bigtable 支持在服务器的地址空间中执行客户端提供的脚本。这些脚本使用Sawzall[28] 编写, 这是Google开发的用于数据处理的编程语言。目前，我们基于 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 节）；发现片服务器 (tablet server) 并确认片服务器死亡（见第 5.2 节）；存储 Bigtable 模式信息（每个表的列族信息）；以及存储访问控制列表。如果 Chubby 长时间不可用，Bigtable 将变得不可用。我们最近在跨越 11 个 Chubby 实例的 14 个 Bigtable 集群中测量了这种影响。由于 Chubby 不可用（由 Chubby 中断或网络问题引起）导致存储在 Bigtable 中的某些数据不可用的服务器时间百分比平均值为0.0047%。受 Chubby 不可用影响最严重的单个集群的百分比为 0.0326%。
5 实现
Bigtable 实现有三个主要组件：链接到每个客户端的库、一个主服务器 (master server) 和许多分片服务器 (tablet servers)。可以动态地向集群添加（或移除）分片服务器以适应工作负载的变化。
主服务器负责将分片 (tablet) 分配给分片服务器，检测片服务器的添加和过期，平衡片服务器的负载，以及回收 GFS 中的文件。此外，它还处理模式更改，例如表和列族的创建。
每个片服务器管理一组片（通常每个片服务器管理大约十到一千个片）。片服务器处理对其已加载片的读写请求，并拆分变得过大的片。
与许多单主节点的分布式存储系统[17,21]一样，客户端数据不经过主节点：客户端直接与片服务器通信进行读写操作。因为 Bigtable 客户端不依赖主节点获取片位置信息，所以大多数客户端在实践中从不与主节点通信。因此，主节点在实际负载很轻。
一个 Bigtable 集群存储多个表。每个表由一组片组成，每个片包含与一个行范围关联的所有数据。最初，每个表只包含一个片。随着表的增长，它会自动拆分成多个片，默认情况下每个片大约 100-200 MB。
5.1 片定位 (Tablet Location)
我们使用类似于 B+ 树[10] 的三层层次结构来存储片位置信息（图 4）。
图 4：分片位置层级。
第一层是存储在 Chubby 中的一个文件，包含根片 (root tablet) 的位置。根片包含一个特殊的 METADATA 表中所有片的位置。每个 METADATA 片包含一组用户片的位置。根片只是 METADATA 表中的第一个片，但被特殊对待——它永远不会被分割——以确保片位置层次结构不超过三层。
METADATA 表在其行键下存储用户片的位置，该行键是用户片的表标识符和结束行的编码。每个 METADATA 行在内存中存储大约 1KB 的数据。在 METADATA 片大小限制为适中的 128 MB 的情况下，我们的三层位置方案足以寻址 234 个片（或在 128 MB 的片中寻址 264 字节）。
客户端库缓存片位置。如果客户端不知道片的位置，或者它发现缓存的位置信息不正确，那么它会沿着片位置层次结构递归向上移动。如果客户端的缓存为空，定位算法需要三次网络往返，包括一次从 Chubby 读取。如果客户端的缓存是陈旧的，定位算法可能需要多达六次往返，因为陈旧的缓存条目只有在未命中时才会被发现（假设 METADATA 片移动不频繁）。尽管片位置存储在内存中，因此不需要 GFS 访问，但我们通过在客户端库读取 METADATA 表时预取多个片的位置，进一步降低了常见情况下的开销。
我们还在 METADATA 表中存储辅助信息，包括与每个片相关的所有事件的日志（例如服务器何时开始服务它）。此信息有助于调试和性能分析。
5.2 片分配 (Tablet Assignment)
每个片在任意时刻只分配给一个片服务器。主服务器跟踪活动片服务器的集合，以及片到片服务器的当前分配，包括哪些片未被分配。当一个片未被分配，并且有一个具有足够空间的片服务器可用时，主服务器通过向该片服务器发送片加载请求来分配该片。
Bigtable 使用 Chubby 来跟踪片服务器。当片服务器启动时，它会在特定的 Chubby 目录中创建并获取一个唯一命名文件的独占锁。主服务器监视此目录（服务器目录）以发现片服务器。如果片服务器丢失其独占锁（例如，由于网络分区导致服务器丢失其 Chubby 会话），它将停止服务其加载的分片。（Chubby 提供了一种高效机制，允许片服务器检查其是否仍持有其锁而不会产生网络流量。）只要文件仍然存在，片服务器将尝试重新获取其文件的独占锁。如果文件不再存在，那么片服务器将永远无法再服务，因此它会终止自身。每当片服务器终止时（例如，因为集群管理系统正在将片服务器的机器从集群中移除），它会尝试释放其锁，以便主服务器更快地重新分配其分片。
主服务器负责检测片服务器何时不再服务其加载的分片，并尽快重新分配这些分片。为了检测片服务器何时不再服务其加载的片，主服务器定期询问每个片服务器其持有锁的状态。如果片服务器报告其丢失了锁，或者主服务器在几次尝试中无法联系到服务器，则主服务器尝试获取该服务器锁文件的独占锁。如果主服务器能够获取锁，则 Chubby 是存活的，而片服务器要么死亡，要么无法连接 Chubby，因此主服务器通过删除其服务器锁文件来确保该片服务器永远无法再服务。一旦服务器的锁文件被删除，主服务器就可以将该服务器之前分配的所有片移动到未分配片集合中。为了确保 Bigtable 集群不易受主节点和 Chubby 之间网络问题的影响，如果主节点的 Chubby 会话过期，主节点会终止自身。然而，如上所述，主节点故障不会改变片到片服务器的分配。
当主节点被集群管理系统启动时，它需要先发现当前的片分配情况，然后才能更改它们。主节点在启动时执行以下步骤。(1) 主节点在 Chubby 中获取一个唯一的主节点锁，以防止并发的主节点实例化。(2) 主节点扫描 Chubby 中的服务器目录以找到活动服务器。(3) 主节点与每个活动片服务器通信，以发现每个服务器已分配了哪些片。(4) 主节点扫描 METADATA 表以了解片的集合。当此扫描遇到尚未分配的片时，主节点将该片添加到未分配片集合中，这使得该片有资格被分配。
一个复杂之处在于，在 METADATA 片被分配之前，无法进行 METADATA 表的扫描。因此，在开始此扫描之前（步骤 4），如果在步骤 3 期间未发现根片的分配，主节点将根片添加到未分配片集合中。此添加确保根片将被分配。因为根片包含所有 METADATA 片的名称，主节点在扫描完根片后就知道所有 METADATA 片。
现有片的集合仅在创建或删除表、两个现有片合并成一个更大的片，或一个现有片分裂成两个较小的片时才会更改。主节点能够跟踪这些更改，因为它发起了除最后一种（分裂）之外的所有更改。片分裂被特殊对待，因为它是由片服务器发起的。片服务器通过在 METADATA 表中为新片记录信息来提交分裂。当分裂提交后，它通知主节点。如果分裂通知丢失（要么是因为片服务器或主节点死亡），当主节点要求片服务器加载现在已分裂的片时，主节点会检测到新片。片服务器会通知主节点分裂情况，因为它在 METADATA 表中找到的片条目将只指定主节点要求其加载的片的一部分。
5.3 片服务 (Tablet Serving)
如图 5 所示，片的持久状态存储在 GFS 中。更新被提交到一个存储重做记录 (redo records) 的提交日志 (commit log)。在这些更新中，最近提交的更新存储在内存中一个称为内存表 (memtable) 的排序缓冲区中；较旧的更新存储在一系列 SSTable 中。为了恢复片，片服务器从 METADATA 表中读取其元数据。该元数据包含组成片的 SSTable 列表以及一组重做点 (redo points)，这些重做点是指向可能包含该片数据的任何提交日志的指针。服务器将 SSTable 的索引读入内存，并通过应用自重做点以来已提交的所有更新来重建内存表。
当写操作到达片服务器时，服务器检查其格式是否正确，并检查发送者是否有权执行变更。授权通过从 Chubby 文件（几乎总是命中 Chubby 客户端缓存）中读取允许的写入者列表来执行。有效的变更被写入提交日志。组提交 (group commit) 用于提高大量小变更的吞吐量[13, 16]。写操作提交后，其内容被插入到内存表中。
当读操作到达片服务器时，同样检查其格式和权限。有效的读操作在 SSTable 序列和内存表的合并视图上执行。由于 SSTable 和内存表是字典序排序的数据结构，因此可以高效地形成合并视图。
在片分裂和合并期间，传入的读写操作可以继续进行。
5.4 压缩 (Compactions)
随着写操作的执行，内存表的大小会增加。当内存表大小达到阈值时，内存表被冻结 (frozen)，一个新的内存表被创建，冻结的内存表被转换为 SSTable 并写入 GFS。次要压缩 (minor compaction) 过程有两个目标：它缩小片服务器的内存使用量，并在该服务器死亡时减少恢复期间需要从提交日志读取的数据量。在压缩发生期间，传入的读写操作可以继续进行。
图 5：分片展现。
每次次要压缩都会创建一个新的 SSTable。如果这种行为不加控制地继续下去，读操作可能需要合并来自任意数量 SSTable 的更新。相反，我们通过在后台定期执行合并压缩 (merging compaction) 来限制此类文件的数量。合并压缩读取几个 SSTable 和内存表的内容，并写出一个新的 SSTable。一旦压缩完成，输入 SSTable 和内存表就可以丢弃。
将所有 SSTable 重写为恰好一个 SSTable 的合并压缩称为主要压缩 (major compaction)。非主要压缩产生的 SSTable 可能包含特殊的删除条目，这些条目会抑制仍存活的旧 SSTable 中的已删除数据。另一方面，主要压缩产生的 SSTable 不包含删除信息或已删除数据。Bigtable 周期性地遍历其所有片，并定期对它们执行主要压缩。这些主要压缩允许 Bigtable 回收被删除数据使用的资源，并确保已删除数据及时从系统中消失，这对于存储敏感数据的服务非常重要。
6 改进 (Refinements)
前一节描述的实现需要进行一些改进，以实现用户要求的高性能、高可用性和高可靠性。本节更详细地描述了实现的部分内容，以突出这些改进。
局部性群组 (Locality groups)
客户端可以将多个列族分组到一个局部性群组 (locality group) 中。每个片中的每个局部性群组都会生成一个单独的 SSTable。将通常不一起访问的列族隔离到单独的局部性群组中可以实现更高效的读取。例如，Webtable 中的页面元数据（如语言和校验和）可以放在一个局部性群组中，而页面内容可以放在另一个不同的群组中：想要读取元数据的应用程序不需要通读所有页面内容。
此外，一些有用的调优参数可以在每个局部性群组的基础上指定。例如，一个局部性群组可以被声明为内存驻留 (in-memory)。内存驻留局部性群组的 SSTable 会被延迟加载到片服务器的内存中。一旦加载，属于此类局部性群组的列族可以在不访问磁盘的情况下读取。此特性对于访问频繁的小数据非常有用：我们在内部将其用于 METADATA 表中的位置 (location) 列族。
压缩 (Compression)
客户端可以控制局部性群组的 SSTable 是否压缩，以及如果压缩，使用哪种压缩格式。用户指定的压缩格式应用于每个 SSTable 块（其大小可通过局部性群组特定的调优参数控制）。尽管通过分别压缩每个块我们会损失一些空间，但我们受益于无需解压缩整个文件即可读取 SSTable 的一小部分。许多客户端使用两遍自定义压缩方案。第一遍使用 Bentley 和 McIlroy 的方案[6]，该方案在一个大窗口内压缩长公共字符串。第二遍使用一种快速压缩算法，在数据的 16 KB 小窗口中查找重复。两种压缩遍都非常快——在现代机器上，编码速度为 100-200 MB/s，解码速度为 400-1000 MB/s。
尽管在选择压缩算法时我们强调速度而不是空间缩减，但这种两遍压缩方案的表现却出奇地好。例如，在 Webtable 中，我们使用此压缩方案来存储网页内容。在一个实验中，我们在一个压缩的局部性群组中存储了大量文档。出于实验目的，我们限制自己只存储每个文档的一个版本，而不是所有可用版本。该方案实现了 10:1 的空间缩减。这比 HTML 页面上典型的 Gzip 缩减（3:1 或 4:1）要好得多，这是因为 Webtable 行的布局方式：来自同一域的所有页面彼此靠近存储。这使得 Bentley-McIlroy 算法能够识别来自同一域的大量共享模板（boilerplate）。许多应用程序，不仅仅是 Webtable，选择其行名是为了将相似的数据聚集在一起，因此获得了非常好的压缩比。当我们在 Bigtable 中存储同一值的多个版本时，压缩比甚至更好。
读性能缓存 (Caching for read performance)
为了提高读取性能，片服务器使用两级缓存。扫描缓存 (Scan Cache) 是较高级别的缓存，它缓存由 SSTable 接口返回给片服务器代码的键值对。块缓存 (Block Cache) 是较低级别的缓存，它缓存从 GFS 读取的 SSTable 块。扫描缓存对于倾向于重复读取相同数据的应用程序最有用。对于倾向于读取其最近读取数据的附近数据的应用程序（例如，顺序读取，或在热点行 (hot row) 内同一局部性群组中随机读取不同列），块缓存很有用。
布隆过滤器 (Bloom filters)
如第 5.3 节所述，读操作必须读取构成片状态的所有 SSTable。如果这些 SSTable 不在内存中，我们最终可能需要进行多次磁盘访问。我们通过允许客户端指定应为特定局部性群组中的 SSTable 创建布隆过滤器[7] 来减少访问次数。布隆过滤器允许我们询问某个 SSTable 是否可能包含指定行/列对的任何数据。对于某些应用程序，片服务器中用于存储布隆过滤器的少量内存能显著减少读操作所需的磁盘寻道次数。我们使用布隆过滤器还意味着大多数对不存在行或列的查找不需要接触磁盘。
提交日志实现 (Commit-log implementation)
如果我们为每个片在单独的文件中保留提交日志，在 GFS 中会同时写入非常大量的文件。根据每个 GFS 服务器底层文件系统的实现，这些写入可能导致大量的磁盘寻道以写入不同的物理日志文件。此外，每个片拥有单独的日志文件也降低了组提交优化的有效性，因为组往往会变小。为了解决这些问题，我们将变更追加到每个片服务器的单个提交日志中，将不同片的变更混合在同一个物理日志文件中[18, 20]。
在正常操作期间,使用单个日志提供了显著的性能优势，但它使恢复过程复杂化。当片服务器死亡时，它所服务的片将被移动到大量其他片服务器上：每个服务器通常加载原服务器的一小部分片。为了恢复某个片的状态，新的片服务器需要从原片服务器写入的提交日志中重新应用对应片的变更。然而，这些片的变更混合在同一个物理日志文件中。一种方法是让每个新的片服务器读取完整的提交日志文件，仅应用它要恢复的片所需的条目。然而，在这种方案下，如果 100 台机器各自从故障片服务器分配到一个片，那么日志文件将被读取 100 次（由每台服务器各读取一次）。
为避免免重复读取日志，我们对提交日志条目按格式 <table, row name, log sequence number> 排序。在排序后的输出中，特定片的所有变更都是连续的，因此可以通过一次磁盘寻道后接一次顺序读取来高效读取。为了并行化排序，我们将日志文件划分为 64 MB 的段，并在不同的片服务器上并行排序每个段。此排序过程由主节点协调，并在片服务器表明需要从某个提交日志文件恢复变更时启动。
向 GFS 写入提交日志有时会因各种原因导致性能间歇性波动（hiccups）（例如，参与写入的 GFS 服务器机器崩溃、到达特定三台 GFS 服务器的网络路径遭遇网络拥塞或负载过重）。为了防止数据变更受 GFS 延迟尖峰的影响，每个片服务器实际上有两个日志写入线程，每个线程写入其自己的日志文件；任何时候只有一个线程处于活动状态。如果对活动日志文件的写入性能不佳，日志文件写入将切换到另一个线程，处于提交日志队列中的变更是由新的日志写入线程进行写入。日志条目包含序列号，允许恢复过程消除因这种日志切换而产生的重复条目。
加速片恢复 (Speeding up tablet recovery)
如果主节点将片从一台片服务器移动到另一台片服务器，源片服务器首先对该片执行一次次要压缩。此压缩通过减少片服务器提交日志中未压缩状态的数据量来缩短恢复时间。完成此压缩后，片服务器停止服务该片。在它实际卸载该片之前，片服务器执行另一次（通常非常快的）次要压缩，以消除在第一轮次要压缩期间到达的、片服务器日志中任何剩余的未压缩状态。这第二次次要压缩完成后，该片可以在另一台片服务器上加载，而无需恢复任何日志条目。
利用不可变性 (Exploiting immutability)
除了 SSTable 缓存之外，Bigtable 系统的其他各个部分也因我们生成的所有 SSTable 都是不可变的这一事实而得以简化。例如，当我们从 SSTable 读取时，不需要对文件系统访问进行任何同步。因此，可以在行级别非常高效地实现并发控制。唯一同时被读和写访问的可变数据结构是内存表。为了减少读取内存表时的竞争，我们使每个内存表行成为写时复制（copy-on-write），并允许读取和写入并行进行。
由于 SSTable 是不可变的，永久删除数据的问题就转变为垃圾回收淘汰的 SSTable。每个片的 SSTable 在 METADATA 表中注册。主节点会移除淘汰的 SSTable 文件，这是对 SSTable 集合进行“标记-清除”式垃圾回收[25]，而 METADATA 表则包含了这些文件的根目录集合。
最后，SSTable 的不可变性使我们能够快速拆分片。我们不是为每个子片生成一组新的 SSTable，而是让子片共享父片的 SSTable。
7 性能评估 (Performance Evaluation)
我们设置了一个包含 N 个片服务器的 Bigtable 集群，以测量 Bigtable 在 N 变化时的性能和可扩展性。片服务器配置为使用 1 GB 内存，并将数据写入一个由 1786 台机器组成的 GFS 单元，每台机器有两个 400 GB IDE 硬盘。N 台客户端机器生成了用于这些测试的 Bigtable 负载。（我们使用与片服务器数量相同的客户端数量，以确保客户端永远不会成为瓶颈。）每台机器有两个双核 Opteron 2 GHz 处理器，足够的物理内存来容纳所有运行进程的工作集，以及一个千兆以太网链路。这些机器被布置在一个两级树形交换网络中，根节点总带宽约为 100-200 Gbps。所有机器位于同一个托管设施内，因此任意两台机器之间的往返时间小于一毫秒。
片服务器和主节点、测试客户端以及 GFS 服务器都运行在同一组机器上。每台机器运行一个 GFS 服务器。一些机器还运行片服务器进程、客户端进程或在测试期间同时使用资源池的其他作业的进程。
R 是测试中涉及的唯一 Bigtable 行键数量。选择 R 使得每个基准测试在每个片服务器上大约读取或写入 1 GB 数据。
顺序写 (sequential write) 基准测试使用的行键名称为 0 到 R-1。这个行键空间被划分为 10 N 个大小相等的范围。这些范围由一个中央调度器分配给 N 个客户端，该调度器在客户端完成前一个分配的范围后立即为其分配下一个可用的范围。这种动态分配有助于减轻由运行在客户端机器上的其他进程引起的性能变化的影响。我们为每个行键写入一个字符串。每个字符串是随机生成的，因此是不可压缩的。此外，不同行键下的字符串是不同的，因此无法进行跨行压缩。随机写 (random write) 基准测试类似，不同之处在于在写入之前立即对行键进行模 R 的哈希操作，以便在整个测试期间将写负载大致均匀地分布在整个行空间上。
顺序读 (sequential read) 基准测试生成行键的方式与顺序写基准测试完全相同，但它不是写入行键下的数据，而是读取存储在该行键下的字符串（由之前的顺序写基准测试写入）。类似地，随机读 (random read) 基准测试模拟了随机写基准测试的操作。
扫描 (scan) 基准测试类似于顺序读基准测试，但利用了 Bigtable API 提供的扫描行范围内所有值的功能。使用扫描减少了基准测试执行的 RPC 数量，因为单个 RPC 可以从片服务器获取大量连续的值。
随机读（内存）(random reads(mem)) 基准测试类似于随机读基准测试，但包含基准测试数据的局部性群组被标记为内存驻留，因此读取是从片服务器的内存中满足的，而不是需要 GFS 读取。仅针对此基准测试，我们将每个片服务器的数据量从 1 GB 减少到 100 MB，使其能舒适地放入片服务器可用内存中。
图 6 显示了我们在向 Bigtable 读写 1000 字节值时基准测试性能的两个视图。表格显示了每台片服务器每秒的操作数；图表显示了每秒的聚合操作总数。
单台片服务器性能 (Single tablet-server performance)
让我们首先考虑只有一台片服务器时的性能。随机读比其他所有操作慢一个数量级或更多。每次随机读涉及通过网络从 GFS 向片服务器传输一个 64 KB 的 SSTable 块，其中只有一个 1000 字节的值被使用。片服务器大约执行每秒 1200 次读取，这相当于大约每秒 75 MB 的数据从 GFS 读取。由于网络堆栈、SSTable 解析和 Bigtable 代码的开销，该带宽足以使片服务器的 CPU 饱和，并且也几乎足以使我们系统中使用的网络链路饱和。具有此类访问模式的大多数 Bigtable 应用程序会将块大小减小到更小的值，通常为 8KB。
从内存中进行随机读要快得多，因为每次 1000 字节的读取都是从片服务器的本地内存中满足的，无需从 GFS 获取大的 64 KB 块。
随机写和顺序写的性能优于随机读，因为每台片服务器将所有传入的写入追加到单个提交日志中，并使用组提交将这些写入高效地流式传输到 GFS。随机写和顺序写之间没有显著的性能差异；在两种情况下，对片服务器的所有写入都被记录在同一个提交日志中。
顺序读的性能优于随机读，因为从 GFS 获取的每个 64 KB SSTable 块都被存储到我们的块缓存中，用于服务接下来的 64 次读取请求。
扫描甚至更快，因为片服务器可以在响应单个客户端 RPC 时返回大量值，因此 RPC 开销被分摊到大量值上。
可扩展性 (Scaling)
随着我们将系统中的片服务器数量从 1 台增加到 500 台，聚合吞吐量急剧增加，超过了一百倍。例如，从内存中进行随机读的性能在片服务器数量增加 500 倍时提升了近 300 倍。这种行为发生是因为该基准测试的性能瓶颈在于单个片服务器的 CPU。
表 1：Bigtable 集群中片服务器数量的分布。
然而，性能并不是线性增长的。对于大多数基准测试，当从 1 台片服务器增加到 50 台时，每台服务器的吞吐量会显著下降。这种下降是由于在多服务器配置中存在负载不平衡造成的，通常是由于其他进程争用 CPU 和网络。我们的负载均衡算法试图处理这种不平衡，但无法做到完美，主要有两个原因：重新平衡受到限制以减少片移动的数量（片在移动时短时间内不可用，通常少于一秒），以及我们基准测试产生的负载会随着基准测试的进行而转移。
随机读基准测试显示出最差的可扩展性（服务器数量增加 500 倍时，聚合吞吐量仅增加了 100 倍）。这种行为的发生是因为（如上所述）我们为每次 1000 字节的读取通过网络传输一个大的 64KB 块。这种传输使我们网络中各种共享的 1 Gbps 链路饱和，因此，随着机器数量的增加，每台服务器的吞吐量显著下降。
8 实际应用 (Real Applications)
截至 2006 年 8 月，有 388 个非测试 Bigtable 集群在各种 Google 机器集群中运行，总共约有 24,500 台片服务器。表 1 显示了每个集群片服务器数量的粗略分布。许多这些集群用于开发目的，因此在相当长的时间内处于空闲状态。一组包含 14 个繁忙集群（总共 8069 台片服务器）的聚合请求量超过每秒 120 万次，传入 RPC 流量约为 741 MB/s，传出 RPC 流量约为 16 GB/s。
表 2 提供了当前使用中的一些表的数据。一些表存储提供给用户的数据，而其他表存储用于批处理的数据；这些表在总大小、平均单元大小、数据从内存提供的百分比以及表模式的复杂性方面差异很大。在本节的其余部分，我们简要描述三个产品团队如何使用 Bigtable。
表 2：生产中使用的几个表的特征。表大小（压缩前测量）和 ##Cells（单元数）表示近似大小。对于禁用压缩的表，不给出压缩比。
8.1 Google Analytics
Google Analytics (analytics.google.com) 是一项帮助网站管理员分析其网站流量模式的服务。它提供聚合统计信息，例如每天的独立访客数和每个 URL 每天的页面浏览量，以及网站跟踪报告，例如在用户先前查看过特定页面的前提下进行购买的百分比。
为了启用该服务，网站管理员在其网页中嵌入一个小型 JavaScript 程序。每当访问页面时都会调用此程序。它会将有关请求的各种信息记录到 Google Analytics，例如用户标识符和有关所获取页面的信息。Google Analytics 汇总这些数据并将其提供给网站管理员。
我们简要描述 Google Analytics 使用的两个表。原始点击表 (raw click table) (~200 TB) 为每个最终用户会话维护一行。行名是一个元组，包含网站名称和会话创建时间。此模式确保访问同一网站的会话是连续的，并且按时间顺序排序。该表压缩到其原始大小的 14%。
摘要表 (summary table) (~20 TB) 包含每个网站的各种预定义摘要。该表由定期调度的 MapReduce 作业从原始点击表生成。每个 MapReduce 作业从原始点击表中提取最近的会话数据。整个系统的吞吐量受限于 GFS 的吞吐量。该表压缩到其原始大小的 29%。
8.2 Google Earth
Google 运营着一系列服务，为用户提供对地球表面高分辨率卫星图像的访问，既通过基于 Web 的 Google Maps 接口 (maps.google.com)，也通过 Google Earth (earth.google.com) 自定义客户端软件。这些产品允许用户在地球表面导航：他们可以平移、查看不同分辨率级别的卫星图像并进行标注。该系统使用一个表进行数据预处理，另一组表用于服务客户端数据。
预处理流水线使用一个表来存储原始图像。在预处理过程中，图像被清理并整合成最终的服务数据。该表包含大约 70 TB 的数据，因此从磁盘提供服务。图像本身已经过高效压缩，因此禁用了 Bigtable 压缩。
Google Earth 服务系统使用一个表来索引存储在 GFS 中的数据。该表相对较小（~500 GB），但它必须在每个数据中心以低延迟提供每秒数万次查询。因此，该表分布在数百台片服务器上，并包含内存驻留列族。
8.3 个性化搜索 (Personalized Search)
个性化搜索 (www.google.com/spearch) 是一项选择加入的服务，记录用户在各种 Google 属性（如网页搜索、图片和新闻）上的查询和点击。用户可以浏览他们的搜索历史以重新访问旧的查询和点击，并且可以要求基于其历史 Google 使用模式的个性化搜索结果。
个性化搜索将每个用户的数据存储在 Bigtable 中。每个用户有一个唯一的 userid，并被分配一个以该 userid 命名的行。所有用户操作都存储在一个表中。为每种操作类型保留一个单独的列族（例如，有一个列族存储所有网页查询）。每个数据元素使用其对应的用户操作发生时间作为其 Bigtable 时间戳。个性化搜索使用在 Bigtable 上运行的 MapReduce 生成用户画像。这些用户画像用于个性化实时搜索结果。
个性化搜索数据在多个 Bigtable 集群之间复制，以提高可用性并减少因与客户端的距离而产生的延迟。个性化搜索团队最初在 Bigtable 之上构建了一个客户端复制机制，以确保所有副本的最终一致性。当前系统现在使用内置于服务器中的复制子系统。
个性化搜索存储系统的设计允许其他小组在他们自己的列中添加新的每用户信息，该系统现在被许多需要存储每用户配置选项和设置的 Google 属性所使用。在多个小组之间共享一个表导致了异常多的列族。为了帮助支持共享，我们在 Bigtable 中添加了一个简单的配额机制，以限制共享表中任何特定客户端的存储消耗；该机制在使用此系统存储每用户信息的不同产品组之间提供了一定程度的隔离。
9 经验教训 (Lessons)
在设计、实现、维护和支持 Bigtable 的过程中，我们获得了有用的经验，并学到了一些有趣的经验教训。
我们学到的一个教训是，大型分布式系统容易受到多种类型故障的影响，而不仅仅是许多分布式协议中假设的标准网络分区和故障停止故障。例如，我们遇到过由以下所有原因引起的问题：内存和网络损坏、大的时钟偏差、挂起的机器、长期和不对称的网络分区、我们正在使用的其他系统中的错误（例如 Chubby）、GFS 配额溢出以及计划内和计划外的硬件维护。随着我们在处理这些问题方面获得更多经验，我们通过更改各种协议来解决它们。例如，我们在 RPC 机制中添加了校验和。我们还通过移除系统某一部分对另一部分的假设来处理一些问题。例如，我们不再假设某个 Chubby 操作只能返回一组固定错误中的一个。
我们学到的另一个教训是，延迟添加新功能直到清楚新功能将如何使用是重要的。例如，我们最初计划在我们的 API 中支持通用事务。然而，由于我们当时没有立即需要它们，因此没有实现它们。现在，我们有许多真实的应用程序运行在 Bigtable 上，我们能了解查它们的实际需求，并发现大多数应用程序只需要单行事务。人们要求分布式事务，最重要的用途是维护辅助索引（secondary indices），我们计划添加一个专门的机制来满足这一需求。新机制将不如分布式事务通用，但会更高效（特别是对于跨越数百行或更多行的更新），并且也能更好地与我们用于乐观的跨数据中心复制的方案交互。
我们从支持 Bigtable 中获得的一个实践教训是系统级监控的重要性（即同时监控 Bigtable 本身以及使用 Bigtable 的客户端进程）。例如，我们扩展了 RPC 系统，使得对于采样的 RPC，它会详细跟踪为该 RPC 执行的重要操作。此功能使我们能够检测和修复许多问题，例如片数据结构上的锁争用、提交 Bigtable 变更时向 GFS 写入缓慢，以及在 METADATA 片不可用时访问 METADATA 表卡住。另一个有用的监控例子是每个 Bigtable 集群都在 Chubby 中注册。这使我们能够跟踪所有集群，了解它们有多大，查看它们运行我们软件的哪个版本，它们接收多少流量，以及是否存在任何问题，例如意外的大延迟。
我们学到的最重要的教训是简单设计的价值。考虑到我们系统的规模（约 10 万行非测试代码），以及代码会随着时间以意想不到的方式演化的事实，我们发现代码和设计的清晰度对代码维护和调试有巨大的帮助。一个例子是我们的片服务器成员资格协议。我们的第一个协议很简单：主节点定期向片服务器发放租约，如果租约到期，片服务器会终止自己。不幸的是，该协议在网络问题存在时显著降低了可用性，并且也对主节点恢复时间敏感。我们多次重新设计该协议，直到得到一个性能良好的协议。然而，得到的协议过于复杂，并且依赖于 Chubby 中很少被其他应用程序使用的特性。我们发现我们花费了过多时间调试晦涩的边界情况，不仅是在 Bigtable 代码中，也在 Chubby 代码中。最终，我们废弃了该协议，转而采用一个仅依赖于广泛使用的 Chubby 特性的更新、更简单的协议。
10 相关工作 (Related Work)
Boxwood 项目[24] 的组件在某种程度上与 Chubby、GFS 和 Bigtable 有重叠，因为它提供了分布式协议、锁定、分布式块存储和分布式 B 树存储。在每种存在重叠的情况下，Boxwood 的组件似乎都定位在比相应 Google 服务更低的层次上。Boxwood 项目的目标是为构建更高级别的服务（如文件系统或数据库）提供基础设施，而 Bigtable 的目标是直接支持希望存储数据的客户端应用程序。
许多最近的项目解决了在广域网上提供分布式存储或更高级别服务的问题，通常是在“互联网规模”。这包括始于 CAN[29]、Chord[32]、Tapestry[37] 和 Pastry[30] 等项目的分布式哈希表 (DHT) 的工作。这些系统处理的问题在 Bigtable 中不会出现，例如高度可变的带宽、不受信任的参与者或频繁的重新配置；去中心化控制和拜占庭容错不是 Bigtable 的目标。
就提供给应用程序开发者的分布式数据存储模型而言，我们认为由分布式 B 树或分布式哈希表提供的键值对模型过于局限。键值对是一个有用的构建块，但它不应该是提供给开发者的唯一构建块。我们选择的模型比简单的键值对更丰富，并且支持稀疏的半结构化数据。尽管如此，它仍然足够简单，使其适用于非常高效的平面文件表示，并且（通过局部性群组）足够透明，允许我们的用户调整系统的重要行为。
几家数据库供应商已经开发了可以存储海量数据的并行数据库。Oracle 的 Real Application Cluster 数据库[27] 使用共享磁盘存储数据（Bigtable 使用 GFS）和一个分布式锁管理器（Bigtable 使用 Chubby）。IBM 的 DB2 Parallel Edition[4] 基于类似于 Bigtable 的 shared-nothing[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 使用内存表和 SSTable 存储片更新的方式类似于日志结构合并树 (Log-Structured Merge Tree)[26] 存储索引更新的方式。在两个系统中，排序的数据在写入磁盘之前被缓冲在内存中，并且读取必须合并来自内存和磁盘的数据。
C-Store 和 Bigtable 共享许多特征：两个系统都使用 shared-nothing 架构，并有两种不同的数据结构，一种用于最近的写入，一种用于存储长期存在的数据，并带有一种将数据从一种形式移动到另一种形式的机制。系统在它们的 API 上有显著差异：C-Store 的行为类似于关系数据库，而 Bigtable 提供更低级别的读写接口，并设计为支持每台服务器每秒数千次此类操作。C-Store 也是一个“读优化的关系 DBMS”，而 Bigtable 在读密集型和写密集型应用上都提供良好的性能。
Bigtable 的负载均衡器必须解决与非共享数据库所面临的负载和内存平衡问题类似的一些问题（例如，[11, 35]）。我们的问题稍微简单一些：(1) 我们不考虑同一数据的多个副本（可能由于视图或索引导致形式不同）的可能性；(2) 我们让用户告诉我们哪些数据应在内存中，哪些数据应保留在磁盘上，而不是试图动态确定；(3) 我们没有复杂的查询需要执行或优化。
11 结论 (Conclusions)
我们描述了 Bigtable，一个用于在 Google 存储结构化数据的分布式系统。Bigtable 集群自 2005 年 4 月起已投入生产使用，在此之前我们花了大约七人年进行设计和实现。截至 2006 年 8 月，超过六十个项目正在使用 Bigtable。我们的用户喜欢 Bigtable 实现所提供的性能和高可用性，并且他们可以在资源需求随时间变化时，通过简单地向系统添加更多机器来扩展其集群的容量。
鉴于 Bigtable 的非寻常接口，一个有趣的问题是用户适应使用它的难度有多大。新用户有时不确定如何最好地利用 Bigtable 接口，特别是如果他们习惯于使用支持通用事务的关系数据库。尽管如此，许多 Google 产品成功使用 Bigtable 的事实证明了我们的设计在实践中运行良好。
我们正在实施几项额外的 Bigtable 功能，例如对二级索引 (secondary indices) 的支持以及用于构建具有多个主副本的跨数据中心复制的 Bigtable 的基础设施。我们也已开始将 Bigtable 作为服务 (as a service) 部署给产品团队，这样单个团队就不需要维护自己的集群。随着我们的服务集群规模扩大，我们将需要在 Bigtable 内部处理更多的资源共享问题[3, 5]。
最后，我们发现，在 Google 构建我们自己的存储解决方案 (building our own storage solution) 具有显著优势。通过为 Bigtable 设计我们自己的数据模型，我们获得了极大的灵活性。此外，我们对 Bigtable 实现以及 Bigtable 所依赖的其他 Google 基础设施的控制，意味着我们可以在瓶颈和低效问题出现时移除它们。
致谢 (Acknowledgements)
我们感谢匿名审稿人、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, and Arthur Zwiegincew。
以下是以 Markdown 格式呈现的完整参考文献列表，包含所有 38 项引用，并添加了权威来源链接。原始文献信息完整保留，未做翻译处理：
📚 参考文献 (References)
ABADI, D. J., MADDEN, S. R., AND FERREIRA, M. C.
https://dl.acm.org/doi/10.1145/1142473.1142540.
Proc. of SIGMOD (2006).AILAMAKI, A., DEWITT, D. J., HILL, M. D., AND SKOUNAKIS, M.
https://link.springer.com/article/10.1007/s007780100052.
In The VLDB Journal (2001), pp. 169-180.BANGA, G., DRUSCHEL, P., AND MOGUL, J. C.
https://www.usenix.org/legacy/publications/library/proceedings/osdi99/full_papers/banga/banga.pdf.
In Proc. of the 3rd OSDI (Feb. 1999), pp. 45-58.BARU, C. K., FECTEAU, G., GOYAL, A., HSIAO, H., JHINGRAN, A., PADMANABHAN, S., COPELAND, G. P., AND WILSON, W. G.
https://ieeexplore.ieee.org/document/5389461.
IBM Systems Journal 34, 2 (1995), 292-322.BAVIER, A., BOWMAN, M., CHUN, B., CULLER, D., KARLIN, S., PETERSON, L., ROSCOE, T., SPALINK, T., AND WAWRZONIAK, M.
https://www.usenix.org/legacy/events/nsdi04/tech/full_papers/bavier/bavier.pdf.
In Proc. of the 1st NSDI (Mar. 2004), pp. 253-266.BENTLEY, J. L., AND MCILROY, M. D.
https://ieeexplore.ieee.org/document/755679.
In Data Compression Conference (1999), pp. 287-295.BLOOM, B. H.
https://dl.acm.org/doi/10.1145/362686.362692.
CACM 13, 7 (1970), 422-426.BURROWS, M.
https://static.googleusercontent.com/media/research.google.com/en//archive/chubby-osdi06.pdf.
In Proc. of the 7th OSDI (Nov. 2006).CHANDRA, T., GRIESEMER, R., AND REDSTONE, J.
https://dl.acm.org/doi/10.1145/1281100.1281103.
In Proc. of PODC (2007).COMER, D.
https://dl.acm.org/doi/10.1145/356770.356776.
Computing Surveys 11, 2 (June 1979), 121-137.COPELAND, G. P., ALEXANDER, W., BOUGHTER, E. E., AND KELLER, T. W.
https://dl.acm.org/doi/10.1145/50202.50214.
In Proc. of SIGMOD (1988), pp. 99-108.DEAN, J., AND GHEMAWAT, S.
https://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf.
In Proc. of the 6th OSDI (Dec. 2004), pp. 137-150.DEWITT, D., KATZ, R., OLKEN, F., SHAPIRO, L., STONEBRAKER, M., AND WOOD, D.
https://dl.acm.org/doi/10.1145/602260.602261.
In Proc. of SIGMOD (June 1984), pp. 1-8.DEWITT, D. J., AND GRAY, J.
https://dl.acm.org/doi/10.1145/129726.129727.
CACM 35, 6 (June 1992), 85-98.FRENCH, C. D.
https://dl.acm.org/doi/10.1145/223784.223844.
In Proc. of SIGMOD (May 1995), pp. 449-450.GAWLICK, D., AND KINKADE, D.
https://dl.acm.org/doi/10.5555/1287331.1287344.
Database Engineering Bulletin 8, 2 (1985), 3-10.GHEMAWAT, S., GOBIOFF, H., AND LEUNG, S.-T.
https://static.googleusercontent.com/media/research.google.com/en//archive/gfs-sosp2003.pdf.
In Proc. of the 19th ACM SOSP (Dec. 2003), pp. 29-43.GRAY, J.
https://dsf.berkeley.edu/cs286/papers/dbos-1978.pdf.
In Operating Systems—An Advanced Course, vol. 60 of Lecture Notes in Computer Science. Springer-Verlag, 1978.GREER, R.
https://dl.acm.org/doi/10.1145/304181.304584.
In Proc. of SIGMOD (1999), pp. 525-526.HAGMANN, R.
https://dl.acm.org/doi/10.1145/41457.37504.
In Proc. of the 11th SOSP (Dec. 1987), pp. 155-162.HARTMAN, J. H., AND OUSTERHOUT, J. K.
https://dl.acm.org/doi/10.1145/168619.168625.
In Proc. of the 14th SOSP (Asheville, NC, 1993), pp. 29-43.KX.COM.
https://kx.com/products/kdb-q-database/.
Product page.LAMPORT, L.
https://dl.acm.org/doi/10.1145/279227.279229.
ACM TOCS 16, 2 (1998), 133-169.MACCORMICK, J., MURPHY, N., NAJORK, M., THEKKATH, C. A., AND ZHOU, L.
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/osdi2004-boxwood.pdf.
In Proc. of the 6th OSDI (Dec. 2004), pp. 105-120.MCCARTHY, J.
https://dl.acm.org/doi/10.1145/367177.367199.
CACM 3, 4 (Apr. 1960), 184-195.O'NEIL, P., CHENG, E., GAWLICK, D., AND O'NEIL, E.
https://dl.acm.org/doi/10.1007/s002360050048.
Acta Inf. 33, 4 (1996), 351-385.ORACLE.COM.
https://www.oracle.com/database/real-application-clusters/.
Product page.PIKE, R., DORWARD, S., GRIESEMER, R., AND QUINLAN, S.
https://research.google/pubs/pub32062/.
Scientific Programming Journal 13, 4 (2005), 227-298.RATNASAMY, S., FRANCIS, P., HANDLEY, M., KARP, R., AND SHENKER, S.
https://dl.acm.org/doi/10.1145/383059.383072.
In Proc. of SIGCOMM (Aug. 2001), pp. 161-172.ROWSTRON, A., AND DRUSCHEL, P.
https://dl.acm.org/doi/10.5555/646591.697650.
In Proc. of Middleware 2001 (Nov. 2001), pp. 329-350.SENSAGE.COM.
https://www.servicenow.com/products/security-operations.html.
Product page.STOICA, I., MORRIS, R., KARGER, D., KAASHOEK, M. F., AND BALAKRISHNAN, H.
https://dl.acm.org/doi/10.1145/383059.383071.
In Proc. of SIGCOMM (Aug. 2001), pp. 149-160.STONEBRAKER, M.
https://dl.acm.org/doi/10.5555/10921.10922.
Database Engineering Bulletin 9, 1 (Mar. 1986), 4-9.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.
https://dl.acm.org/doi/10.5555/1083592.1083658.
In Proc. of VLDB (Aug. 2005), pp. 553-564.STONEBRAKER, M., AOKI, P. M., DEVINE, R., LITWIN, W., AND OLSON, M. A.
https://ieeexplore.ieee.org/document/295083.
In Proc. of the Tenth ICDE (1994), IEEE Computer Society, pp. 54-65.SYBASE.COM.
https://www.sap.com/products/sybase-iq.html.
Product page.ZHAO, B. Y., KUBIATOWICZ, J., AND JOSEPH, A. D.
https://www2.eecs.berkeley.edu/Pubs/TechRpts/2001/CSD-01-1141.pdf.
Tech. Rep. UCB/CSD-01-1141, CS Division, UC Berkeley, Apr. 2001.ZUKOWSKI, M., BONCZ, P. A., NES, N., AND HEMAN, S.
https://www.cidrdb.org/cidr2005/papers/P19.pdf.
IEEE Data Eng. Bull. 28, 2 (2005), 17-22.