4.2 BigTable的实现

本节介绍BigTable的具体实现。

4.2.1 tablet location

前面讲解了BigTable会把数据组织成表，表会被切分成tablet，并且master会把tablet分配给一个tablet server，这涉及BigTable的很多元数据，比如：

● BigTable中有哪些表。

● 每个表被切分成哪些tablet（每个tablet包含哪些范围的key，即起始行和结束行（endrow）是什么）。

● tablet都被分配给了哪个tablet server。

这些元数据也被保存成一个BigTable的表（叫作metadata表）。也就是说，元数据和普通数据采用了相同的存储逻辑，都被存储在tablet中。不过，BigTable对这个metadata表和存储元数据的tablet会进行特殊对待。

metadata表中存储着tablet location信息，metadata表中的每一行都是一个tablet location，一个tablet location中记录着这个tablet的信息，每个tablet（包括元数据的tablet，也包括普通数据的tablet）都在metadata表中有一行记录。

tablet location中包含的信息有：

● 这个tablet属于哪个表。

● 这个tablet拥有该表中的哪一段数据（用end row表示）。

● 目前这个tablet由哪个tablet server负责。

● 这个tablet被保存在GFS的哪些文件中。

BigTable对一个tablet所属的表的标识（table identifier）和该tablet的end row进行编码，生成这个tablet location的row key，来存储上面的前两条信息，而上面的后两条信息被存储在value中。

前面讲过，在chubby中存储了BigTable集群的基础信息，它就是一行tablet location记录。这行tablet location记录指向metadata表的第一个tablet，该tablet被称作root tablet。

BigTable采用三层的n叉树结构来存储数据。这棵树的每个节点都是一个tablet，如图4.2所示。

4.2.2 tablet的指派

前面讲到，需要将tablet指派给一个tablet server。在下面的几种情况下，会出现未被指派的tablet，并且需要将这些未被指派的tablet指派给一个tablet server。

● 创建新表，同时会创建该表的第一个tablet，BigTable会选择一个tablet server，并且将该tablet server的地址写入这个tablet在metadata表的这一行中，这样就完成了对这个tablet的指派（assignment）。

● tablet分裂。

● tablet server出现宕机，需要将该tablet server上的tablet重新指派（reassignment）给一个tablet server。

重新指派的过程比指派的过程要复杂，这里详细讲解一下。BigTable用chubby来追踪哪些tablet server是活的，如果发现有tablet server宕机，那么该tablet server上的所有tablet都不处于服务状态，master把这些tablet放到一个未指派集合中。未指派集合中的tablet会被master一次一个地分配给适合的tablet server。master修改metadata表中的该tablet对应的那一行tablet location记录，并且给选定的tablet server发送一个tablet加载请求（tablet load request），让这个tablet server从GFS中加载该tablet。

4.2.3 加载tablet

tablet中保存的信息（也称为tablet的状态）是持久化在GFS中的，以GFS文件的形式存在。前面讲过，在metadata表中，每一行tablet location记录，除了记录为该tablet所分配的tablet server，还记录一个GFS文件列表。这个列表中的文件就持久化保存着该tablet的状态。当tablet server加载一个tablet时，会先从metadata表中读取该tablet的location记录，从而知道这个tablet被保存在哪些GFS文件中。

tablet的状态被保存在两种类型的GFS文件中，即日志文件和数据文件。

● 日志文件中保存着重做（redo）记录，称为提交日志（commit log）。

● 数据文件是一种SSTable格式的文件。

在metadata表中，还会保存名为重做点（redo point）的信息，用来记录提交日志中哪部分还在内存（即memtable）中，哪部分已经写入GFS的数据文件中，完成了持久化。加载tablet的过程就是从GFS中读取日志文件，然后从重做点重新执行一遍redo log，在内存中重建memtable。此外，加载tablet，还包括将SSTable文件的索引加载到内存中，这里就不展开介绍了。

4.2.4 tablet的读/写操作

当tablet server加载tablet完成后，就可以处理读/写请求了。tablet的读/写过程如图4.3所示。

最近写入的数据会被保存在内存的buffer中，这个buffer叫作memtable。比较旧的数据会被保存在SSTable文件中。

● 执行tablet的写入操作，会先调用GFS的客户端向日志文件中追加一条redo记录，然后数据会被插入memtable中。

● 执行tablet的读取操作，需要先在memtable中查找数据，如果查找不到，则会调用GFS的客户端在SSTable文件中进行查找。

4.2.5 合并

随着不断地写入，memtable的长度会不断地增加，当达到一定的阈值之后，这个memtable会被冻结，同时一个新memtable会被建立。这个冻结的memtable会被转成一个SSTable文件写入GFS中，这个过程叫作小合并（minor compaction）。小合并可以减少内存的使用，并且缩短宕机后恢复的时间。

随着小合并的执行，SSTable文件会越来越多，每个读取操作都需要合并从这些SSTable文件中读取的结果。为了减少SSTable文件的数量，需要定期执行融合合并（merging compaction）。merging compaction会读取几个SSTable文件，合并成一个新的SSTable文件，再写回GFS中。

另外，还存在一种叫作大合并（major compaction）的过程。大合并会读取全部的SSTable文件，把它们合并成一个SSTable文件。