bigtable

Bigtable论文，称作google的三驾马车（MapReduce，DFS，Bigtable）之一。Hadoop系统就是基于MapReduce和DFS论文的开源实现，而hbase是bigtable的开源实现。bigtable具有如下特点：

• 分布式存储系统
• 存储的是结构化数据
• 集群，海量数据
• 支持批处理，也支持实时数据读取
• 低延迟

1. Introduction

bigtable被设计成可以部署在上千台机器上，容纳P级别数据的系统。即可用于面向吞吐率的批处理场景，也可以用于面向终端用户的低延迟场景。
在很多方面，bigtable类似于数据库，或者说，采用了类似于数据库的实现策略。如，类似于并行数据库和内存数据库的高性能。但是，bigtable并不是一个严格意义上的数据库，只支持数据库的部分模型，其提供了一些对数据分布和格式的动态控制。数据通过row和column的名称来索引，可以是任何字符串，bigtable对这些字符串不解析，只是存储。

2. Data Model

A Bigtable is a sparse, distributed, persistent multidimensional sorted map.
The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes.
Bigtable是一个稀疏的，分布式的，持久化的多维有序映射表。键是row key，column key，时间戳组成，值是一个不需解释的字节数组。

bigtable数据模型

Row（主键）

row key可以是任意的字符串，长度上限是64KB，但一般10-100个字节足矣。对一个rowkey的读和写都是原子操作。
Bigtable通过字典序对rowkey进行存储。当bigtable的数据量越来越多时，就要对数据进行划分（partition），聚在一起的数据就叫做tablet，tablet是分布和负载均衡的最小单位。

Column Families（列簇）

列簇下面可以有多个字段，是访问控制的最小单位。列簇里面的数据都是相同的数据类型。列簇需要先创建，然后才能向其添加字段，存储数据。一个bigtable最好列簇不要太多，一般保持在100个左右，但是一个列簇里面的字段数量是不限制。
column key的语法格式是column family:qualifier。列簇的名字是可见字符，但是qulifier可以是任意字符串。
访问控制和内存硬盘存取设置，都是针对列簇级别的。

Timestamps（时间戳）

值可以有多个时间戳，也就是说有多个版本，按时间戳的倒序排列，默认显示最新的时间戳。
存储的时候，可以自己指定时间戳的值，也可以由系统指定。如果自己指定，请注意时间戳的唯一性，避免冲突。
时间戳还可以用于值的清理，有两种设置，一种是最多保持多少个版本，历史版本的就会被清理回收掉；另一种是，保留多久，过期就会被清理。

3. API

bigtable可以作为mapreduce的输入和输出。

4. Building Blocks

bigtable构建于一些谷歌基础框架之上。采用GFS来存储日志和数据文件。底层采用谷歌内部一种叫做SSTable的文件格式。

SSTable本身是一个持久化，有序的，不可变的映射map，其key和value可以是任意字符串。可以通过单个key查询value，也可以通过指定key的范围查询一批value。SSTable内部包含一系列Block(大小一把为64KB，可配置)。Block的索引，存储于SSTable的底部，可用于定位Block；当SSTable被打开时，Block的索引还会被加载到内存中。通过索引，可以找到Block，然后通过一次磁盘读取，将Block整个加载到内存中，即可完成查找。如果SSTable可以被读取到内存，那么就可以省略掉这一次磁盘读取，直接在内存中进行操作。

还采用Chubby（开源实现，zookeeper）来实现高可用和分布式锁服务。包括，确保只有一台master节点存活；发现tablet server以及tablet server的下线；存储bigtable的schema信息（列簇信息）；存储控制列表等。

5. Implementation

The Bigtable implementation has three major components: a library that is linked into every client, one master server, and many tablet servers.
tablet server可以被动态的添加or删除。

master节点的工作职责如下：

• 分配tablet到tablet server
• 处理tablet server节点的添加or删除
• tablet server的负载均衡
• GFS文件的垃圾回收
• table的元数据管理，如table变更，列簇变更等

tablet server节点的工作职责如下：

• 管理tablet，一般一个节点可以有 1000个tablet
• 负责本节点的tablet的读or写
• 负责tablet的split操作

和每个单主节点的分布式存储一样，client不会将数据移动到master节点：client直接与tablet server节点进行读写操作交互。client也无需和master进行交互来获取tablet位置信息，因此master节点的负载很小。
bigtable集群有多个table，每个table有多个tablets组成，每个tablet对应一个rowkey区间的数据。table创建时，只有一个tablet，随着数据的变多，tablet会进行split操作，一般一个tablet有100-200MB大小。

5.1 Tablet Location

tablet索引信息

tablet位置信息是由一种类似于B+树的三层层次结构来存储的，如下图所示。

Tablet localtion hierarchy

• 第一层是全局tablet位置信息，每一行对应第二层中每一个tablet的第一行位置信息，索引的rowkey之间跨度最大
• 第二层可以有多个tablet，每个tablet是存储的是实际tablet的位置信息，按表名和结束rowkey作为键存储
• 第三层就是真实tablet，每行就是一个真实的row。
  三层结构，可以有效的通过前两层，定位到最终要读取的tablet。

5.2 Tablet Assignment

tablet分配

这个部分就是Chubby(zookeeper)来做分布式协调服务的案例。
一个tablet一次只能分配给一个tablet server。master节点维护tablet server的健康信息，负责分配tablet。当一个tablet待分配时，master就会查找当前有哪些tablet server有空间，然后就会发送一个tablet分配请求给tablet server，等待分配。
bigtable采用Chubby来跟踪tablet server的健康信息。当tablet server启动时，先获取一个排它锁，即在Chubby的目录下创建一个命名文件。如果能创建成功，就可以启动了。master节点会监控这个目录，来获取当前有哪些tablet server是存活的。如果一个tablet server失去了这个排它锁，那么就会停止服务。tablet server会再次尝试获取这个排它锁，如果这个文件还存在的话。如果这个文件不存在了，那么这个tablet server就不再服务了，server会自己关闭。如果一个tablet server终止服务了，那么就会释放掉这个排它锁，master节点就会将该server上的tablet重新分配给其他存活的server。
当master节点启动时，它需要获取启动之前已分配的tablet信息。master节点启动时步骤如下：

1. master节点通过Chubby获取一个排它锁，这样能确保只要一个master节点启动；
2. master节点扫描Chubby的server目录，获取当前存活的server节点列表；
3. master节点与tablet server节点通信，获取各个server上已经分配的tablet列表；
4. master节点扫描METADATA表获取tablets集合信息。
   只有当table创建或删除时，已经存在的tablets集合才会变化，如当两个tablet合并成一个大的tablet，或当一个大的tablet分裂成两个小的tablet。master节点能够跟踪到合并信息，但是分裂动作是由tablet server发起的。tablet server提交分裂的新的tablet信息到METADATA表，当split完成后，会通知给master节点。

5.3 Tablet Serving

读写流程

最终数据是存储在GFS上。
最近更新和追加的数据写到一个commit log文件中，并写到一个排序的内存buffer（memtable）中。
最终数据+memtable or commit log中的数据，就是当前完整的数据。

tablet模型

写流程。当写操作到达tablet server，server先检查格式和权限。如果都没问题，则写入commit log，然后写入memtable。也可以批量提交，会提供吞吐率。
读流程。当读操作到达tablet server，server先检查格式和权限。然后基于SSTables和memtable组成合并视图，进行查询。由于SSTable和memtable是按字典序存储的数据结构，因此合并操作很高效容易。

5.4 Compactions

合并

当上一节的更新写到一定程度时，就要生成SSTable，从而减少memtable的内存压力。当memtable到达一定的阈值后，memtable就会被冻结，然后创建一个新的memtable，冻结的memtable就会被转化成SSTable，并写到GFS中。minor compaction有两个目标：

1. 缩减tablet server的内存大小消耗
2. 避免tablet server崩溃后恢复时，需要读取太多未合并的commit log，影响恢复速度，实际上就是早点将未持久化的数据落地，落地为安

每次minor compaction就会生成一个SSTable文件。如果SSTable很小，并且过多，那么一次read操作就可能需要读取多个SSTable并合并，因此需要进行major compaction。
如果说minor compaction是将memtable或commit log生成SSTable，那么major compaction就是将多个SSTable合并成一个SSTable的过程。minor compaction生成的SSTable可能还包含已删除的数据，但在major合并的过程中，会将这些数据清除掉。

6. Refinements

Locality groups

多个列簇可以存储到一个locality group。一个tablet中，可以有多个locality group，每个group对应一个SSTable。如果列簇不需要一起读取，则无需存储到一个locality group，这样读的效率会高些。个人理解，locality group类似于数据块，每次读取时候，会全部读取，这样即使本次不用读取的列簇，也需要读取了。

Compression

压缩针对的是SSTable block，采用两轮压缩。
第一轮，采用Bentley and McIlroy's 压缩，最长公共前缀压缩；
第二轮，快速压缩算法
压缩在bigtable中，首先考虑的是速度，其次才是压缩比。但实际上，公共前缀压缩就有较好的效果，因为SSTable中的数据是有序的，相近rowkey的数据可能会相似，因此有较多的公共前缀；其次，数据多版本之间，内容相似。因此最终压缩比在10比1左右。

Caching for read performance

两个层次的缓存
其一，高层次，缓存到具体的rowkey，下次读取同一个rowkey较快
其二，低层次，缓存到SSTable block信息，读取相同block的rowkey较快

Bloom filters

布隆过滤器

采用布隆过滤器来判断一个rowkey/column对是否在SSTable中。如果结论是不在，那么一定不在，如果结论是在，那么有一定的概率最终不在SSTable，但是这种误判是可以接受的。因为它以较小的代码判断了不在的问题。如果误判了，那么无非就是读一次SSTable。可以有效的减少磁盘访问次数。

Commit-log implementation

bigtable采取的是一个tablet server有一个commit-log文件。采用上述实现，写的效率是高的，但是recovery就复杂了。如果tablet server挂了，需要将tablet重新分配，如果有10个tablet server接到了分配任务，各自取一部分tablet进行恢复。为了恢复tablet，需要先获取原先tablet server写的commit-log，重新执行一次。但如果只有一个commit-log，那么多个tablet写到commit-log，是否都要复制到新的tablet server，实际上这里面只有一些是需要的。
bigtable是按照如下方法解决这个问题的。先按<table, row name, log sequence number> 作为key进行排序，有序了，所有对同一个table的操作就是连续的，读取就方便多了。还可以将log文件按段划分，然后在不同的tablet server对各个段进行排序。

Speeding up tablet recovery

Exploiting immutabilty

SSTable是不可变的，即只能追加，不能更新。因此就不需要进行加锁同步操作了。由于SSTable是不可变的，因此清理已经删除的数据，就转移到对SSTable进行回收时进行。

7. Performance Evaluation

8. Real Applications

9. Lessons