NoSQL database： Big Table

关系型数据库曾经在网站和企业应用中都是占统治地位的结构化数据存储技术。自从上世纪70年代关系型数据诞生，一直到本世纪初，关系型数据库和SQL语言几乎是结构化数据存储和访问的唯一选择。这几乎是一个奇迹 - 想象一下， 同一时期，硬件技术，软件开发技术变化可以用天翻地覆来形容。而这个领域几乎没有发生革命性的改变。

 变革起初发生在数据访问层面上。 如早期的EJB体系中的实体Bean，到SSH中的Hibernate等。但这些领域的进展只是为了避免数据库厂商的锁定，为了把关系型的数据更方便映射到面向对象的世界里等等这些原因。 关系型数据库基本上还统治着整个数据存储领域。

同时，一些针对数据分析领域的OLAP数据库开始出现，如TD, Sybase IQ等。这些数据库针对分析型的场景做了一些改变，甚至底层的存储方式发生了很大的变化（如列式存储），但是逻辑对象的组织和访问的语言，仍然极大程度上兼容了OLTP关系型数据库。

 随着大数据时代的到来，这种折衷式的妥协方案逐渐变得无法应对了。数据库领域开始了激烈的蜕变，至今这个变化仍然在进行中。可以确定的是，我们再也无法回到用一种工具，一种技术去解决所有数据存储领域的问题的时代了。 取而代之的是，架构师需要细致地思考数据应用的场景，从众多的方案中仔细的筛选，找出最贴合场景的选择。甚至，从零开始为你的场景去构建一个合适的数据存储方案。

 这个系列会过一遍主流的NoSQL数据库，从而能够理解每类数据库适用的场景，试图解决的问题，蕴含的数据结构，以及它们不擅长的领域。

 

Big Table (Google)

 

1 数据结构

 

谷歌的Big Table最初的设计为了存储 “稀疏的，分布式的，持久的多维的Sorted Map”。这个Sorted Map以行键，列键（列簇名+列名）, 和时间戳来索引，定位出存储的具体内容。 在Big Table里所有的数据以Bytes Array的形式存储。

 

行

Row key 最长可以到64KB。记录按字典顺序保存，并且动态被分成“数据片” (Tablet)。数据片是Bigtable中数据分布和负载平衡的最小单位。客户端应用可以通过仔细设计选择row key，使得需要经常访问的多条记录存放在一起，这样在行范围读取的时候，只需要读取比较少的数据片就可以完成。 比如上图的例子里， row key 被设计成反过来的域名。这样同一个二级域名下的访问记录就会存放在一起。

字段的个数是基本上可以认为是无限的。字段按列簇组织在一起。Bigtable中加入列簇的主要考虑是值的稀疏性。因为Bigtable是按列存储的，而列的值可能是稀疏的，而且列的数目非常多，如果只按照列来组织存储的话，可能会形成很多个小文件。而分布式文件系统对小文件的管理成本是比较高的。因此bigtable 引入列簇的概念，把同一个列簇的列存储在一起。

具体来说，列簇有以下的特性：

• 列簇是访问权限控制的单元

• 列簇中的列存储相同类型，或者类似类型的数据

• 列簇中的数据是在一起被压缩存储的

• 列簇必须预先定义 （而列不需要）

• 列簇名必须是可打印字符串（而列名可以是任意字符串）

• 列簇应该是有限个的，并且很少被修改。

 

时间戳

 时间戳是64位整数，在bigtable中用来区分数据的不同版本。时间戳可以由数据库自动生成，也可以由应用自行指定。数据的存储按照时间戳的倒序排列，因此最近的版本会被最先读到。Bigtable支持指定数据最多有多少个版本，或者数据的生存时间。过期的数据有自动的垃圾回收机制删除。应用程序不需要维护数据的删除问题。

 

2 API

Big table 不提供SQL接口。只提供编程访问接口。

 

读操作 提供按row key查询，按row key范围查询， 按列簇过滤，按时间戳过滤，以及列的迭代器。

 写操作 包括创建记录，更新记录，删除记录。也有批量写接口（但是不保证事务性）

 管理操作 管理集群，表，列簇，权限等

 服务器端 代码执行 支持在服务器端脚本的执行。可以进行数据的过滤， 表达式转换，数据聚合等操作。

 Map reduce  Hbase表可以作为map reduce的输出和输入

 

3 组件依赖

Bigtable 依赖于这些组件GFS (对应于开源界的HDFS)，Chubby(对于开源界的ZooKeeper), 大规模集群管理系统 （开源界的如Yarn， Meos差不多都是这个领域）。对于这些依赖的组件，此处不做展开。

 

4 实现细节

 

4.1 系统组件

• 数据片服务器

一个bigtable 系统有多个数据片(tablet)服务器。每个数据片服务器负责管理一些数据片，包括对这些数据片的读写，数据片过大的时候的拆分，数据片过小的时候的合并等。 数据片服务器可以灵活的增加与减少。

1. 客户端库

应用通过客户端库来和bigtable系统进行交互。客户端负责数据库服务器的查找，和数据片服务器直接交互，提供数据的读写，并把服务器的响应返回给应用。

1. 主服务器

主服务器有着多种职责。首先它管理数据片和数据片服务器。它把数据片分配给数据片服务器，发现新的数据片服务器，移除死掉的数据片服务器，并平衡数据片服务器的负载。其次，它负责管理bigtable的schema，包括表的创建和列簇的创建。最后它负责删除和过期文件的垃圾回收处理。尽管主服务器承担很多职责，它的负责是很轻的，因为客户端库负责自己查找数据片的位置信息。 因此，大多数客户端始终不会和主服务器交互。主服务器是单点，因此一般会有备的主服务器。

 

4.2 数据片位置信息

之前提到过，表动态地被划分到数据片，而数据片分布在多个数据片服务器上。 数据片服务器可以随时增加，也可能随时减少。因此，bigtable必须有一个管理和查询数据片位置信息的方式。这样，主服务器才能重新平衡数据片，客户端库才能发现是哪一个数据片服务器管理想要查询的数据。下图说明了数据片信息是如何被管理的。
 

 

数据片的位置信息是保存在一个叫METADATA的数据片中。这个数据片在运行期间是被完全读入保持在内存中的。这个表被分隔为特殊的第一个数据片（根数据片）和其余的任意数目个非根数据片。非根数据片包含了所有的用户表的数据片信息。而根数据片包含了所有的非根METADATA数据片。根数据片的位置保存在Chubby命名空间中的一个文件中。数据片的位置信息用表的标识符（表名）和数据片的最后一条记录来描述。假设一行元数据记录的大小占用1KB的内存，假设元数据片的大小为128M， 那么这个体系可以描述( 128M/1K * 128M/1K = 2^32 >10亿)个数据片信息。其总体占用内存为(128M/1K+1)*128M = 128G。

客户端在访问数据的时候，是不需要扫描所有的的METADATA数据片的。而是说，它会缓存数据片信息。如果缓存的数据片信息失效，它会在这个三层结构中上移一层寻找新的（分裂或合并后的）数据片信息。为了进一步优化性能，当客户端获取METADATA数据片信息时，它总会读取一批数据片，而不是仅仅一个数据片。

 

4.3 主服务器，数据片服务器和数据片生命周期

 

数据片生命周期  数据片由主服务器创建，删除，被分配给某个具体的数据片服务器。每个数据片最多同时被分配给一个数据片服务器。主服务器当发现一个相对空闲的数据片服务器时，也会将其重新分配给空闲的数据片服务器。主服务会主动合并数据片，或者数据片服务器会分裂数据片并通知主服务器。 关于数据片的详细结构，参考下面数据片详情部分。

 数据片服务器的生命周期 当一个数据片服务器启动时，它在Chubby上创建一个唯一的文件锁。主服务器会持续监控Chubby文件锁的状态从而知道数据片服务器是否存活。如果主服务器发现一个数据片服务器不再持有这个锁，那么它会认为这个数据片服务器已经不可用，并且删掉这个锁。然后，分配给这个数据片服务器的数据片标记为待分配的数据片。一个数据片服务器如果发现它丢失了Chubby上的文件锁，那么它会停止服务并自杀。如果数据片服务器被管理员停止时，它也会主动释放Chubby上的锁，这样主服务器可以尽早发现并重新分配数据片。

 主服务器的生命周期  当主服务器启动时，它也会在Chubby上放置一个文件锁，用来防止其他的服务器获得主服务器资格。假如主服务器无法稳定持有这个锁（网络延时），那么主服务器会自杀，因为一旦它无法和Chubby很好通讯，那么它也无法管理好数据片服务器。因此，主服务器和Chubby的网络必须良好。

除了在Chubby上的注册， 主服务器启动时还会做一下的事情：

1. 扫描Chubby，发现存活的数据片服务器。

1. 和数据片服务器对话，获得每个数据片服务器服务的数据皮

1. 扫描METADATA数据片，构建表的列表和数据片列表。

1. 通过2和3，推导出未分配数据片列表。

 

4.4 数据片详解

 

首先所有的写操作都会写入redo日志，持久化在GFS中。然后，最近的提交的更新都会进入内存的一个有序缓冲区，叫做memtable。当一个memtable增长到一定程度后， 系统会创建出一个新的memtable，然后把原来的memtable转换成SSTable格式并写入到GFS。这个过程被称之为一次微压缩。因此，新的数据总是在内存中，老的数据会以SSTable的格式持久化到硬盘上。一个数据片由哪些SSTable组成的信息存放在METADATA中。同时，会包含日志的位置。当数据片被重新分配到一个数据片服务器上时，依靠这些信息，数据片服务器能够重新构建出memtable.

写操作在写入日志和memtable前会进行完整性和权限检查。 权限信息以列簇为管理最细粒度，保存在Chubby中。

 读操作同样需要检查完整性以及对应的客户端是否有权限。如果读操作允许，那么读操作会动态合并memtable和SSTable得到结果。这种合并效率很高，因为memtable和SStable都是按字典排序的。

 除了微压缩 - memtable的冻结，转换为SSTable并写入文件系统 -  SStable自己也会时常进行压缩。一个后台的进程会读取memtable和几个SSTable，把它们合并成一个SSTable。这主要是为了减轻读取的负担，避免读取需要扫描很多个SSTable文件。系统也会定期把一个Tablet的所有SSTable文件合并成一个大SSTable，并剔除掉所有已经删除的，过期的数据，这个过程称之为大压缩。

 

这些所有的压缩操作都不会影响系统的读写。整个系统在压缩期间都是可用的。

 

4.5 优化上的一些细节考虑

 

为了提升Bigtable的性能，可用性，可靠性，Google做了不少优化的设计工作。其中包括下面这些部分。

 

本地化组 （Hbase无对应概念)  本地化组是一组列簇。如果客户端应用期望总是同时访问一组列簇，那么可以把它们定义到一个本地化组里。Bigtable会为每个本地化组创建单独的SSTable。 这样，读取的时候需要更少的磁盘扫描。同时，为了更好提升读性能，Bigtable可以把整个本地化组对应的SSTable放入内存。对METADATA表，Bigtable使用了这个技术。

压缩 客户端应用可以要求对本地化组进行压缩。客户端应用可以指定对本地化组的压缩算法和压缩格式。SSTable的内容被按块进行压缩，而不是把整个SSTable作为整体进行压缩。这样，虽然压缩比较低，但是读取的时候可以只读取需要的块进行解压，而不是把整个文件解压。通常应用采用两次性压缩。 第一次压缩用长窗口扫描，以发现长的重复字符串。第二次用更小的窗口扫描，发现短的重复字符串。这两种算法都是非常快的。大概压缩是能达到每秒100~200M，解压能达到400~1000M。

尽管压缩时我们更强调速度而压缩比，这种两次性压缩仍然达到了很高的压缩比。对于谷歌的索引库，可以达到10:1。 这是因为按row key组织的数据，把同一网站的网页组织到了一起，因此数据的重复性比较明显。

数据片服务器端缓存 在数据片服务器上有两级缓存。一种是针对key value结果的缓存，叫做scan cache。 一种是SSTable块级别的缓存，叫做块缓存。Scan Cache解决的是针对同样的数据重复访问的优化，块缓存是解决应用连续读取数据的性能。

布隆过滤器 布隆过滤器也是为了提高读性能设计的。应用可以要求Bigtable对一个本地化组创建布隆过滤器。布隆过滤器可以帮助应用快速判断SSTable文件是否包含一条指定记录。这样创建合并视图的时候，减少了需要从磁盘扫描的SSTable数量。

批量提交  把很多个小的改动合并到一起进行批量提交 （批量写日志，批量修改memtable)

日志文件数量 每个数据片服务器虽然可以管理多个数据片，但只保存两个只允许追加的日志文件。这是因为如果为每个数据片创建一个日志文件，那么日志文件的数量会很多，这样会有很密集的同步写，引发大量的磁盘查找动作，不利于批量提交优化的效果。这样做的一个弊端是如果一个数据片服务器死掉后，它管理的所有数据片会被重新分配到不同的服务器上，在构建memtable的时候，这个日志会被反复读取n遍。 解决这个问题的方法是，提交按<表，行，日志序列号>进行排序。这样读取时一次磁盘扫描就可以得到需要的日志。日志的排序也是经过优化的。首先，一个日志的排序是惰性的，只有等真正需要的时候，数据片服务器告知主服务器开始日志的排序。另外主服务器也会把日志按64M切片后，同步进行排序。

减少GFS的延迟 GFS在文件写入到时候，有时候会发生网络抖动引起的延迟。为了避免这种延迟对Bigtable的影响，每个数据片服务器创建两个日志文件。当对一个文件写入发生困难时，系统自动切换到另一个文件。对日志文件的改动会追加上一个唯一的序列号，因此日志的重复数据块在后期读取的时候会被剔除。

提升数据片恢复性能  数据片恢复是指一个数据片服务器打开装载数据片的过程。这个过程中，数据片服务器需要处理日志，重建memtable。为了提升这个过程的性能，除了我们之前提到过的布隆过滤器，另外一个做法是在数据片服务器接收到停止服务的指令时，它会做两次微压缩。第一次微压缩会把内存中已有的改动写入SSTable。第二次微压缩把第一次微压缩执行期间的数据改动再次压缩到SSTable。在第二次微压缩执行前，数据片服务器会停止响应新进来的服务请求。第二次微压缩完成后，数据片服务器停止，交出数据片管理权。

不变性于可变性  由于SSTable是不变的，因此，读SSTable不需要加锁。另外数据的删除，垃圾回收也是异步进行的。Memtable本身内容是可变的，不过为了提升同步性能，这种写也是复制后写的方式进行。

5 派生产品

Bigtable的著名派生产品有Hypertable和Hbase。

后面这个系列会对Hbase的实现上做一些探讨。

 

Hbase和Bigtable的概念对比：

 

Bigtable	Hbase
Tablet	Region
SSTable	Hfile
Memtable	Memstore
METADATA	METADATA
Tablet Server	Region server
Master Server	Master Server
Chubby	Zookeeper
Location Group	无
Column Family	Column Family
GFS	HDFS