LOADING

缓存加载中...

BigTable

2025/3/14 论文

 

bigtable + google file system + mapreduce （1）

Bigtable 的设计动机:

需要存储的数据种类繁多,包括URL、网页内容、用户的个性化设置在内的数据都是Google需要经常处理的
需要存储的数据种类繁多海量的服务请求,Google运行着目前世界上最繁忙的系统,它每时每刻处理的客户服务请求数量是普通的系统根本无法承受的.
商用数据库无法满足需求,一方面现有商用数据库的设计着眼点在于其通用性。另一方面对于底层系统的完全掌控会给后期的系统维护、升级带来极大的便利

Bigtable 数据的存储格式

Bigtable is a sparse, distributed, persistent multidimensional sorted map.

  • Persistent：一个表是一个包含海量 Key-Value 键值对的 Map，数据是持久化存储的；
  • Distributed：这个大的 Map 需要支持多个分区来实现分布式；
  • Multidimensional Sorted Map：这个 Map 按照 Row Key 进行排序，这个 Key 是一个由 {Row Key, Column Key, Timestamp} 组成的多维结构；
  • Sparse：每一行列的组成并不是严格的结构，而是稀疏的，也就是说，行与行可以由不同的列组成：

Bigtable 是一个分布式, 多维, 映射表. 表中的数据通过一个行关键字（Row Key）、一个列关键字（Column Key）以及一个时间戳（Time Stamp）进行索引.
在Bigtable中一共有三级索引. 行关键字为第一级索引，列关键字为第二级索引，时间戳为第三级索引。
物理结构上基于 Map 实现。

Bigtable的Webc存储逻辑可以表示为：

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

Row Key
  • 行关键字可以是任意字符串，最大容量为 64KB，但是在大多数场景下，字节数只有 10～100 Bytes 左右。Bigtable 按照 Row key 的字典序组织数据。
  • 什么是字典顺序？ASCII 码表中的后面的字符比前面的字符大，比如 c>a，因为 Row Key 本质就是字符串，因此可以使用字典顺序进行排序。
  • 利用这个特性可以通过选择合适的行关键字，使数据访问具有良好的局部性。如 Webtable 中，通过将反转的 URL 作为行关键字，可以将同一个域名下的网页聚集在一起。
  • 网站的反转指的是 www.google.com 反转为 com.google.www，类似于 Java 中的 package 的命名。因为 URL 解析过程本身就是从后往前解析的，这符合 URL 的使用逻辑。另一方面，方便域名管理，将同一个域名下的子域名网页能聚集在一起。
  • 拿 www.github.com 作为一个 URL 的一个例子，为 www 开头的 URL 建立集群的意义并不大（没有区分度，相当于没有建集群），但是将 com.github 域名建立集群就有一定的使用用途了。
  • 注意：在 Bigtable 中仅仅涉及一个 Row key 的读/写操作是原子的。
Tablet

在 Bigtable 中，Row Key 相同的数据可以有非常多，为此 Bigtable 中表的行区间需要动态划分（也就是横向进行数据分区，横向的意思便是将表横着切），每个行区间称为一个 Tablet（子表）。Tablet 是 Bigtable 数据分布和负载均衡的基本单位，不同的子表可以有不同的大小。为了限制 Tablet 的移动成本与恢复成本，每个子表默认的最大尺寸为 200 MB。Tablet 是一个连续的 Row Key 区间，当 Tablet 的数据量增长到一定大小后可以自动分裂为两个 Tablet。同时 Bigtable 也支持多个连续的 Tablet 合并为一个大的 Tablet。

Column Key 与 Column Family

Column Key 一般都表示一种数据类型，Column Key 的集合称作 Column Family(列族)。存储在同一 Column Family 下的数据属于同一种类型，Column Family 下的数据被压缩在一起保存。

  • Column Family 是 access control（访问控制）、disk and memory accounting（磁盘和内存计算）的基本单元。数据在被存储之前必须先确定其 Column Family，然后才能确定具体的 Column Key，并且表中的 Column Family 不宜过多，通常几百个。但 Column key 的个数并不进行限制，可以有无限多个。在 Bigtable 中列关键字的命名语法为：**family:qualifier 即 “列族:限定词”**，列族名称必须是可打印的字符串，限定词则可以是任意字符串。如 Webtable 中名为 anchor 的列族，该列族的每一个列关键字代表一个锚链接；anchor 列族的限定词是引用网页的站点名，每列的数据项是链接文本。
TimeStamp
  • Bigtable 中的表项可以包含同一数据的不同版本，采用时间戳进行索引。时间戳是 64 位整型，既可以由系统赋值也可由用户指定。时间戳通常以 us（微秒）为单位。时间戳既可以由 Bigtable 进行分配，也可以由客户端进行分配，如果应用程序希望避免冲突，应当生产唯一的时间戳。
    表项的不同版本按照时间戳倒序排列（大的在前，时间戳越大表明数据加入的时间越晚），即最新的数据排在最前面，因而每次查询会先读到最新版本。为了简化多版本数据的管理，每个列族都有两个设置参数用于版本的自动回收，用户可以指定保存最近 N 个版本，或保留足够新的版本(如最近 7 天的内容)。
  • 在 Bigtable 论文的 Webtable 例子中，contents family 存储的时间戳是网络爬虫抓取页面的时间，表中的回收机制可以选择保留任一页面的最近 3 个版本。

Bigtable 架构

  • 依赖 WorkQueue 负责故障处理和监控；
  • 依赖 GFS 存储日志文件和数据文件；
  • 依赖 Chubby存储元数据和进行主服务器的选择。

Bigtable 集群(cluster)通常在运行其他分布式应用程序的共享机器池(shared pool of machines)中，这是因为 Bigtable 本质是一个进程，Bigtable 进程通常与其他应用程序的进程共享同一台机器。Bigtable 依赖于集群管理系统来调度作业、管理共享机器上的资源、处理机器故障和监视机器状态。

Bigtable 主要由链接到每个客户端的库、主服务器和多个子表服务器组成，其架构如下图所示。为了适应工作负载的变化，可以动态地向集群中添加或删除子表服务器。

组件介绍：

1.chubby

一个分布式锁服务，用于提供可靠的协调和元数据管理。

Bigtable 依赖于 Chubby 提供的锁服务，如果 Chubby 长时间不能访问，Bigtable 也会无法使用。

  • 确保任意时间至多存在一个活跃的主服务器副本；
  • 即 At most one active master at any time.
  • 存储 Bigtable 中数据的 bootstrap location（引导位置）；
  • 发现 Tablet（子表）服务器，并在子表服务器失效时进行善后；
  • 存储 Bigtable 的 schema 信息，即表的 column family 信息；
  • 存储 access control lists（访问控制列表）；

注意：如果集群内的 Chubby 在长时间内不可用（比如宕机或者网络问题），那么整个 Bigtable 系统也将会不可用。但是如果系统内仅仅是部分 Chubby 不可用，那么事实上只会导致 Bigtable 的部分数据不可用。

2.主服务器

主服务器起到系统管家的作用，主要用于为子表服务器分配子表、检测子表服务器的加入或过期、 进行子表服务器的负载均衡和对保存在 GFS 上的文件进行垃圾收集。主服务器持有活跃的子表服务器信息、子表的分配信息和未分配子表的信息。如果子表未分配，主服务器会将该子表分配给空间足够的子表服务器。

3.子表服务器

每个子表服务器管理一组子表（a set of tablets），负责其磁盘上的子表的读写请求，并在子表过大时进行子表的分割。与许多单一主节点的分布式存储系统一样，读写数据时，客户端直接和子表服务器通信，因此在实际应用中，主服务器的负载较轻。

4.客户端程序库

客户端使用客户端程序库访问 Bigtable，客户端库会缓存子表的位置信息。当客户端访问 Bigtable 时，首先要调用程序库中的 Open() 函数获取文件目录，文件目录可能在缓存中，也可能通过与主服务器进行通信得到。最后再与子表服务器通信。

5.元数据信息

如下图所示，Bigtable 使用三层类 B+ 树结构来存储元数据信息。
第一层是存储在 Chubby 中的根子表，根子表是元数据(METADATA)表的第一个子表。根子表包含了所有元数据子表的位置信息。
元数据子表包含一组用户子表的位置信息。在元数据的三级结构中，根子表不会被分割，用于确保子表的层次结构不超过三层。由于元数据行大约存储 1KB 的内存数据，在容量限制为 128MB 内的元数据子表中，三层模型可以标识 2^34^ 个子表。

基于 GFS 存储系统的 Bigtable 的存储逻辑则如下图所示：

特点是：

  • 拥有相同 row key 的键值对分为多个 Tablet 进行分布式存储（每一个 Tablet 默认大小为 200 MB），如果字节大小不足以填满 200 MB，那么也需要占用一个 Tablet 大小（这种情况不常见）；
  • Tablet 是 Bigtable 中数据分布和负载均衡的最基本单位，这个性质对于 GFS 系统来说，就是 GFS 会为每一个 Tablet 默认提供 3 个副本，每一个副本尽量存储在不同机架上的不同主机的磁盘上；

客户端的数据读取流程

我们之前已经提到了 Bigtable 的一大特点便是提出一种不同于传统关系型数据库的模型，即更为灵活的 Key-Value 数据存储模型，对外暴露一个逻辑上的多维表：

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

因此当客户端读取数据时，在内部有如下的执行流程：

  1. 首先，确定 Row Key；
  2. 其次，根据 Row Key 查找特定的 Column Key；
  3. 最后，根据 colomn 以及 version 确定具体读取的内容；

这是一个多维表查询的典型过程，这个过程类似于磁盘的直接读取，先确定分区，在顺序读写。

客户端定位子表服务器时：

  1. 首先，需要访问 Chubby 以获取根子表地址，然后浏览元数据表定位用户数据；
  2. 然后，子表服务器会从 GFS 中获取数据，并将结果返回给客户端。

Bigtable 数据访问结构如下图所示。

  • 如果客户端不知道子表的地址或缓存的地址信息不正确，客户端会递归查询子表的位置。
  • 若客户端缓存为空，寻址算法需要三次网络往返通信。
  • 如果缓存过期，寻址算法需要六次网络往返通信才能更新数据。地址信息存储在内存中，因而不必访问 GFS，但仍会预取子表地址来进一步减少访问开销。
  • 元数据表中还存储了一些次要信息，如子表的事件日志，用于程序调试和性能分析。

通常而言，为了加快数据访问以及数据的分块存储管理，存储系统通常会提供各种排序逻辑，在 Bigtable 中的排序逻辑主要有三种：

  1. 利用 Row Key 进行排序，目的是横向化划分为多个 Tablet，避免形成超大块的数据，便于数据管理；
  2. 利用 Column key 以及 Column family 进行排序，目的是加快检索时的速度；
  3. 利用 timestamp 的天然时间线排序，目的是提供多版本控制以及过期数据的自动回收；