preface

看完mit的课程, 意犹未尽, 因为google素有三驾马车之称的论文中, GFS 和 spanner 已经看过, 但是bigtable却没有深入了解过, 虽然基于 bigtable 论文实现的 hbase已经非常知名, 顺便结合之前的 hbase 学习的经验.

design

在数据模型上, bigtable在论文中是宣称是 sparse, distributed, persistent multidimensional sorted map, 存储的kv结构是 (row:string, column:string, time:int64) → string, 通过key 中包含的time 实现了多版本的机制(会配置只保持最近n个版本, 或者老版本存活多少天), 通过 row 将同一个对象的多个属性(column)进行聚合, column 的分散设计能够高效的并发. bigtable 通过rowkey的字节序排序维护数据, 并且每个table的数据是动态partition的(分布式&负载均衡), partition的row range就是 tablet. 为了更好的管理column, 采用了 column family/cf 的设计, 类似于 group的概念, 一个 cf 下的数据通常是一起压缩的 并且数据类型相同, 访问控制配置也一样. 由于cf的设计, 一个 column key name就会变成: family:qualifier, qualifier 可以理解为 key, 在举例的场景中, web page 存储就分成了 cf: anchor, qualifer 是被引用的站点, 比如 google.com/facebook.com, 因此一个 column name 就会是 anchor:google.com.

在存储上, 分为 用户数据和元数据. 用户数据依赖底层的GFS做日志和数据存储, 按照论文的说法, bigtable 是和其他应用混部的(怀疑是borglet类似的系统). 除此之外, bigtable 在GFS上还设计了 memtable 和 sstable 的数据结构, 整体逻辑和 leveldb/rocksdb 一致, sstable由 多个block、block index, 64KB一个block, 这样在搜索的时候, 可以二分定位到具体的block, 在从block中读取. 元数据存储在 chubby中, 比如 tablet server的注册信息、schema信息管理、access权限管理等. tablet 的位置信息使用 三层类似 B+ 树的结构存储在chubby中, root tablet 是顶层, 永远不会分裂, METADATA存储row key->tablet的映射关系, METADATA 的数据存储在 tablet上, root tablet 包含了所有 METADATA 的所有tablets信息 (今日头条/Bytedance的表格存储也是这么设计的), root tablet 是存储在 chubby 中的. 这样读取一次数据 需要3次往返: 1次chubby读取所有METADATA tablet信息、一次根据rowkey读取相应的METADATA tablet获取usertablet信息, 根据cf读取 user tablet.

在部署上, bigtable 由一个master 和 多个 tablet server 构成, master是用 chubby(基于paxos的持久化布式锁服务) 进行选主出来的, 除此之外, chubby还用来 tablet servers 服务发现和生命周期管理、schema信息管理、access权限管理. (chubby提供了namespace服务, 由文件和目录组成, 每个文件/目录操作都是原子的). master 需要负责分配 tablet -> tablet server, 检测tablet的生命周期(新增/过期), tablet-server 的负载均衡 和 GFS 的gc, 以及schema变化. client的数据处理流程并不需要经过master, 是直接和 tablet server 进行交互的.

最复杂的地方, 应该就是 tablet的运行时了, 论文讨论了很多意外情况, tablet server 启动后会上报给 chubby(servers目录, 互斥文件保证了信息的准确性). master 周期性的询问 tablet-server 的lock情况(这种设计还是比较少见), 当tablet-server 上报不持锁以及 服务不可达, 那么master会尝试获取锁(是为了保证chubby正常), 然后删除锁文件确保 tablet-server无法在服务, 然后 master 才能进行重新分配. 当 master 的chubby session过期, 则直接自杀. 为了能够发现未分配的tablet (意外情况未分配: server宕机, 紧跟着master宕机), master会周期性对比 从tablet-server发现的分配的tablet 和 METADATA 中的 tablet, 发现没有分配的tablet.

为了避免数据重复的问题, 也会进行 minor compaction(memtable->sstable)、periodic merging compaction 和 major compaciton(所有的sstable重写到一个sstable).

对外提供的api上, 除了常规的管理接口(cf/table的创建和删除, cluster/table/cf 元信息比如权限控制), 主要是 write、delete、scanner/iterator、RowMutation(多个操作的原子性)、单行事务(rmw)、计数、客户端脚本执行.

其他的优化, 提供了 多个cf的 Locality groups, 将一个 lg 下面的cf存储在一起. 压缩 和 缓存的读优化. 使用 bloom-filter 减少不必要的查找. 一个tablet-server上的tablet共享一个 commit log, 这个导致在recovery的时候需要排序(table, row name, log sequence number的维度)成有序输出. tablet迁移前进行一次minor-compaction减少不必要的commit-log解压缩状态 来提升恢复时间.

在性能压测上, 大规模场景下, scan > 内存读 > 顺序读 > 随机读; 写性能差异不大, 随机 ~ 顺序

整体的论文结构还是很紧凑的.

问题&思考

  • kv模型中key的time虽然实现了多版本, 但是并没有解决多个依赖版本的问题.

  • 印象中, spanner 的元数据也是存储在 gfs或后继者 中? 头条是这么做的

  • 可以参考bigtable, 通过rpc保证下游可用且持有锁, 同时通过持有锁确保 锁服务正常,

  • cf 的选择就很重要了, 最好是同时获取的数据,

  • bigtable 本质上是混部的

implement

hbase, 整体实现和 bigtable一致, 首先确定元数据流程如下:

  1. client访问zk获取root表, root表中记录了meta表信息存储在了哪些regionServer
  2. 读取regionServer获取meta表信息, 计算数据所在的 regionServer

这个流程和 bigtable 一致.

写入流程差异不大:

  1. 确定元数据流程
  2. 确定当前要写入的HRegion和HRegionServer
  3. clinet向HRegionServer发出写相应的请求，HRegionServer收到请求并响应
  4. HRegion将数据写入到HLog中，以防数据丢失, 然后写入 MemStore. (需要都成功才表示成功)
  5. MemStore 达到阈值, 会flush到 StoreFile, StoreFile太多会触发 Compact合并. 当Region太大会触发split. 整个逻辑和 bigtable一致

读取流程差异也不大:

  1. 确定元数据流程
  2. 读取HRegionServer, 根据MemStore和StoreFile查询数据
  3. 将数据传给client

文件类型: HLog: Hadoop sequence file StoreFile: HFile

因为有时候面试大数据背景的小伙伴, 参考了这个: https://zhuanlan.zhihu.com/p/75454915

参考