ThinkLab

引言

文章引言

在过去的两年半时间里，我们设计、实现并部署了一个名为 Bigtable 的分布式存储系统，用于在 Google 内部管理结构化数据。Bigtable 的设计目标是能够在数千台机器上可靠地扩展至 PB 级的数据。Bigtable 已经实现了若干目标：广泛适用性、可扩展性、高性能和高可用性。目前，超过六十个 Google 产品和项目使用了 Bigtable，包括 Google Analytics、Google Finance、Orkut、个性化搜索、Writely 和 Google Earth。这些产品对 Bigtable 的使用场景多样，从 面向吞吐量的批处理任务 到 对用户数据请求的低延迟响应。

这些产品所依赖的 Bigtable 集群配置差异极大：从少量服务器到上千台服务器不等，存储的数据量则从数十 TB 到数百 TB 不等。在许多方面，Bigtable 类似于数据库：它与数据库共享了许多实现策略。并行数据库 [14] 和内存数据库 [13] 已经在可扩展性和高性能方面取得了成就，但 Bigtable 提供了与这些系统不同的接口。

Bigtable 不支持完整的关系数据模型；相反，它为客户端提供了一种简单的数据模型，支持对数据布局和格式的动态控制，并允许客户端推理底层存储中数据的局部性特征。数据通过 行键（row key）和列名（column name） 进行索引，这些名称可以是任意字符串。Bigtable 将数据视为 未解释的字符串，但客户端通常会将各种结构化或半结构化的数据序列化为这些字符串。客户端可以通过在 模式设计（schema） 中的选择来控制数据的局部性。最后，Bigtable 的模式参数允许客户端动态控制数据是从内存还是磁盘中提供服务。

第 2 节 将更详细地描述数据模型，第 3 节 概述客户端 API，第 4 节 简要介绍 Bigtable 所依赖的 Google 基础设施。第 5 节 描述 Bigtable 的核心实现原理，第 6 节 介绍了一些性能优化的改进。第 7 节 提供了性能测试数据，第 8 节 描述了 Bigtable 在 Google 内部的使用实例。第 9 节 总结了在设计和支持 Bigtable 过程中获得的一些经验，第 10 节 介绍了相关工作，第 11 节 给出了结论。

数据模型

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

bigtableeg

图 1： 示例表的一部分，用于存储网页。行名为反转后的 URL。contents 列族包含网页内容，anchor 列族包含所有指向该网页的锚文本。CNN 的主页同时被 Sports Illustrated 和 MY-look 的主页引用，因此该行包含名为 anchor:cnnsi.com 和 anchor:my.look.ca 的列。每个锚点单元格只有一个版本，而 contents 列在时间戳 t3、t5 和 t6 下具有三个版本。

形式化表示为：

(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 family），它是访问控制的基本单位。通常，一个列族中的所有数据类型相同（我们会对同一列族中的数据一起压缩）。列族必须在使用前显式创建；创建后，可以在该列族下使用任意列键。我们设计的目标是：一个表中的列族数量应保持较少（最多几百个），并且在运行过程中很少发生变动。相比之下，一个表可以包含无限数量的列。

列键的命名规则为：

family:qualifier

其中，列族名必须是可打印字符串，但限定符（qualifier）可以是任意字符串。

例如，在 Webtable 中，一个有用的列族是 language，用于存储网页所使用的语言。该列族中仅使用一个列键，存储每个网页的语言 ID。另一个重要的列族是 anchor；该列族中的每个列键表示一个外部锚点（参见图 1）。限定符是引用站点的名称，单元格内容则为链接文本。

访问控制、磁盘与内存资源核算均在列族级别进行。在 Webtable 示例中，这些控制使我们能够管理多种不同类型的应用：一些用于新增基础数据，一些用于读取基础数据并生成派生列族，还有一些应用只能查看现有数据（出于隐私原因，甚至可能无法查看所有列族）。

时间戳（Timestamps）

Bigtable 中的每个单元格可以包含同一数据的多个版本，这些版本通过 时间戳 进行索引。时间戳是 64 位整数。它们可以由 Bigtable 自动分配（此时表示微秒级的“真实时间”），也可以由客户端应用显式分配。若应用需避免冲突，则必须自行生成唯一的时间戳。

同一单元格的多个版本按照 时间戳递减顺序 存储，因此最新版本总是最先被读取。为简化版本化数据的管理，Bigtable 支持两种 列族级别的垃圾回收策略：

仅保留最近的 n 个版本；
仅保留足够新的版本（例如，仅保留最近 7 天写入的值）。

在 Webtable 示例中，contents: 列下网页的时间戳设置为网页被抓取的时间。通过上述垃圾回收机制，我们可以仅保留每个页面最近的 三个版本。

图2：写入BigTable

// 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：读取BigTable

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

API

Bigtable API 提供了 创建和删除表及列族 的功能，同时还支持修改 集群、表和列族的元数据，例如访问控制权限。

客户端应用可以在 Bigtable 中 写入或删除值，从单独的行中查找数据，或者迭代表中某一部分数据。图 2 展示了使用 RowMutation 抽象进行一系列更新的 C++ 代码（为简洁起见省略了部分无关细节）。Apply 调用会对 Webtable 执行一个 原子变更：它向 www.cnn.com 添加一个锚点，同时删除另一个锚点。

图 3 展示了使用 Scanner 抽象在某一行中迭代所有锚点的 C++ 代码。客户端可以在多个列族之间迭代，并且有多种机制来限制扫描结果的 行、列和时间戳。例如，我们可以限制扫描只返回列名匹配正则表达式 anchor:*.cnn.com 的锚点，或者只返回 时间戳在当前时间前后 10 天范围内 的锚点。

Bigtable 还支持一些更复杂的数据操作功能：

单行事务：支持在单行键下执行原子性的 读-修改-写 操作。目前 Bigtable 尚不支持跨行键的一般事务，但提供了客户端侧跨行批量写接口。
整数计数器：单元格可以作为整数计数器使用。
执行用户脚本：Bigtable 支持在服务器地址空间中执行客户端提供的脚本。这些脚本使用 Google 为数据处理开发的语言 Sawzall [28] 编写。目前基于 Sawzall 的 API 不允许脚本回写数据到 Bigtable，但它支持多种形式的数据转换、基于任意表达式的过滤，以及通过多种操作符进行数据汇总。

此外，Bigtable 可以与 MapReduce [12] 协同使用。MapReduce 是 Google 开发的一个用于大规模并行计算的框架。我们编写了一组封装器，使得 Bigtable 可以同时作为 MapReduce 作业的输入源和输出目标。

构建基石

Bigtable 建立在 Google 的若干基础设施之上。它使用 分布式 Google 文件系统（GFS） [17] 来存储日志和数据文件。一个 Bigtable 集群通常运行在一个共享的机器池中，这些机器同时运行着各种分布式应用，Bigtable 进程往往与其他应用的进程共享同一台机器。Bigtable 依赖于 集群管理系统 来进行作业调度、共享机器上的资源管理、处理机器故障以及监控机器状态。

Bigtable 内部使用 Google SSTable 文件格式 存储数据。SSTable 提供了一个 持久的、有序的、不可变的键值映射，其中键和值都是任意字节串。它支持根据指定键查找对应值，也支持遍历指定键区间内的所有键值对。

在实现上，每个 SSTable 由一系列块组成（典型块大小为 64KB，但可配置）。一个 块索引 存储在 SSTable 文件末尾，并在文件打开时加载到内存中。查找操作只需一次磁盘寻道：首先在内存索引中通过二分查找定位目标块，然后从磁盘中读取对应的块。可选地，SSTable 也可以被完全映射到内存，从而支持在不访问磁盘的情况下完成查找和扫描。

Bigtable 依赖于一个 高可用的持久化分布式锁服务 Chubby [8]。一个 Chubby 服务由五个活动副本组成，其中一个被选举为主节点来处理请求。当多数副本存活并能互相通信时，服务即被认为可用。Chubby 使用 Paxos 算法 [9, 23] 来在故障情况下保持副本一致性。

Chubby 提供了一个由 目录和小文件 组成的命名空间。每个目录或文件都可以用作锁，对文件的读写操作是原子的。Chubby 客户端库提供了一致性的文件缓存。每个客户端与 Chubby 服务保持一个会话；若客户端未能在租约到期前续约，会话将过期，此时客户端会失去所有的锁和文件句柄。Chubby 客户端还可以在目录或文件上注册回调，以便在文件变更或会话过期时收到通知。

Bigtable 使用 Chubby 来完成多种任务：

确保任一时刻只有一个活动的 主控节点（master）；
存储 Bigtable 数据的 引导位置（见第 5.1 节）；
发现 tablet 服务器 并确认其失效（见第 5.2 节）；
存储 Bigtable 模式信息（每个表的列族信息）；
存储 访问控制列表。

如果 Chubby 长时间不可用，Bigtable 也会随之不可用。我们最近在 14 个 Bigtable 集群（覆盖 11 个 Chubby 实例）中对这一影响进行了测量：由于 Chubby 故障或网络问题导致 Bigtable 数据不可用的时间占比，平均为 0.0047%；在受影响最严重的单个集群中，该比例为 0.0326%。

实现

Bigtable 的实现包含三个主要组件：客户端库（链接到每个客户端）、一个主服务器（master）、以及 多个 tablet 服务器。Tablet 服务器可以根据工作负载的变化动态添加或移除。

主服务器（master） 负责：

将 tablets 分配给 tablet 服务器；
检测 tablet 服务器的加入与过期；
进行负载均衡；
回收 GFS 中的垃圾文件；
处理模式变更（如表和列族的创建）。

每个 tablet 服务器 管理一组 tablets（通常在 10 ~ 1000 个之间）。它负责所加载 tablets 的读写请求，同时还会对过大的 tablet 进行分裂。

与许多单主分布式存储系统类似 [17, 21]，客户端数据不会经过主服务器：客户端直接与 tablet 服务器通信以完成读写。由于客户端不依赖主服务器获取 tablet 位置，大多数客户端几乎不会与主服务器交互，因此主服务器在实际运行中负载较轻。

一个 Bigtable 集群存储多个表，每个表由一组 tablets 组成，每个 tablet 包含一个 行区间（row range） 的所有数据。最初，每个表只有一个 tablet。随着表的增大，它会被自动拆分为多个 tablets，默认每个大小约为 100–200 MB。

Tablet 定位

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

图4：Tablet定位层次结构

bigtable-4

第一层：一个存储在 Chubby 中的文件，记录根 tablet（root tablet）的位置。
根 tablet：包含一个特殊 METADATA 表 中所有 tablets 的位置。
METADATA tablets：包含一组用户 tablets 的位置信息。

根 tablet 实际上就是 METADATA 表中的第一个 tablet，但它有特殊处理：永不分裂，以确保 tablet 定位层级不超过三层。

METADATA 表 通过行键存储 tablet 的位置，行键由 tablet 的表标识符（table identifier）与其 结束行（end row） 编码而成。每行大约占用 1KB 内存。即使限定 METADATA tablet 的大小为 128MB，这一三层结构也足以寻址 2³⁴ 个 tablets（约等于在 128MB tablets 中寻址 2⁶¹ 字节 数据）。

客户端库会缓存 tablet 位置。如果客户端不知道某个 tablet 的位置，或者发现缓存信息错误，它会递归地向上查询 tablet 定位层级：

缓存为空 时，定位算法需要 3 次网络往返，其中包括一次 Chubby 读取。
缓存过期 时，可能需要 最多 6 次往返，因为只有在查询未命中时才会发现缓存失效（假设 METADATA tablets 不会频繁迁移）。

虽然 tablet 位置信息存储在内存中（因此不需要访问 GFS），我们仍进一步优化了常见情况：客户端库会预取 tablet 位置，即在读取 METADATA 表时获取多个 tablets 的元数据。

此外，我们还在 METADATA 表 中存储了辅助信息，例如每个 tablet 的事件日志（如某服务器开始服务该 tablet 的时间）。这些信息对于 调试和性能分析 非常有帮助。

Tablet 分配

每个 tablet 在同一时刻只会被分配给一个 tablet 服务器。主服务器（master） 负责维护存活的 tablet 服务器集合，以及当前 tablets 的分配情况（包括未分配的 tablets）。当某个 tablet 尚未分配，而有合适的 tablet 服务器可用时，master 会向该服务器发送 加载请求 来完成分配。

Bigtable 使用 Chubby 来跟踪 tablet 服务器。当一个 tablet 服务器启动时，它会在指定的 Chubby 目录中创建一个具有唯一名称的文件，并获得该文件的独占锁。master 通过监控这个目录（servers 目录）来发现 tablet 服务器。如果某个 tablet 服务器失去了独占锁（例如，由于网络分区导致它失去了 Chubby 会话），它会停止提供 tablets 服务。（Chubby 提供了一种高效机制，使得 tablet 服务器无需网络流量即可检查自己是否仍持有锁。）

Tablet 服务器会不断尝试重新获取该文件的独占锁，只要该文件仍然存在。
如果文件被删除，tablet 服务器将永远无法再次提供服务，因此会主动终止自身进程。
当 tablet 服务器终止（例如，集群管理系统移除了运行该服务器的机器），它会尝试释放锁，以便 master 更快地重新分配其 tablets。

master 的职责是检测 tablet 服务器是否不再提供服务，并尽快重新分配这些 tablets。

master 会周期性地向每个 tablet 服务器查询其锁的状态。
如果 tablet 服务器报告丢失了锁，或者 master 在多次尝试后无法与该服务器通信，master 会尝试获取该服务器文件的独占锁。
- 如果成功，说明 Chubby 仍然可用，而该 tablet 服务器要么已宕机，要么无法访问 Chubby。
- master 会删除该服务器文件，确保该服务器 永远无法再次提供服务。
一旦服务器文件被删除，master 就可以将该服务器先前负责的所有 tablets 移入 未分配集合，并重新分配。

为了避免 Bigtable 集群因 master 与 Chubby 之间的网络问题而陷入不一致，如果 master 的 Chubby 会话过期，master 会主动终止自己。不过，如前所述，master 故障并不会改变 tablet 与服务器之间的分配关系。

当集群管理系统启动一个 master 时，它需要先发现当前的 tablet 分配情况，然后才能进行修改。master 在启动时执行以下步骤：

在 Chubby 中获取一个 唯一的 master 锁，防止并发出现多个 master。
扫描 Chubby 中的 servers 目录，找到所有存活的服务器。
与每个存活的 tablet 服务器通信，获取其已分配的 tablets。
扫描 METADATA 表，以获取完整的 tablet 集合。

在第 4 步中，如果遇到尚未分配的 tablet，master 会将其加入 未分配集合，使其进入分配流程。

一个问题是：必须先分配 METADATA tablets，才能扫描它们。因此，在第 4 步之前，如果第 3 步未发现 root tablet 的分配，master 会将 root tablet 加入未分配集合，从而确保它会被分配。由于 root tablet 包含所有 METADATA tablets 的位置信息，master 在扫描 root tablet 后就能获知全部 METADATA tablets。

Tablet 集合的变化来源有四种：

创建表；
删除表；
合并两个现有 tablets 形成一个更大的 tablet；
将一个现有 tablet 拆分为两个更小的 tablets。

除最后一种情况外，所有变化均由 master 发起，因此 master 能够追踪这些变化。tablet 拆分由 tablet 服务器发起，并通过在 METADATA 表中记录新 tablet 信息来提交。当拆分提交完成后，tablet 服务器会通知 master。

如果通知丢失（例如 tablet 服务器或 master 在此时崩溃），master 会在之后让服务器加载已拆分的 tablet 时检测到该情况：tablet 服务器会报告 tablet 已拆分，因为它在 METADATA 表中找到的条目只覆盖 master 请求加载的部分数据。这样 master 仍能获知拆分的发生。

Tablet 服务

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

图5：Tablet表示

bigtable-5

更新操作 首先被写入 提交日志（commit log），日志中保存重做（redo）记录。
最近提交的更新存储在内存中的有序缓冲区 memtable 中；较旧的更新则存储在一系列 SSTables 中。

要恢复一个 tablet 时，tablet 服务器会：

从 METADATA 表 中读取其元数据；
获取组成该 tablet 的所有 SSTables 列表和一组 redo 点（指向可能包含该 tablet 数据的提交日志）；
将 SSTables 的索引加载到内存；
从 redo 点起应用所有提交的更新，重建 memtable。

写操作流程：

Tablet 服务器检查写请求是否格式正确，以及请求方是否有权限执行该更新。
授权检查通过读取 Chubby 文件中允许写入者的列表完成（几乎总是命中本地缓存）。
合法更新会写入提交日志，并使用 批量提交（group commit） 技术提升小更新的吞吐量 [13, 16]。
提交完成后，数据会被插入 memtable。

读操作流程：

类似地，读请求也会被检查格式和权限。
合法的读请求会在 SSTables 与 memtable 的合并视图 上执行。
由于两者都按字典序排序，合并视图可以高效构建。

在 tablets 分裂或合并 时，新的读写请求仍可继续执行。

压缩（Compactions）

随着写操作的执行，memtable 的大小逐渐增加。当 memtable 达到阈值时：

该 memtable 被冻结；
创建一个新的 memtable；
冻结的 memtable 被转换为 SSTable 并写入 GFS。

这一过程称为 小压缩（minor compaction），目的有二：

减少 tablet 服务器的内存使用；
若服务器崩溃，减少恢复时需要从提交日志中读取的数据量。

在压缩期间，新的读写操作仍可继续。

每次小压缩都会生成一个新的 SSTable。若无限制地生成 SSTables，读操作可能需要合并任意数量的文件。为此，系统在后台周期性执行 合并压缩（merging compaction）：

读取多个 SSTables 与 memtable 的内容；
输出一个新的 SSTable；
输入文件在压缩完成后即可丢弃。

当合并压缩将所有 SSTables 重写为 单个 SSTable 时，这一过程称为 大压缩（major compaction）。

非大压缩生成的 SSTables 可能包含特殊的删除标记（deletion entries），用于屏蔽仍存活的旧 SSTables 中的已删除数据。
大压缩生成的 SSTable 不再包含任何删除信息或已删除数据。

Bigtable 会循环遍历所有 tablets，并定期对其执行 大压缩。大压缩的作用是：

回收被已删除数据占用的资源；
确保已删除的数据能及时从系统中彻底移除。

优化改进

前一节介绍的基本实现经过了一系列优化，才实现了用户所需的高性能、高可用性与高可靠性。本节对部分实现细节进行展开说明，以突出这些优化点。

局部性分组（Locality groups）

客户端可以将多个列族组合为一个 局部性分组。在每个 tablet 中，每个局部性分组会生成一个独立的 SSTable。

将不常同时访问的列族放在不同的局部性分组中，可以提升读操作效率。
- 例如，在 Webtable 中，网页的元数据（语言、校验和等）可以单独放在一个分组，网页正文则放在另一个分组。这样，读取元数据的应用无需扫描整个网页内容。

此外，每个局部性分组还支持一些调优参数：

内存分组：局部性分组可以声明为“常驻内存”，其 SSTables 会在访问时按需加载到内存，从而避免磁盘访问。此功能适用于体积小但访问频繁的数据。例如，Bigtable 内部将 METADATA 表中的 location 列族设置为内存分组。

压缩（Compression）

客户端可以控制某个局部性分组的 SSTables 是否压缩，以及选择哪种压缩格式。压缩在 SSTable 块级别（典型为 64KB，可配置）进行，从而在读取小块数据时无需解压整个文件。

许多客户端采用 两阶段压缩方案：

第一阶段：使用 Bentley 和 McIlroy 算法 [6]，跨大窗口压缩重复的长字符串；
第二阶段：使用快速压缩算法，在 16KB 小窗口内查找重复数据。

压缩速度极快：编码速率可达 100–200 MB/s，解码速率可达 400–1000 MB/s。尽管算法更强调速度而非空间节省，但在实践中压缩比效果良好。

在 Webtable 中，该方案在存储网页内容时实现了 10:1 的压缩比，显著优于 HTML 页面使用 Gzip 的典型 3:1 或 4:1。原因在于 Webtable 将同一主机的页面存储在相邻行，从而能压缩掉大量相同的网页模板内容。
对于存储多个版本的值时，压缩比效果更佳。

读性能缓存（Caching for read performance）

Tablet 服务器使用两级缓存以提升读性能：

Scan Cache：高层缓存，存储 SSTable 接口返回的键值对，适合重复读取同一数据的应用；
Block Cache：底层缓存，存储从 GFS 读取的 SSTable 块，适合访问相邻数据的场景（如顺序读取或在热点行中访问不同列）。

Bloom 过滤器

正如 5.3 节所述，读操作需要检查组成 tablet 状态的所有 SSTables。若 SSTables 未在内存中，可能触发大量磁盘访问。

为减少访问开销，客户端可以指定为某个局部性分组的 SSTables 创建 Bloom 过滤器 [7]。

过滤器能快速判断某个行/列对是否可能存在于 SSTable 中；
小量内存开销即可显著降低磁盘寻道次数；
对于不存在的行或列，大多数查找无需触盘。

提交日志实现（Commit-log implementation）

如果每个 tablet 独立维护一个提交日志文件，GFS 中会有大量文件并发写入：

这会导致底层文件系统频繁磁盘寻道；
同时，group commit 优化失效，因为每个文件中的写入分组很小。

解决方案：每个 tablet 服务器使用 单一提交日志，将不同 tablets 的更新混写在同一物理文件中 [18, 20]。

优点：大幅提升正常运行时的写入性能；
缺点：增加了恢复的复杂度。

当 tablet 服务器宕机后，其 tablets 会迁移到多个新服务器。新服务器必须从原服务器的日志中恢复各自 tablets 的变更，但日志内容是混合的。

朴素做法：每个新服务器读取完整日志，再提取自己需要的部分。但若 100 台服务器各分配到一个 tablet，则日志会被重复读取 100 次。
Bigtable 的做法：先对日志排序，按 <table, row, log sequence number> 排序，确保同一 tablet 的变更记录连续存储。这样只需一次磁盘寻道和顺序读取即可完成恢复。
日志文件被分为 64MB 段 并行排序，排序由 master 协调，并在新 tablet 服务器需要恢复时触发。

此外，为避免 GFS 写入延迟引发性能抖动：

每个 tablet 服务器有 两条日志写线程，各写入一个日志文件；
若当前文件写入性能不佳，会切换至另一线程；
日志条目带有序列号，以便在恢复时去除因切换导致的重复记录。

加快 tablet 恢复（Speeding up tablet recovery）

当 master 将一个 tablet 迁移到另一台服务器时：

源服务器先对该 tablet 执行一次 小压缩（minor compaction），减少日志中未压缩的状态。
完成压缩后，停止为该 tablet 提供服务。
在卸载前，再快速执行一次小压缩，以清理压缩期间产生的新日志状态。

这样，新服务器加载该 tablet 时无需额外恢复日志条目，大大缩短了恢复时间。

不可变性优化（Exploiting immutability）

SSTables 一旦生成即不可变，这一特性简化了系统设计：

读取 SSTables 时无需文件系统访问的同步；
行级并发控制可高效实现；
读写间唯一的可变结构是 memtable，通过 写时复制（copy-on-write） 行级数据，使读写能并行进行。

不可变性还将 删除数据的彻底移除 转化为对过时 SSTables 的垃圾回收。

每个 tablet 的 SSTables 都登记在 METADATA 表中；
Master 执行 标记-清除（mark-and-sweep），以清理无效 SSTables。

最后，SSTables 的不可变性使 tablet 拆分 更高效：

新的子 tablet 无需重新生成新的 SSTables；
它们可以直接共享父 tablet 的 SSTables。

性能评估

我们搭建了一个包含 N 个 tablet 服务器的 Bigtable 集群，以评估 Bigtable 在不同规模下的性能与可扩展性。

实验环境配置：

每个 tablet 服务器配置 1GB 内存，写入到一个包含 1786 台机器 的 GFS 单元；每台机器配有 两块 400GB IDE 硬盘。
N 台客户端机器用于产生负载，客户端数量与 tablet 服务器相同，以避免客户端成为瓶颈。
每台机器配备 双路双核 Opteron 2GHz CPU、足够的内存和 千兆以太网链路。
网络拓扑为 两层树形交换结构，在根节点处总带宽约为 100–200 Gbps；任意两台机器间的往返延迟 < 1ms。
同一机器上可能同时运行 GFS 服务器、tablet 服务器、客户端进程及其他作业。

参数设置：

R 为测试中涉及的 Bigtable 行键数量，选取 R 使得每个 tablet 服务器读写约 1GB 数据。
各基准测试均使用 1000 字节的值。

图6：

bigtable-6

基准测试设计

顺序写（Sequential Write）
- 行键为 0 至 R-1，划分为 10N 个区间，由调度器动态分配给客户端。
- 每个行键写入一个随机生成的字符串（不可压缩）。
随机写（Random Write）
- 与顺序写类似，但在写入前对行键取哈希并取模 R，从而均匀分布写负载。
顺序读（Sequential Read）
- 与顺序写相同的行键空间，但操作为读取之前写入的值。
随机读（Random Read）
- 与随机写对应，均匀分布在整个行空间。
扫描（Scan）
- 使用 API 的扫描接口遍历行区间值。单个 RPC 可批量返回多个值，减少了 RPC 开销。
随机读（内存）（Random Read (mem)）
- 与随机读相同，但数据所在局部性分组标记为 内存型，因此直接从内存中返回结果。
- 为保证数据适配内存，每台服务器的数据量缩减为 100MB。

单台 tablet 服务器性能

随机读：最慢，每秒约 1200 次读，即从 GFS 读取约 75MB/s 数据。瓶颈在于网络栈、SSTable 解析及 Bigtable 开销。
- 读取 1000B 值时需传输 64KB 块，浪费严重。大多数应用将块大小缩小到 8KB。
随机内存读：更快，因为直接从内存返回结果，无需从 GFS 获取大块数据。
随机/顺序写：性能优于随机读。所有写入追加到单一提交日志，并通过 group commit 高效写入 GFS。顺序写与随机写差异不大。
顺序读：性能优于随机读，因 64KB 块会被缓存，用于后续 64 次读取。
扫描：更快，因为单次 RPC 可批量返回大量数据，摊薄了 RPC 开销。

扩展性（Scaling）

随着 tablet 服务器数量从 1 增至 500，聚合吞吐量提高超过 100 倍。

例如，随机内存读的性能随服务器数量增加 500 倍，吞吐量提高近 300 倍。瓶颈在于单台服务器 CPU。

bigtable-table1

但性能提升并非线性：

在 1 → 50 台服务器的扩展中，单台吞吐量下降明显，主要因多机配置下的负载不均衡（CPU/网络资源争用）。
负载均衡算法虽能部分缓解，但受限于：
1. tablet 迁移次数受限（迁移会造成 <1s 的短暂不可用）；
2. 基准测试过程中负载不断变化。

随机读扩展性最差：

500 倍规模扩展仅带来约 100 倍吞吐提升。
原因是每次读取 1000B 值都需传输一个 64KB 块，很快饱和了多条共享的 千兆链路，导致单台吞吐量显著下降。

实际应用

截至 2006 年 8 月，Google 内部运行着 388 个非测试 Bigtable 集群，合计约 24,500 台 tablet 服务器。表 1 展示了每个集群中 tablet 服务器的大致分布。许多集群主要用于开发，因而长时间处于空闲状态。

其中一组包含 14 个繁忙集群（共 8069 台 tablet 服务器），在运行中观测到：

每秒处理超过 120 万次请求；
RPC 入站流量约为 741 MB/s；
RPC 出站流量约为 16 GB/s。

表 2 给出了部分正在使用的表的数据，这些表既有直接为用户提供服务的数据，也有用于批处理的数据。其特点差异极大，包括表规模、单元格平均大小、内存提供比例及模式复杂性。以下简要介绍三个产品团队对 Bigtable 的使用。

Google Analytics

Google Analytics (analytics.google.com) 是一项帮助网站管理员分析流量模式的服务：

提供 聚合统计信息（如每日独立访客数、每 URL 的每日浏览量）；
提供 行为追踪报告（如查看某页面后最终完成购买的用户比例）。

实现方式是网站管理员在网页中嵌入一个小型 JavaScript 程序。用户访问页面时，程序会记录相关信息（如用户 ID、页面信息），并将其存入 Google Analytics。随后系统对数据进行汇总并提供给管理员。

该服务依赖两张核心表：

原始点击表（~200TB）
- 每行代表一次终端用户会话；
- 行键为 <网站名, 会话创建时间>，保证同一网站的会话相邻且按时间排序；
- 压缩后仅为原始大小的 14%。
汇总表（~20TB）
- 存储每个网站的预定义统计结果；
- 通过定期运行 MapReduce 从原始点击表生成；
- 压缩后为原始大小的 29%。
- 系统总体吞吐量受限于 GFS 吞吐量。

Google Earth

表2：

bigtable-table2

Google 提供的 Google Earth (earth.google.com) 和 Google Maps (maps.google.com) 为用户提供高分辨率的卫星影像访问与导航功能。系统包含预处理与服务两部分：

预处理流水线
- 使用一张表存储原始影像（约 70TB，直接从磁盘提供服务）；
- 每行对应一个地理区域，行键保证相邻区域存储相邻；
- 影像已高度压缩，因此 Bigtable 压缩被禁用；
- 一个列族用于跟踪影像来源，该列族非常稀疏（每区域仅依赖少量原始影像）；
- 大量依赖 MapReduce over Bigtable，某些任务中每台 tablet 服务器处理超过 1MB/s 数据。
服务系统
- 使用一张表索引存储在 GFS 的数据（约 500GB）；
- 必须以低延迟支撑每个数据中心 每秒数万次查询；
- 表分布在数百台 tablet 服务器中，包含内存型列族。

个性化搜索（Personalized Search）

个性化搜索 (<www.google.com/psearch>) 是一项可选服务，记录用户在 Google 各类服务（网页、图片、新闻等）的查询与点击。用户可以：

浏览历史记录，重温查询与点击；
根据历史使用模式获取个性化搜索结果。

实现方式：

每个用户分配唯一 userid，并以此作为行键；
用户所有行为存储在同一表中，不同行为类型使用不同的列族（如网页查询列族）；
每个数据元素的时间戳为该行为发生的时间；
用户画像通过 MapReduce over Bigtable 生成，并用于在线个性化搜索。

数据跨多个 Bigtable 集群复制，以提升可用性并降低延迟。系统最初在客户端实现了最终一致性的复制机制，后迁移为 Bigtable 内置的 服务器端复制子系统。

此外，个性化搜索的设计允许其他团队在表中增加新的用户相关列，用于存储个性化配置与设置。结果该表拥有异常多的列族。为支持表共享，Bigtable 引入了简单的 配额机制，限制单个客户端在共享表中的存储消耗，从而在不同产品组间提供一定的隔离。

经验总结

在 Bigtable 的设计、实现、维护和支持过程中，我们积累了许多宝贵经验，并从中学到了一些重要教训。

复杂故障类型

一个重要的教训是：大型分布式系统会遭遇多种故障类型，而不仅仅是分布式协议中常见的网络分区或 fail-stop 故障。例如，我们曾遇到：

内存与网络数据损坏；
严重的时钟偏差；
机器挂起；
长时间或不对称的网络分区；
依赖系统的缺陷（如 Chubby 的 bug）；
GFS 配额溢出；
计划内及计划外的硬件维护。

随着经验积累，我们通过修改协议解决了部分问题：

在 RPC 机制中加入 校验和 来发现数据损坏；
取消系统内部关于其他子系统的过度假设，例如不再假设 Chubby 操作只会返回固定错误集。

功能演进的时机

另一条经验是：延迟新功能的引入，直到明确其使用方式。

例如，我们最初计划在 API 中支持通用事务，但因没有直接需求而未实现。
随着大量实际应用运行在 Bigtable 上，我们发现绝大多数场景只需 单行事务。
少数需要分布式事务的场景主要用于维护二级索引。为此我们计划引入一种专用机制：
- 功能上不如分布式事务通用；
- 但更高效，尤其在跨数百行更新时；
- 并能更好地与跨数据中心的乐观复制机制结合。

系统级监控的重要性

支持 Bigtable 的实践表明：系统级监控至关重要，既要监控 Bigtable 本身，也要监控其客户端应用。

我们扩展了 RPC 系统，对部分 RPC 进行详细追踪，记录其关键操作。这帮助我们发现并修复了：
- Tablet 数据结构上的锁竞争；
- Bigtable 提交时写入 GFS 过慢；
- METADATA tablets 不可用时的卡死访问问题。
另一个例子是：所有 Bigtable 集群均在 Chubby 中注册，这使我们能够：
- 查找所有集群；
- 了解规模、运行的软件版本、流量情况；
- 快速定位如延迟过高等异常问题。

简单设计的价值

最重要的经验是：保持设计简单。

Bigtable 系统规模庞大（约 10 万行非测试代码），且代码会随时间意外演进。
简洁的代码与设计对 维护与调试 帮助巨大。

例如，tablet 服务器的成员协议：

初始版本简单：master 定期向 tablet 服务器发放租约，若租约过期，服务器自杀。
然而，该协议在网络问题下严重降低了可用性，并且对 master 恢复时间极其敏感。
我们多次改进协议，使其性能提升，但协议复杂度急剧上升，还依赖 Chubby 中其他应用很少使用的特性，导致我们在调试边界情况时花费了大量精力，不仅是 Bigtable 代码，还包括 Chubby 代码。
最终，我们放弃了复杂协议，转向依赖 Chubby 常用功能 的新协议，该协议更简单，也更可靠。

结论

我们介绍了 Bigtable，一个用于存储结构化数据的分布式系统。自 2005 年 4 月 起，Bigtable 已在生产环境中运行。在此之前，设计与实现工作耗时约 7 人年。截至 2006 年 8 月，已有 60 多个项目 使用 Bigtable。用户普遍认可其性能与高可用性，并能随着需求增长，通过简单增加机器扩展集群容量。

一个有趣的问题是：Bigtable 接口不同于传统数据库，用户是否难以适应？新用户初期常对如何最佳使用 Bigtable 存疑，尤其是习惯了支持通用事务的关系型数据库。但事实证明，众多 Google 产品的成功应用表明 Bigtable 的设计在实践中运作良好。

目前，我们正在实现一些新特性，例如 二级索引支持 以及用于构建 跨数据中心、多主复制 Bigtable 的基础设施。我们也开始将 Bigtable 部署为服务，供产品团队直接使用，而无需各自维护集群。随着服务集群规模增长，未来需要解决更多 资源共享 问题 [3, 5]。

最后，我们发现 自研存储系统带来显著优势：

通过为 Bigtable 设计自有数据模型，我们获得了极大的灵活性；
控制 Bigtable 实现及其依赖的 Google 基础设施，使我们能够随时消除瓶颈与低效点。

Google BigTable 翻译

引言