Bigtable： A Distributed Storage System for Structured Data

2003年USENIX，出自谷歌，开启分布式大数据时代的三篇论文之一，底层依赖 GFS 存储，上层供 MapReduce 查询使用

Abstract

是一种分布式结构化数据存储管理系统，存储量级是PB级别。存储的数据类型和延时要求差异都很大。论文介绍数 bigtable 的数据模型。

Introduction

BigTable 达成了几个目标：适用面广、伸缩性好、高性能、高可用。即可以满足吞吐导向的批处理的需求，也满足延迟敏感服务的需求。很多时候 BigTable 看起来像数据库，但又有不同的接口层。不支持全部关系数据模型、支持动态控制数据布局和格式。支持数据再底层存储时候的属性推断。数据用字符串作为行列名建索引。BigTable 把数据当字符串。

Data Model

BigTable 是一个稀疏、分布式、持久化、多维存储的字典(map)。map 由一个 row key、column key、timestamp 组合建索引，map 的值是字节流(array of bytes)。(row:string, column:string, time:int64) → string，以下是一个具体的例子：

这个 Webtable 表存储了网页内容，和引用该网页的网页地址。

Rows

对一个 row key 的读写都是原子的，不管里面包含了多少列。这个设计使得客户端使用的时候更好做并发控制。

BigTable按照字典序存储 row key。行范围动态划分，一个范围称为一个 tablet，其作为分布式存储平衡的单元。这个性质帮助客户端探索数据的局部性存储，得到更高的效率。比如对于 webtable 来说，同一个网站的页面因为 url 的倒序排列而聚集到一起。

Column Families

column keys 聚集到 column families 里面，column families 作为访问控制的基本单元。同一个 column families 的数据通常来说有相同的数据类型，并且系统会把数据放一起压缩。column family 先创建，再使用。系统的用意就是 column family 的数量比较少，并且不经常变动。相反，column 的数量不做限制。

一个 column key 的格式 family:qualifier，例如对于 webtable 来说，一个 column family是 language family。里面只有一个 column key，存储网页的 language ID。另一个 column family 是 anchor，如图一所示。

Timestamps

每个 BigTable 的单元格可以存储同一份数据的多个版本，版本号就是 timestamp。并且从大到小倒序排列。为了高效管理，系统支持设置保留最近几个版本，或者回收多久以前的旧版本。

API

提供了基本的API来控制 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)

还有一个用 Scanner 来扫描特定行列的例子：

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 支持单行的事务，用 read-modify-write 模式保证原子性。支持单元格计数。支持服务器上执行客户端提供的脚本，脚本功能是对数据进行转化，过滤，统计等操作。

Building Blocks

BigTable 依赖几个谷歌内部的基础服务，第一个就是GFS。

存储文件格式是 Google SSTable 文件格式。这个格式是一种持久化，有序、不可变的 key -> value 映射格式，key 和 value 都是字符串的二进制数组形式。每一个 SSTable 包括连续的 blocks，一个 block 64KB。block index 用于查找 block。当 SSTable 打开的时候，block index 载入内存，通过二分查找找到合适的索引。然后从磁盘读取合适的 block。此外 SSTable 还可以映射到内存中，这样可以完全避免磁盘操作。

BigTable 还依赖一个高可用的分布式锁服务 Chubby。Chubby 有5个服务组成，其中一个是 master，用来处理请求。当超过一半副本存活的时候，集群可用。Chubby 使用 Paxos 算法来保持副本间的一致性。Chubby 基本可以看作是 zookeeper 的谷歌版。客户端和 Chubby 保持session，能一致性的读写小文件，文件带锁，Chubby 支持对保存文件注册回调函数。

BigTable 用 Chubby 有几个不同用处：确保任何时刻只有最多一个 master；存储 bootstrap 文件地址；tablet 服务发现和死亡摘除；存储表的 schema 信息(每张表的 column family)；保存存储权限列表。Chubby 不可用了，BigTable 也就不可用了。

5 Implementation

整体有三大组件：客户端需要链接的依赖库，一个 master Server，一堆 tablet Servers。tablet server 可以动态加入或者移除集群。

master 的职责是分配 tablets 给 tablet servers；发现并加入 tablet server，删除过期的 tablet server，平衡 tablet servers 之间的负载，垃圾回收无效的文件，表格 schema 的变化。

tablet Server 负责一系列的 tablet，包括读写请求，对于增长过大的 tablet 负责分裂。

client 也是直接和 tablet Server 进行读写数据通信。client 不依赖 master 获取 tablet 的定位信息，绝大多数 client 不会和 master进行通讯。

一个 BigTable 集群储存多张 table，每个 table 由多个 tablet 组成，每个 tablet 里面存储 row range 里面的全部数据。一开始，一张 table 只有一个 tablet，随着 table 数据增长，会自动分裂成多个 tablet，每一个 tablet 大约100~200M

5.1 Tablet Location

三层结构存储 tablet 位置信息的 B+ 树

Chubby 里面保存 root tablet 的地址，root tablet 不会分裂，里面保存其他所有 MetaData 里的 tablet，而MetaData 里面的 tablet 里保存 user tablet 的位置信息。

MetaData table 保存一个 row key 存储在 tablet 的位置信息，这个位置信息是 tablet 对其所属 table 标识符和row key的开始行和结束行的 encoding。其中存储的是以开始和结尾的Row Key作为键，tablet位置作为值的映射。每一个 MetaData row 差不多1KB，通常128MB的大小的 MetaData tablet 限制，三层的 location schema 能存储2^34 个 tablets。

client 会 cache tablet 的位置信息，如果 cache 中没有或者不正确，就递归的向上查找。这个位置信息存储在内存中，客户端在读取时也会采取“预取”策略，一次读取多个 tablet 位置信息。

MetaData 里面还存储一些二级信息，例如事件日志，用于调试。

5.2 Tablet Assignment

master 追踪所有 tablet Server，一个 tablet 一个时刻也只能分配给一个 tablet Server。
当一个 tablet 没有被分配，如果出现足够资源的 tablet Server，master 就会将其分配给这个 tablet Server。

BigTable 用 Chubby 来追踪 tablet Server。当 tablet Server 启动的时候，在 Chubby 的一个特定目录下申请一个排它锁（一个唯一文件名的文件）。master 会一直监控这个目录以感知 tablet Server 的变化。当 tablet Server 不服务的时候，就会释放 Chubby 上的锁。

master 会周期性的询问 tablet Server 是否还持有 Chubby 上的锁。如果 tablet 不持有或者无法应答 master 的请求，master 会尝试获取这个 tablet Server 的锁，并删除这个文件对应的锁。之后 master 会标记 tablets 为不可用。当 master 和 Chubby 断链，master 会自动退出，并不改变 tablet 的分配。

当 master 启动时，执行一下操作（1）获取 Chubby 上的 mater 锁，确保只有一个 master（2）master 扫描 Chubby 上的 server 目录，发现活着的 tablet Server。（3）和每个 tablet Server 通讯，查询被分配的 tablet（4）扫描 MetaData 表，如果遇到 tablet 没有被分配，标记为未分配。后续会对未分配的 tablet 做分配。

一个复杂的情况是扫描 MetaData 表的时候，MetaData tablet 本身就还未分配。因此在执行步骤（4）之前，如果 root table 没有 分配，master 把 root tablet 标记为未分配。因为 root table 包含所有 MetaData 的 tablets，所以 master 扫描 root table 之后就能扫描全部的 MetaData。

一个已有的 tablet 只有创建/删除、合并、分裂的时候才会改变。当 tablet 分裂时，tablet Server 往 MetaData 中记录新的 tablet，之后会通知 master。

5.3 Tablet Serving

更新操作提交到 commit log 中，作为重做记录（redo log）。整体这块的顺序是WAL（write after log）。最近的一些更新提交存储在内存中，有序存储，这块儿叫做 memtable；老一些的更新提交存储在磁盘上的 sequence SSTable 上。所以可以看出来，一个 tablet 由三部分组成，磁盘上的 tablet log，一系列的 SSTable 文件，以及内存上的 memtable。这种操作在后续的 ElasticSearch 上也有体现。

为了恢复一个 tablet Server，tablet Server 会先读取其 MetaData 知道包含哪些 SSTable，并且 MetaData 里有一系列的重做指针，指向 commit log。tablet Server 读取 SSTable 索引，并通过重做指针指向的更新提交，重建 memtable。

新来一个写操作的时候，先校验格式、鉴权。通过之后先写都 commit log 里。多个 commit 聚合起来写，提升吞吐，写完之后，再把内容写入到 memtable。

读操作也是先校验，鉴权，然后在 memtable 和 SSTable 里面查询，并将结果合并。

5.4 Compactions

随着 memtable 越来越大，达到阈值之后冻结转化成 SSTable，写入GFS，同时创建一个新的 memtable。这个操作叫 minor compaction，能较少内存使用，也能较少 commit log 的大小。

minor compaction 每次都会创建一个 SSTable，放任不管小文件会越来越多。因此还需要控制文件数量， BigTable 通过一个默认的线程执行 major compaction 来达成。这个操作读取新生成的小碎 SSTable，然后合并写入一个新的大的 SSTable 里。

在 major compaction 会删除之前 SSTable 里面标记软删除的数据。

6 Refinements

Locality groups（存储位置分组）

Compression（数据压缩）

Caching for read performance（读时缓存）

Bloom filters（布隆过滤器）

例如5.3节里的图例表示，需要读取 tablet Server 下所有的 tablet 来获取最新的数据，这会有比较多的磁盘读取操作。在 tablet Server 上建立 bloom filter，验真查找的 row-cloumn 对是否在某个 SSTable 上，减少磁盘操作。

Speeding up tablet recovery（恢复加速）

master 移动一个 tablet 的时候，原来的 tablet Server 对这个 tablet 先做一次 minor compaction，这样能减少 commit log，从而加速恢复。然后该 tablet Server 停止对这个 tablet 服务。在确保卸载完全之前，还会在做一次 minor compaction，彻底干掉内存里的 commit log。

Exploiting immutability（不可变性）

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

由于 SSTables 是不可变的，永久删除已删除数据的问题转化为垃圾收集过时的 SSTables。每个 tablet Server 的 SSTable 都注册在 MetaData 中。主进程删除过时的 SSTables，作为对 SSTables 集的标记和清除垃圾回收，其中元数据表包含根集。

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

9 Lessons

作者总结了大型分布式系统的一些经验

第一条经验：大型分布式系统容易受到多种失败类型的困扰，不仅仅是标准的网络不通，故障停止(fail-stop)等。例如内存和网络崩溃、锁倾斜、机器宕机、非对称的网络分裂、依赖系统的 bug、GFS配额超限、硬件过保等等。作者通过修改协议来缓解。例如在 RPC 里面增加校验和，去掉对依赖系统的一些假设。

第二大经验：除非清楚新功能有什么用，否则延迟增加新需求很重要。例如作者想实现【事务】的时候，等实际使用了来，才发现只需要实现单行级别的事务就可以了。

第三大经验：系统级的监控非常重要（例如监控 BigTable 本身和使用 BigTable 的客户端）。例如扩展了RPC系统，用于追踪系统通过RPC做的重要动作。这个特性帮助排查解决了很多问题。

最重要的经验：设计简单的价值。考虑到我们系统的规模，以及代码随着时间的推移以意想不到的方式演变的事实，我们发现代码和设计的清晰性对代码维护和调试有着巨大的帮助。其中一个例子就是我们的tablet服务器成员协议。我们的第一个协议很简单：主机定期向tablet服务器发出租约，如果租约到期，tablet服务器就会自杀。不幸的是，这种协议在出现网络问题时会大大降低可用性，而且对主恢复时间也很敏感。我们重新设计了几次协议，直到我们有了一个性能良好的协议。但是，生成的协议太复杂，并且依赖于其他应用程序很少使用的Chubby功能的行为。 我们发现，不仅在Bigtable代码中，而且在Chubby代码中，我们花费大量时间调试晦涩难解的案例。 最终，我们放弃了该协议，转而使用仅依赖于广泛使用的Chubby功能的更新的更简单协议。

参考链接：
https://zhuanlan.zhihu.com/p/338566270
https://zhuanlan.zhihu.com/p/164926186
https://zhuanlan.zhihu.com/p/158607288