kudu 设计 -tablet

1. 逻辑组成

tablet

tablet 是 kudu 表的一个水平分区，类似于 Hbase 的 region 概念。每个 tablet 包含一个连续主键范围的记录，不同 tablet 的键范围不会有重叠，一个表的所有 tablet 就组成了这个表完整的键空间，充分利用 kudu 的分区功能，可以有效避免数据热点问题。

RowSet

每个 tablet 由若干个 RowSet 构成，一个 RowSet 由一组行数据组成，对于给定一个 key 的那一行记录，只会出现在一个 RowSet 里面(MenRowSet 或 DiskRowSet)。但是 RowSet 的键空间不是连续的，所以不同 RowSet 的键空间范围会有重叠，但键不会有重复。

mutation

对数据的插入、修改、删除统一叫做 mutation

MemRowSet

MemRowSet 是一个按主键排序的内存 B-tree(一行数据对应这个 B-tree 的一个 entry，即一个 MRSRow 实例)，数据插入时都会先进入 MemRowSet，然后数据就对查询可见了，而为了维持快照的一致性(可以理解为并发读写某行数据时候，可以读到自己正确的快照数据)，那么就要求对每行数据的所有修改(叫做 mutation)都需要保存下来，形成一个 mutation 链表，作为该行的 redo log。当内存满后，MemRowSet 会刷到磁盘中形成 DiskRowSet，然后再创建新的 MemRowSet。

DiskRowSet

MemRowSet 刷到存盘形成 DiskRowSet，而 DiskRowSet 真正存储为一系列的 cfile；每个 DiskRowSet 中的每行记录都会对应一个"rowid" （DiskRowSet 有点像数组，"rowid"对应一个数组下标且对使用者不可见）,"rowid"与主键之间会有一个映射关系：

1. 当主键为单列主键时，"rowid"其实就内置在存储主键列的 cfile 中，主键是排序存储的，所以每个主键默认对应着一个"rowid"，通过主键获得"rowid"，然后再从其它 cfile 快速定位其它列，这个就是所谓的主键索引。

2. 

3. 当主键为复合主键时，会有一个单独的索引文件(index cfile)保存着编码后的复合主键，这样就可以像单主键提供一样的功能。

4. 

一行数据以列式格式储存到不同的 cfile，读取一行完整记录时，虽然要扫描多个 cfile，但是具有有相同的 rowid，所以还是可以快速地获取到各个列的数据。

在逻辑上，每个 DiskRowSet 由三个部分组成，分别是：

Base data

MemRowSet 刷到磁盘后形成的列式数据

UNDO records

可以对 base data 进行回滚到 MemRowSet 刷盘之前的历史记录

REDO records

数据刷新到磁盘后，对 Base data 所做的 mutation 集合 ，被应用于读取更新版本的数据

落盘后 Base data 和 REDO delta 进行的 Major compation 会生成新的 Base data 和新的 UNDO records

DeltaMemStore

是一个内存并发 BTree，节点的键由 rowid 与 mutation 时间戳组合而成，当在读取时，与 MemRowSet 中的 mutation 处理逻辑一样。当 DeltaMemStore 大小到一定程度会被刷到磁盘形成 DeltaFile，然后重置自己为空。

DeltaFile

UNDO records 和 REDO records 存储为相同的文件格式，叫作 DeltaFile，包含着一系列的 mutation 数据。

2. 读写过程

2.1 数据在 MemRowSet 中的读写

数据首次插入是会落到 MemRowSet，随后的更新、删除、删除后重新插入这些操作会有一个链表按时间顺序把这些 mutations 保存起来，逻辑如下图：

每个 mutation 都会标记一个时间戳，用来用为 MVCC 的主要依据，当在 tx 时提交一个查询，

1. 如果 tx<tx1，表示 tx1 还没提交，会跳过该行数据

2. 否则会把 tx1 时的行数据 copy 到 scanner 的缓冲区，然后遍历 mutation 链表，找到所有时间戳小于 tx(表示发生在查询之前)的 mutation 与 buffer 中的行数据进行合并。

如果对单行更新得太频繁，那么每次在链表尾部插入 mutation 都是一个 O(n)操作；另外读取数据的时候要遍历连接，这也会造成许多 cpu 缓存的丢失。

2.2 数据在 DiskRowSet 中的读写

2.2.1 更新过程：

数据刷新到磁盘后的修改删除操作不会再进 MemRowSet，而是执行如下步骤：

1. 根据主键结合元数据和布隆过滤器快速定位到行记录所在的 DiskRowSet

2. 寻找主键索引(index cfile)来确定行的 rowid

3. 然后 mutation 会进入 DeltaMemStore，到时 DeltaMemStore 会刷到磁盘形成 DeltaFile，所以 DeltaMemStore 和 DeltaFile 包含的内容相同，但是后者经过序列化压缩得更紧凑，这些 DeltaFile 被称作为 REDO files，而里面的 mutations 被称作 REDO records

HBase 中采用了非原地更新的方式，将更新操作和删除操作转换成插入一条新数据的形式，虽然这样能够较快的实现更新与删除，但是将导致满足指定 rowkey，列族、列名要求的数据有多个，并且可能分布在不同的 storefile 中。

2.2.2 读过程：

1. 当想要在 MemRowSet 刷新之后立即读取最新版本的数据时，只需要扫描 Base data 即可

2. 如果想对历史记录进行回溯查询，那么还是先读取 base data，然后根据当前扫描器的时间戳会找到一系列的 UNDO records 与 base data 合并恢复历史的状态。

3. 

4. 在数据落盘一段时间后，数据可能变更过，所以会产生 DeltaFiles，这个时候的扫描除了读取 base data 之外，还需要将 REDO records 进行合并得到新版本的数据

5. 

3. RowSet 内的 Delta compaction

DeltaMemStore 每次 flush 都会生成新的 delta file，每次扫描都需要将 delta 文件与 base data 进行合并，读取性能会越来越差，所以 kudu 会有后台任务，负责将 RowSet 低效的物理储存布局转换为更高效的布局，这个过程叫做“delta compactions”，主要分为两种类型

3.1 Minor REDO delta compaction

不涉及 base data，主要是为了减少 delta 文件数量

3.2 Major REDO delta compaction

除了可以减少 delta 文件数量之外，还能把 REDO records 转为 UNDO records，因为 major 需要读取并重写 base data,而 base data 一般比 delta data 大得多，所以 major 任务比 minor 任务消耗更大的性能。

因为两种 compaction 都是发生在 RowSet 内，而 RowSet 内维护着 rowid，所以可以完全独立在后台运行，而不需要对 compaction 目标数据进行锁定，compaction 后将结果与输入数据进行原子交换，再把 compaction 前的文件删除

4. RowSet 之间的 Merging compactions

随着 tablet 的数据增加，DiskRowSet 也会逐渐累积起来，对下面几种情况会有性能影响：

1. 随机访问(或根据主键更新)，由于 RowSet 的键范围可能会有重叠，所以需要查询所有的 RowSet 键范围来确定指定的键可能存在哪些 RowSet，通过 bloom filter 可以有效的过滤一些 RowSet 而减少物理扫描，但是额外对 bloom filter 的访问也会增加内存和 cpu 的消耗

2. 范围扫描，这种情况下，有重叠键范围的 RowSet 都需要进行扫描，bloom filter 不能像随机访问那样有效进行过滤。

3. 排序扫描，从各个 RowSet 扫描到目标数据后，需要将各个 RowSet 的扫描结果进行汇总合并排序，RowSet 越多，这个过程就会越耗性能。

4.