The Bigtable Paper
Bigtable是基于GFS研发的结构化数据分布式存储系统，这篇blog是对原论文的导读，包含对Bigtable数据模型的解释。
原论文：Bigtable: A Distributed Storage System for Structured Data
数据模型
我们可以把 Bigtable 视作一张多维的有序哈希表，它通过行、列和时间戳映射到值，存储的值即简单的字节序列，由用户自行解析，以网页存储为例：
图中 cnn 网页的域名为行键，网页内容、导向该页面的网页为列键，每个单元格中都可能存在多个以时间戳区分的版本。
Bigtable 确保对单独一行的读写操作是原子化的，且数据按照行键语序排列。这样设计的好处有两点： 首先，对开发者来说，同行数据并发更新的行为更加清晰； 其次，可以合理组织行键，充分利用数据访问的局部性现象。
数据表中的列键将按照列族分组，图中的 anchor 即为列族，它是访问控制的最小单元。列名的格式为：列族：列键。 在 Bigtable 中，列族需要事先定义，列键必须从属于列族，且列键是可以动态添加的。
Bigtable 使用时间戳来索引每个单元格的版本信息。时间戳可由 Bigtable 生成，或者由用户指定，后者需要用户保证时间戳的唯一性。 GC 时，Bigtable 可自动保留最近 n 个版本，或大于指定时间戳的版本。
底层依赖
Bigtable 依赖 GFS 存储日志和数据文件，并使用 Chubby 确保若干性质：
- master 的唯一性；
- 存储数据的自举位置；
- 实现 tablet 服务器的服务注册和发现（tablet 是 Bigtable 中的若干连续行片段，是负载均衡和数据分片的最小单元）；
- 存储表格元数据，如列族信息；
- 存储访问控制列表。
由于我们后续会解读 GFS 和 Chubby 的论文，这里就省略对两者的介绍。
Bigtable 使用 Google SSTable 格式存储数据，该格式是一种不可变的顺序哈希表，支持按键查询和按键范围遍历的功能。
实现方式
整个 Bigtable 的组件分三部分：
- 客户端：提供通信相关的库；
- master：负责集群管理、动态数据分片、负载均衡和 GFS 文件 GC；
- tablet 服务器：管理一个或多个 tablet，处理其读写请求，如果 tablet 过大，则将其拆分。
Tablet 的位置信息按照上图方式存储：首先，Chubby 中存放 root tablet 的位置，其中包括 METADATA 表中所有 tablet 的位置信息，而 METADATA 表中存储了用户表的 tablet 位置。 特殊的是，root tablet 不会因为数据量太大自动拆分，否则会破坏图中的三层架构。 在 METADATA 表中，用户 tablet 的行键是用户表名和 tablet 最后一行的编码。 用户端将缓存 tablet 的位置，一旦出现缓存未命中现象，它将顺着图中结构上溯，直至查询到其位置。 每次查询 METADATA 表时，客户端会缓存多个 tablet 位置，减少上溯查询的次数。 该表格同样存储 tablet 的操作日志信息，便于 debug 和性能分析。
master 将负责追踪活跃的 tablet 服务器和 tablet 的分配情况，如果出现未分配的 tablet，master 会将其分配到有足够空间的 tablet 服务器上。
每个 tablet 服务器在启动时会向 Chubby 的特定目录注册唯一的互斥锁，只要它还在正常运作，它会持续地重新获取这把锁，当出现异常情况时，锁因为超时会被自动释放，服务器发现锁不存在后也会终止进程。master 通过监听服务器目录下的锁信息，就可以发现集群中活跃的 tablet 服务器。
master 将周期性询问 tablet 服务器的锁状态，如果无法得到回应，或者 tablet 服务器认为失去了锁，那么 master 会自行在 Chubby 获取这把锁，以确保 Chubby 是正常运作的。如果 master 无法和 Chubby 集群建立联系，它将终止进程。 注意，由于 tablet 的分配是保存在 Chubby 中的，master 的变更对集群没啥影响，毕竟它本身是无状态的。
master 在初始化时执行下列步骤：
- 向 Chubby 申请 master 锁，防止并发的 master 初始化；
- 扫描 Chubby 的 server 目录，发现活跃的服务器对象；
- 和活跃的 tablet 服务器交换信息，了解 tablet 的分配情况；
- 如果
METADATE表尚未被分配，master 将 root tablet 加入待分配列表，并由此得到MATADATA表的所有 tablet，进行MATADATA表的分配。 - 扫描
METADATA表，了解一共有哪些 tablet，这样可以推断出还有哪些未分配的 tablet，加入待分配列表。
当出现 tablet 分裂时，相关的 tablet 服务器将提示 master，如果这条提示信息丢失（双方出现一方崩溃），master 必然会将已经分裂的 tablet 分配给一个 tablet 服务器，这台服务器必然发现 METADATA 表中的记录和 master 的指令中，tablet 的范围不符，此时它将提示 master 出现了 tablet 分裂。
上图展示了 tablet 的存储形式：写操作首先会记录一条 redo log，最近的操作保存在内存的 memtable 中，更早的操作被持久化到 SSTable 文件里。要恢复一个 tablet，tablet 服务器首先从 METADATA 表中获取 SSTable 文件列表，其中包含 tablet 和若干存档点（指向 redo log 中的某些位置），然后先将 SSTable 文件索引读入内存，再按照存档点的指示重放 redo log 中的部分操作。
在执行了一系列写操作之后，memtable 必然膨胀，等达到一个阈值后，服务器将新建一个 memtable 用于记录操作，并将旧的 memtable 转换为 SSTable 文件写入 GFS。另外，Bigtable 将周期性地一些 SSTable 和 memtable 合并，写入一个新的 SSTable 文件，并删除源文件。
细节优化
局部组（locality group）
客户端可将多个列族合并为一个局部组。每个组在每个 tablet 中生成一个独立的 SSTable 文件，将不常一起使用的列族分开成组，可以有效提升读性能。局部组也可以被声明在内存中，减少对磁盘的操作。 客户端还可自定义局部组的 SSTable 文件压缩格式，此时我们可以读取部分文件内容，而不必解压整个文件。
读缓存
Tablet 服务器存在两种级别的缓存：
- 扫描缓存：将 SSTable 文件的扫描结果缓存，有助于反复读取相同数据的场景。
- 块缓存：将 GFS 中的 SSTable 数据块缓存，有助于频繁读取邻近数据的场景。
布隆过滤器（bloom filters）
要恢复一个 tablet，服务器不得不扫描所有的 SSTable 文件，造成大量的磁盘 IO，为了优化这一点，客户端指定，为特定的局部组创建布隆过滤器，帮助 Bigtable 快速检测特定的行列对是否存储在该文件中。
log 优化
如果给每个 tablet 分配单独的 redo log，那么将造成大量的并发读写。 因此，Bigtable 在每个 tablet 服务器上使用统一的 redo log 文件，混合记录所有 tablet 的操作日志，这将复杂化日志重放操作，可能需要重放多次，才能恢复所涉及的全部 tablet。 为了规避多次读取，首先将按照表名、行键、日志号对所有日志进行排序，保证同一个 tablet 的日志分布集中，然后再顺序恢复所有 tablet。
为减少 GFS 写入时的性能抖动带来的影响，Bigtable 使用两个线程写入日志，两者各自有独立的日志文件。如果第一个线程性能不佳，另一个线程就将接力日志写入任务。而日志序列号可以帮助删除重复的日志。
tablet 恢复优化
当 master 将 tablet 从 A 服务器移交给 B 时，A 将对 memtable 进行前述压缩操作，以减少需要重放的 redo log 大小。 这一操作完成后，A 不再对外服务该 tablet，此时，它将再进行一次压缩操作，将时间窗口内的日志进行压缩，再进行 tablet 转交，这样一来，B 服务器就可以直接装载 tablet，无需进行重放。