从Bigtable聊分布式存储

   Bigtable是Google的用来应对PB级数据的分布式存储,广泛应用在Goolgle的60多个产品中,如Analytics、Earth等。Bigtable在这些产品中往往被用于高吞吐的批处理、低延迟的面向用户的在线服务。


数据结构

  Bigtable是表格型kv数据库。其中value的内容可以是任意结构的字节流,而对于key来说有多个维度:有row key、column key以及timestamp时间戳版本。

Row

   Bigtable以字典序来组织row key,并且根据相应row key的范围来进行分区,每个分区就叫做一个tablet单元。
  对key排序的好处在于,范围查询的应用其实很多:比如可以用来查询连续的日期、“2022-03-xx”月份下的记录,或者说查询“com.google.maps/xxx”某个hostname下的各个path,这样可以用来更高效地访问相关的数据。
  从另一个角度来看,对于目前很多分布式存储来说,数据已经无法全部保存在内存中了。对key排序的方式可以在内存中维护一个松散的key排序的map作为索引,这个map可以是跳表也可以是红黑树等,每隔一定的key的范围记录这个key在磁盘文件中的offset,于是就可以用这种轻量的二级索引定位到磁盘文件的位置,因为文件的内容本身也是有序的,因此可以二分找到目标的key,这种思想的存储格式就是下文之后所要介绍的SSTable。

Column family

  Column family叫做列族,是把一系列column keys打包成一组,用于权限控制。在Bigtable中,只有列族创建了之后才能操作数据,列族的格式为family:qualifier,表示一类column,例子可以参考上图的Figure1。权限控制比如不同的应用程序根据这同一份表,可以添加新数据、只读数据、或者创建新的列族等等操作,粒度是列族。

Timestamp

   Bigtable的每个value内容,或者说行列下的单元格cell,具有多版本概念,默认是一个64位的微妙时间戳,也可以由client自定义。Bigtable也会后台按照规则自动清理掉数据的旧版本。
  这种数据元素对版本的支持,在分布式系统中处理冲突中广泛应用,最典型的是写数据时通过显式指定version,使version低的数据写失败,基于CAS机制来协调client并发写数据。

存储结构

LSM-Tree与SSTable

  分区tablet持久化保存在GFS之上,保存的内容是SSTable格式的文件数据以及redo log。
  Bigtable每次写数据时,会先检查写请求是否合法以及权限,然后记wal后写入内存中的一个跳表,这个跳表被叫做memtable,当memtable到达一定阈值时,memtable就会冻结写入变更,变成了所谓的SSTable放到GFS上,此时新的写入请求就需要另外开一个memtable。
  SSTable全称是Sorted String Table,是一种有序不可变的结构。Bigtable的每个SSTable文件的末尾会保存这个文件的二级索引,当打开SSTable文件时,就会载入这个索引,通过这个索引来找到磁盘上的数据。
  在最初这个索引结构以LSM-Tree来命名,它建立在更早的日志结构的文件系统之上,因此基于合并和压缩排序文件原理的存储引擎通常都被称为LSM存储引擎。

读优化

  关于LSM-Tree其实还有很多细节,如当查找某个不存在的key时,由于需要先找memtable,再一直回溯到最旧的SSTable文件,读取会涉及多次IO,可以使用布隆过滤器来优化。

合并策略

  此外,不同的后台SSTable压缩合并策略对性能也很重要,初衷是为了优化读写放大或者数据冗余的问题。比如采用大小分级(size-tiered)的压缩,每个分级定义了这一层SSTable的大小,当达到一定数量时会压缩这层全部的SSTables,变成一个稍大一些的SSTable放到下一层,较新和较小的SSTable被连续合并到较旧和较大的SSTables中。再比如LevelDB采用的正是分层(leveled)压缩,核心思想是每一层的SSTable互相没有交集,每个层级容纳的总大小范围逐层递增,因此读取的时候可以直接定位到该层的某个SSTable文件。
  即使有很多细微差异,但LSM-Tree的基本思想(保存在后台合并的一些列SSTable)简单高效,得益于顺序存储,可以有效执行区间查询,并且由于磁盘是顺序写入的,所以可以支持很高的写吞吐。

分布式结构

分区

  分区结构在分布式存储中也很常见,常见的像比如kafka是将topic分区为partition,es将doc映射到shard放到单机lucene上,甚至redis的cluster模式也是将key使用一致性hash进行分区。这样做是为了扩大数据规模,并且通过将分区安排到不同实例上的形式,来有效分担查询压力。
  在Bigtable集群中可以存储多张表,而每一张表由一系列tablet构成,tablet管理的是某个row key范围的数据。与很多分区数据库的区别是,Bigtable的数据存储在GFS上,相当于各个tablets的数据是共享的,每个tablet server是逻辑上管理被master指定分配的tablets。
  通常来说,很多分区数据库每个分区都是主从结构,分区数据保存在本地,如果要变更分区数就意味着大量数据到分区的重新分配,以及分区到节点的rebalance,这就伴随着巨大数据迁移的代价。而Bigtable基于GFS,可以逻辑上直接分配节点和分区关系,由此也可以做到分区的动态分裂与合并。

Tablet 定位

  因为Bigtable的client是直接和tablet server交互读写的,不走master,因此需要client需要清楚分区与节点的映射关系。因为在Bigtable中,分区与节点的信息保存在一个共识服务Chubby中,因此client需要预拉取tablet定位信息。
  由于一张表中的tablet的数量可能会非常多,Bigtable的方案是采用一个3层BTree的结构来索引到一个tablet。

  如图所示,这个BTree的索引节点称为METADATA tablet,其中根节点root tablet保存在Chubby中,一般来说这种索引结构足够可以容纳2^34个user tablet。
Tablet 分配
​ Bigtable的分区tablet-节点server分配操作由master动态指定,tablet server节点成员管理由共识服务Chubby负责,master借此可以发现所有的server节点,以及通过上述tablet定位的方式发现所有的tablets。冷启的master会询问所有的server已经被分配的tablet,从而可以维护一个未被分配的tablet列表。
  另一方面,master节点通过遍历METADATA tablets,可以找到未被分配的user tablet(在此之前需要先分配METADATA tablet到server上)。
  当一个tablet产生分裂时,对应的server会记录到METADATA中去,并且通知到master。master此外也会跟踪像建表删表,tablet合并导致的tablet分区变化。
  因为Bigtable底层一套源数据都是基于GFS的,相当于是GFS上组织了一套DB结构,在Bigtable论文中并没有明确指出每个tablet server有slave备份的存在,因此一个tablet分区就对应一个server,因为GFS读写的入口均来自同一个tablet server,因此Bigtable相当于牺牲了可用性换来了一致性。

共识服务

  在分布式中(可信环境下),很重要一点的就是各个节点的行动要达成一致,比如主从结构来说,各节点的行动纲领就是听master的,完全接受从master传过来的数据,并且数据之间需要有先后顺序关系,相当于维护写写操作的一致性,一般情况下master确认了半数节点同步后再commit落盘,这就至少保证了最终一致性。
  除了日志复制以外,主从结构另一个方面就是master选举,本质上也是各个节点达成共识的过程,除了人工指定master之外,比较简单的是Bully算法,就选出server id最大的节点作为master。
  共识算法此外还需要支持容错,在分布式结构中到处都可能发生问题,比如投master的过程中candidate挂了,不能发生选举推进不下去的情况,一般就采用心跳超时机制重投。
  Bigtable使用Chubby集群来作为共识服务,类似的还有zookeeper、etcd等,可以用于master选举、成员管理和发现,此外root tablet定位的信息也是放在Chubby中。基于这套共识服务就不需要集群自己再使用某套共识算法选主或维护成员节点信息了。

-------------本文结束-------------
0%