本篇是Bigtable[1]的阅读笔记，Bigtable的单机引擎与LevelDB基本一致，本文省略单机引擎的特性。

1 Data Model

Bigtable将数据组织成下面这样的map:

\[(row:string,column:string,timestamp:int64)\rightarrow string\]

对应用层而言，则可以将Bigtable视为如下的表结构：

Bigtable按row-key的字典序存储数据。同一个row-key的数据读写都是原子的，不论读写涉及到多少列。Bigtable按行做partition，每个partition称为一个tablet，分布及负载均衡都以tablet为最小单元。

Column keys被划分成若干个column family，column family是access control的单位，内存及磁盘用量计算也是以column family为基本单元的。同一个Column family下的各个column的数据是一起压缩的，且需预先创建并较少变更。

同一个cell按timestamp降序存储，保证新数据可以优先被读取。Bigtable支持保留最新的\(n\)个版本或者保存某个指定timestamp后的版本。

2 API

Bigtable API包括table及column family的创建删除，cluster, table, column family metadata的修改，如access control rights变更。以及数据的write/delete/look up/iterate。

3 Building Blocks

Bigtable使用GFS存储其log及data。文件格式使用google SSTable。

Bigtable依赖于chubby保证最多只有一个active master；存储数据初始位置；发现及结束tablet servers；存储schema；存储access control list。如果chubby一段时间不可用，则Bigtable不能提供服务。

4 Implementation

Bigtable实现包括三个主要部分，客户端library，master server及tablet server。

Master server负责分配tablet到tablet server上，并检测新加入的tablet server，剔除无响应的tablet server，均衡tablet server的负载，对GFS中无用的文件执行garbage collection等。

Tablet server管理一组tablet，处理这些tablet的读写，及分裂。

Client直接与tablet server通信，完成读写，也不依赖于master server提供位置信息，所以client无需与master server交互。

每个table从一个tablet开始，随着数据增多，自动分裂成多个tablet。

4.1 Tablet Location

Bigtable利用一个类B+ tree的结构存储tablet location信息。如下图：

Chubby中存root tablet的location info，root tablet中存metadata tablets的location info，metadata tablet中存各个tablet的location info。root tablet不分裂，以此保证树不超过三层。Metadata tablet的row-key包含table identifier和最后一行的信息。

Client会缓存tablet location，当发现没有缓存某个tablet的位置信息或者缓存的位置信息不正确时，client会递归拉取最新的tablet位置信息。Client会prefetch多个tablet的位置信息。

Metadata tablet中还存了tablet的event log方便debugging和performance analysis。

4.2 Tablet Assignment

Master server负责维护tablet的位置信息，包括未分配的tablet。Bigtable通过chubby来维持tablet server的心跳，每个tablet server对应chubby中的一个文件，只有当tablet server持有对应的lock时才提供服务。Master server周期性的询问各个tablet server对应lock的状态，如果不再持有锁或者联系不上tablet server，Master尝试在chubby获取锁状态决定是否要重新分配对应的tablet。

Master启动时先从chubby获取live tablet servers，再从各个tablet server获取assigned tablets，最后对比metadata tablet diff出unassigned tablet。Tablet创建，删除合并都由master发起，tablet分裂由tablet server决定。

References