迟到的Kudu设计要点面面观（前篇）

目录

• Prologue
• Kudu的初衷
• 集群架构与共识保证
• 表与分区的设计
• 底层存储设计细节
• 事务与数据一致性（待续）
• 与Impala、Spark集成（待续）
• Benchmarking（待续）
• 当前的主要不足（待续）
• 简单调优方法（待续）

Prologue

Kudu在大数据技术栈中是个相对年轻的角色，它原本是Cloudera的内部存储项目，用C++开发，其1.0版本在2016年9月发布，最新版本则是1.9。Kudu本质上是个列式存储引擎，主打“fast analytics on fast data”。由于Kudu非常适合我们的日历数据分析业务的场景，所以我们在一年多前就开始研究它，建设了Kudu集群承载相关业务，并运行至今。

本文可以当做一篇迟来的对Kudu的浅显但全面的介绍，信息量很大，所以拆成两篇，请慢慢食用。

Kudu的初衷

在Kudu诞生之前，针对分布式系统中的海量数据，有两种存储和分析方式：

• 静态数据以Parquet、ORC等形式持久化在HDFS中，通过Hive等工具进行批量数据OLAP处理。
• 动态数据则通过HBase、Cassandra等NoSQL数据库组织，提供高效的单行级别OLTP服务。

由此可见，前者适合大量数据离线分析，但它几乎是只追加的，无法支持更新、删除，随机获取数据的效率也低。后者随机访问效率高，但获取批量数据的性能差，并且除了按Key访问之外，基本不能进行其他维度的操作。而在不少业务场景中，都同时要求OLTP风格的实时读写与OLAP风格的多维分析，传统的解决方案有二：

• 所有数据存在NoSQL，当有OLAP需求时，借助其他组件实现，如Spark on HBase、Hive on HBase、Phoenix等，要承受OLAP性能的损失。
• 定期将在线数据冗余到HDFS，这样就得付出双倍的存储成本，并且牺牲了实时性，还得额外保证在线数据和离线数据的一致性。如下图所示。

Kudu就是为了真正填补OLTP与OLAP之间的鸿沟而设计的，它的目标是在快变数据集（fast data）上进行快速分析（fast analytics），从其PPT上抄来的图可以说明这一点。

下面我们逐一简述Kudu的设计要点，看看它是如何有效地将OLTP和OLAP能力结合在一起的。

集群架构与共识保证

下图示出典型的Kudu集群架构。

Kudu采用了与HBase近似的中心式Master-Slave架构，主节点就叫做Master（相当于HMaster），从节点叫做Tablet Server/TServer（相当于Region Server）。Kudu表的数据被分割成一个或多个Tablet来存储，与HBase Region基本相似，它们由TServer来持有，并向客户端提供读写服务。

Kudu Master的主要作用有如下三点：

• 作为Catalog Manager，维护各个表的元数据，创建及更改表的Schema；
• 作为Coordinator，观察所有TServer的状态，处理TServer失败后数据的恢复与重分布；
• 作为Tablet Directory，管理所有Tablet与TServer之间的映射关系。

由此可见，由于Kudu并不依赖ZooKeeper这样的分布式协调服务，所以Master节点需要自己负责这部分工作，任务比HMaster要重一些。但现如今商用服务器的资源往往非常充裕，这不算什么问题。

下图示出一个客户端执行更新操作时，与Master和TServer的交互过程。为了避免每次都向Master查询Tablet位置，客户端会维护元数据的缓存，只有当要访问的Tablet Leader发生变化时，客户端才会重新向Master请求最新的位置关系。

Kudu通过Raft协议保证集群共识（与高可用）。在Kudu中虽然可以同时存在多个Master，但同一时间只有一个Master起主要作用，即Leader；其他Master只同步信息，作为备份，即Follower。Tablet也是如此，一个Tablet的多个副本均匀分布在多个TServer上，同样由Raft协议来选举出Leader和Follower副本，并确保数据同步强一致。只有Leader副本可以处理写请求，所有副本都可以处理读请求。显然，Master和Tablet副本的数量必须是奇数，上图中均为3。

关于Raft协议的细节，可以参考我之前写过的《详解分布式共识（一致性）算法Raft》。

表与分区的设计

Kudu并不是NoSQL数据库，它的表是具有Schema（即强类型）的，并且是纯列式存储，格式与Parquet类似。相对而言，HBase表是Schema-less、面向列族的，且HFile实际是按行存储的。下图示出Kudu表的强类型及列存储特征。

在创建Kudu表时，必须显式指定每一列的数据类型，Kudu内部会对不同类型施加不同的压缩编码，以提高存储效率。下表示出对应关系。

另外，创建Kudu表时必须指定一列或多列的有序集合组成主键组，主键组全局唯一，更新行与插入行是不同的两种操作。Kudu会为主键组创建与MySQL等传统RDBMS类似的聚集索引。这点也与HBase不同，HBase通过在Cell内显式地加入版本号或时间戳来表示当前RowKey+列限定符指定的数据的版本，更新行就相当于插入一条更新版本的数据。

与Hive表类似，Kudu表也存在分区的概念，两种分区方式是：哈希分区（hash partitioning）和范围分区（range partitioning）。前者是Cassandra的分区思路，后者则是HBase的分区思路，Kudu同时吸取了它们的长处。顾名思义，哈希分区的每个桶对应一个Tablet，范围分区的每个区间对应一个Tablet。这两种方式可以单用，也可以结合使用，比Hive分区更灵活。

良好的分区设计有助于使数据均匀分布在各个Tablet中，避免热点问题。下面举出一个建表和分区的示例。

CREATE TABLE tmp.metrics (
    host STRING NOT NULL,
    metric STRING NOT NULL,
    time INT NOT NULL,
    value1 DOUBLE NOT NULL,
    value2 STRING,
    PRIMARY KEY (host, metric, time)
)
PARTITION BY HASH (host, metric) PARTITIONS 4,
RANGE (time) (
    PARTITION VALUES < 20140101,
    PARTITION 20140101 <= VALUES < 20150101,
    PARTITION 20150101 <= VALUES < 20160101,
    PARTITION 20160101 <= VALUES < 20170101,
    PARTITION 20170101 <= VALUES
)
STORED AS KUDU;

该表的主键组包含3个列。用两个字符串列做哈希分区，同时用日期列做范围分区，这也是最常见的科学分区方式。最终会形成如下图所示的正交分区。

表建好之后，就不允许修改建表当时指定的哈希分区，但还可以添加、删除范围分区。由于范围分区列大多是时间维度的，这可以保证表在时域上是可扩展的。

底层存储设计细节

Kudu的底层存储没有依赖HDFS等已有的轮子，而是借鉴HBase的一些特点，自己全新实现了一套方案，这是Kudu能够同时具有OLTP和OLAP能力的关键所在。因此本节在笔者已经读过相关源码的基础上，会讲得详细些。

下图更细粒度地表示出Kudu表数据存储的层级结构。

在这个存储方案中，Tablet被进一步拆分为多个RowSet。每个Tablet都有且仅有一个只存在于内存中的RowSet，称为MemRowSet；另外还会有一个或多个主要存在于磁盘中（也会少量存在于内存中）的RowSet，称为DiskRowSet。DiskRowSet的组成更加复杂，稍后再说。

数据写入Tablet时，会先写到MemRowSet。它是一棵支持并发操作的满的B+树，以主键组作为Key，数据存储在叶子节点中。需要注意的是，如果MemRowSet里的数据发生了更改，是不会直接改掉原数据的，而是采用MVCC的思想，将更改以链表的形式追加在叶子节点后面，这样就避免了在树上发生更新和删除操作。

MemRowSet的简单图示如下。

可见，Kudu行中其实也存在时间戳字段，但是不会开放给用户，仅供内部的MVCC机制使用。MemRowSet是按行存储数据的，而非按列，因为内存的速度比磁盘高得多，不需要特殊处理。当MemRowSet写满之后（默认大小是32MB），就会Flush到磁盘，形成DiskRowSet，其中记录的更改也就在Flush阶段一同完成。Flush操作由后台线程执行，不影响MemRowSet的继续写入。

Kudu的磁盘文件称为CFile，按列存储。在查询时，就会优先过滤出谓词逻辑中涉及到的列，将符合条件的行筛选出来之后，再决定是否去取其他的列。这个特性叫做延迟物化（lazy materialization）。

DiskRowSet刷写完成时，其中的CFile称为基础数据（BaseData）。我们已经知道，直接在列式存储上按行更新或删除数据是不靠谱的，Kudu的处理方式是：一旦DiskRowSet上的BaseData有后续的变更，这些变更都会写入DiskRowSet附属的内存区域中，该区域称为DeltaMemStore，其组织方式与MemRowSet完全相同。

DeltaMemStore写满之后，也会刷成CFile，不过与BaseData分开存储，名为RedoFile。看官很容易想起MySQL中的重做日志（redo log），RedoFile的作用与它类似，用来持久化上一次Flush之后对这块数据的修改。同理，DiskRowSet中也存在UndoFile，它则用来持久化上一次Flush之前对这块数据的修改，也就是说可以按时间戳回滚到历史数据。UndoFile一般只有一份，而RedoFile随着MemRowSet的写入会有多份。

下图示出完整的写入流程，该图印证了前面说过的“更新与插入（在Kudu中）是不同的两种操作”。

随着RedoFile数量的增加，如果不进行合并的话，肯定会有性能问题。Kudu中将合并CFile的过程称为Compaction（压缩），这个概念与HBase中是完全相同的，并且也分为Minor和Major Compaction。Minor Compaction就是指简单地将RedoFile合并，而Major Compaction则是将所有现存RedoFile中记录的变更写回到BaseData，并重新开始记录Redo/Undo File。另外，RowSet之间也会进行Compaction，即将不同的DiskRowSet合并成一个。在Compaction过程中，会从物理上删除那些已经被标记为删除的行，并且Key的范围也会合并，减少交叉，提高存储效率。

下面两张来自Kudu PPT的幻灯片形象地说明了Major Compation和RowSet Compaction。

除了BaseData、DeltaMemStore、RedoFile和UndoFile之外，DiskRowSet中还保存有一些其他的东西，比如针对主键的索引和布隆过滤器等，以提高访问主键组的效率。

最后还有一个问题：既然一个Tablet中可能同时存在很多DiskRowSet，如何快速判定Key到底在哪个DiskRowSet里呢？O(n)时间的遍历显然是不现实的，所以Kudu用区间树（线段树的近亲）维护了一个DiskRowSet的索引，关于区间树的介绍见Wikipedia。下图示出该索引的简单结构。

可见，它是一个二叉查找树（确切地说，是红黑树）的变种。每个节点中维护有多个RowSet的最小键和最大键，该区间的中值是分裂点。这样就可以在O(logn)时间内定位到Key所属的DiskRowSet了。

To be continued