BigTable

BigTable发展于2004年，是一个用于管理大规模结构化数据的分布式存储系统，基于Google文件系统（Google File System，GFS），它有非常优秀的扩展性，可以同时处理上千台机器中的 PB 级别的数据。

于2005年投入使用，在 2006 年的 OSDI 上，Google 发布了名为 Bigtable: A Distributed Storage System for Structured Data 的论文，其中描述了一个用于管理结构化数据的分布式存储系统 - Bigtable 的数据模型、接口以及实现等内容。

Google 中的很多项目，都使用 Bigtable 来存储海量的数据；Bigtable 的论文中声称它实现了四个目标：

广适用性、扩展性、高性能、高可用性。

BigTable不是传统关系型数据库，不支持SQL语法，即NoSQL，无事务概念。

Bigtable 到底是如何实现的。

数据模型

Bigtable 与数据库在很多方面都非常相似，但是它提供了与数据库不同的接口，它并没有支持全部的关系型数据模型，反而使用了简单的数据模型，使数据可以被更灵活的控制和管理。

在实现中，Bigtable 其实就是一个稀疏的、分布式的、持久化存储的多维有序哈希表。

A Bigtable is a sparse, distributed, persistent multi-dimensional sorted map.

它的定义其实也就决定了其数据模型非常简单并且易于实现，我们使用 row key、column key 和 timestamp 三个字段作为这个哈希表的键，值就是一个未经解析的字节数组，也可以理解为字符串。

行关键字

row key 的长度最大可以为 64KB，对于同一 row key 下数据的读写都可以看做是原子的；

因 Bigtable 是按照 row key 字典序组织数据，所以可按 row key 的范围划分区间，并交给一个 tablet 进行处理，默认尺寸200M。

列族/簇

col key一般都表示一种数据类型，列关键字的集合称作列族。存储在同一列族下的数据属于同一种类型，列族下的数据被压缩在一起保存。数据在被存储之前必须先创建列族，并且表中的列族不宜过多，通常几百个，但表中可以有无限多个列。在Bigtable中列关键字的命名语法为：“列族：限定词”，列族名称必须是可打印的字符串，限定词则可以是任意字符串.

时间戳

Bigtable中的表项可以包含同一数据的不同版本，采用时间戳进行索引。时间戳是64位整型，既可以由系统赋值也可由用户指定。表项的不同版本按照时间戳倒序排列，即最新的数据排在最前面。为了简化多版本数据的管理，每个列族都有两个设置参数用于版本的自动回收，用户可以指定保存最近N个版本，或保留足够新的版本(如最近7天的内容)。

示例

JSON的数据格式展示了Bigtable的数据模型：

表名“tableName”，行名“rowA”。

“rowA”有两个列族“ColumnFamilyA”和“ColumnFamilyB”。

每个列族又可以同时拥有多个列，每列都有自己唯一的列标示符。例如，在列族“ColumnFamilyA”中有两列，分别为“IdentifierA”和“IdentifierB”。

每列同时存储多个版本的数据，每个版本的数据都有自己唯一的时间戳，且按时间戳递减的顺序排列。

实例

上面是一个用于存储海量网页的大表WebTable的存储结构，
以反转的URL作为row行名(方便过滤)，
以网页中的锚点保存在anchor列簇中，
以网页内容contents作为column列名。
contents列有3个版本，分别是t3,t5,t6，通过timestamp字段来区分版本。

具体的数据是通过行名（row name）和列名（column name）来进行索引的。

架构

Master的主要任务是向Tablet服务器分配Tablet，检测是否有新加入或者失效的Tablet服务器，对Tablet-server进行负载均衡，以及对GFS上文件进行垃圾收集。除此之外，它还可以进行模式修改，例如表和列族的建立。

每个TabletServer 都管理了一系列的Tablet。每个Tablet服务器处理它自身上面的Tablet的读写请求，并且当其上面的Tablets增长到一定程度对过大的Tablets进行分割。

和很多的单一Master分布式存储系统类似，客户端读取的数据不经过Master，客户直接和TabletServer 通信进行读写操作。

Bigtable依赖一个高可用和持续分布式锁服务器 Chubby 进行管理。Chubby提供了一个名字空间，里面包含了目录和小文件。每个目录或者文件可以当成是一个锁，读写文件的操作都是原子的。每个Chubby的客户程序都维护一个与Chubby服务的会话。

Bigtable使用Google的分布式文件系统（GFS）存储日志文件和数据文件。Bigtable集群通常运行在一个共享的机器池里，Bigtable依赖集群管理系统调度任务、管理共享机器上的资源、处理机器的故障以及监视机器的状态。

实现

在这一节中，我们将介绍 Bigtable 论文对于其本身实现的描述，其中包含很多内容：tablet 的组织形式、tablet 的管理、读写请求的处理以及数据的压缩等几个部分。

tablet 的组织形式

我们使用类似 B+ 树的三层结构来存储 tablet 的位置信息，第一层是一个单独的 Chubby 文件，其中保存了根 tablet 的位置。

Chubby 是一个分布式锁服务，类似于Zookeeper。

每一个 METADATA tablet 包括根节点上的 tablet 都存储了 tablet 的位置和该 tablet 中 key 的最小值和最大值；每一个 METADATA 行大约在内存中存储了 1KB 的数据，如果每一个 METADATA tablet 的大小都为 128MB，那么整个三层结构可以存储 2^61 字节的数据。

tablet 的管理

既然在整个 Bigtable 中有着海量的 tablet 服务器以及数据的分片 tablet，那么 Bigtable 是如何管理海量的数据呢？Bigtable 与很多的分布式系统一样，使用一个主服务器将 tablet 分派给不同的服务器节点。

为了减轻主服务器的负载，所有的客户端仅仅通过 Master 获取 tablet 服务器的位置信息，它并不会在每次读写时都请求 Master 节点，而是直接与 tablet 服务器相连，同时客户端本身也会保存一份 tablet 服务器位置的缓存以减少与 Master 通信的次数和频率。

读写请求的处理

从读写请求的处理，我们其实可以看出整个 Bigtable 中的各个部分是如何协作的，包括日志、memtable 以及 SSTable 文件。

当有客户端向 tablet 服务器发送写操作时，它会先向 tablet 服务器中的日志追加一条记录，在日志成功追加之后再向 memtable 中插入该条记录；这与现在大多的数据库的实现完全相同，通过顺序写向日志追加记录，然后再向数据库随机写，因为随机写的耗时远远大于追加内容，如果直接进行随机写，由于随机写执行时间较长，在写操作执行期间发生设备故障造成数据丢失的可能性相对比较高。

当 tablet 服务器接收到读操作时，它会在 memtable 和 SSTable 上进行合并查找，因为 memtable 和 SSTable 中对于键值的存储都是字典顺序的，所以整个读操作的执行会非常快。

表的压缩

随着写操作的进行，memtable 会随着事件的推移逐渐增大，当 memtable 的大小超过一定的阈值时，就会将当前的 memtable 冻结，并且创建一个新的 memtable，被冻结的 memtable 会被转换为一个 SSTable 并且写入到 GFS 系统中，这种压缩方式也被称作 Minor Compaction。

每一个 Minor Compaction 都能够创建一个新的 SSTable，它能够有效地降低内存的占用并且降低服务进程异常退出后，过大的日志导致的过长的恢复时间。既然有用于压缩 memtable 中数据的 Minor Compaction，那么就一定有一个对应的 Major Compaction 操作。

Bigtable 会在后台周期性地进行 Major Compaction，将 memtable 中的数据和一部分的 SSTable 作为输入，将其中的键值进行归并排序，生成新的 SSTable 并移除原有的 memtable 和 SSTable，新生成的 SSTable 中包含前两者的全部数据和信息，并且将其中一部分标记为删除的信息彻底清除。

Ref

Bigtable 论文的原文 Bigtable: A Distributed Storage System for Structured Data 。