Bigtable论文阅读总结

2019/03/24 Paper

本文记录Bigtable论文阅读总结。个人感觉不论从论文的逻辑结构还是具体原理描述,GFS写的都比Bigtable写的让人容易理解。GFS描述的很细致,用词也很具体,但是Bigtable很多用词很抽象,得仔细揣摩它具体的含义。并且论文开始没有像GFS一样给一个整体架构图,论文里给的图也都是阐述局部原理的图,很容易读着读着进入盲人摸象的状态。本文主要讲述整个Bigtable的原理,其中的一个重点SSTable之前写过一篇博客见SSTable 原理 — langrx

Bigtable概览

Bigtable有三个核心组件:clientLibrary,master,tabletServer。

  • clientLibrary是一个客户端库,用于读写数据,为了简洁图中没有画出。clientLibrary基本不需要和Master进行交互,只需要和tabletServer交互读取数据即可。tips:和GFS设计类似,读取数据不走Master,不然Master会成为瓶颈
  • tabletServer:tabletServer承担数据的具体读写任务,一般有多台,可以动态的增加和删除。一个tabletServer中一般有多个tablet(数十到数千),tablet在tabletServer中可以根据负载动态调度。tabletServer还负责tablet的分裂,当一个tablet过大时,tabletServer主动发起分裂操作。
  • master:master负责tablet的分配,感知tabletServer的增加和减少,tabletServer负载的均衡,GFS文件的GC等。

总体来说,Bigtable就是一张有序的大表,每个tablet存储了一段范围内的数据。初始的时候,只有一个tablet,随着数据的增长,tablet不断分裂,形成越来越多的tablet均匀分布在多个tabletServer中。为了加速数据的读写,有些tablet承担起索引的功能,称为MEATDATA tablet。Bigtable限制索引的层级只能有三层,所以METADATA tablet上边有且只有一个索引,称为rootTablet。rootTablet是最顶级的索引,也是数据访问的入口。

我理解的Bigtable架构图

上文提到Bigtable论文中,没有一张总体的架构图,我绘制了一张我理解的架构图,如图所示。

chubby

Bigtable依赖于chubby,一个类似于ZK的组件。Bigtable依赖chubby主要做了三件事情:

  1. 记录rootTablet的元信息。上文说到rootTable是数据访问的入口,这个入口信息是记录在chubby中的。
  2. 记录当前活跃的tabletServer。每个tabletServer会在chubby固定的目录(server directory)下创建一个排他锁,并通过session的机制维持着这个排他锁(类比zk的session机制,在一个长连接中周期性的上传心跳),当tabletServer挂掉或者发生网络分区,排它锁会超时失效。master通过监听这个目录,可以得知当前活跃的tabletServer。一种特殊情况是发生网络分区,tabletServer短时间与chubby网络隔离,网络恢复后,如果tabletServer对应的排它锁没有过期,则该tabletServer可以正常提供服务,如果已经过期,这个tabletServer则不能继续提供服务。当一个tabletServer被master停止服务时,它会主动释放这个排它锁,方便master将其上的tablet尽快调度到其他tabletServer上。
  3. master选主。master会在chubby上创建一个master锁,成功获得锁的当前的主master。当master发生网络隔离或宕机后,该锁失效,可以完成master的主备切换。

master

当master启动的时候,master需要完成以下步骤:

  1. 在chubby上获取master锁。
  2. 扫描chubby server directory获取活跃的tabletServer。
  3. 获取每个活跃的tabletServer上分配的tablet
  4. 扫描所有的METADATA tablet获取所有的tablet,与3对比,可以获取未分配的tablet,进行分配。在扫描METADATA tablet的过程中,如果发现MEATADATA tablet还没有初始化,就新创建rootTablet和MEATADATA tablet,进行初始化。

tablet在四种情况下会发生变化:创建、删除、合并和分裂。这四种变化中,前三种是由master发起的,最后一种是由chunkServer发起的。tablet的分裂实际上不涉及到数据的移动,只涉及到元数据的更改。chunkServer在对应的METADATA进行元数据的更改和插入,就可以完成分裂操作,然后通知master这个分裂操作。如果这个通知失败了,通过后续的心跳信息,master也很容易知道知道tablet的最新情况。tablet分裂的细节请参考tabletServer一节。

master负责tablet的调度,Bigtable的数据是存储在GFS上的,数据的调度由GFS负责,master调度更多是让memtable在tabletServer间均衡分布。

tabletServer

tabletServer托管着很多tablet,负责数据的实际读写。关于tablet的读写流程和数据组织方式,请参考SSTable 原理 — langrx。本节主要关注tablet重建、分裂和迁移。tabletServer不负责数据的存储,因为数据是存放在GFS上的,对于一个tablet而言,tabletServer只需要维护对应的tabletLog、对应的SSTable文件路径和memtable就可以完成tablet的数据读写操作,实际上tabetServer是非常轻的。

  • 重建:在METADATA tablet中包含对应tablet的tabletLog和SSTable的路径,重建的时候获取对应信息就可以完成tablet的重建。根据论文中的描述,推测METADATA包含的元信息至少包括<id, endKey, tabletLogInfo, SSTablesInfo>, 其中id是tablet的唯一标识,endKey是tablet rowKey的范围,起索引的作用,tabletLogInfo和SSTablesInfo则是数据相关的信息。
  • 分裂:当chunkServer发现一个tablet过大决定分裂时,需要在SSTables中选定一个分裂点,在METADATA tablet中插入新tablet的信息进去,并更新原来tablet的endKey。新的tablet会生成一个空的memtable,原tablet的memtable会在minor compaction的时候决定数据是应该落在新的tablet中还是原tablet中。
  • 迁移:当tablet从一个tabletServer迁移到另外一个tabletServer时,为了避免memtable中数据的迁移,chunkServer会首先进行一次minor compaction,把memetable中的数据flush成SSTable,在这次minor compaction完成后,chunkServer会停止tablet的相关请求,并再进行一次minor compaction,把上次minor compaction时tablet接收到的请求flush成SSTable,然后进行tablet的迁移,迁移完成后开始接受请求,由于不涉及数据的迁移,这样的迁移通常可以很快完成。

tabletLog

Bigtable对tablet提到了一个关于tabletLog的优化,如果每个tablet都拥有一个tabletLog,会导致GFS中存在很多文件并发写入,因此可以对一个chunkServer中所有的tablet创建一个tabletLog,可以大大提高写入的效率。基于tabletLog重建的时候,首先对table按照⟨table, row name, log sequence number⟩进行排序,每个tablet只读取自己相关的部分即可。

Bigtable的单行事务

Bigtable提供了单行事务的支持,包括单行的read-update-write及单行多列的事务性。原文中关于单行事务的描述很少,本文基于我的理解描述一下。Bigtable虽然是分布式存储,但是Bigtable的单行事务本质上不是分布式事务。因为Bigtable单行的数据一定在同一个tablet中,所以一定不会跨tabletServer,自然是单机事务。我们先从ACID的维度去分析一下Bigtable的单行事务:

  • A:原子性,体现在两方面:read-update-write过程中数据不能被其他事务更改,多列的更改要么同时成功,要么同时不成功。
  • C:一致性,Bigtable不存在一致性约束。
  • I:隔离性,Bigtable的事务是单行的,隔离性就是RC,没有其他情况。
  • D:持久性,Bigtable基于GFS分布式文件系统,成功写入即认为是可靠的。

所以对这个单行事务而言,关键就是保证原子性。对于单行多列操作的原子性,Bigtable写内存之前会写操作日志,如果写入过程中发生异常,重放操作日志就可以保证多列的原子性。对于read-update-write的原子性,用CAS机制就可以得到保证。

所以,Bigtable的单行事务是很简单的,甚至比Mysql的单机事务都简单很多,这也许就是原文没有讲解单行事务的原因。

关于跨行事务

后续Google发表了Percolator在Bigtable基础上实现了跨行事务的支持,Percolator是强依赖于Bigtable的单行事务的,基本思想是MVCC+2PC。

在《大规模分布式存储》一书中提到,OceanBase认为Percolator的2PC对数据库性能有很大影响,通过把更新操作都聚集到一台服务器UpdateServer上,避免了分布式事务的处理。OceanBase最初始为了解决淘宝收藏夹数据存储的问题,对于这样一个读多写少的应用,OceanBase的这种方案非常适用。其缺点是所有更新在UpdateServer进行,容易成为系统瓶颈。

TiDB是最近比较火的NewSQL数据库,TiDB思路和Google比较一致。TiDB用RocksDB作为底层存储引擎,RockDB原理类似SSTable。Bigtable的SSTable是基于GFS的,自然拥有多副本的能力。RocksDB是单机的,TiDB通过RocksDB+Raft的方式提供副本,相当于构建了一个Bigtable。在RocksDB+Raft的基础上,TiDB基于Percolator实现了跨行事务。通过RocksDB+Raft+Percolator,TiDB构建了底层分布式的支持跨行事务的存储引擎。

Search

    Table of Contents