标题：Bigtable：结构化数据的分布式存储系统

今天来学习下大名鼎鼎的Google Bigtable的原论文，在当年称之为Google的三驾马车之一，是后面Hbase, Cassendra等等KV-store的开山之作。

Abstract

Bigtable有下面一些能力：

• 扩展能力：PB级别数据，数千台服务器
• 灵活性：可服务于各种数据类型，各种延迟需求（批处理到线上服务）

1. INTRODUCTION

• Bigtable像是一个数据库，但是不提供完整关系模型，只提供一个简单的数据模型，具体的数据属性要靠用户来推理。Bigtable只把数据当成无法解释的字符串。
• 用户可以通过scheme设计控制数据的局部性，也可以动态控制数据在内存还是在磁盘。

2. DATA MODEL

行、列、时间戳决定一个Cell，一个cell存一个值。

• 行：行按照Row key的字典序存储，row key是任意字符串。
  • 行是事务一致性的基本单元，一个事务只能读写一行，对行的更新都是可串行化的。
  • 连续的多行构成一个tablet，tablet是负载均衡的基本单元。因此行键的设计可以决定数据局部性。每个tablet大约1GB。
• 列：列会聚集成列族，列族是预先定义好的。列族一般很少，列的数量则不作限制。
  • 列族是访问控制（权限之类的）和审计的基本单位；
  • 正因为列族数量十分有限，所以也限制了meta data不会很大。
• 时间戳：每个cell数据的版本。

3. API

Bigtable的API主要是对表中行的更新和其它操作，以及对整个列族的Scan。

4. BUILDING BLOCKS

Bigtable用GFS作文件存储。文件格式是SSTable。锁服务用一个叫Chubby的软件，也是Paxos的一种实现【编者：在Hbase中，Chubby的任务应该由zookeeper来完成】。

• SSTable：不可变的key-value文件格式
  • SSTable统一按照key排序；
  • 由一系列blocks组成（每个默认64MB），每个block有index在内存中，指明key的范围；
  • 查询时首先在内存定位block，然后顺序读取块即可。

5. IMPLEMENTATION

Bigtable是主从架构，一个库可以用于连接每个客户端，一个master，许多tablet servers。

• master负责保持和tablet servers的联系，把tablets分配给tablet server，做负载均衡，回收掉过期数据，处理scheme change。
  • 由于tablet位置不在master上，所以很多client的数据大部分不经过master，直接和tablet server沟通。这样master的负载是非常轻的。
• tablet server一般负责几十到几百个tablets，处理其上的读写请求，当tablet过大时会对其进行分裂。

5.1 Tablet Location

Tablet位置不在master，那在哪里呢？请看下图：

• METADATA tablet一行管一个用户表中的tablet位置。也会有一些其它的log信息.各个tablet的breakpoint（文中称redo point）也存在这里。
• METADATA的Row key就是表名+某个tablet末尾的row key的一种编码。METADATA tablets全都在内存，只有MB级别，非常小。
• 客户端库会对tablet位置做缓存，如果缓存空的话，就要3次网络调用了，但由于在内存中就不涉及磁盘读取。除此之外，客户端库还会做预测读。都是为了减少寻址开销。

image.png

5.2 Tablet Assignment

【编者：这部分更多是容错、分布式协议的部分，编者能力有限，略述之】
tablet分配是master来做，它发现哪个server有空间，就把这个tablet塞给他，除非那个服务器挂了，否则必须接受干活。

• 每个tablet server在Chubby上有一个文件，只有这个Server有这个文件的互斥锁；master通过周期性的问tablet server其锁状态来跟踪这些服务器。
• master一旦发现谁失联了，会确认它是不是死了（Chubby上的文件是不是丢了），文件如果都没了的话，master就把它的tablets重新分配。

tablets发生变动的情况有4种：建新表，删表，小tablets合并，大tablets分裂。
前三个都是由master来初始化的，但是分裂是由tablet server初始化的。所以这里涉及一个通知master的问题。

5.3 Tablet Serving

所有更新操作首先写log，然后进入memtable，memtable也是按照row-key排序的。

• 恢复：tablet server一旦宕机，恢复时首先从METADATA tablet中读到自己负责哪些tablets，breakpoint在哪里，然后根据本地的log恢复memtable。
• 插入流程：首先是鉴权（鉴权信息各个tablet servers都会缓存的），然后写log，提交好之后写入memtable。
• 读取流程：首先是鉴权，然后以统一的视角看待memtable。因为row-key是排好序的，所以读取时候可以迅速定位读取。
• 读写在tablets分割和合并过程中均可以持续，在compaction过程也可以持续。

5.4 Compactions

• minor compaction: 当Memtable写满之后，立即冻结，然后启用一个新的memtable继续服务。老的要刷写到SStable中，即写回文件系统。每次刷写都要创建一个新的SStable。
• merging compaction：如果只有minor compaction的话，那么做一次读，要从任意多个SSTable中的数据做整合。解决方法是限制SSTable的数量，做merging compaction。一次merging compaction将读取几张SStables和memtable，写入一个新的SStable。
• major compaction：如果读取了全部SStables然后写入一个新的SStable，则称之为major compaction。major compaction会消除所有的更新和删除，变成最干净的数据。major Compaction由Bigtable定期轮询所有tablets执行。

因为数据写入时总之要写进GFS里，GFS会优先在writer服务器上写一份，所以tablet server上肯定会有自己负责的tablet上的数据，这为读取时提供了方便，省去了网络通信和网络带宽。

6. REFINEMENTS

本节讲调优。

6.1 本地组

本地组其实指的就是一个列族，其目的是不同列族之间往往不需要一起查询，设置本地组就可以在概念上隔离开不同的列族。这样很多参数就可以针对本地组来设置。

• 一个例子，METADATA table中的tablet-location列族，就被单独设置为在内存中，但是tablet-breakpoint就没有这样的设置。

6.2 压缩

压缩选项也针对于每个本地组。压缩对象是SStable的每个block。压缩算法暂时略过。

6.3 缓存

tablet-server的数据缓存分两个层级，Scan Cache是缓存返回的数据，Block Cache缓存从GFS里读上来的块。

6.4 布隆过滤器

如果SSTable比较多的话，那么每次读总是要读所有SStable才能得到数据确切的信息，这会造成许多磁盘访问。优化方法是引入布隆过滤器。用户可以为列族使用布隆过滤器，用于检验row/column对是否存在于指定列族。效果显著。

6.5 日志

如果为每一个tablet用单独的log file，那么log file就会太多，从GFS的层面来看，会有很多并发地写。解决方案就是一个tablet server用一个大的log file，所有tablet的修改全混在这个log file里面。

• 恢复问题：这种方法对于CRUD是方便了，但是恢复就麻烦了。当一个tablet server挂掉，它负责的tablets就会分散到很多其它tablet servers上。新服务器要像恢复tablet的状态，只能通读一遍原先的大log file，然后找出有用的执行。这太费时了。
• 新的回复算法：一个聪明的办法就是先把log file排序，按照〈table,row name,log sequence number〉的顺序，这样一个tablet负责的log record一定在连续的范围内，就不用重复读了。排序由master协调，作分布式的归并排序。
• 为了避免GFS写出现一些拥塞问题，实际上每个tablet server有两个写日志的线程，也有两个log file，一个慢的话就换另一个。

6.6 无恢复迁移

tablet迁移到不同的服务器上是常事，如果能避免tablet在新服务器上加载时要先执行恢复的话，能节省很多时间和流量。
具体方法是要卸载一个tablets时：

1. 做一次minor compaction
2. 停止这个tablet的服务
3. 做第二次minor compaction
4. 无恢复迁移

6.7 SStable不可变性的好处

• 读写分离：SStable只会有读，不会有写，那就完全不用管事务方面的隔离性，天生就可以同步读。
• 删除变成了文件整合：SStable通过major compaction实际执行删除操作。由于tablets对应的SStable在METADATA table中也有信息，这部分用标记清除法删，由master来处理。
• 分裂方便：两个孩子共享父亲的SStables，而非创建一组新的SSTables。