写在前面

对 Google 的论文译文进行了一些修改,因为做笔记不需要论文全部的内容。

摘要

Bigtable 是海量结构化数据的分布式存储系统,用于处理分布在几千台普通 服务器 上的PB级的数据。

Google 的很多项目都使用 Bigtable 存储数据,包括 Web 索引、Google Ear th 以及 GoogleFinance。不管是从数据量层面(从 URL 到网页到卫星图像)还是从响应速度层面(从后端的批量处理到实时数据服务),这些应用都对 Bigtable提出了各种各样的要求。针对千差万别的需求,Bigtable 成功提供了灵活的高性能解决方案。

本文介绍了 Bigtable 的简单数据模型。利用该模型,客户端可以动态地控制数据的分布和格式。本文还介绍了 Bigtable 的设计和实现。

引言

  • 过去两年,我们设计、实现并部署了结构化数据的分布式存储系统 Bigtable,用于处理分布在几千台机器上的PB级的数据。Bigtable 具有适用性广、可扩展性强、高性能和高可用性的优点。
  • BigTabl e已经用于了 Google 的多个项目,他们的要求各不相同,如下
    • 有的需要高吞吐量的批处理
    • 有的则需要及时响应
  • 集群时的配置方式也有很大差异,有的集群只有几台服务器,而有的则需要上千台服务器,存储几百 TB 的数据。
  • Bigtable 的很多实现策略都与 数据库 类似。并行数据库和内存数据库已经具备可扩展性和高性能,但Bigtable提供的接口与这些系统完全不同。
  • Bigtable 不支持完整的关系数据模型;相反,它提供了简单的数据模型。
  • 允许通过设置BigTable的模式参数来决定将数据存放在内存中还是硬盘上。

数据模型

Bigtable 是一个稀疏的分布式持久化存储的多维度排序 Map。Map 的索引是行关键字、列关键字以及时间戳;Map 中的每个 value 都是一个未经解析的 byte 数组。

(row:string,column:string, time:int64) → string

认真分析了一个类似于 Bigtable 系统的各种潜在功能后,我们决定使用这个数据模型。举个例子:假设我们需要存储海量网页及相关信息,这些数据可以用于很多不同的项目。我们暂且称该表为Webtable。在Webtable中,我们以 URL 为行关键字,以网页的某些属性为列名,网页内容放在“contents:”列中,并以时间戳标记该网页的获取时间,如下图所示

图片加载失败

存储 Web 页面的样表的片段行名为反向 URL contents 列族为网页内容,anchor 列族为引用该网页的锚链接文本。CNN 的主页被 SportsIllustrator 和 MY-look 的主页引用,因此该行包含了名为 “anchor:cnnsi.com” 和 “anchhor:my.look.ca” 的列。每个锚链接只有一个版本;而 contents 列则有三个版本,分别由时间戳 t3、t5 和 t6 标识。

表中的行关键字是任意字符串(目前支持最大 64KB 的字符串,但是大多数用户仅需要 10-100 个字节)。对同一个行关键字的读或者写操作都是原子的(不受读或者写这一行中的列数影响),这种设计便于用户理解程序在对同一个行进行并发更新操作时的行为。

Bigtable 通过行关键字的字母顺序组织数据。表中的每个行都可以动态分区。每个分区叫做一个”Tablet”,Tablet 是数据分布和负载均衡调整的最小单位。当操作只读取行中很少几列的数据时,效率很高,通常只需要机器间的少数几次通信即可完成。用户可以利用该特点,选择合适的行关键字,更加合理地安排数据位置。举例来说,在Webtable中,通过反转URL中主机名,可以把同一个域名下的网页聚集起来组织成连续的行。例如,我们可以把 maps.google.com/index.html 的数据存放在关键字 com.google.maps/index.html 下。把相同域中的网页存储在连续的区域能够提高基于主机和域名的分析效率。

列族

列关键字组成的集合叫做“列族“,列族是访问控制的基本单位。存放在同一列族下的所有数据通常属于同一类型(可以把同一列族下的数据压缩在一起)。必须先创建列族,然后才能在列族中的任何列关键字下存放数据;列族创建后,其中的任何一个列关键字下都可以存放数据。一张表中的列族不能太多(最多几百个),且列族在运行期间几乎不发生改变;但一张表中可以有无限多个列。

列关键字的命名语法为列族:限定词。列族的名称必须是可打印的字符串。

访问控制、磁盘和内存的使用统计都是在列族层面进行的。

时间戳

在 Bigtable 中,表的每一个数据项都可以包含同一份数据的不同版本;不同版本的数据通过时间戳来索引。Bigtable 时间戳的类型是 64 位整型。Bigtable 可以给时间戳赋值,时间可以精确到毫秒;用户程序也可以给时间戳赋值。如果应用程序需要避免数据版本冲突,则必须生成唯一的时间戳。在数据项中,不同版本的数据按照时间戳倒序排序,即最新的数据排在最前面。

为了便于管理不同版本的数据,我们对每一个列族配置了两个设置参数,Bigtable 可以通过这两个参数自动对废弃版本的数据进行垃圾收集。客户端程序可以指定只保存最后 n 个版本的数据,也可以指定只保存最近版本的数据(比如,只保存最近7天写入的数据)。

构件

Bigtable 基于 Google 的其他几个基础构件。

  • Bigtable 使用 Google 的分布式文件系统(GFS)存储日志文件和数据文件。

  • Bigtable 集群一般运行在共享的机器池中,池中的机器还会运行其它各种分布式应用程序。

  • Bigtable 的进程往往需要和其它应用的进程共享机器。

  • Bigtable 依赖集群管理系统调度任务、管理共享的机器上的资源、处理机器故障、监视机器状态。

  • Bigtable 内部存储数据文件是 Google SSTable 格式的。SSTable 是有序的持久化 Map 结构,不可更改;Map 是 key-value 映射的数据结构,key 和 value 的值都是任意的 Byte 串。

  • Bigtable 还依赖高可用的持久化分布式锁服务组件 Chubby。一个 Chubby 服务包含 5 个活动副本,其中一个副本为 Master,负责处理请求。Bigtable 使用 Chubby 处理以下几类任务:

    • 确保最多只有一个活动的 Master 副本;
    • 存储 Bigtable 数据的自引导指令的位置(见第5.1节);
    • 查找 Tablet 服务器,负责处理失效的T ablet 服务器(见第5.2节);
    • 存储 Bigtable 的模式信息(每张表的列族信息);
    • 存储访问控制列表。
    • 如果 Chubby 长时间无法访问,Bigtable 就会失效。

参考文章(不是论文的参考文献)