Abstract#
Bigtable 是一个用于管理结构化数据的分布式存储系统，被设计成能够扩展到非常大的规模：分布在数千台商用服务器上的 PB 级别的数据。Google 内部的许多项目使用 Bigtable 存储数据，包括 web 索引，Google Earth 和 Google Finance。这些应用给 Bigtable 提出了不同的需求，无论是在数据大小 (从 URL 到网页到行星图像) 还是延迟要求 (从后台批处理到实时数据服务) 方面。尽管存在各种各样的需求 Bigtable 成功的提供了一个用于所有这些 Google 产品的灵活的，高性能的解决方案。
Introduction#
在过去两年半的时间里，我们在 Google 设计实现和部署了一个称为 Bigtable 的用于管理结构化数据的分布式存储系统。Bigtable 被设计成可靠的扩展到 PB 级别的数据和数千台机器。Bigtable 已经达成了多个目标：广泛适用性，扩展性，高性能和高可用性。Bigtable 在 Google 用在超过 60 个产品和项目，包括 Google Analytics, Google Finance, Orkut, Personalized Search, Writely 和 Google Earth。这些产品使用 Bigtable 处理各种高负荷工作负载，范围从吞吐量导向的批处理作业到用于用户端的延迟敏感型服务。这些产品使用的 Bigtable 集群覆盖了广泛的配置范围，从几台到数千台服务器，存储多达数百 TB 的数据。
从很多方面来说 Bigtable 类似于数据库，和数据库的共享很多实现策略。并行数据库和内存数据库已经实现了扩展性和高性能，但是 Bigtable 提供了相对于这些系统不同的接口。Bigtable 不支持完整的关系型数据模型，相反，它给客户端提供了一个简单的数据模型，支持数据布局和数据格式的动态控制，并允许客户端自行推理底层存储中所表示的数据的局部性质 (译注：允许客户端根据底层存储的数据的位置关系推断数据之间的局部关联性质)。数据通过 row 和 column 来索引，其名字可以是任意的字符串。Bigtable 将数据视作原始字符串，尽管客户端序列化各种形式的结构化和半结构化数据序列化成这些字符串。客户端可以通过精心选择数据格式来控制数据的局部性。最后 Bigtable 的 schema 参数允许客户端动态控制是否从内存或磁盘中获取数据。
Data Model#
bigtable 是稀疏分布式持久化多维度有序哈希表，通过行键，列键和一个时间戳进行索引，每个值都是一个原始字节数组。
(row: string, column: string, time: int64) -> string
在研究了很多潜在使用 Bigtable-like 系统后我们选定了这种数据模型。举一个实际影响我们设计决策的例子，假设我们想要维护一个可以用于不同项目的，大规模的网页集合及其相关信息的集合的拷贝，我们将这个表称为 Webtable 在 Webtable 中我们可能会使用 URLs 作为行键，网页的各个属性 (译注：如网页内容，其中的锚点等等) 作为列键，然后将对应的 (不同时间获取到的) 内容存储为值。如下图：
Rows#
table 中的行键可以是任意的字符串 (目前最大 64KB)。在同一个行键下进行的每次读写数据都具有原子性，这样设计使得客户端更容易推断系统在并发更新同一行时的行为。Bigtable 根据行键的字典序维护数据。表内行的范围是动态分区的，每个行范围叫做一个 tablet 也是一个分布和负载均衡的基本单元。这样，读取一个小的行范围非常高效，一般只需要跟很少数量的机器通信。客户端可以在选择行键时利用这个性质，在访问数据时得到较好的局部性。比如在 Webtable 中通过反转 URLs 中的 hostname 部分，将域相同的网页分组在一起。比如我们将 maps.google.com/index.html 的数据存储在键 com.google.maps/index.html 下，将相同域的页面存储在彼此相近的位置使得一些主机和域的分析更加高效。
Column Families#
列键被分组成叫做列族的集合 (column families)，组成一个访问控制的基本单元。在一个列族内存储的所有数据类型一般是一样的 (我们将相同列族的数据压缩在一起)。列族必须在数据可以存储到列族内的任一列键之前创建，在列族创建之后，列族内的所有列键都可以使用。
我们的目的是让一个表内不同的列族的数量较少 (最多上百个)，并且在操作期间列族很少改变，相比之下一个表可能有无限多数量个列。一个列键可以用这种语法命名：族：标识符。列族的名字必须是可打印出来的，但是标识符可以是任意字符串。比如 Webtable 中的一个列族是语言，存储编写网页内容使用的语言。我们在语言列族中只使用一个列键，其存储每个网页的语言 ID。这个表另一个有用的列族是锚点 (anchor)，这个族内的每个列键表示一个单独的锚点 (如上图)，其中的标识符是其引用的网址，内容是链接文本。
访问控制，磁盘和内存计量都在列族这一级别进行。在我们 Webtable 的例子中，这种控制允许我们管理多种不同的应用：一些添加新的基础数据，一些读取基本数据并且创建派生出来的列族，还有一些只允许查看当前存在的数据 (出于隐私的原因甚至不能查看所有的列族)。
Timestamps#
Bigtable 内的每个 cell 可以包含相同数据的多个版本，这些版本通过时间戳来索引。Bigtable 的时间戳是 64 位整数。时间戳可以被 Bigtable 以微秒表示的真实时间赋值，也可以由客户端应用显式赋值，应用必须生成唯一时间戳以避免产生冲突。一个 cell 的不同版本以递减的顺序存储，这样最新的数据可以被最先读取到。
为了减轻管理不同版本数据的负担，我们支持两种列族级别的设置使 Bigtable 进行自动垃圾收集：客户端可以指定只保存最近的 n 个版本，或者只存储足够新的版本 (比如最新七天写入的数据)。
在 Webtable 的例子中，我们将存储在内容中的爬取到的网页的时间戳设置为这些页面被实际爬取时的时间，上面描述过的垃圾回收机制让我们只存储每个页面最近的三个版本。
API#
Bigtable API 提供了创建和删除表以及列族的功能，也提供了修改集群，表，和列族元数据的功能，比如访问控制权力。
客户端应用可以写入和删除 Bigtable 的值，通过单独的行查找值，或者遍历表内数据的一个子集。下面是一个使用 RowMutation 抽象执行一系列数据更新的 C++ 代码 (省略了一些无关代码)。其中 Apply 调用在 Webtable 上执行了一个原子性的变更：在 www.cnn.com 行上添加了一个锚点，删除了一个不同的锚点。
// 打开 table
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);
下面是一个使用 Scanner 抽象来遍历指定行的所有锚点的 C++ 代码。客户端可以遍历多个列族，并且有很多机制可以限制扫描产生的行，列和时间戳的数目。比如我们可以限制扫描只产生锚点满足正则表达式 anchor:*.cnn.com 的列，或者只产生时间戳落在最近十天以内的锚点。
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 允许将 cell 用于整数计数器。最后 Bigtable 支持在服务端的地址空间内执行客户端提供的脚本，这个脚本使用 Google 开发的一个用于处理数据的语言 Sawzall 目前我们基于 Sawzall 的 API 不支持客户端脚本写入 Bigtable 但是支持很多形式的数据转换，基于任意表达式的过滤，通过各种操作进行聚合。
Bigtable 也可以用于 MapReduce, Google 开发的一个用于运行大规模并行计算的框架，我们做了一系列的封装允许将 Bigtable 用于 MapReduce 作业的输入源和输出目标。
Building Blocks#
Bigtable 构建在 Google 的许多其他的基础设施之上，Bigtable 使用 GFS 存储日志和数据文件。一个 Bigtable 集群一般运行在一个共享的机器池中，其中还运行着广泛的其他分布式应用，并且 Bigtable 进程经常和其他分布式应用进程共享相同的机器。Bigtable 依赖一个集群管理系统进行作业调度，在共享机器上管理资源，处理机器故障，和监控机器状态。
Bigtable 使用 Google SSTable 文件格式存储内部数据 SSTable 提供了一个持久化，有序的，不可变键值映射表，其中键和值是任意字节字符串。SSTable 提供了查找指定键对应的值，和根据一个指定键范围进行所有键值对遍历的操作。
在内部，每个 SSTable 包含一些连续的块 (通常每个块的大小是 64KB 但是可配置)。在 SSTable 末尾有一个索引块用于块定位，当 SSTable 被打开时这个块被加载到内存中。一次查询操作可能是通过单次磁盘查找来完成：首先通过在内存索引中执行二叉搜索到找到正确的块，然后在磁盘中读取对应的块。另外，一个 SSTable 也可以整个映射到内存中，使得我们不需要任何磁盘操作就可以执行查询和扫描。
Bigtable 依赖一个高可用，持久化的分布式锁服务 Chubby 一个 Chubby 服务由五个活动副本组成，其中一个被选举为 master 负责主动处理请求。当大多数副本存活且能够彼此通信时服务就在线 Chubby 使用 Paxos 算法来保证面临故障时副本保持一致。Chubby 提供了一个由目录和小文件组成的命名空间，每个目录或者文件都可以被用作一个锁，并且单个文件的读写都是原子性的。Chubby 客户端库提供了 Chubby 文件的一致性缓存。每个 Chubby 客户端维护一个跟 Chubby 服务的会话。当租约时间过期且不能将租约续期时客户端会话将会过期。当客户端会话过期，它会丢弃所有的锁和打开的文件句柄。Chubby 客户端也可以在 Chubby 目录和文件上注册回调，以获取变更或会话过期的通知。
Bigtable 用 Chubby 处理多种任务：确保在任何时候最多只有一个活动的 master；存储 Bigtable 数据的启动位置；发现 tablet 服务器和确认 tablet 服务器死亡；存储 Bigtable 格式信息 (每个表的列族信息)；存储访问控制列表。如果 Chubby 在很长时间内不可用 Bigtable 也会跟着不可用。我们最近在跨越 11 个 Chubby 实例的 14 个 Bigtable 集群中测量了这种影响。由于 Chubby 的不可用 (Chubby 中断或者是网络问题) 导致存储在 Bigtable 的某些数据不可用的 Bigtable 服务时间的平均百分比是 0.0047% 单个集群被 Chubby 的不可用性影响的最高百分比是 0.0326%.
Implementation#
Bigtable 的实现包含三个主要的组件：链接到每个客户端的库，一个 master 服务和很多 tablet 服务。其中 tablet 服务可以在集群中动态的添加或移除，以适应工作负载的变更。
master 负责将表分配到 tablet 服务器，发现新增和过期的 tablet 服务器，均衡 tablet 服务器的负载，GFS 中的文件的垃圾回收。此外，也处理 schema 变更比如表和列族的创建。
每个 tablet 服务器管理一组 tablet 的集合 (一般一个 tablet 服务器上有十到一千个 tablet)，处理其加载的 tablet 的读写请求，分割过大的 tablet.
像很多单 master 的分布式存储系统一样，客户端数据不直接发送到 master 而是和 tablet 服务器直接读写通信。由于 Bigtable 客户端不依赖 master 获取 tablet 位置信息，所以大多数客户端不会和 master 通信。最终 master 在实践中的负载很低。
一个 Bigtable 存储许多表，每个表由一组 tablets 组成，每个 tablet 包含一个行范围内关联的所有数据。一开始每个表只有一个 tablet 随着表数据的增长，它会自动分割成多个 tablets 默认每个 tablet 的大小在 100-200MB 之间。
Tablet Location#
我们使用一个类似 B+ 树的三级层级结构来存储 tablet 位置信息。
第一级是一个存储在 Chubby 上的文件包含 root tablet 的信息。root tablet 在一个特殊的 METADATA 表中包含所有 tablet 的位置信息。每个 METADATA tablet 包含一系列用户 tablets 的集合。root tablet 实际上就是 METADATA 表的第一个 tablet 其永远不会被分割，以确保 tablet 位置结构不会超过三级。
METADATA 表将 tablet 的位置信息存储在存储在以 tablet 的表标识符加上其结尾的行键编码成的行键上。每个 METADATA 行在内存中存储将近 1KB 的数据 METADATA tablet 采用了一个适度的限制 128MB 这样我们的三级定位方案足够寻址 2^34 个 tablet 也即 2^61 字节的数据。(译注: root metatablet 可以容纳 128MB / 1KB = 2^17 个次级条目，每个次级条目也可以容纳 128MB / 1KB = 2^17 个三级条目，共 2^34 个 tablet 每个 tablet 的大小在 100-200 MB 取 128MB 即 2^27 得到总大小 2^61 字节)
客户端库会缓存 tablet 位置，如果客户端不知道一个 tablet 的位置，或者发现其缓存的位置信息不正确，则会递归向上查找目标 tablet 的位置信息。如果客户端缓存是空的，则寻址算法需要三次网络来回，包括一次 Chubby 读取。如果客户端缓存是旧的，寻址算法可能会花费最多六个来回（假设 METADATA tablet 不会频繁的移动），因为仅有在不命中时才会发现缓存过时 (译注：先用缓存，向上找三次都不命中，然后从上往下重新查询三次)。
由于 tablet 的位置信息存储在内存中，所以不需要访问 GFS 我们通过客户端库预取 tablet 位置信息又进一步降低了开销：客户端每次读取 METADATA 表时都会读取多个 tablet.
我们在 METADATA 表中也存储了次要 (secondary) 信息，包括与每个 tablet 相关的事件的所有日志 (比如一个 tablet 开始服务)，这些信息在调戏和性能分析时很有帮助。
Tablet Assignment#
每个 tablet 在同一时间只会赋值到一个 tablet server 上 master 会持续跟踪所有存活的 tablet server 的集合，和当前所有 tablet 在 tablet server 上的分配情况，包括那些没有被分配的 tablet 当一个 tablet 未分配，并且由一个可用的 tablet server 有足够的空间，则 master 会通过发送一个 tablet 加载请求将 table 分配到这个 tablet server 上。
Bigtable 使用 Chubby 持续追踪 tablet server 当一个 tablet server 启动，它会在一个指定的 Chubby 目录下创建一个独一无二的文件，并且申请一个互斥锁。master 会监控这个目录。
一个 tablet server 在丢失互斥锁时会停止工作：比如网络分区导致 server 丢失了 Chubby 会话 (Chubby 提供了一种高效的机制允许 tablet server 在不使用网络流量的情况下检查自己是否仍然持有锁)。只要文件仍然存在 tablet server 就会尝试重新获取文件上的互斥锁，而如果文件不再存在，则 tablet server 就不可能再次提供服务，所以会将自己终止掉。无论何时，一个 tablet server 终止时 (比如由于集群管理系统将 tablet server 的机器从集群中移除)，会尝试释放自己持有的锁，这样 master 可以更快速的将其 tablet 分配到其他服务器上。
master 负责检测何时 tablet server 不再服务于其 tablets 然后将这些 tablets 尽可能快的从新分配。为了检测何时 tablet server 不再服务于其 tablets master 会周期性的询问每个 tablet server 的锁的状态。如果一个 tablet server 报告自己丢失了锁，或者是 master 在几次尝试之后，不能够达到这个 server 则 master 会尝试获取对应 server 的文件的互斥锁。如果 master 能够获取到锁，说明 Chubby 存活且 tablet server 可能已经终止或者是和 Chubby 有通信故障，因此 master 通过删除 server 文件，以确保其不可能再次提供服务。一旦 server 文件被删除 master 可以将之前分配到这个 server 上的所有 tablets 移动到未分配的 tablets 集合中。为了确保 Bigtable 集群不会受到 master 和 Chubby 之间网络的影响，master 会在和 Chubby 的会话过期时将自己终止，然而如上所述 master 的故障不改变 tablets 在 tablet server 上的分配。
当一个 master 被集群管理系统启动，在进行修改之前，需要知道 tablet 的分配情况。master 执行以下步骤以启动：1. master 在 Chubby 上申请一个独一无二的锁，以避免并行的 master 实例化；2. master 扫描 Chubby 上的 servers 目录来找到存活的 server；3. master 与每个存活的 tablet server 通信来发现每个 tablet server 已经分配了哪些 tablet；4. master 扫描 METADATA 查看所有的 tablet 每当扫描到一个还未被分配的 tablet 则 master 会将其添加到一个未分配 tablet 的集合，使得这个 tablet 可以被分配 (译注：只有在未分配 tablet 集合的 tablet 可以被分配)。
一个复杂的情况是只有 METADATA tablets 被分配之后才能扫描 METADATA 表。因此在开始第四步的扫描之前，如果在第三步没有发现 root tablet 则 master 将 root tablet 添加到未分配集合中。这一步确保 root tablet 会被分配。由于 root tablet 包含所有 METADATA tablets 的名字，在 master 扫描完 root tablet 后就可以知道所有的 tablets.
当前存在的 tablets 集合在以下情况变更：tablet 被创建或者删除，两个存在的 tablet 合并成一个更大的 tablet，或者一个 tablet 分割成两个更小的 tablet。master 能够追踪到这些变更，因为其发起了除最后一项以外的所有变化 (译注：创建 / 删除 / 合并都是由 master 执行的，分割不是)。Tablet 的分割是特殊的，因为他们由 tablet server 执行。tablet server 通过在 METADATA 表中记录新的 tablet 的信息来提交分割操作，当分割操作已经提交，它会通知 master 如果这个通知丢失 (tablet server 或者 master 宕机)，master 也会在请求 tablet server 加载已经被分割的 tablet 时发现，因为 tablet server 在 METADATA 表中找到被要求加载的 tablet 对应的条目只包含了一部分 (译注：通过 row range 判断) 然后 tablet server 会向 master 发送 tablet 已经被分割的通知。
Tablet Serving#
tablet 的持久化状态存储在 GFS 中，如上图。更新操作提交了一条包含 redo 记录的提交日志。关于这些更新，最近的提交存储在内存一个叫做 memtable 的有序缓冲区中；旧的提交存储在一系列的 SSTables 中。 为了恢复一个 tablet，tablet server 从 METADATA 表中读取 tablet 的元数据：包含组成 tablet 的 SSTables 的列表和一个 redo 指针集合，指向
所有可能包含该 tablet 数据的提交日志。server 将 SSTables 的索引读取到内存中，并通过执行已经提交过的所有 redo 日志来执行更新，重建 memtable.
当一个写操作到达 tablet server，server 检查格式是否正确，这样发送者被授权执行这个变更，授权是通过从一个 Chubby 文件中读取 (大部分情况下都会命中缓存) 允许写入者列表来执行的。一个有效的变更会写入到提交日志，分组提交 (group commit) 用于提高小型变更的吞吐量。在写入被提交后，其内存会被插入到 memtable。当 tablet server 收到一个读操作，同样先检查格式和权限合适。一个合法的读取操作会在 memtable 和一系列 SSTables 的合并视图上执行。由于 SSTables 和 memtable 都是以字典序排序的数据结构，合并视图可以高效的构建。
tablets 分割或合并时，读写操作都可以持续进行。
Compactions#
写操作执行后 memtable 的大小会递增，当 memtable 的大小达到一个阈值 memtable 会被冻结，然后一个新的 memtable 会被创建出来，被冻结的 memtable 会被转换成一个 SSTable 并写入 GFS。这个 * 次要压缩 (minor major)* 进程有两个目标：收缩 tablet server 的内存占用，减少 server 宕机恢复时需要读取提交日志数据的数量。在压缩过程中读写操作可以持续进行。
每个次要压缩创建一个新的 SSTable 如果这种操作一直继续下去，读操作可能需要合并任意数量的 SSTables 的更新。相反，我们通过在后台周期性的执行合并压缩来限制文件的数量。每个合并压缩读取一些 SSTables 和 memtable 的内容，写入到一个新的 SSTable，在压缩完成之后，输入的 SSTable 和 memtable 就可以被丢弃了。
重写所有 SSTables 合并压缩到只有一个 SSTable 的操作称为主要压缩 (major compaction)，通过非主要压缩产生的 SSTables 可能会包含特殊的删除条目，抑制旧的 SSTable 中依然存活的数据 (译注：没看明白)。换种说法，主要压缩产生的一个 SSTable 不包含任何的删除信息或者被删除的数据 (译注：所有数据都存在这一个 SSTables 里面不需要保存删除相关的信息)。Bigtable 周期性的遍历所有的 tablets 并且在其上执行主要压缩操作。这些主要压缩操作允许 Bigtable 回收被删除的数据使用的资源，也能够确保已经删除的数据及时从系统中消失，这对于存储敏感数据的服务来说很重要。
Refinements#
上面所描述的实现需要一定的优化来达到我们的用户要求的高性能，高可用和可靠性。本节会更详细的描述部分实现，以突出这些改进。
Locality groups#
客户端可以将多个列族组合成一个 locality group 每个 tablet 都会给每个 locality group 创建一个单独的 SSTable。将通常不会一起访问的列族分隔到不同的 locality groups 可以提高读取效率。比如 Webtable 中的页面元数据可以被放到一个 locality group，而页面内容可以放到不同的 locality group，这样一个需要读取页面元数据的应用就不需要读取到任何页面的内容。
此外，可以在每个 locality group 的基础上指定一些有用的微调参数。比如一个 locality group 可以被声明为存储在内存中。存储在内存 SSTables 中的 locality groups 会被 tablet server 惰性加载到内存中。一旦加载，读取属于这个 locality groups 的列族就可以无需访问磁盘。这个特性对一些小块但是经常访问的数据很有用：在内部，我们在 METADATA 表中使用这个特性来定位列族。
Compression#
客户端可以控制是否压缩一个 locality group 的 SSTables 如果是则使用压缩格式。用户指定的压缩格式会使用在每个 SSTable 块上 (大小可以通过 locality group 的微调参数指定控制)。尽管将每个块分开压缩会丢失一些空间，但好处是读取 SSTable 的一小部分时需要解压整个文件。许多客户端使用两步自定义压缩格式，第一步使用 Bentley and McIlroy’s scheme 在一个大的窗口中压缩长的公共字符串，第二部使用一个快速压缩算法，在一个 16KB 大小的窗口上查找重复的模式。两个压缩过程速度都非常快，在现代机器上编码速度 100–200 MB/s 解码速度 400–1000 MB/s.
尽管我们在选择压缩算法时更注重速度而非空间缩减，这种两步压缩模式还是取得了出人意料的好结果。比如在 Webtable 中我们使用这种压缩模式存储网页内容。在一个实验中，我们在一个被压缩的 locality group 中存储了大量的文档，为了实验的目标，我们限制在每个文档中只存储一个版本 (译注：同一文档多个版本的内容可能是极其相似的)。这种压缩模式在空间上达到了 10:1 的压缩比。这比普通的 Gzip 在 HTML 页面上 3:1 或者 4:1 的压缩比要好很多，原因在于 Webtable 的行存储方式是：同一主机的所有所有页面存储在相近的位置，这使得 Bentley-McIlroy 算法能够标识相同主机下页面上大量的共享样板 (译注：大量网页可能有相同的页眉页脚或其他静态模板)。
许多应用不仅是 Webtable 选择能够将相似的数据最终聚合到一起的行名称，因此能够达到非常高的压缩比。Bigtable 在存储多版本数据时压缩比甚至更高。
Caching for read performance#
为了改善读性能 tablet servers 使用了两层缓存。Scan Cache 是高层级的缓存，缓存 tablet server 代码里 SSTable 接口返回的键值对，Block Cache 是低层级的缓存直接缓存从 GFS 读取的 SSTables 块。Scan Cache 对于会重复读取相同数据的应用最有用，Block Cache 对于短期内读取的数据非常接近的应用最有用 (比如顺序读或者在一个热点行上随机读取相同 locality group 的不同列)。
Bloom filters#
如上所述，一个读操作必须读取构成 tablet server 状态的所有 SSTables，如果 SSTables 不在内存中，会导致很多磁盘访问，我们通过允许客户端指定应该为特定的 locality group 创建 Bloom 过滤器来减少这个数量。一个 Bloom 允许我们询问一个 SSTable 是否包含一个指定行 / 列对的任何数据。对于某些应用，在 tablet server 使用很小的一块内存存储 Bloom 过滤器能够大幅度的减少读取操作的磁盘访问数量。使用 Blook 过滤器也意味着，大部分对不存在的行或列的查询根本不需要访问磁盘。
Commit-log implementation#
如果我们一直将每个 tablet 的提交日志写到不同的日志文件，那么在 GFS 会有非常大量的文件并发写入。依赖于每个 GFS server 上的底层文件系统的实现，这些写入可能会造成大量的磁盘定位 (seek) 以写入到不同的物理日志文件。此外，给每个 tablet 上写入不同的日志文件会减少 group commit 优化的效率，因为 groups 会变得很小 (译注：不同的 commit 写入到不同的文件不能放入同一个 group)。为了修复这个问题，我们在每个 tablet server 将变更附加到单独的提交日志，在同一个物理日志文件中混合不同 tablets 的变更。
使用一个日志文件可以在常规操作提供了极大的提升性能，但是会使恢复变得复杂。当一个 tablet server 宕机，其服务的 tablets 会被移动到大量的其他的 tablet servers 上：每个 server 通常只加载原先 tablet server 上的很小数量的数据。为了恢复一个 tablet 的状态，新的 tablet server 需要从原先 tablet server 的提交日志文件上重放对应 tablet 的变更。然而，这个 tablet 的变更和其他 tablet 的变更混合到相同的物理日志文件上。一个方法是每个新的 tablet server 读取全量的提交日志文件，然后只重放恢复所需要的对应的 tablet 的条目。然而，在这种模式下，如果一个故障的 tablet server 上的 tablet 被分配给了 100 台机器，则日志文件会被读取 100 次 (每个 tablet server 都读取一次)
我们通过首先将提交日志条目按照 <table, row name, log sequence number> 作为键进行排序。在排序的输出中，所有特定的 tablet 的变更都是连续的因此可以只通过一次磁盘定位高效的顺序读取出来。为了并行化排序，我们将日志文件分隔成 64MB 的段，然后在不同的 tablet server 上并行排序各个段。这个排序过程由 master 协调，并且在一个 tablet server 表明自己需要从一些提交日志文件上恢复变更时启动。
将提交日志写入到 GFS 有时导致一段短暂的性能问题，由于各种各样的原因：比如一个 GFS server 机器产生写崩溃，或者到达三个 GFS 服务器的网络路径上出现拥堵，又或者是负载太高等等。为了保护在 GFS 延迟峰值情况下的变更，每个 tablet server 实际上有两个线程同时使用。如果写入到活动日志文件的性能很低，日志文件写入会切换到其他线程，并且提交日志队列中的变更通过新的线程写入。日志条目中包含序列号，允许恢复进程忽略由于日志切换线程产生的重复条目。
Speeding up tablet recovery#
如果 master 将一个 tablet 从一个 tablet server 转移到另一个，源 tablet server 首先在对应的 tablet 上做一个次要压缩，这个压缩通过减少 tablet server 提交日志中未压缩的状态的数量来减少恢复所需要的时间。在完成这次压缩后这个 tablet server 停止为这个 tablet 服务，在其真正取消加载 tablet 之前 tablet server 会再做一次次要压缩 (通常很快) 来消除在第一次次要压缩执行后到达的，剩下的其他没有压缩的状态。在第二次次要压缩完成后，这个 tablet 就可以被加载到其他 tablet server 上而无需恢复任何日志条目。
Exploiting immutability#
除了 SSTable 缓存，Bigtable 系统的许多其他部分也因为实际上我们生成的 SSTables 是不可变的而被简化了。比如，当从 SSTables 进行读取时，我们不需要在访问的文件系统上做任何同步操作。最终，可以很高效的实现不同行之间的并发通知。唯一可变的，可以被同时读写的数据结构是 memtable 为了减少 memtable 读取时的竞争，我们给 memtable 的每行做了 copy-on-write 并且允许读写并行执行。
由于 SSTables 是不可变的，永久移除已删除数据的问题转换成了垃圾回收废弃 SSTables。每个 tablet 的 SSTables 注册在 METADATA 表内。master 通过标记 - 擦除在 SSTables 中移除淘汰的 SSTables METADATA 表包含根 tablet 的集合。最终，不可变的 SSTables 使得我们能够将 tablets 快速的分隔，我们让子 tablets 共享父 tablet 的 SSTables 而非给每个子 tablet 生成一个新的 SSTables 集合。
Lessons#
在设计，实现，维护和支持 Bigtable 的过程中，我们收获了很多经验并且学到了许多有趣的教训。
我们学到的一个教训是大型分布式系统容易受到很多各种故障的影响，不仅是标准的在许多分布式协议中假设的网络分区和故障停止错误。比如我们发现很多由于这些原因造成的问题：内存和网络故障，大的时钟偏差，机器挂起 (无响应)，持续的不对称的网络分区，我们使用其他系统 (比如 Chubby) 的 bug，GFS 配额溢出，以及其他计划和非计划内的硬件维护。随着我们已经在这些问题上获得了许多这些问题的，我们通过修改各种协议来解决他们。比如，我们在 RPC 机制中添加了校验和。我们也通过移除系统中的一部分对其他部分做出的假设来处理这些问题，比如我们不再假设一个给定的 Chubby 只会返回一定范围内的错误。
另一个我们学到的教训是，在搞清楚新的特性会被如何使用之前延迟添加新特性很重要。比如我们一开始计划在我们的 API 中支持通用事务。因为目前没有使用场景，我们没有实现它们。现在我们有许多真实的应用运行在 Bigtable 上，我们可以调查它们的实际需求，发现大多数应用只需要单行事务。对于用户需求的分布式事务，最重要的用途是维护辅助索引，我们计划添加一个特殊的机制来满足它们的需求。新的机制会不比分布式事务更加通用 (less general)，但是会更高效 (特别是在更新数百行的跨度上)，并且也能和我们跨数据中心副本乐观复制方案更好的兼容 (interact better)。
我们在支持 Bigtable 的过程中学到的一个实用的教训是，适当的系统级监控非常重要 (比如：不仅监控 Bigtable 本身，还监控使用 Bigtable 的客户端)。例如：我们扩展了我们的 RPC 系统，这样对于一个简单的 RPC 他会详细记录所有该 RPC 所作的所有重要操作的详细跟踪。这个特性允许我们发现和修复了许多问题，比如：tablet 数据结构的锁竞争，提交到 Bigtable 的变更写入 GFS 太慢，当 METADATA tablets 不可用时访问 METADATA table 导致阻塞访问。另一个监控有用的例子是，每个 Bigtable 集群都注册在 Chubby 中，这允许我们跟踪到所有集群的，了解它们的大小，运行的软件版本，收到了多大的流量，监控是否存在延迟异常高的问题。
我们学到的最重要的教训是简单设计的价值。鉴于我们系统的大小 (除去测试代码大概 100000 行)，代码以不可预期的方式发展，我们发现代码和设计的清晰度极大的影响维护和调试。比如我们的 tablet-server 成员协议。我们的第一个协议很简单：master 周期性的向 tablet-server 发出租约，然后 tablet servers 在租约过期时杀死自己。不幸的是，在产生网络问题时，这个协议极大的降低了可用性，而且对 master 的恢复时间很敏感。我们重新设计了很多次，直到有一个表现良好的协议。然而结果是，这个协议过于复杂而且依赖于 Chubby 的一些很少被其他应用使用的特性的行为。
我们发现我们在处理一些模糊的边界情况上花费了太多的时间，不仅仅是在 Bigtable 的代码，而且还有 Chubby 代码。最终，我们废弃了这个协议并且转移到了一个新的简单的协议，仅依赖于常用的 Chubby 特性。
Conclusions#
我们已经描述了 Bigtable 这样一个 Google 用来存储结构化数据的分布式系统。Bigtable 自 2005 年四月开始子啊生产环境中使用，在这之前，我们花费了将近七人 - 年来设计和实现它。在 2006 年八月份，超过六十个项目使用 Bigtable。我们的用户喜欢 Bigtable 提供的高性能和高可用性，并且随着时间资源需求的增长，可以通过简单的增加更多的机器来扩展集群的容量。
考虑到 Bigtable 不同寻常的接口，一个有趣的问题是，对于我们的用户来说适应使用 Bigtable 有多困难。新用户通常不确定怎么最好的使用 Bigtable 的接口，尤其当他们已经习惯于使用关系型数据库提供的支持的通用事务。尽管如此，许多 Google 产品成功的使用了 Bigtable 的事实证明我们的设计在实践上工作的还不错。
我们仍在开发许多额外的 Bigtable 的新特性，比如支持辅助索引，构建跨数据中心复制的，具有多个 master 副本的 Bigtables 基础设施。我们也开始将 Bigtable 部署为提供给产品组的一个服务，这样单独的产品不需要维护他们自己的集群。随着我们服务集群的扩展，我们需要解决更多 Bigtable 本身资源共享的问题。
最终，我们发现在 Google 自建存储解决方案有巨大的好处，在给 Bigtable 设计我们自己的数据模型时，获取了显著的灵活性。除此以外，我们可以自主控制 Bigtable 的实现及其所依赖的 Google 基础设施，意味着在我们可以及时的消除瓶颈和低效。