in LevelDB 分布式数据库 ~ read.

BigTable

BigTable

BigTable发展于2004年,是一个用于管理大规模结构化数据的分布式存储系统,基于Google文件系统(Google File System,GFS),它有非常优秀的扩展性,可以同时处理上千台机器中的 PB 级别的数据。

于2005年投入使用,在 2006 年的 OSDI 上,Google 发布了名为 Bigtable: A Distributed Storage System for Structured Data 的论文,其中描述了一个用于管理结构化数据的分布式存储系统 - Bigtable 的数据模型、接口以及实现等内容。

Google 中的很多项目,都使用 Bigtable 来存储海量的数据;Bigtable 的论文中声称它实现了四个目标:

Goals-of-Bigtable

广适用性、扩展性、高性能、高可用性。

BigTable不是传统关系型数据库,不支持SQL语法,即NoSQL,无事务概念。

Bigtable 到底是如何实现的。

数据模型

Bigtable 与数据库在很多方面都非常相似,但是它提供了与数据库不同的接口,它并没有支持全部的关系型数据模型,反而使用了简单的数据模型,使数据可以被更灵活的控制和管理。

在实现中,Bigtable 其实就是一个稀疏的、分布式的、持久化存储的多维有序哈希表。

A Bigtable is a sparse, distributed, persistent multi-dimensional sorted map.

它的定义其实也就决定了其数据模型非常简单并且易于实现,我们使用 row keycolumn keytimestamp 三个字段作为这个哈希表的就是一个未经解析的字节数组,也可以理解为字符串。

Bigtable-DataModel-Row-Column-Timestamp-Value

行关键字

row key 的长度最大可以为 64KB,对于同一 row key 下数据的读写都可以看做是原子的;

因 Bigtable 是按照 row key 字典序组织数据,所以可按 row key 的范围划分区间,并交给一个 tablet 进行处理,默认尺寸200M。

列族/簇

col key一般都表示一种数据类型,列关键字的集合称作列族。存储在同一列族下的数据属于同一种类型,列族下的数据被压缩在一起保存。数据在被存储之前必须先创建列族,并且表中的列族不宜过多,通常几百个,但表中可以有无限多个列。在Bigtable中列关键字的命名语法为:“列族:限定词”,列族名称必须是可打印的字符串,限定词则可以是任意字符串.

时间戳

Bigtable中的表项可以包含同一数据的不同版本,采用时间戳进行索引。时间戳是64位整型,既可以由系统赋值也可由用户指定。表项的不同版本按照时间戳倒序排列,即最新的数据排在最前面。为了简化多版本数据的管理,每个列族都有两个设置参数用于版本的自动回收,用户可以指定保存最近N个版本,或保留足够新的版本(如最近7天的内容)。

示例

JSON的数据格式展示了Bigtable的数据模型

Bigtable-Model-eg

表名“tableName”,行名“rowA”。

“rowA”有两个列族“ColumnFamilyA”和“ColumnFamilyB”。

每个列族又可以同时拥有多个列,每列都有自己唯一的列标示符。例如,在列族“ColumnFamilyA”中有两列,分别为“IdentifierA”和“IdentifierB”。

每列同时存储多个版本的数据,每个版本的数据都有自己唯一的时间戳,且按时间戳递减的顺序排列。

实例

Bigtable-webtable

上面是一个用于存储海量网页的大表WebTable的存储结构,
以反转的URL作为row行名(方便过滤),
以网页中的锚点保存在anchor列簇中,
以网页内容contents作为column列名。
contents列有3个版本,分别是t3,t5,t6,通过timestamp字段来区分版本。

具体的数据是通过行名(row name)和列名(column name)来进行索引的。

架构

architect

Master的主要任务是向Tablet服务器分配Tablet,检测是否有新加入或者失效的Tablet服务器,对Tablet-server进行负载均衡,以及对GFS上文件进行垃圾收集。除此之外,它还可以进行模式修改,例如表和列族的建立。

每个TabletServer 都管理了一系列的Tablet。每个Tablet服务器处理它自身上面的Tablet的读写请求,并且当其上面的Tablets增长到一定程度对过大的Tablets进行分割。

和很多的单一Master分布式存储系统类似,客户端读取的数据不经过Master,客户直接和TabletServer 通信进行读写操作。

Bigtable依赖一个高可用和持续分布式锁服务器 Chubby 进行管理。Chubby提供了一个名字空间,里面包含了目录和小文件。每个目录或者文件可以当成是一个锁,读写文件的操作都是原子的。每个Chubby的客户程序都维护一个与Chubby服务的会话。

Bigtable使用Google的分布式文件系统(GFS)存储日志文件和数据文件。Bigtable集群通常运行在一个共享的机器池里,Bigtable依赖集群管理系统调度任务、管理共享机器上的资源、处理机器的故障以及监视机器的状态。

实现

在这一节中,我们将介绍 Bigtable 论文对于其本身实现的描述,其中包含很多内容:tablet 的组织形式、tablet 的管理、读写请求的处理以及数据的压缩等几个部分。

tablet 的组织形式

我们使用类似 B+ 树的三层结构来存储 tablet 的位置信息,第一层是一个单独的 Chubby 文件,其中保存了根 tablet 的位置。

Chubby 是一个分布式锁服务,类似于Zookeeper。

Tablet-Location-Hierarchy

每一个 METADATA tablet 包括根节点上的 tablet 都存储了 tablet 的位置和该 tablet 中 key 的最小值和最大值;每一个 METADATA 行大约在内存中存储了 1KB 的数据,如果每一个 METADATA tablet 的大小都为 128MB,那么整个三层结构可以存储 2^61 字节的数据。

tablet 的管理

既然在整个 Bigtable 中有着海量的 tablet 服务器以及数据的分片 tablet,那么 Bigtable 是如何管理海量的数据呢?Bigtable 与很多的分布式系统一样,使用一个主服务器将 tablet 分派给不同的服务器节点。

Master-Manage-Tablet-Servers-And-Tablets

为了减轻主服务器的负载,所有的客户端仅仅通过 Master 获取 tablet 服务器的位置信息,它并不会在每次读写时都请求 Master 节点,而是直接与 tablet 服务器相连,同时客户端本身也会保存一份 tablet 服务器位置的缓存以减少与 Master 通信的次数和频率。

读写请求的处理

从读写请求的处理,我们其实可以看出整个 Bigtable 中的各个部分是如何协作的,包括日志、memtable 以及 SSTable 文件。

Tablet-Serving

当有客户端向 tablet 服务器发送写操作时,它会先向 tablet 服务器中的日志追加一条记录,在日志成功追加之后再向 memtable 中插入该条记录;这与现在大多的数据库的实现完全相同,通过顺序写向日志追加记录,然后再向数据库随机写,因为随机写的耗时远远大于追加内容,如果直接进行随机写,由于随机写执行时间较长,在写操作执行期间发生设备故障造成数据丢失的可能性相对比较高。

当 tablet 服务器接收到读操作时,它会在 memtable 和 SSTable 上进行合并查找,因为 memtable 和 SSTable 中对于键值的存储都是字典顺序的,所以整个读操作的执行会非常快。

表的压缩

随着写操作的进行,memtable 会随着事件的推移逐渐增大,当 memtable 的大小超过一定的阈值时,就会将当前的 memtable 冻结,并且创建一个新的 memtable,被冻结的 memtable 会被转换为一个 SSTable 并且写入到 GFS 系统中,这种压缩方式也被称作 Minor Compaction

Minor-Compaction

每一个 Minor Compaction 都能够创建一个新的 SSTable,它能够有效地降低内存的占用并且降低服务进程异常退出后,过大的日志导致的过长的恢复时间。既然有用于压缩 memtable 中数据的 Minor Compaction,那么就一定有一个对应的 Major Compaction 操作。

Major-Compaction

Bigtable 会在后台周期性地进行 Major Compaction,将 memtable 中的数据和一部分的 SSTable 作为输入,将其中的键值进行归并排序,生成新的 SSTable 并移除原有的 memtable 和 SSTable,新生成的 SSTable 中包含前两者的全部数据和信息,并且将其中一部分标记为删除的信息彻底清除。

Ref

Bigtable 论文的原文 Bigtable: A Distributed Storage System for Structured Data