BigTable论文分析

一、BigTable简介

1.BigTable

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

2.GFS和MapReduce

GFS 和 MapReduce 通过非常简单的设计，解决了海量数据的存储、顺序写入，以及分布式批量处理的问题。
不过，GFS 和 MapReduce 的局限性也很大。在 GFS 里，数据写入只对顺序写入有比较弱的一致性保障。而对于数据读取，虽然 GFS 支持随机读取，但是考虑到当时 Google 用的是孱弱的 5400 转的机械硬盘，实际上是支撑不了真正的高并发地读取的。而 MapReduce，它也是一个批量处理数据的框架，吞吐量（throughput）确实很大，但是延时（latency）和额外开销（overhead）也不小。
所以，即使有了 GFS 和 MapReduce，仍然有一个非常重要的需求没有在大型的分布式系统上得到满足，那就是可以高并发、保障一致性，并且支持随机读写数据的系统。而这个系统，就是Bigtable。

3.设计目标

wide applicability
scalability
high performance
high availability

二、Bigtable诞生前面临的问题

1. 业务需求

（1）网页存储
Google每天要抓取很多网页：

• 新出现的网页，新URL
• 旧网页，旧URL

对一个已抓取的网页，旧URL为什么要反复抓取？
因为网页会更新，例如新浪首页：sina.com.cn/index.html，URL虽然没有变，但依然会抓取。

这里，对于存储系统的需求，是要存储：不同URL、不同时间Time，的内容Content。
URL+“Content”+Time => Binary。
网页的实际内容Binary，是Spider抓取出来的。
（2）Google Analytics
Google Analytics要给站长展示其网站的流量PV，独立用户数UV，典型访问路径等，以帮助站长了解站点情况，优化站点。
这里，对于存储系统的需求，是要存储，不同URL，不同时间Time，的PV和UV。
URL+”PV”+Time => $count
URL+”UV”+Time => $count
PV和UV的值，是MapReduce离线任务计算出来的。
（3）不管是“网页存储”还是“站点统计”存储，它们都有几个共同的特点：

• 数据量极大 ： TB，PB级别
• 和时间维度相关
• 同一个主键，属性与值有映射
  主键是URL，属性是“Content”，值是网页Binary；
  主键是URL，属性是“PV”和“UV”，值是计数count。

2. 当前技术解决

（1）关系型数据库——二维table，解决Google网页存储

如上图所示，如果没有时间维度Time，似乎是可以的：

• 主键，使用URL
• 属性，schema的列名，例如content，author等
• 值，不同URL的内容与作者等值
  但是，一旦加入时间维度Time，二维table似乎就不灵了。

增加一个time属性是没有用的；
增加一个time属性，只能记录同一个URL，某一个time的content，不能记录多个time的多个content；
增加一个time属性，联合主键，URL就不是KEY了；

（2）关系型数据库——用二维table存储三维数据

如上图所示，仍然是二维table，通过URL+Time来瓶装key，也能够实现，存储同一个URL，在不同Time，的不同content、author。
但是，这种trick方案存在的问题是：没法实现URL查询（key上无法进行%like%查询。）
大量空洞，浪费存储空间，这并不是一个好的方案。况且，当数据量达到TB、PB级别时，传统单机关系型数据库，根本无法满足Google的业务需求。

3.Bigtable解决的问题

传统二维small table，无法解决Google面临的存储问题，于是Google搞了一个big table来解决。
Google对这些业务模型进行分析，在二维table的基础上扩充，抽象了一个新的“三维table”：

• 主键，使用URL
• 属性，schema的列名，例如content，author等
• 时间，timestamp
• 值，不同URL的内容与作者等值
  
  如上图所示：
• 第一维：key（黄色）
• 第二维：属性（橙色）
• 第三维：time（蓝色）
  同一个key，不同属性，不同时间，会存储一个value。
  不像以行为单位进行存储的传统关系型数据库，这个三维的大表格BigTable是一个稀疏列存储系统。（能够压缩空间。）
  它的数据模型的本质是一个map：key + column + time => value的一个超级大map。

很多业务符合这一个模型；
Google的东西能解决业务问题，所以用的人多，这一点很重要。

4.总结

BigTable是一个稀疏的、分布式的、持久化的、多维度排序的、大数据量存储系统，它能够解决符合上述map数据模型业务的存储问题。

GFS是文件系统；
MapReduce是计算模型；
BigTable是存储系统。

三、Data Model

1.结构简介

bigtable虽然名字上有“表”，其逻辑上也确实可以提供表的功能，但实际上的物理结构是基于Map实现的，是一个多维有序map。
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.
关键点：

• Persistent：一个表是一个包含海量 Key-Value 键值对的 Map，数据是持久化存储的；
• Distributed：这个大的 Map 需要支持多个分区来实现分布式；
• Multidimensional Sorted Map：这个 Map 按照 Row Key 进行排序，这个 Key 是一个由 {Row Key, Column Key, Timestamp} 组成的多维结构；
• Sparse：每一行列的组成并不是严格的结构，而是稀疏的，也就是说，行与行可以由不同的列组成：
  Bigtable 的数据模型具体来说就是：Bigtable 的每一个键值对的 Key 都为 Row key + Column key + Timestamp 的结构，Value 则是字符串。

2.bigtable的数据模型：

例如，用于存储爬虫爬取下来的网页，row key就是网址，有两个列簇，contents(用于存储网页内容)和anchor（用于存储网页内部的链接锚url）。如图1所示。一个rowkey可以在3个不同的时间戳(t3,t5,t6)，有3个不同的内容，即有3个值，默认显示最新的。列簇anchor有2个字段。

3.专有名词

（1）Row Key

行关键字可以是任意字符串，最大容量为 64KB，但是在大多数场景下，字节数只有 10～100 Bytes 左右。
Bigtable 按照 Row key 的字典序组织数据。

什么是字典顺序？ASCII 码表中的后面的字符比前面的字符大，比如 c>a，因为 Row Key 本质就是字符串，因此可以使用字典顺序进行排序。

利用这个特性可以通过选择合适的行关键字，使数据访问具有良好的局部性。如 Webtable 中，通过将反转的 URL 作为行关键字，可以将同一个域名下的网页聚集在一起。

网站的反转指的是 www.google.com 反转为 com.google.www，类似于 Java 中的 package 的命名。为什么需要进行翻转？因为 URL 解析过程本身就是从后往前解析的，这符合 URL 的使用逻辑。另一方面，方便域名管理，将同一个域名下的子域名网页能聚集在一起。拿 www.github.com 作为一个 URL 的一个例子，为 www 开头的 URL 建立集群的意义并不大（没有区分度，相当于没有建集群），但是将 com.github 域名建立集群就有一定的使用用途了。

注意：在 Bigtable 中仅仅涉及一个 Row key 的读/写操作是原子的。支持行级事务

（2）Tablet（Bigtable的水平分区）

在 Bigtable 中，Row Key 相同的数据可以有非常多，为此 Bigtable 中表的行区间需要动态划分（也就是横向进行数据分区，横向的意思便是将表横着切），每个行区间称为一个 Tablet（子表）。
Tablet 是 Bigtable 数据分布和负载均衡的基本单位，不同的子表可以有不同的大小。为了限制 Tablet 的移动成本与恢复成本，每个子表默认的最大尺寸为 200 MB。Tablet 是一个连续的 Row Key 区间，当 Tablet 的数据量增长到一定大小后可以自动分裂为两个 Tablet。同时 Bigtable 也支持多个连续的 Tablet 合并为一个大的 Tablet。

（3） Column Key 与 Column Family

Column Key 一般都表示一种数据类型，Column Key 的集合称作 Column Family(列族)。存储在同一 Column Family 下的数据属于同一种类型，Column Family 下的数据被压缩在一起保存。
Column Family 是 access control（访问控制）、disk and memory accounting（磁盘和内存计算）的基本单元。
数据在被存储之前必须先确定其 Column Family，然后才能确定具体的 Column Key，并且表中的 Column Family 不宜过多，通常几百个。但 Column key 的个数并不进行限制，可以有无限多个。在 Bigtable 中列关键字的命名语法为：family:qualifier 即 “列族:限定词”，列族名称必须是可打印的字符串，限定词则可以是任意字符串。如 Webtable 中名为 anchor 的列族，该列族的每一个列关键字代表一个锚链接；anchor 列族的限定词是引用网页的站点名，每列的数据项是链接文本。

（4）TimeStamp

Bigtable 中的表项可以包含同一数据的不同版本，采用时间戳进行索引。时间戳是 64 位整型，既可以由系统赋值也可由用户指定。时间戳通常以 us（微秒）为单位。时间戳既可以由 Bigtable 进行分配，也可以由客户端进行分配，如果应用程序希望避免冲突，应当生产唯一的时间戳。
表项的不同版本按照时间戳倒序排列（大的在前，时间戳越大表明数据加入的时间越晚），即最新的数据排在最前面，因而每次查询会先读到最新版本。为了简化多版本数据的管理，每个列族都有两个设置参数用于版本的自动回收，用户可以指定保存最近 N 个版本，或保留足够新的版本(如最近 7 天的内容)。

在 Bigtable 论文的 Webtable 例子中，contents family 存储的时间戳是网络爬虫抓取页面的时间，表中的回收机制可以选择保留任一页面的最近 3 个版本。

4. 使用示例

Map中的索引key包含行关键字 + 列关键字 + 时间戳 三个部分，Map中的每个value都是一个未经解析的byte数组，这些存储的数据都被视为字符串，Bigtable本身不去解析这些字符串，它们通过客户程序把各种结构化或者半结构化的数据序列化到这些字符串里。

如上图一个表Table的示例，经过上述多维度排序Map转换为BigTable数据模型如下所示，其中行关键字为apple的Logo列有六个版本，分别由时间戳1976 ,1977 ,1998 ,2000 ,2001 ,2013标识。

四、API

1.Bigtable提供了建立和删除表以及列族的API函数。Bigtable还提供了修改集群、表和列族的元数据的API，比如修改访问权限。
2.客户程序可以对Bigtable进行如下的操作：写入或者删除Bigtable中的值、从每个行中查找值、或者遍历表中的一个数据子集
3.Bigtable支持单行上的事务处理，利用这个功能，用户可以对存储在一个行关键字下的数据进行原子性的读-更新-写操作。虽然Bigtable提供了一个允许用户跨行批量写入数据的接口，但是，Bigtable目前还不支持通用的跨行事务处理。
4.Bigtable允许把数据项用做整数计数器
5.Bigtable允许用户在服务器的地址空间内执行脚本程序。
6.Bigtable可以和MapReduce一起使用，MapReduce是Google开发的大规模并行计算框架。通过使用Google开发的一些Wrapper类，Bigtable可以作为MapReduce框架的输入和输出。

五、Bigtable的架构

1.Bigtable依赖其他的几个google基础构件：

(1) google flie system：用gfs存储日志和数据文件
(2) google sorted string table：为了加快数据的查找和存储效率，Bigtable在存储数据之前都进行了排序，而用到的内部存储文件格式就是SSTable(Sorted String Table)，关于sstable可以参照leveldb。
SSTable本身是一个持久化，有序的，不可变的映射map，其key和value可以是任意字符串。可以通过单个key查询value，也可以通过指定key的范围查询一批value。SSTable内部包含一系列Block(大小一般为64KB，可配置)。Block的索引，存储于SSTable的底部，可用于定位Block；当SSTable被打开时，Block的索引还会被加载到内存中。通过索引，可以找到Block，然后通过一次磁盘读取，将Block整个加载到内存中，即可完成查找。如果SSTable可以被读取到内存，那么就可以省略掉这一次磁盘读取，直接在内存中进行操作。
(3) chubby：因为bigtable是分布式的数据库，在节点的协调上需要额外的处理，这里用chubby协调服务，例如master选举、元数据保存等。可以把Chubby看作是Zookeeper,因为Zookeeper本质也是Chubby的开源版本。
(4) workqueue : 依赖WorkQueue负责故障处理和监控

2.架构

(1) Bigtable 集群(cluster)通常在运行其他分布式应用程序的共享机器池(shared pool of machines)中，这是因为 Bigtable 本质是一个进程，Bigtable 进程通常与其他应用程序的进程共享同一台机器。Bigtable 依赖于集群管理系统来调度作业、管理共享机器上的资源、处理机器故障和监视机器状态。
(2）Bigtable包含几个主要组件：链接到客户程序中的库、master节点、多个子表服务器tablet server。
其中master负责为tablet server分配tablet、检测新加入的或者失效的tablet server、对tablet server进行负载均衡、对保存在gfs上的文件进行垃圾收集。
为了适应工作负载的变化，可以动态地向集群中添加或删除子表服务器。

3.tablet

见另一篇博客Tablet简介

六、Bigtable依赖的组件

1.Chubby

Bigtable 依赖于 Chubby 提供的锁服务，如果 Chubby 长时间不能访问，Bigtable 也会无法使用。Bigtable 依赖于 Chubby 完成以下任务：

• 确保任意时间至多存在一个活跃的主服务器副本；（即 At most one active master at any time.）
• 存储 Bigtable 中数据的 bootstrap location（引导位置）；（root tablet的地址存储在Chubby里）
• 发现 Tablet（子表）服务器，并在子表服务器失效时进行善后；（tablet server在Chubby的指定目录有一个对应的文件和该文件的锁）
• 存储 Bigtable 的 schema 信息，即表的 column family 信息；
• 存储 access control lists（访问控制列表）；
  注意：如果集群内的 Chubby 在长时间内不可用（比如宕机或者网络问题），那么整个 Bigtable 系统也将会不可用。但是如果系统内仅仅是部分 Chubby 不可用，那么事实上只会导致 Bigtable 的部分数据不可用。

2.主服务器

主服务器起到系统管家的作用，主要用于为Tablet服务器分配Tablet、检测Tablet服务器的加入或过期、 进行Tablet服务器的负载均衡和对保存在 GFS 上的文件进行垃圾收集。主服务器持有活跃的Tablet服务器信息、Tablet的分配信息和未分配Tablet的信息。如果Tablet未分配，主服务器会将该Tablet分配给空间足够的Tablet服务器。

3.Tablet服务器

每个Tablet服务器管理一组子表（a set of tablets），负责其磁盘上的Tablet的读写请求，并在Tablet过大时进行Tablet的分割。与许多单一主节点的分布式存储系统一样，读写数据时，客户端直接和Tablet服务器通信，因此在实际应用中，主服务器的负载较轻。

4.客户端程序库

客户端使用客户端程序库访问 Bigtable，客户端库会缓存Tablet的位置信息。当客户端访问 Bigtable 时，首先要调用程序库中的 Open() 函数获取文件目录，文件目录可能在缓存中，也可能通过与主服务器进行通信得到。最后再与Tablet服务器通信。

七、客户端的数据读取流程

1.我们之前已经提到了 Bigtable 的一大特点便是提出一种不同于传统关系型数据库的模型，即更为灵活的 Key-Value 数据存储模型，对外暴露一个逻辑上的多维表：
(row:string, column:string, time:int64) → string
因此当客户端读取数据时，在内部有如下的执行流程：

• 首先，确定 Row Key；（确定在哪个tablet）
• 其次，根据 Row Key 查找特定的 Column Key；
• 最后，根据 colomn 以及 version 确定具体读取的内容；

这是一个多维表查询的典型过程，这个过程类似于磁盘的直接读取，先确定分区，在顺序读写。

2.客户端定位子表服务器时：

• 首先，需要访问 Chubby 以获取根子表(root tablet)地址，然后浏览元数据表(metadata tablet)定位用户数据；
• 然后，子表服务器会从 GFS 中获取数据，并将结果返回给客户端。

Bigtable 数据访问结构如下图所示。如果客户端不知道子表tablet的地址或缓存的地址信息不正确，客户端会递归查询子表tablet的位置。若客户端缓存为空，寻址算法需要三次网络往返通信(root tablet——>other metadata tablets——>metadata tablets)；如果缓存过期，寻址算法需要六次网络往返通信才能更新数据。地址信息存储在内存中，因而不必访问 GFS，但仍会预取子表tablet地址来进一步减少访问开销。元数据表中还存储了一些次要信息，如子表tablet的事件日志，用于程序调试和性能分析。

3.通常而言，为了加快数据访问以及数据的分块存储管理，存储系统通常会提供各种排序逻辑，在 Bigtable 中的排序逻辑主要有三种：

• 利用 Row Key 进行排序，目的是横向化划分为多个 Tablet，避免形成超大块的数据，便于数据管理；
• 利用 Column key 以及 Column family 进行排序，目的是加快检索时的速度；
• 利用 timestamp 的天然时间线排序，目的是提供多版本控制以及过期数据的自动回收；

八、Bigtable的设计特点

1.Non-SQL接口

提供自定义的数据读写接口而非用户已习惯的 SQL 接口，会带来额外的学习成本。

2.Master-Slave架构

3.Schema Less

Bigtable 本是为结构化数据存储而设计的，却采用了 Schema Less 的设计。论文中提及的关于网页数据存储的场景，应该是促成该设计的最大因素。另一方面，可以猜测，Schema 变更在 Google 内部是经常发生的。所以，最后选定了 SSTable (在 Google 内部先于 Bigtable 而出现) 作为底层的文件存储格式。
该设计的优势在于能够支持 Schema 的灵活变更，不需要预先定义 Schema 信息。
但该设计的缺点也非常明显：

• Key-Value 中携带了充分的自我描述信息，导致数据有大量的膨胀。
• 在数据压缩粒度上比较受限。

4.Range分区

优点：

• Range 分区能够很好的保证数据在底层存储上与 Row Key 的顺序是一致的，对 Scan 类型查询比较友好。

缺点：

• 对用户 Row Key 的设计提出了非常高的要求。
• 容易导致数据不均匀。

5.事务支持

Bigtable 论文中提到仅需要支持单行事务的设计初衷：

We initially planned to support general-purpose transactions in our API. Because we did not have an immediate use for them, however, we did not implement them. Now that we have many real applications running on Bigtable, we have been able to examine their actual needs, and have discovered that most applications require only single-row transactions.

从业界已广泛应用的 HBase 的应用场景来看，单行级别的事务还是可以满足大多数场景的，也正因为放弃了对复杂事务的支持，Bigtable/HBase 才能够取得吞吐量以及并发上的优势，正如上述观点中提到的，Bigtable 不加入分布式事务是不希望系统变得复杂。

6.计算与存储分离

Tablet Server 中仅仅提供了数据读写服务入口，但并不存储任何数据，数据文件交由底层的 GFS/Colossus 来存储，可以说，这是一个典型的计算与存储分离的架构。
该架构优点：

• 分层设计，每一层更专注于自身的业务能力。
• Tablet 在 Tablet Server 之间迁移时，不需要移动底层的数据文件。
• Tablet Server 故障不会导致数据丢失问题。
• 可更充分的利用每一层的资源，降低整体的成本。
• 更适合云上服务架构模型。

缺点：

• 更多的网络开销。

7.可用性

存储于底层 GFS 中的文件有多个副本，但 Tablet 本身却是单副本的，当 Tablet Server 故障或因负载均衡原因对 Tablet 进行迁移时，就会导致 Tablet 短暂不能提供读写服务，带来可用性问题。

九、优化

1.局部性群组Locality groups

（1) bigtable的key是（行、列、时间戳）的三元组，通过将不同列合并为一个局部性群组，可以为数据定制存储形式。
例如，以行为url举例，一个url有很多列，大致可以分为两类，一类是元数据，例如语言、编码格式等，这类数据特征是占用存储空间小，访问频繁；另一类是html body，这类数据的特点是占用存储容量大。根据这两类分成两个局部性群组后，每个群组的文件存储在不同的sstable文件，这样在读取元数据时，不用连带读取大块的html body，大幅提升了读取效率，同时可以为不同的局部性群组选取不同的物理存储介质，例如元数据存在ssd中，html body存在磁盘上。
(2) 多个列簇可以存储到一个locality group。一个tablet中，可以有多个locality group，每个group对应一个SSTable。

2.缓存Caching for read performance

缓存有两个方面：
一方面client缓存tablet地址信息数据，不用每次都从chubby文件开始访问；
另一方面，tablet server对数据内容建设缓存机制，实际上就是leveldb中的缓存机制，对sstable的key-value和block进行缓存（Tablet Server使用Scan Cache缓存SSTable返回的数据，在重复读时提高效率。使用Block Cache缓存从GFS读取的SSTable，这样在读取附近的数据时就无需从磁盘读取），前者利于时间局部性好的程序，后者利于空间局部性好的程序。（两个层次的缓存）

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

3.bloom filter

bloom filter是针对读操作的优化，针对每个sstable文件都有一个关联的bloom filter并维护在内存中，在sstable磁盘文件访问前先查询bloom filter进行过滤，这样可以大幅减少磁盘文件访问，具体实现细节见leveldb源码分析。

4.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对各个段进行排序。

5.Exploiting immutabilty

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

参考文章：
Google BigTable到底解决了什么问题？
浅谈Google的三驾马车之BigTable