本文主要参考《大规模分布式存储系统》

基本结构

客户端：发起请求。

RootServer：管理集群中的所有服务器，子表数据分布及副本管理，一般为一主一备，数据强同步。

UpdateServer：存储增量变更数据，一般为一主一备，客户端的写入数据只更UpdateServer。

MergeServer：接收并解析SQL请求，进行词法分析和查询优化之后把请求转发给ChunkServer查询，并合并查询后的结果。客户端直接访问MergeServer。

ChunkServer：存储基线数据，一般存储两到三份。

上述组件可以构成一个OB集群，另外还可以在此基础上部署多个集群,集群之间的数据同步通过主集群的UpdateServer向备集群同步来实现。

组件实现

RootServer

RootServer负责管理集群中所有的MergeServer，ChunkServer和UpdateServer，功能主要包括以下三点：

集群管理

RootServer通过心跳与其他组件连接。

保证一个集群内同一时刻只有一个UpdateServer提供服务，通过租约机制选择唯一的主UpdateServer。

数据分布

中心表RootTable

使用主键对表格数据排序，按顺序分布（和Hbase一样）。把所有数据划分为大致相等的数据范围(Tablet)，每个子表默认256MB。采用根表一级索引结构，即只有根表和子表两层。

由于中心表RootTable的修改很少，直接使用有序数组实现，增加子表时通过CopyOnWrite的方式创建一个新的数据，对新的数据写入和重新排序，然后吧指针指向新的RootTable。

子表分裂和合并

分裂：每台ChunkServer采用同样的分裂规则，根据子表的数据行数和子表大小设定分裂规则。

合并：先选择若干连续范围的子表，把它们迁移到相同的ChunkServer机器上，然后执行合并。只要有一个副本合并成功，就认为合并成功。

副本管理

每个子表一般包含3个副本，RootServer定期执行负载均衡，转移子表到负载低的节点。

RootServer的主备之间数据强一致同步。

UpdateServer

集群中只有UpdateServer接收写操作，更新时首先写入内存，当内存表的数据量超过阈值时转储到磁盘。和Hbase一样，为了保证可靠性，写入数据前先写入操作日志并同步到备UpdateServer。

由于只有一台UpdateServer提供写服务，很容易实现跨行跨表事务。

UpdateServer中的增量数据结构为一颗内存中的B+树（Hbase为跳跃表），每个叶子结点对应一行数据，key为行主键，value为行操作链表的指针，每行按照时间顺序构成一个行操作链表（更新、删除）。

UpdateServer的主备节点各保存增量数据的一个副本，以此保证高可用。同步机制跟MySQL的主备同步一致基本一样，主UpdateServer往备机推送操作日志，备UpdateServer接受线程接收日志并写入全局日志缓冲区。

ChunkServer

ChunkServer是集群中实际存储数据的节点，数据结构为B+树。每个表格按主键组成一颗B+树，每个叶子结点包含表格中某个主键范围内的数据。每个叶子结点称为一个子表（Tablet），包含一个或多个SSTable，每个SSTable由多个块组成，支持布隆过滤器过滤。叶子结点是负载平衡和任务调度的基本单元。

ChunkServer中保存基线数据的2-3个副本，以此保证高可用。

ChunkServer的功能主要包括以下:

存储多个子表

每个子表由1个SSTable组成，每个SSTable由多个块组成，每个块大小为4KB-64KB之间(和HBase一样)。

支持两种缓存：块缓存和行缓存。

SSTable分为两种格式：稀疏格式和稠密格式。稀疏格式的每一行只存储包含实际值的列（列存储），稠密格式每一行需要存储所有列，但不需要存储列名（行存储）。

列存储的好处有两个：

1. 在SQL语句只读取部分列时，避免把完整行加载到内存中。
2. 同一列数据在物理上存放到一起，提高压缩率。

提供读取服务

MergeServer把请求发到子表所在的ChunkServer读取基线数据，然后请求UpdateServer获取增量数据并融合。

定期合并

把UpdateServer转储来的增量表和本地的基线数据执行多路合并，生成新的SSTable。

数据分发

冻结UpdateServer当前活跃的内存表，生成冻结内存表并缓存到ChunkServer中。

MergeServer

负责解析用户的SQL请求、转发到ChunkServer执行、合并结果并返回。

MergeServer中缓存子表信息以减少对RootServer的读取。MergeServer本身是无状态的，理论上在宕机后不会对使用者产生影响。

SQL执行

读取

select c1, sum(c2)
from t1
where c3=10
group by c1
having sum(c2) >= 10
order by c1
limit 0, 20

执行顺序依次为：

TableScan(table = t1, col = {c1, c2, c3}, filter = {c3 = 10})：读取数据。

HashGroupBy(groupby = {c1}, aggr = {sum)(c2)})：分组并计算每个分组内c2的总和。

Filter(cond = {sum(c2) >= 10})：过滤。

Sort(col={c1})：排序。

Project(col = {c1, sum(c2})：返回指定列。

Limit(offset = 0, count = 20)：返回限定行数。

select t1.c1, sum(t2.c3)
from t1, t2
where t1.c2 = t2.c2and t1.c3=10
group by t1.c1
having sum(t2.c3) >= 10
order by t1.c1
limit 0, 20

执行顺序依次为：

TableScan(table = t1, col = {c1, c2, c3}, filter = {c3 = 10}) 和 TableScan(table = t2, col = {c1, c2, c3}, filter = {c3 = 10}) 分别读取数据。

Sort(col={t1.c2) 和 Sort(col={t2.c2) 分别排序。

MergeJoin(cond = {t1.c2 = t2.c2}) 合并两张表的结果。

… 后面和单表一样。

写入

REPLACE：直接写入UpdateServer。

INSERT：读取ChunkServer中的基线数据并发送到UpdateServer，如果行已存在则返回错误，不存在则执行插入操作。

UPDATE：如果行已存在则执行更新，否则什么也不做。

DELETE：如果行已存在则执行删除，否则什么也不做。

多版本并发控制

写操作的两个步骤：

预提交：锁住待更新行，把操作追加到该行的未提交行操作链表中，然后往提交任务队列加入一个提交任务。

提交：线程从提交任务队列中获取提交任务，然后把任务的操作日志写入到日志缓冲区中（缓冲区满时写入磁盘）。操作日志写成功后，把未提交行操作链表追加到已提交行操作链表，释放锁。

默认情况的隔离级别为读已提交。

单行只写事务预提交时对单行加写锁；多行只写事务预提交时对所有行加写锁；读写事务中的读操作是读取某个版本的快照。

允许用户显式锁住某一行（select xxx for update）,发生死锁时超过指定时间自动回滚。

一些设计

1. 惊群效应：N个线程同时读取一行已失效的缓存，第一个线程在读取时往缓存中加入fake标记，其他线程发现fake标记时先等待。
2. LightyQueue：使用多个队列分散读写请求。
3. 双缓存机制：分配当前和预读两个缓冲区，使用当前缓冲区读取完成并返回上层计算之后，预读缓冲区切换成当前缓冲区并异步读取数据，原来的当前缓存区计算完之后清空内存并切换成预读。