kylin 的核心思想是预计算，利用空间换时间来 加速查询模式固定的 olap 查询。
kylin 的理论基础是 cube 理论，每一种维度组合称之为 cuboid，所有 cuboid 的集合是 cube。 其中由所有维度组成的 cuboid 称为 base cuboid，图中 (a,b,c,d) 即为 base cuboid，所有的 cuboid 都可以基于 base cuboid 计算出来。 在查询时，kylin 会自动选择满足条件的最“小”cuboid，比如下面的 sql 就会对应 cuboid（a,b）:
select xx from table where a=xx group by b
kylin-cube
下图是 kylin 数据流转的示意图，kylin 自身的组件只有两个：jobserver 和 queryserver。 kylin 的 jobserver 主要负责将数据源（hive,kafka）的数据通过计算引擎（mapreduce，spark）生成 cube 存储到存储引擎（hbase）中；queryserver 主要负责 sql 的解析，逻辑计划的生成和优化，向 hbase 的多个 region 发起请求，并对多个 region 的结果进行汇总，生成最终的结果集。
kylin-data
下图是 kylin 可插拔的架构图, 在架构设计上，kylin 的数据源，构建 cube 的 计算引擎，存储引擎都是可插拔的。kylin 的核心就是这套可插拔架构，cube 数据模型和 cuboid 的算法。
kylin
palo 是一个基于 mpp 的 olap 系统，主要整合了 google mesa（数据模型），apache impala（mpp query engine) 和 apache orcfile(存储格式，编码和压缩) 的技术。
baidu-palo
palo 的系统架构如下，palo 主要分为 fe 和 be 两个组件，fe 主要负责查询的编译，分发和元数据管理（基于内存，类似 hdfs nn）；be 主要负责查询的执行和存储系统。
baidu-palo
kylin 将表中的列分为维度列和指标列。在数据导入和查询时相同维度列中的指标会按照对应的聚合函数 (sum, count, min, max, 精确去重，近似去重，百分位数，topn) 进行聚合。
在存储到 hbase 时，cuboid 维度 会作为 hbase 的 rowkey, 指标会作为 hbase 的 value，一般所有指标会在 hbase 的一个列族，每列对应一个指标，但对于较大的去重指标会单独拆分到第 2 个列族。
kylin-model
palo 的聚合模型借鉴自 mesa，但本质上和 kylin 的聚合模型一样，只不过 palo 中将维度称作 key，指标称作 value。
palo-data-model
palo 中比较独特的聚合函数是 replace 函数，这个聚合函数能够保证相同 keys 的记录只保留最新的 value， 可以借助这个 replace 函数来实现 点更新。一般 olap 系统的数据都是只支持 append 的，但是像电商中交易的退款，广告点击中的无效点击处理，都需要去更新之前写入的单条数据，在 kylin 这种没有 relpace 函数的系统中我们必须把包含对应更新记录的整个 segment 数据全部重刷，但是有了 relpace 函数，我们只需要再追加 1 条新的记录即可。 但是 palo 中的 repalce 函数有个缺点：无法支持预聚合， 就是说只要你的 sql 中包含了 repalce 函数，即使有其他可以已经预聚合的 sum，max 指标，也必须现场计算。
为什么 palo 可以支持点更新呢？
kylin 中的 segment 是不可变的，也就是说 hfile 一旦生成，就不再发生任何变化。但是 palo 中的 segment 文件和 hbase 一样，是可以进行 compaction 的，具体可以参考 google mesa 论文解读中的 mesa 数据版本化管理（https://blog.bcmeng.com/post/google-mesa.html#mesa数据版本化管理）
palo 的聚合模型相比 kylin 有个缺点：就是一个 column 只能有一个预聚合函数，无法设置多个预聚合函数。 不过 palo 可以现场计算其他的聚合函数。 baidu palo 的开发者 review 时提到，针对这个问题，palo 还有一种解法：由于 palo 支持多表导入的原子更新，所以 1 个 column 需要多个聚合函数时，可以在 palo 中建多张表，同一份数据导入时，palo 可以同时原子更新多张 palo 表，缺点是多张 palo 表的查询路由需要应用层来完成。
palo 中和 kylin 的 cuboid 等价的概念是 rollup 表，cuboid 和 rollup 表都可以认为是一种 materialized views 或者 index。 palo 的 rollup 表和 kylin 的 cuboid 一样，** 在查询时不需要显示指定，系统内部会根据查询条件进行路由。 如下图所示：
palo rollup
palo 中 rollup 表的路由规则如下：
选择包含所有查询列的 rollup 表
按照过滤和排序的 column 筛选最符合的 rollup 表
按照 join 的 column 筛选最符合的 rollup 表
行数最小的
列数最小的
kylin cuboid vs palo rollup
由于 palo 的聚合模型存在下面的缺陷，palo 引入了明细模型。
必须区分维度列和指标列
维度列很多时，sort 的成本很高
count 成本很高，需要读取所有维度列（可以参考 kylin 的解决方法进行优化）
palo 的明细模型不会有任何聚合，不区分维度列和指标列，但是在建表时需要指定 sort columns，数据导入时会根据 sort columns 进行排序，查询时根据 sort column 过滤会比较高效。
如下图所示，sort columns 是 year 和 city。
kylin-detail-model
这里需要注意一点，palo 中一张表只能有一种数据模型，即要么是聚合模型，要么是明细模型，而且 roll up 表的数据模型必须和 base 表一致， 也就是说明细模型的 base 表不能有聚合模型的 roll up 表。
kylin 存储引擎 hbase：
如上图所示，在 kylin 中 1 个 cube 可以按照时间拆分为多个 segment,segment 是 kylin 中数据导入和刷新的最小单位。kylin 中 1 个 segment 对应 hbase 中一张 table。 hbase 中的 table 会按照 range 分区拆分为多个 region, 每个 region 会按照大小拆分为多个 hfile。
关于 hfile 的原理网上讲述的文章已经很多了，我这里简单介绍下。首先 hfile 整体上可以分为元信息，blcoks，index3 部分，blcoks 和 index 都可以分为 data 和 meta 两部分。block 是数据读取的最小单位，block 有多个 key-value 组成，一个 key-value 代表 hbase 中的一行记录，key-value 由 kylin-len，value-len，key-bytes,value-bytes 4 部分组成。更详细的信息大家可以参考下图 (下图来源于互联网，具体出处不详）：
hbase-hfile
palo 存储引擎：
如上图所示，palo 的 table 支持二级分区，可以先按照日期列进行一级分区，再按照指定列 hash 分桶。具体来说，1 个 table 可以按照日期列分为多个 partition， 每个 partition 可以包含多个 tablet，tablet 是数据移动、复制等操作的最小物理存储单元，各个 tablet 之间的数据没有交集，并且在物理上独立存储。partition 可以视为逻辑上最小的管理单元，数据的导入与删除，仅能针对一个 partition 进行。1 个 table 中 tablet 的数量 = partition num * bucket num。tablet 会按照一定大小（256m）拆分为多个 segment 文件，segment 是列存的，但是会按行（1024）拆分为多个 rowblock。
palo segment file
下面我们来看下 palo segment 文件的具体格式，palo 文件格式主要参考了 apache orc。如上图所示，palo 文件主要由 meta 和 data 两部分组成，meta 主要包括文件本身的 header，segment meta，column meta，和每个 column 数据流的元数据，每部分的具体内容大家看图即可，比较详细。 data 部分主要包含每一列的 index 和 data，这里的 index 指每一列的 min,max 值和数据流 stream 的 position；data 就是每一列具体的数据内容，data 根据不同的数据类型会用不同的 stream 来存储，present stream 代表每个 value 是否是 null，data stream 代表二进制数据流，length stream 代表非定长数据类型的长度。 下图是 string 使用字典编码和直接存储的 stream 例子。
palo string encoding
下面我们来看下 palo 的前缀索引：
palo index
本质上，palo 的数据存储是类似 sstable（sorted string table）的数据结构。该结构是一种有序的数据结构，可以按照指定的列有序存储。在这种数据结构上，以排序列作为条件进行查找，会非常的高效。而前缀索引，即在排序的基础上，实现的一种根据给定前缀列，快速查询数据的索引方式。前缀索引文件的格式如上图所示，索引的 key 是每个 rowblock 第一行记录的 sort key 的前 36 个字节，value 是 rowblock 在 segment 文件的偏移量。
有了前缀索引后，我们查询特定 key 的过程就是两次二分查找：
先加载 index 文件，二分查找 index 文件获取包含特定 key 的 row blocks 的 offest, 然后从 sement files 中获取指定的 rowblock；
在 rowblocks 中二分查找特定的 key
订阅号：睿帆科技