526互联

大数据经典论文解读 - BigTable

发布时间 2023-03-31 16:57:21作者: 某某人8265

BigTable

定位是分布式表格系统。步入21世纪后，单机关系db无法支撑海量数据，GFS等分布式文件系统可低成本支持存储但效率低。分布式事务模型、共识算法和Percolator、Spanner等NewSQL到2010年前后才成熟。所以当时取各项目共性，在GFS上封装一层KV结构。技术对标HBase等NoSQL产品，业务上对标大中台。bigtable在gfs和chubby基础上实现了可用的LSM树结构。

GFS解决了海量数据存储、顺序写入，但是仅对顺序写有较弱的一致性保障；
MapReduce实现了大吞吐量的批量处理数据，但是延时、额外开销都不小；
Bigtable要实现的是高并发、保障一致性的随机读写数据系统。

4大组件：

  1. 负责存储的 GFS
  2. 负责分布式锁和目录服务的 Chubby
  3. 负责实际提供服务的 Tablet Server
  4. 负责调度 Tablet 的负载均衡的 Master

Bigtable解决什么问题？能否用RDBMS集群解决？

Bigtable的架构如何解决可用性、一致性、易运维的目标？

Bigtable底层数据结构如何？如何做到机械硬盘上的高并发随机读写？

MySQL 集群处理“大数据”

随着数据的增加，将数据库按照业务垂直分库、按照哈希取模水平分表。同时不得不放弃很多RDBMS的特性，如外键约束、单个数据库中跨行跨表事务。这不利于伸缩性和可运维性。当数据增大到不得不扩容时，MySQL集群需要使用“翻倍扩容”。

例如订单数据库，以前通过对订单号模4而分到不同的4个库，随着数据的增大为了不进行数据搬运，不得不将模4改为模8，增加一倍的机器数量。如果只增加2台机器，需要进行大量的数据搬运，而翻倍扩容只需要简单复制50%数据，且在完成复制后自动切换分片即可。但扩容分片带来了资源浪费，且缩减服务器时也十分麻烦。

理想的伸缩性是可以任意增加或减少机器，且无需停机。

此外，在MySQL集群中即使有高可用备份，出现一个故障节点也需要运维立刻介入，手动添加一台新机器，同步最新数据。理想的可运维性是，1000个节点的集群，坏了10台会自动下线，剩下的继续服务，只需每月定期维护即可，无需随时维护。

Facebook 曾经就使用上千台MySQL集群处理数据，为了维护这么庞大集群需要实现分布式锁、自动分片、自动故障隔离与恢复，与开发一个Bigtable类似。见： MySQL Automation at Facebook Scale x

Bigtable 设计目标

支撑百万级随机读写IOPS，可伸缩到上千台服务器的数据库。

  • 伸缩性：可随时增减服务器，对增减的机器数量限制要少
  • 自动分片：数据的分片会自动根据负载调整
  • 故障自动恢复：小部分节点的故障不应影响整个集群的运行

实现方式：

  1. 将系统存储放在GFS上，通过单Master调度多Tablets实现易伸缩和维护
  2. 通过MemTable + SSTable 的底层文件格式，解决高速随机读写数据
  3. 通过高可用分布式锁Chubby解决一致性

实现将整个集群当做一台机器，但也放弃了一些目标：

  • 放弃了关系模型，不支持SQL语言
  • 放弃了跨行事务，Bigtable只支持单行事务（在Spanner中被解决）

数据模型

问题：

  1. 如何进行数据分区，使得整个集群灵活可拓展
  2. 如何设计使得Master避免单点故障和单点性能瓶颈
  3. 整体架构和组件由哪些组成

Bigtable的数据模型是：一系列内存 + 数据文件 + 日志文件，组合封装出的逻辑视图

一开始就没考虑事务、join等，核心在可伸缩。其数据模型就是一个很宽的稀疏表。这个逻辑表依靠行键进行读写，每行数据要指定列族（Column Family），每个列族下无需指定列。每条数据都可以有属于自己的列，每行数据的列可以不一样，这意味着Bigtable是一个稀疏表。列下如果有值则可以保存多个版本，不同版本对应不同时间戳。
整张表是逻辑表，同一列族下数据会在物理上存储在一起，是一张物理表。

这种结构避免了增加列时修改表的Schema，而是直接向相应的行里写入数据即可。这里的列和值是以KV形式存储的。这种灵活稀疏表适合数据量大、但是数据本身Schema没想清楚的场景。

HBase将每个列族数据存在同一个HFile文件；Bigtable论文中定义了一个本地组概念，多个列族可放在一个本地组，同一个本地组的数据放在同一个SSTable文件中。这就避免了MySQL中的纵向拆表。

KV格式：

  • Key：(row:string, column:string, time:int64) -> string
  • Value: 未解析的byte数组，如html网页、二进制图片

下图url即为行关键字，contents、anchor为列关键字，内部是value，存在5条不同数据

  • (com.cnn.www, contents, t3) -> ("<html>...")
  • (com.cnn.www, contents, t5) -> ("<html>...")
  • (com.cnn.www, contents, t6) -> ("<html>...")
  • (com.cnn.www, anchor:my.look.ca, t8) -> ("CNN.com")
  • (com.cnn.www, anchor:cnnsi.com, t9) -> ("CNN")

为什么把各个列拆为多个KV对，而非按行存储？因为对应value的值可能很大或很小，将“大表拆为小表”有利于查询访问。

数据分区

把一个表中数据按照主键不同分到不同服务器即为数据分区，分区存储保障了伸缩性，避免了MySQL中的水平分库。Bigtable中分区后的一片数据被称为Tablet。为了避免哈希取模分区带来的扩缩容问题，采用了动态区间分区，采用了自动“分裂”（split）的方法。

表中数据按照行键一段段的分区，分区增大可能一份为二，减小后可能二合一。

分区管理

Master 和 Chubby 进行分区管理，这两组件加上Tablet Server和GFS共同组成Bigtable集群。

Bigtable的Tablet Server只负责在线服务，不负责数据存储。实际存储通过SSTable格式写入GFS，Tablet服务和底层SSTable数据不一定在同一服务器。Bigtable中数据存储和在线服务是完全分离的。调度Tablet是，只调度在线服务的负载，不搬运数据。

Master 负载5项工作：

  1. 分片Tablets给Tablet Server
  2. 检测 Tablet Server 的新增和过期
  3. 平衡 Tablet Server 的负载
  4. 对于GFS上的数据进行GC
  5. 管理表Table和列族的Schema变更，如表和列族的创建与删除

Chubby负责：

  1. 只有一个Master
  2. 存在Bigtable数据引导位置 （Bootstrap Location）
  3. 发现 Tablet Servers 以及它们终止后完成清理工作
  4. 存储Bigtable的Schema信息
  5. 存储ACL，即Bigtable访问权限

分区和Tablets的分配信息存在集群中METADATA表，通过Chubby告诉程序这张表存在哪个 Tablet Server。

  • Bigtable在Chubby中指定一个文件，存放分区 Root Tablet 所在位置
  • 这个 Root Tablet 分区时METADATA表第一个分区，且永不会分裂。里面存的时METADATA里其他Tablets所在位置
  • 其它Tablets，每个都存放了用户创建的数据表，包含Tablets位置

METADATA 和 Root Tablet 结构如下：

Chubby、Root Tablet、METADATA 三层结构使 Bigtable 可伸缩到足够大，理论最大160亿个Tablet。

读写流程

一个查询例子如下：

  1. 客户端向Chubby查询Root Tablet位置
  2. 得到Root Tablet在5号Tablet Server
  3. 客户端向TS5查询存放指定表名和行键的记录的位置
  4. TS5从Root Tablet里查询并返回客户端这个记录位置，在Tablet Server8上的tablet107
  5. 客户端向tablet107查询表中行键对应的数据在哪
  6. Tablet Server8 返回数据所在Tablet Server和tablet位置
  7. 客户端向用户表所在服务发起请求
  8. 返回数据

共4次请求，3次查询数据位置，1次请求数据。为了加速，将前3次查询位置的结果缓存，整个METADATA表保留在内存。

查询Tablets位置被分摊到了Bigtable的整个集群，而非某个Master节点上。Chubby和Root Tablet不会分裂且客户端都有缓存，所以压力可以承受。同时，所有的读写请求都不会经过Master。

调度者 Master

数据读写无需Master，Master只负责Tablets的调度，调度功能也依赖Chubby

  1. 所有Tablet Server上线后在Chubby指定目录下获得与名字相同的独占锁
  2. Master会监听次目录，每当Tablet Server注册即可为其分配Tablets
  3. 分配Tablets原因很多：其他Tablet Server挂了；其他TabletServer负载太大需要从新分配；等
  4. Tablet Server根据是否还独占Chubby上对应的锁判断是否还为已有Tablets服务，如Tablet Server到Chubby的网络中断则Tablet Server失去独占锁，也不再为原有Tablets服务
  5. Tablet Server移出集群，那么Tablet Server会主动释放锁，Tablets也要重新分配
  6. Master检测Server是否正常都是通过心跳
    出现问题时，Master向Chubby获取这个Server对应锁，获得就说明Chubby正常Tablet Server 异常，Master删除这个锁，确保Tablet Server不会再为Tablets提供服务。而相应的Tablets需要重新分配
  7. 一旦Master与Chubby间网络出现问题，Master会自杀。这不影响已存在的分配关系，也不会影响读写流程

Tablet 随机写入

Bigtable是一个支持随机读写的KV数据库，实际数据存储有GFS提供。但GFS没有一致性保障，硬盘的顺序写相比随机写更加高效且损耗小。为了实现基于硬盘的GFS上高性能随机读写，使用一下方法：

  • 将随机写转化为顺序写，即将Bigtable中提交日志（Commit Log）和内存表（MemTable）输出到磁盘的 Minor Compaction
  • 利用局部性原理，最近写入的数据会保留在内存表，最近读取的数据放在缓存，不存在的行键通过内存中的布隆过滤器快速过滤，减少真正需要随机访问次数

Bigtable实际写入操作如下：

  1. 写请求来时，Tablet Server先验证数据格式权限等，权限从chubby得到并缓存
  2. 将数据追加到GFS的提交日志文件中，这对GFS上硬盘是顺序写
  3. 提交日志成功后，Tablet Server再将数据写入一张内存表，即MemTable
  4. 当数据超出阈值时，Tablet Server将MemTable冻结并创建新的MemTable。冻结的MemTable 被称为Immutable MemTable，被转化为SSTable文件并写入GFS，再从内存中释放。这个写文件的过程也是顺序写

假如在第2步后机器奔溃，会通过重放（replay）所有在最后一个SSTable写入到GFS之后提交日志，重构MemTable。

在出入数据和更新数据时，只是追加一个新版本数据；删除数据时也只是写入一个删除标识。

  • 存在  Major Compaction 机制，按照前面的数据写入机制，随着数据写入SSTable文件也变多。需要通过一个后台进程不断对SSTable文件进行合并。如可设计策略只保留最近三个时间戳数据
  • 在读数据时将MemTable和多个SSTable文件合并得到一个视图，在内存中合并数据，并返回给客户端

SSTable文件一旦写入就不可变，所有写入删除都是追加一个新版本，后台会有定期的垃圾回收操作。所以多时间戳版本就很正常。

高性能随机读取

随机读代价不小，一次查询可能要多次访问GFS上硬盘，读取多个SSTable。

3个步骤提高Bigtable的数据随机写入：

  1. 将随机写变为顺序写，将数据写入变为追加
  2. 将数据写入跳表实现的MemTable
  3. 定期将MemTable变为按行键排序的SSTable文件

3个步骤提高读性能：

  1. 定期合并SSTable，减少要访问的SSTable数量
  2. 通过内存中BloomFilter过滤不存在的行键
  3. 通过Scan Cache 和 Block Cache 两层缓存减少硬盘访问

MemTable的数据结构通常是一个AVL、红黑树、跳表。MemTable 只有三种操作：

  1. 根据行键的随机数据插入
  2. 根据行键的数据读取
  3. 更加行键的有序遍历，在将MemTable转化为SSTable时会用到

SSTable由两部分组成：

  1. 数据块：实际要存储的行键、列、时间戳、值，这些会按行键分成一个固定大小块进行存储
  2. 元数据块：一系列的元数据和索引信息，包括快速过滤当前SSTable中不存在的行键的布隆过滤器、对数据块的统计信息
  3. 数据索引块
  4. 元数据索引块

因为SSTable中数据块顺序存储，所以Major Compaction就是进行有序链表的多路归并。期间无论读写都是顺序操作。

在SSTable里查询数据时，先读取索引数据，找到查询的数据在哪个数据块再返回给Tablet Server。期间使用了压缩和缓存机制：

  1. 通过压缩算法对每个块压缩
  2. 把每个SSTable的布隆过滤器直接缓存再Tablet Server里
  3. Bigtable提供了两级缓存机制
    1. 高层缓存 Scan Cache，在Tablet Server的缓存空间中缓存查询结果
    2. 底层缓存 Block Cache，对查询所获取的整个数据块缓存在Tablet Server

且对于索引进行的实际数据查询，只要查询有时间局部性和空间局部性，就可以通过缓存而非随机访问硬盘。

API

不支持标准SQL，支持操作如下：

  1. 建表、删表等功能
  2. 对单行数据的增删查，不支持修改
  3. 范围扫描功能
  4. 单行操作事务，不保证跨行事务ACID（MetaStore做了补充）