BigTable Note 1: Basic

03 Feb 2014 by fleuria

最近用 Evernote 明显多于纸质笔记和 blog,有些笔记就留在了里面长草,没有进一步整理。放假在家正好整理一下前段时间看 BigTable 论文的笔记。

传统关系式数据库很难做到水平扩展,BigTable 是 Google 三大件之一的海量数据库方案。它基于 GFS 之上,在 GFS 的海量存储之上提供结构化的表存储。然而相对于面向高吞吐优化的 GFS,BigTable 的应用场景更加广泛,既适用于高吞吐的数据分析应用,也适用于面向用户的低延时应用。

论文中对 BigTable 的定义为: “A sparse, distributed, persistent multi dimension sorted map”。此 map 基于行键、列键和时间戳进行索引,其中的键与值为裸的字节序列。

为了方便讲解,论文中将 WebTable 作为例子,假定为爬虫爬来的网页数据表:

行与 Tablet

BigTable 不支持跨行事务,但是每行的数据读写是原子的,因而得以安全高效地基于行做数据分割。每个行键对应一行数据,行键按字典序排列。每张表按一定行键的范围划分为 Tablet,Tablet 也正是数据分割与负载均衡的基本单位。每张 Tablet 大约为 100mb,当数据增大会自动分裂;当一台节点上的 Tablet 数量增多时,会尝试将 Tablet 的所有权 1 迁移到其它节点上。

基于行键按字典序排列并按范围存储的性质,应用得以组织数据的局部性。比如 WebTable 将倒序的域名作为行键(像 com.cnn.www/index.html),这一来分析同一域名之下的一系列地址更加高效。

列与 Column Family

列键会组织在 Column Family 中,作为基本的访问控制单元。往列中存储数据之前,该列必先加入某个 Column Family。Column Family 中的数据一般类型相同,会被一同压缩。每张表中 Column Family 的数量是有限的,但每个 Column Family 中可以存储无限数量的列。

列键的命名规范为 family:qualifier,其中 family 必须为人类可读的字符,而 qualifier 可以为任意数据。比如 WebTable 中有个 Column Family 为 language,作为该网页唯一的语言标识;另一个有用的 Column Family 为 anchor,用以表示网页中的所有超链接地址,像 anchor:cnnsi.com, anchor:my.look.ca 。直白地说,一个 Column Family 可以在某种程度上视为表中的一个 Key-Value 类型字段。

时间戳

时间戳允许每个单元格存储多个版本的数据。它的值可以作为默认的毫秒级的系统时间,也可以由客户端手工指定。多版本的单元格数据,按照时间倒序排列,因为近期的数据更容易访问到。客户端可以设置仅保留最近的 n 个版本的数据。

比如 WebTable 中的 contents 列,用于存储爬虫爬下来的同一网页的多个版本的内容。从这个例子也可以看出,BigTable 的设计是完全本着谷歌的业务出发的。

API

接口的设计非常漂亮,偷懒从论文里贴过来:

// Open the table
Table *T = OpenOrDie("/bigtable/web/webtable");
// Write a new anchor and delete an old anchor
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);

RowMutation 对象允许录制针对某行的一系列操作,到 Apply() 时原子执行。虽说不支持多行事务,但可以基于单行事务实现 Read-Modify-Write 式的原子同步。

Scanner 对象允许扫描某行数据特定 Column Family 中所有的列:

Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
    printf("%s %s %lld %s\n",
        scanner.RowName(),
        stream->ColumnName(),
        stream->MicroTimestamp(),
        stream->Value());
}

遍历 Column Family 时甚至支持正则表达式,比如 anchor:*.cnn.com

此外也有一系列”高级”接口,比如支持客户端批处理加速多行数据处理;允许将单元格中的数据作为数值处理;支持内嵌 Sawzall 脚本对数据进行读取和转换等。

References

  • http://static.googleusercontent.com/media/research.google.com/zh-CN//archive/bigtable-osdi06.pdf
  • http://www.cs.utexas.edu/~dahlin/Classes/439/lectures/bigtable.txt