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

Bigtable最初是谷歌设计用来存储大规模结构化数据的分布式系统,其可以在数以千计的商用服务器上存储高达PB级别的数据量。开源社区根据Bigtable的设计思路开发了HBase。其优势在于提供了高效的随机读写,缺陷在于不(原生)支持类SQL的数据分析。
Bigtable的设计目标是:适应性广泛,可扩展,高性能和高可用。Bigtable将数据看作是一串无编码的字符串,由客户端负责对数据“编解码”,也就是说,对于Bigtable而言,数据是没有格式的,用数据库的术语即是,数据没有Schema,用户需要自行定义Schema。本文是Google的Bigtable论文的总结。


数据模型Data Model

Bigtable“集群”(cluster)是一组运行着Bitable软件的进程,每一个集群都负责一组表(tables),Bigtable中每一个table都是一个稀疏的,分布式的,持久化存储的多维度已排序的Map。每一条记录都以三个维度组织:行,列和时间戳(timestamps)。Map格式:(row:string,column:string,time:int64)->string。称行,列和时间戳指定的数据为cell。一个典型的Bigtable中表的例子:

1. Row

  • BigTable通过行关键字(row key)的字典顺序组织数据。(Bigtable maintains data in lexicographic order by row key)
  • 连续的行关键字又被分组为tablets,tables是数据分布和负载均衡的最小单位。(Rows with consecutive keys are grouped into tablets, which form the unit of distribution and load balancing. )

2.Columns

  • 列关键字(column key)被分组为多个集合,称这些集合为列族(column families),列族是权限控制的单位,一个列族中的列所对应的数据通常是同一类型的,这样就可以对同一类型的一个列族进行数据压缩。( Column keys are groupedinto sets called column families, which form the unit of access control. All data stored in a column family is usually of the same type (we compress data in the same column family together). )
  • 列族极少在操作过程中发生变化,这一限制主要是防止共享的元数据(metadata)过大。( families rarely change during operation; this limitation keeps widely shared metadata from being too large)
  • 当改变一个表的模式(schema)时,列族可以被删除。随之列族下的所有列对应的数据也将全部被删除。(Entire column families may be deleted by changing a table’s schema, in which case the data stored under any column keys in that family is deleted. )
  • 列关键字格式是:family:qualifier,前者为列族名,后者为修饰语。如上表,anchor即为列族名,而cnnsi.com即为修饰语。(A column key is named using the following syntax: family:qualifier. )
  • 权限控制和磁盘,内存占用都是以列族为单位进行的。(Access control and both disk and memory accounting are performed at the column-family level)

3.Timestamps
- 不同的cells(即上文提到的,特定行列和时间戳指定的数据)可以包含同一数据的不同版本,每个版本都是以timestamp降序索引的,也就是说,最先读到的总是最新的版本。(Different cells in a table can contain multiple versions of the same data, where the versions are indexedby timestamp.Different versions of a cell are stored in decreasing timestamp order, so that the most recent versions can be read first.)


Building Blocks

  • SSTable是Bigtable内部存储数据文件的不可变文件格式。一个SSTable提供了一个持久化,有序且不可变的Map,其keys和values都是任意byte strings。(The Google SSTable immutable-file format is used internally to store Bigtable data files. An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings.)
  • BigTable使用Chubby承担多重任务:任何时候确保至多一个活动的master;存储Bigtable数据的引导域;监控table server的存活状态;储存Bigtable的schemas。(Bigtable uses Chubby for a variety of tasks: to ensure that there is at most one active master at any time; to store the bootstrap location of Bigtable data (see Section 5.1); to discover tablet servers and finalize tablet server deaths (see Section 5.2); and to store Bigtable schemas (see Section 5.5).)

实现

Bigtable包含三个主要部分:一个能够连接到每一个客户端的库,一个master服务器和许多tablet服务器。tablet服务器应该能够使用工作流而动态增删。

  • master服务器需要负责分配tablet给tablet服务器,监视tablets服务器的增删,平衡tablet服务器负载以及GFS的垃圾回收。此外,master服务器还需要处理schema的变化,比如table和列族的增删。由于Bigtable客户端不需要向master询问tablet位置信息,所以大多数客户端并不和master服务器交互。
  • 每一个tablet服务器需要管理一组tablets(通常每个tablet server需要管理10~1000的tablets)。tablet服务器处理它所负载的table的读写请求,以及在tablets过大时切分tablets。
Tablet位置
  • 使用一个类似于B+树的三层架构存储tablet位置信息。第一层是存储在Chubby上的文件(上图中Chubby file),其包含了root tablet的位置。而root tablet(上图中Root tablet)指向了存储着metadata特殊table的table位置,每一个metadata table指向一组用户的tablets(存储实际数据)。其中,root tablet不可分,以保证只有三层。
  • client library从chubby递归的查找tablets的位置,并且缓存它查找到的位置。
Tablet分配
  • master监控存活的tablet服务器和当前tablets分配给tablet服务器的情况,包括哪些tablets未分配。
  • Bigtable使用Chubby监控tablet服务器,当一个tablet服务器启动时,它首先在Chubby一个特殊目录下创建一个“独占锁”(一个特殊的文件)。master监视该目录就可以发现tablet服务器,如果tablet失效,那么它就将丢失其“独占锁”。假如tablet服务器由于网络断开了与Chubby的会话,只要“独占锁”还存在,它就会请求该“独占锁”,如果该“独占锁”不存在,那么该tablet server就自行停止。而master会定期查看各个tablet服务器“独占锁”的状态。一旦master发现某一个tablet服务器的“独占锁”被删除,它就将所有分配给该tablet服务器的tablet全部置为“未分配”。
  • 为了保持Bigtable对网络故障的鲁棒性,一旦master服务器和Chubby的会话超时,master服务器应自行停止,master服务器的停止并不改变tablet的分配状态。
  • master启动步骤:
    • 在Chubby中创建一个独特的master“独占锁”。
    • master在Chubby中扫描存活的tablet服务器。
    • master联系每一个tablet服务器,以询问tablet在tablet服务器的分配状态。
    • master扫描metadata table以获得tablets集合,以发现未分配的tablet。
Tablet Serving
  • 更新操作都提交到commit log中,以保存重做记录(redo records)。
  • 近期的提交结果,被保存在内存中的有序缓冲区中,称之为memtable。memtable保存了按行存储的更新结果,为了保证行级一致性,每一行都是写入时复制。
  • 当客户端向tablet服务器发送了一个写请求,tablet服务器首先验证该请求完整无错,然后从Chubby中验证该请求的权限信息,验证通过后,该操作记录到commit log中,批量提交的目的在于提高“小”改变的吞吐量,当写操作提交后,其内容也就被插入到了memtable中了。
  • 读操作类似,需要验证请求有效和权限,值得注意的是,读操作是对SSTables和memtable都执行扫描。
压缩

当一个memtable的大小达到一个临界值,其就会被转化为SSTable并且写入GFS中,同时另一个新的memtable会创建并替换。当一个文件被写入时,GFS会试图在writer所在机器放置一个该文件的副本,当GFS中一个文件被读取时,GFS将试图读取一个最靠近reader的有效副本。以此提高读写速度。


Ref:Bigtable: A Distributed Storage System for Structured Data