StarRocks调研

介绍

StarRocks 是现在比较流行的 MPP 数据库,在数据分析场景中非常有优势。

基本架构


  • FE:负责管理元数据,管理客户端连接,进行查询规划,查询调度
  • BE:负责数据存储和 SQL 执行
  • tablet: 是数据存储的基本单位,可以理解为一个 data block

表设计

列式存储

  • 维度列:就是 key 列,用于分组和排序
  • 指标列:value 列,用于执行聚合函数

一行数据的所有列在各自的列数组中保持对齐,按照维度列做多重排序

表模型

  • 明细模型: 表中存在主键重复的数据行, 和摄入数据行一一对应, 用户可以召回所摄入的全部历史数据。
  • 聚合模型: 表中不存在主键重复的数据行, 摄入的主键重复的数据行合并为一行, 这些数据行的指标列通过聚合函数合并, 用户可以召回所摄入的全部历史数据的累积结果, 但无法召回全部历史数据。
  • 更新模型&主键模型: 聚合模型的特殊情形, 主键满足唯一性约束, 最近导入的数据行, 替换掉其他主键重复的数据行。相当于在聚合模型中, 为数据表的指标列指定的聚合函数为 REPLACE, REPLACE 函数返回一组数据中的最新数据。

StarRocks 提供的 pk 模型是相比 doris 更好的能力,PK 模型使得 starrocks 有接近 RDB 的读取体验,更像一个实时数仓。

tips: 更新模型是读取时合并,主键模型是写入时合并

数据分布

建表时支持分区、分桶来支持两级的数据分区。支持如下的方式:

  • Round-Robin : 以轮转的方式把数据逐个放置在相邻节点上。
  • Range : 按区间进行数据分布,图中区间[1-3],[4-6]分别对应不同 Range。
  • List : 直接基于离散的各个取值做数据分布,性别、省份等数据就满足这种离散的特性。每个离散值会映射到一个节点上,不同的多个取值可能也会映射到相同节点上。
  • Hash : 按哈希函数把数据映射到不同节点上。

优化器

优化器是数据库中最核心和组件。starrocks 自己实现了一个 cascades 模式的自顶向下的 CBO 优化器(主要基于 columnbia 论文来实现)。主要优点是:

  • 针对向量化执行引擎的深度定制
  • 公共表达式复用
  • 相关子查询重写
  • join 分布式执行策略选择
  • 低基数字典优化

StarRocks 整个优化器的执行框架如下

具体以上点如何实现的,可以直接看starrock 的 FE 源码或者 SR 研发写的源码导读,FE 查询引擎包含 optimizer 的实现。

向量化执行器

向量化执行器的特点:

  • 列式数据组织与计算:StarRocks 的数据存储、内存中数据的组织方式,以及 SQL 算子的计算方式(SIMD 指令计算),都是列式实现的。按列的数据组织也会更加充分的利用 CPU 的 Cache,按列计算会有更少的虚函数调用以及更少的分支判断从而获得更加充分的 CPU 指令流水。
  • Operation on Encoded Data: 无需解码即可完成算子执行

向量化执行器实现的核心重点:

  • 算子的向量化
  • 表达式向量化执行
  • 存储层向量化

存储层向量化

按照列式存储和读取。向量化的基数数据结构如下:主要是 column 和 chunk 的数据结构。一行数据在各个 column 内的 value,一起读取出来变成一个 chunk。

算子向量化

关键在于实现算子时多列聚合、join、sort 的向量化处理。

表达式向量化执行

这个主要就是表达式计算利用 CPU 的 SIMD 进行向量化计算。

功能特性

自动物化视图加速

  • 用户可以定义物化视图,SR 保证物化视图和源表同步更新
  • 新的查询 SR 在查询规划时会自动匹配合适的物化视图加速查询
  • 支持 schema change

StarRocks 实现的物化视图理念可以参考 google mesa 的论文。SR 的物化视图基本实现和 rollup 表是一样的,能力上是 rollup 表的超集。在基表基础上构建 rollup 表,将基表更新同步更新到 rollup 表,从而实现物化视图的增量更新。通过 rollup 表提供的预聚合结果可以加速物化视图的查询。

外表数据湖分析

SR 支持 mysql、elasticsearch、hive、iceberg 和 hudi 等数据源作为外表读取数据,更好兼容企业已有数据生态,方便做全域数据湖分析。这里 starrocks 也有一些不错的优化,比如 ES 支持查询时进行谓词下推,用类 SQL 的方式进行查询。

分布式 join

  • Colocate join: 分布式系统实现 join 数据分布的策略之一,能够减少数据分布在多个节点引起的 join 时的数据移动和网络传输,从而提高性能。
  • Lateral join: 这个能力主要是帮用户 string array、数组等做展开使用的。效果如下:

shortkey index 加速数据查找

本质构建了一个按行寻址的稀疏索引。整个步骤归纳为:

  1. 通过维度列 key 值先查找 short key 获得数据块的其实行号
  2. 查找维度列的行号索引获得行关联的目标列数据块位置
  3. 根据数据块位置读取数据解压解码

列级索引技术

  • Bloomfilter 可快速判断数据块中不含所查找值,
  • ZoneMap 通过数据范围快速过滤待查找值,
  • Bitmap 索引可快速计算出枚举类型的列满足一定条件的行。

动态分区

为新到达的数据创建新分区, 删除过期分区。 StarRocks 的动态分区机制可以实现分区 rollover。

内存表

支持把表数据全部缓存在内存中用于加速

参考资料