Bigtable: A Distributed Storage System for Structured Data论文阅读
目录谷歌在2003到2006年间发表了三篇论文
- 2003《The Google File System》
- 2004《MapReduce: Simplified Data Processing on Large Clusters》
- 2006《Bigtable: A Distributed Storage System for Structured Data》
介绍了Google如何对大规模数据进行存储和分析。
这三篇论文开启了工业界的大数据时代，被称为Google的三驾马车
本文将剖析最后一篇论文的设计要点
背景
随着业余越做越大，数据密集性越来越突出，对数据库提出了更高的要求
- 数据量巨大
- delay保持较小
- 应对复杂多样的业务场景
传统的关系型数据库，已经不能满足大容量低延迟等要求
由此的设计目标为
- wide applicability
- scalability
- high per- formance
- high availability
架构
共四个角色
| 角色 | 实现 |
|---|---|
| lock service | Chubby |
| cluster manager | one master server |
| data server | many tablet servers |
| date storage | GFS |
| users | a library that is linked into every client |
lock service
chubby的架构留坑会在另一篇论文阅读分享，其功能类似zk，简化如下：
- 由一个server集群，和任意client组成
- server提供全局namespace(文件夹和文件)，文件的状态可用为分布式锁
- client具有cache一致性，断开连接会丢失拥有的server的一切，可监听文件和连接状态
其用途简化如下：
- 确保只有一个master：某一namespace下，仅可存在一个代表机器的文件
- 保存 维护meta data的机器信息：某一namespace下，存有meta data server信息
- 获得data server状态：某一namespace下，新建机器状态文件代表新机器，机器状态文件的独占锁被释放代表机器出现问题
- 保存table schema信息：某一namespace下，存有table schema的文件
- 保存可访问机器列表：某一namespace下，存有有访问权限的机器列表
cluster manager
- 处理 schema 变更
- 处理 machine 变更，由此负载均衡
- 初始化tablets，合并tablets，分配 tablet 到 machine
- GFS 的 GC
data server
- 维护数据（tablets），处理读写
- split tablet，后通知manager
date storage
- GFS 负责log和data的实际存储
users
- 同GFS，利用library实现集群访问
数据模型
数据模型
用户可当做多维有序map，其kv映射关系如下
(row:string, column:string, time:int64) → string
在传统的structured data的基础上做的优化如下
Row
- key可以为任意string，上至64k，但绝大部分10 - 100B
- key按全局字典序排序
- 可选择url的倒序string作为key，则相同域名在相邻位置
- 行读写是atomic的，支持行级事务
Tablet
- 一定范围的row，视为一个tablet
- 动态划分，是数据分布式和负责均衡的最小单元
- 访问连续范围的数据，可能只需访问一台机器
通过选取key，可以稍微影响数据的物理分布
Column Family
- 一组column成为一个column family，column family必须可打印字符串，column可任意字符串，常为
family:qualifier，可理解为一个大类别的诸多选项，例如language：English - column family需要控制数量，column 数量相对较多
- column family是许多选项配置的基本单位
- 访问权限
- 压缩选项，因为数据类型类似
- 内存or disk
- 时间戳保存原则
Timestamp
- 自带64位毫秒级绝对时间戳
- 用户自定义需要解决冲突
- 降序排列，最先获得最新数据
- 保存最新n个，或最新n天
存储层结构
WAL + Memtable + SSTable
WAL
- 先写WAL，再组提交以提高吞吐
- 含redo points，指向特定log，用于recover
Memtable
- 写完log，就写memtable
- 是内存中的跳表
- 当大小超过阈值，转化为frozen memtable ，生成新的memtable，并稍后转化为SStable
SStable
- 一个特定的文件格式的文件，可参照rocksdb的格式
- 一个SSTable存储column单元，包含一个或者几个
- 读取某column family就不需要读其他的column family
读流程
-
先最新的Memtable
-
读不到，则读取column family对应的所有SSTable，合并生成最终版本
因此SSTable过多会进行合并
- minor compaction：Memtable -> SSTable
- major compaction: SSTables -> SSTable
-
Bloom filters判断SSTable是否含有特定key，加速读取
-
SSTable含有多个block，由meta确定block，加速读取
Tablet
分布
四层分布
- chubby存储 METADATA table 的 root tablet 的位置
- root tablet 存储 METADATA table 其他 tablets 的位置， root tablet 永不 split
- METADATA table 其他 tablets 存储 data table 的 tablet 的位置，可以split
- data tablets 存储用户数据
detail：
-
METADATA table 的所有 tablets cache在内存中
-
client cache 路由信息，当初始化时需要3次网络访问，路由失效时最坏需要6次网络访问，得到正确路由
-
METADATA table 的 tablet 假设 128M，每行数据 1K，可存 128K 行，也即 128K (1 << 17)个tablets
由此 (1 << 17) * (1 << 17) 最多可存 (1 << 34) 个 data tablets
分配
-
tablet 单副本
-
master通过chubby监视机器状态，由此分配tablet
-
新机器加入，master转移负载高机器的tablet到新机器
-
机器宕机，master把其tablet放进未分配tablet的集合
-
自己与chubby失联，kill 自己，不影响服务
-
master重启流程
-
获得chubby的独占锁
-
根据chubby获取机器列表
-
query各个机器获取tablet的当前分布
-
通过 query 到的 METADATA tablets 复现 METADATA table 的信息
-
若 query 不到的 METADATA tablets，需要分配
-
METADATA table 中存在但是 query 不到的，放到未分配tablet的集合
-
METADATA table 中不存在但是 query 到的，在METADATA table中记录路由
-
-
-
tablet变更
- 创建：master发起
- 删除：master发起
- 合并：master发起
- 分裂：tablet server发起，commit到METADATA table后，通知master
- 若丢失通知master，再次访问分裂tablet时会再次通知
拓展性
- master主要负责负载均衡，不会成为瓶颈
- 最多可存 (1 << 34) 个 data tablets
- 添加tablet server即可，master通过chubby发现机器即可分配data
容错性
- 单副本
- 单点master宕机不影响服务
- 单点chubby宕机会影响服务
- 丢失路由信息
- tablet server宕机影响负责tablet
一致性
- 单行线性一致性
优化细节
压缩方案
- SSTable 中的若干 block 分开压缩，可单独压缩解压缩单个block
- 两步压缩，吞吐不是瓶颈
LOG
- 单server单log，单log负责所有tablets
- 恢复时，master先按照table, row name, log sequence numbe对log排序，各个tablet只重演自己那段
- 有两个线程都可以写log，seq加以区分，以此防止log写瓶颈
tablet 转移
- 先进行以此minor compaction，减少log重演
- 停止tablet服务，再次进行minor compaction，不用进行log重演
Lessons
- 分布式开发可能遭遇各种各样的问题
- 网络问题
- 内存问题
- 时钟问题
- 机器宕机
- 依赖的其他系统的bug
- 加入新特性前，需要明确新特性
- 系统层面的监控至关重要
- 设计至简