Bigtable: 结构化数据的分布式存储系统

介绍

Bigtable是Google自研的分布式存储系统,用来存储结构化的数据。Bigtable广泛适用于各种应用,并且保持高可用以及高性能;在Google内部,有很多批处理(以吞吐量为主)或者实时数据处理(以低延迟为主)都使用Bigtable作为数据存储系统,集群从若干台到上万台不等。

Bigtable很多地方都参考了传统数据库的设计,但是也有差异的地方。第一,Bigtable不支持关系型数据模型,相反它允许client对数据格式进行动态调整;第二,数据以行名称与列名称作为索引,而这些名称可以是任意字符串;第三,Bigtable以字符串方式来存储数据,当然字符串是以一定格式存储的;最后,Bigtable允许client控制是否以内存或磁盘方式来处理数据。

数据模型

其实,Bigtable是一个稀疏的、分布式的、持久化的多维度有序的map。这个map以行键值、列键值和时间戳作为索引,索引对应的值则是一个字节数组。

举个例子,假如我们需要存储web页面以及其相关信息到Bigtable中,不妨称这张大表为Webtable;在这个Webtable中,我们使用url作为行键值,web页面的不同属性作为列名称并存储相应信息,其中使用contents:列来存储页面内容,如下所示:

figure-1

  • 行名称以反转的url表示;
  • contents列族包含了页面内容,而且有三个版本的数据,对应于时间戳t3, t4, t5
  • anthor列族包含了所有引用当前web页面作为链接的原始页面,由于cnnsi.com和my.look.ca引用了当前页作为链接,因此行中包含了anchor:cnnsi.com列和anchor:my.look.ca列;

表中的行可以是任意的字符串,最大不超过64KB,通常为10到100字节之间;行的读写是原子性的(无论它有多少个列),这种特性使得client可以在并发更新上非常容易处理。

Bigtable的数据是以行键值的字典序来排序的;行的范围会被动态分割成不同的区域,每个行的区域称作一个tablet,这是分布和负载均衡的基本单元。因此,如果对短的行范围进行读写,这是非常高效的,通常只需要跟少数机器进行读写即可。我们可以通过以特定方式设置行键值来利用这种特性,例如在上面的Webtable例子中,由于行键值是以域名反转的形式来生成的,因此同一个域名下的不同页面会被放在连续的行区域中(页面com.google.maps/index.html的行键值为maps.google.com/index.html)。这种方式使得读写分析同一个域的页面非常方便和高效。

列族

在Bigtable中,列健归属为不同的列族。列族内的数据通常都有相同的类型,Bigtable在存储时会将同一列族内的的数据一起做压缩。在使用时,我们需要先创建列族,然后才能在列族中存储任意的列数据。Bigtable的列族数量是比较有限的(通常为几百个),但列的数量没有上限。

列键的命名遵循这样的语法:列族:标识符。列族名称需要是可打印的,但标识符可以是任意字符串。在上面的Webtable例子中,我们创建了一个anchor的列族,这个列族存放着所有引用当前页面的原始页面。

需要注意的是,访问控制、磁盘计算以及内存计算都是基于列族粒度的。

时间戳

Bigtable的每个存储单元(cell)都可以包含多个版本的数据,版本是通过64位的时间戳来实现的。时间戳既可以在存储时被Bigtable自动分配,也可以由用户自己指定。同一个单元的不同版本数据是按照时间倒序排列的,这样最新的数据可以被最快读到。对于有并发冲突的应用来说,时间戳是用来解决冲突的重要手段。

为了方便历史版本数据的清除,Bigtable中有两种数据清除的策略:

  • 基于个数,保留最近的n个版本数据;
  • 基于时间,保留最近一段时间内的版本数据(例如保留最近7天的版本数据)

API

Bigtable提供了对表和列族进行增加、删除的API,同时还提供了对集群、表、列族等元数据修改的操作,例如修改访问控制权限。

应用可以写入或者删除Bigtable的数据;而对于读取,应用既可以从行中查找特定数据,也可以从一个子集中遍历数据。

下图是一个写数据的C++样例:

figure-2

代码中使用RowMutation来执行行的批量更新,Apply操作将会对Webtable进行原子性的更新:增加一个引用www.cnn.com的新anchor,并且删除另外一个anchor。

下图是一个遍历数据的C++样例:

figure-3

代码中使用Scanner来遍历一个行的所有anchor。此外,我们可以遍历多个列族,而且还有不同的方式来过滤行、列以及数据版本。例如,我们可以使用正则表达式anchor:*.cnn.com来筛选出特定的列,或者筛选出最近10天内产生的anchor。

Bigtable还支持这些特性:

  • 支持单行操作的事务性。也就是说,对于一个行来说,可以原子性的执行读取-修改-写入这三个操作。目前Bigtable不支持多行的事务性,虽然其提供了批量写入多行的操作。
  • 存储单元可以被用来做整数计数器。
  • Bigtable支持Sawzall脚本执行(Sawzall是Google自研的处理数据的脚本语言),但目前只支持脚本读取以及筛选,不支持脚本写入。

最后,Bigtable可以与MapReduce一起使用,Bigtable可以作为MapReduce任务的输入。

Bigtable的依赖基础

Bigtable底层基于其他Google的技术组件,主要为:

  • Bigtable使用了GFS来存储日志和数据文件。
  • Bigtable使用SSTable文件格式来存储Bigtable数据。SSTable提供了一个持久化的、有序的、不可修改的map映射,其中key和value可以是任意字节字符串。它既提供了获取特定key的数据操作,还提供了遍历一个key范围的数据操作。在内部实现中,SSTable由64KB(这个大小可以配置)的block组成;block的索引存储于SSTable的最后,索引可以用来定位block;SSTable的索引放在内存中,因此在读取block时,只需要在内存中对block索引使用二分查找来定位block位置,然后只需要一次磁盘操作来读取block。而且在某些场景下,SSTable整个都可以放进内存,这样读取block数据无需磁盘操作。
  • Bigtable依赖一个高可用的分布式锁服务–Chubby。Chubby服务由5个副本节点组成,其中一个会被选举为master节点。当大部分副本都存活并且相互联通时,服务是可用的。Chubby使用了Paxos算法来保持一致性。Chubby提供了目录文件的命名空间,每个目录或文件都可以作为锁,而且读写文件是原子性的。关于Chubby更多的内容可以看Chubby的论文,此处不再赘述。

Bigtable的实现

Bigtable实现有三个重要组成部分:在client端使用的库,一个master服务器以及若干个tablet服务器。

  • master有几个关键作用:1)负责将tablet分派给tablet服务器;2)监测tablet服务器的添加和失效;3)负责对tablet服务器实现负载均衡;4)GFS文件的垃圾回收;5)负责表与列表的结构更改。
  • tablet服务器维护tablet的集合(tablet数量从十个到上千个不等),并提供这些tablet的读写,并在tablet过大时负责tablet拆分。
  • client读写数据不经过master,而是直接与tablet服务器进行通信读写。由于client不依赖于master获取tablet的位置信息,大部分client不会与master通信,因此实际上master的负载非常小。

Bigtable集群存储许多表的数据,每张表都包含很多tablet,每个tablet包含特定行范围的数据。在初始时,每张表只有一个tablet,当数据增长时,这个tablet会分裂成多个tablet,每个tablet大概100-200MB左右。

Tablet位置

Bigtable使用三层B+树的结构来维护tablet的位置信息,如下所示:

figure-4

第一层是Chubby文件,里面包含root tablet的位置信息。root tablet包含METADATA这张特殊表所有tablet的位置信息;METADATA表的每个tablet包含用户表的tablet信息。root tablet其实只是METADATA表的第一个tablet,但是它与其他tablet不同的是:它不会分裂。这样也保证了tablet信息结构不会超过三层。

METADATA表以行键的方式存储tablet位置,行键以表名和终止行两者编码得到;每一个METADATA行在内存中存储大概1KB数据,如果一个tablet大小为128MB,那么这三层结构可以存储2^34个tablet(也就是2^61字节数据)。

client会缓存tablet的位置信息,如果client不知道某个tablet位置(或者缓存的信息已失效),那么它会递归往上追溯。如果初始缓存为空,那么这个查找位置算法需要三次网络通信(包括从Chubby中读取);如果缓存失效,那么这个算法需要六次网络通信,因为相应缓存失效信息只有在查询miss时才会发现。

Tablet分派

master会跟踪tablet服务器存活情况,并且保存tablet与tablet服务器的对应关系(包括没有分派的tablet)。如果一个tablet没有分派,而且存在一个tablet服务器有空间,那么master会发送tablet加载请求到这个tablet服务器加载这个tablet。

Bigtable使用Chubby来跟踪tablet服务器,当tablet服务器启动时,它会在一个特定的Chubby目录下获取一个唯一文件的互斥锁。master会监听这个目录来发现tablet服务器。如果tablet服务器失去它的排它锁(例如由于网络故障导致Chubby会话失效),那么它会暂停服务。如果文件依然存在的话,tablet服务器会重试以获取排它锁;但如果文件已经不存在了,那么tablet服务器将不能继续服务了,因此需要终止。

master负责监测tablet服务器是否正在服务,如果停止服务,master需要将这个tablet服务器的所有tablet重新分派。为了监测到tablet不再正常服务的信息,master会定期与tablet服务器通信获取其锁状态;如果一个tablet服务器反馈锁丢失或者服务器不可达,那么master会尝试获取这个服务器的锁。如果获取成功,那么证明Chubby是正常的而这个tablet服务器存在故障,master通过获取这个锁并删掉文件,以保证该机器后续都不提供服务。一旦该tablet服务器的Chubby文件被删掉,master会将该服务器上的tablet加入到未分派的tablet集合中(待后续分派)。

如果master与Chubby间通信存在问题,也就是说Chubby会话失效,那么master会终止其服务,但这个不影响tablet与tablet服务器的分派关系。当master启动时,它需要获取当前集群的tablet分派关系,步骤如下:

  1. 在Chubby中获取master锁,以防止其他master机器并发获取的情况;
  2. master扫描Chubby中的目录,获取当前的tablet服务器;
  3. master与tablet服务器通信,获取tablet的分派信息;
  4. master扫描METADATA表收集tablet信息。在此过程中,如果发现某个tablet没有分派,那么master将该tablet加入到未分派集合中并后续进行分派。

一个复杂的地方是,当且仅当METADATA的tablet已经分派了(METADATA也是一张表),METADATA表的扫描才能进行。因此,如果在步骤3中没有发现root tablet的分派信息,那么master会将root tablet加入到未分派集合中并进行分派,这样能够保证root tablet在扫描前已经被分派;由于root tablet包含所有METADATA的tablet信息,因此通过扫描root tablet能够获取到所有METADATA Tablet的信息,并且保证在扫描METADATA前保证其tablet被分派。

tablet集合的改动有几种情况:1)tablet的创建和删除的时候;2)两个tablet合并成一个tablet;3)一个tablet分裂成两个tablet。对于前两种情况,master负责启动;对于第三种情况,tablet服务器负责启动。tablet服务器在最后阶段会提交操作,以便将新的tablet记录到METADATA表中。

tablet处理

tablet使用GFS作为持久化存储,如下图所示:

figure-5

更新操作会提交到一个commit日志文件中,commit日志记录了重做记录(redo record)。同时,最新的更新操作也会存在内存的一个有序缓冲区中,该缓冲区称作memtable;老的更新则以SSTable格式存储。在恢复一个tablet时,tablet服务器需要从METADATA表中读取其元数据,元数据包含了该tablet的SSTable列表以及重做点(redo),这些重做点指向commit日志中该tablet的数据。该tablet服务器将SSTable的索引读进内存,并且重放重做点之后的更新操作,以重新构造memtable。

当有写操作时,tablet服务器会先检查请求是否完整,以及发送者是否有权限进行操作。权限验证通过获取一个Chubby文件的可写列表来完成。检查通过后,更改才会写入到commit日志中。另外,Bigtable使用了批量提交来优化性能。更新的commit日志提交后,其数据会被插入到内存的memtable中。

当有读操作时,tablet服务器同样检查请求完整性和是否有权限;对于合法的请求,其读取视图基于SSTable与memtable合并构建。由于SSTable和memtable都是以字典序排序的,因此视图合并非常高效。

压缩

当执行写操作时,memtable的大小会增长;当其大小超过阈值时,这个memtable会被冻结,同时新建另一个memtable,而这个冻结的memtable会被转化成SSTable,写入到GFS中。这个阶段称为minor compaction阶段,它有两个目标:1)减少内存使用;2)减少故障恢复时从commit日志中读取的数据量。当压缩进行时,读和写操作都能正常进行。

由于每个minor compaction都会创建一个新的SSTable,为了减少读取时的SSTable合并数量,Bigtable通过merging compaction阶段来将若干个SSTable和memtable合并成一个SSTable。在此阶段完成后,这些SSTable和memtable都可以被删除。

最后,Bigtable还有一个major compaction阶段,在这个阶段中Bigtable将所有的SSTable合并成一个SSTable。其他阶段产生的SSTable可能会包含特殊的删除标记来表明之前的SSTable中某些数据需要被删除,此阶段产生的SSTable不会包含任何被删除数据以及删除标记。

优化

上述的实现需要很多细节优化才能实现高性能和高可用,下面总结更多的实现细节来表述这些改进优化。

局部性群组

client可以将多个列族归并成一个局部性群组,在每个tablet中对于每个局部性群组会生成一个独立的SSTable。通过将一起访问的列族归并到一个局部性群组,以及没有关联的列族分开群组,可以提高读的性能。例如,在上面的Webtable中,可以将页面的元数据归并成一个局部性群组,而页面内容使用另外一个群组,这是因为应用如果需要读取页面元数据时不需要读取页面内容。

此外,对于局部性群组还有其他一些有用的调优参数。例如,局部性群组可以通过设置放在内存中,这样群组中的SSTable会以懒加载的方式加载进内存,一旦加载访问其列族无需磁盘访问。

压缩

client可以指明局部性群组里的SSTable是否压缩以及压缩的算法,一旦指明后,该压缩算法会对SSTable的每个block进行压缩。对于block粒度进行压缩牺牲了一些空间,但是这样可以让读取无需解压整个SSTable。很多client都会使用两阶段的压缩算法:1)第一阶段使用Bentley-McIlroy的压缩算法,该算法压缩相同的长字符串;2)第二阶段压缩16KB长度里面重复出现的数据。这两阶段的压缩算法非常快,压缩速度为100–200MB/s,解压速度为400–1000MB/s。

这两阶段压缩算法的空间性能也非常不错。在Webtable中,Google使用了这两阶段压缩算法来存放爬取的网页内容。在一个实验中,他们将大量的网页都存放在一个局部性群组中,并且每个网页只存储一个版本。另外,由于行键的选择使得相同host的网页放在一起,使得Bentley-McIlroy能够对同一个host的相同网页数据进行很好的压缩。在这种背景下,这两阶段算法得到了1/10的压缩比,比Gzip(通常为1/3或1/4的压缩比)要好很多。如果对于每个页面存储多个版本的数据,压缩比会更好。

读数据的缓存

为了提高读数据的性能,tablet服务器使用了两层缓存。第一层缓存是Scan Cache,它缓存了SSTable接口返回的key-value数据;第二层缓存是Block Cache,它缓存了从GFS读取的SSTable的block。Scan Cache提高了读取相同数据的性能,而Block Cache提高了顺序读取数据的性能。

布隆过滤器(Bloom filter)

如前所述,读取操作需要从所有的SSTable读取数据并合并,如果SSTable不在内存中则会造成多次磁盘访问。为了提高速度,在创建局部性群组的SSTable时,client可以指定布隆过滤器,这个过滤器可以快速的知道SSTable中是否有相关的行列数据。对于特定的场景来说,使用一小部分内存来存储布隆过滤器能够显著减少磁盘访问。

commit日志的实现

如果对于每个tablet都使用一个单独的commit日志,那么对于底层的GFS来说会有大量的文件并发写入;而GFS则会需要写入到机器磁盘上大量不同的文件中。除此之外,这种分开策略会降低批量提交的优化性能。因此,Bigtable对于一个tablet服务器(一个服务器有很多个tablet)只维护一个commit日志。

tablet服务器只使用一个commit日志在通常情况下有极好的性能,但在故障恢复时增加了复杂度。当一个tablet服务器出故障时,它的tablet数据需要移动到其他的tablet服务器上,每个新的tablet服务器需要承担一小部分的tablet。因此在故障恢复时,其他的tablet服务器需要重放相应tablet的commit日志,但由于这些tablet的commit日志均放在同一个日志文件中,其他的tablet服务器需要读取整个commit日志。为了减少冗余数据的读取,Bigtable会首先将原始的commit日志按照(表名, 行, 日志序列号)来排序,这样同一个tablet的commit日志会放在一起,读取时可以通过顺序读的方式来提高效率。为了提高排序性能,Bigtable将原始commit日志分割成64MB的段,由多个不同的tablet服务器并行排序。

另外,写入commit日志到GFS时可能会碰到网络抖动,为了尽量不受到GFS的网络抖动影响,Bigtable有两个日志写线程,每个写线程写入到它对应的日志文件中,同一时间只有一个写线程写入日志文件。如果其中一个写线程在写入时遇到网络抖动,那么日志写入会切换到另一个写入线程。日志文件中包含了序列号以保证这两个写线程写入了相同的数据。

加速tablet的故障恢复

如果master将一个tablet从一个服务器移动到另一个服务器,那么原始的服务器需要先做一次minor compaction。这个压缩可以减少commit日志中未压缩(uncompacted)的状态数据,从而减少故障恢复时间。完成这次压缩后,原始服务器停止提供该tablet服务,但在它卸载该tablet之前,它需要再做一次minor compaction以防止在第一次压缩期间有数据写入(这次压缩时间非常快)。完成这两次压缩后,目标服务器可以加载该tablet,并且不需要任何的日志数据。

不可修改的性质

Bigtable很多地方都得益于SSTable的不可修改的特性。例如,在读取SSTable数据时,无需任何的访问同步。唯一可修改的数据结构是memtable,为了减少在修改时对读数据的影响,memtable使用了copy-on-write的技术来允许读写同时并行。

由于SSTable是不可修改的,因此已删除的数据清理需要通过废弃及回收SSTable来实现。每个tablet的SSTable都会在METADATA表中注册,master将废弃SSTable移动到标记-清除的集合中。

最后,SSTable的不可修改特性使得tablet的分裂非常快速,因为分裂出来的子tablet只需要共享父tablet的所有SSTable即可,而无需对于每个子tablet都修改原SSTable集合并且产生新SSTable集合。

Written on August 16, 2017