列存数据库-kylin关键分析

列存数据库-kylin关键分析

作者简介

黄峰,Kyligence 公司高级研发工程师,目前主要负责 Kyligence 企业级产品的开发以及维护工作。

对 OLAP 场景的查询而言,单个查询往往需要在存储端扫描大量数据,再在内存中进行一些统计分析后,才能输出所需要的统计结果。因此,如果不能像以 Kylin 为代表的 MOLAP 引擎采用预计算的方式来避免数据的实时扫描,对于基于磁盘存储的数仓而言,存储端无疑会因为扫描大量数据造成磁盘吞吐的瓶颈。

既然如此,是否存在别的选择,可以少从存储端加载数据呢?列存数据库正是通过采取合适的数据组织结构,来减小查询加载的数据量,最终提高查询效率。

大数据圈的各位对列式存储一定不陌生,快速浮现你脑海里的想必是 ORCFile,Parquet 等,但其实这些只是数据格式,并不能直接和列存数据库划等号。

www.zeeklog.com  - 列存数据库-kylin关键分析

列存格式 = 列存数据库

www.zeeklog.com  - 列存数据库-kylin关键分析

列存数据库[1]更像是基于列存格式,设计的一套完整的数据库解决方案,而这套解决方案不仅需要考虑数据格式,更要考虑以下因素:

  1. 由于考虑成本效率的因素,计算机中的存储常被设计成多级存储的结构,所以数据不单在磁盘上有特定的存储格式,在内存中,甚至 L1,L2,L3 缓存中同样有其独特的布局方式。考虑到存储端复杂的情况,如何结合 OLAP 场景的 workload,从而针对不同的硬件特点设计数据布局,是列存数据库在存储端需要考虑的核心问题;
  2. 有了在不同存储层的数据存储布局之后,数据如何在不同存储层之间流动,比如,如何从磁盘加载数据到内存,什么时候进行加载,这些都是存取方法[2](Access Method)所涉及的内容;
  3. 数据结构配上合适的算法才能横行江湖,计算和数据组织方式往往紧密耦合,彰显团结的力量。如何结合列存的特点设计一个高效的执行引擎,为 Join,Sort,Groupby 等关系算子提供一种更为高效的算法,都是列存数据库需要考虑的问题。

由此可见,为了追求极致的性能,底层存储的变化往往会引发存取方法执行引擎关系算子算法实现等多方面的一系列适配性的变化,真可谓环环相扣,好不紧张。下面,我们就依次从这几个方面介绍其所涉及内容。

01

存储格式

可曾记得把列存的思想引入大数据的先驱者—— RCFile[3],它的基本思想是将数据水平切分成一个个行组,在每个行组内除了元数据和行组切分标识以外,数据部分按列来进行连续存储。

www.zeeklog.com  - 列存数据库-kylin关键分析

这样操作的原因在于 OLAP 的查询虽然一般都会扫描大量行,但只会涉及少量列,通过这样的列存布局方式,能够有效避免无关列的加载,从而达到减小磁盘吞吐的目的。

但似乎先驱者的下场往往不那么尽如人意,RCFile 也没有摆脱这个魔咒。相较传统数仓中的列存而言,RCFile 还是太过粗糙,要学就学全套呀!

Hive 的开发者们总结了 RCFile 的经验教训,指出其核心问题[4]在于:

  1. 对数据类型不感知,从而无法对具体类型做编码优化,限制了列存的存储高效性;
  2. 没有索引辅助过滤数据(如:谓词下推),造成数据读取效率低下。

站在前人的肩膀上,后续的 ORCFile,Parquet 都开启了进化之旅,一方面加入一些 Min、Max、Count 等轻量级统计索引来加速查询;另一方面,针对不同场景,采用 RLE,Bitcode,Dictionary Code 等编码方式进行存储优化,比如 RLE,针对的就是取值范围不大,重复度高的数据,假设有一列数据是 AAABBBB,RLE 就会直接采用 A3B4 来表达(其中“3”和“4”代表前一个值出现的次数)。

自此以后,列存格式的风吹遍了整个大数据生态圈,CarbonData 采用多维排序的方式优化数据的列式布局;Druid 在列存之上,通过对维度列进行 Dictionary 编码加 Bitmap 索引的方式加速了数据的筛选和聚合......

当然,存储格式并不是只需关心存储查询的效率问题,将其应用到实际中所需要考虑的问题同样重要。比如,2019 年 4 月,Databricks 公司重磅开源 Delta Lake,给数据添加了 ACID 特性,支持数据的并发读写,Hudi 和 Iceberg 也不甘落后,存储的故事又拉开了一张大幕,世界就是这样精彩!

02

存取方式

数据存在磁盘上的数据布局叫做存储格式,而存取方式则包括:

  • 数据是怎么从磁盘读到内存的?(例如 MySQL 加载数据的时候,是通过全表扫描,还是通过索引扫描)
  • 数据在内存的布局是怎样的?
  • 数据又是怎么写回磁盘的?

等一系列过程。

这里我们以数据从磁盘加载到内存的过程为例,来探讨列式存储能够给存取过程带来哪些优势。由于数据最终输出时是以行为单位,所以在将列存数据读入内存时,直接定位到要扫描的列,然后按顺序重构一行行数据并交由执行引擎处理,就显得尤为自然,但我们不如想的更深入一步:

  1. 内存中的数据表是不是也可以是列式的?
  2. 数据是不是可以懒加载(延迟物化)?

对于问题一,Presto、ClickHouse 等实践者通过在内存中使用列存布局,不仅优化了存储效率,也使得向量化计算加速分析查询变为可能;

对于延迟物化[5]的问题,核心就在于数据是否能等到真正需要它们的时候再加载,例如对于以下查询:

select b from R where a = X and d = Y
www.zeeklog.com  - 列存数据库-kylin关键分析

是直接如上图左侧所示,将查询涉及到的 a、b、d 列全部加载到内存里构成一行一行数据,然后进行过滤(Filter)和映射(Project);

还是如上图右侧所示,选择尽量延迟加载,先分别对 a、d 列进行单独加载过滤,决定要输出的行(图中的 01 向量),再把对应行的 b 列加载输出,最后再构建成行数据输出?

这两者的 Tradeoff 在于,虽然延迟加载能够减少数据的加载量,但需要维护原始数据的位置,这样才能找到对应行的其他列的值,然而如果筛选条件(R.a = X and R.d = Y )不能大量过滤数据,延迟加载反而低效。对于这种情况,就需要根据一些统计信息选择合适的加载算法,来最大限度的提高效率。

03

执行引擎与关系算子

说完了存储端的故事,让我们转战计算端,唠一唠执行引擎和关系算子与列存之间又有怎样的故事。

执行引擎

首先,来了解一下执行引擎的在 SQL 查询过程中发挥了什么样的作用。

熟悉 SQL 查询引擎的同学应该都清楚,一条 SQL 会经过词法语法解析、语义校验、逻辑执行计划生成优化等一系列步骤,生成最后的物理执行计划,例如,对于如下 SQL:

select * from R where a = 1

其物理执行计划如下图所示:

www.zeeklog.com  - 列存数据库-kylin关键分析

执行引擎所做的事情就包括,定义 TableScan,Filter 等一系列关系算子(Operator)的实现框架,从而可以组合使用多个关系算子,构建它们之间的数据依赖关系(也就是执行计划),最终实现不同 SQL 的功能。

最经典的执行引擎实现非 Volcano[6] 莫属了。它把每一个算子抽象成数据的迭代器(Iterator),分别由 Open,Next,Close 构成。其中 Open 做一些初始化的工作,比如 TableScan 如何实现打开对应的表文件;Next 按照特定算子的功能逻辑处理数据,增量式得到输出;Close 清理资源。如下的伪代码就是 TableScan 的一个实现:

public class TableScan implement Iterator{
    void open(){
        tableFile.open();
    }
    Row next(){
        if ( (row = tableFile.nextRow()) != EOF){
            return row;
        }
        return EOF;
    }
    
    void close(){
        tableFile.close();
    }
}


Volcano 的优点在于处理逻辑清晰,每个算子只需关心自己的处理逻辑即可,耦合性低。不过它的缺点也很明显,过多虚函数的调用,导致大量 CPU cache miss,从而影响 CPU 执行效率。

在数据库诞生之初,数据库先贤们奋战在弥补磁盘和 CPU 速度巨大的鸿沟上,CPU 的浪费显得微不足道。然而,在数据库新时代,摩尔定律的失效使得单核性能提升日渐趋缓,OLAP 的发展导致将大量数据加载到内存进行计算,瓶颈慢慢从存储端向 CPU 端倾斜,榨干 CPU 每一滴性能的企图就变得越发强烈,于是 CodeGen,向量化执行[7]等方法应运而生,它们从不同的方向入手来优化 CPU 的利用率,能够极大的提高执行效率。向量化执行正是利用列式存储的优势,可以一次性对整列数据进行批量处理,减少 CPU 的消耗。

关系算子

有了执行引擎奠定的框架,关系算子只需要一个萝卜一个坑,逐一实现即可,然而算法的世界是层出不穷,千变万化的,比如对于 Join 大家最熟悉的算法就有 BroadcastJoin,LookupJoin,SortJoin 等等, 而列存又会给 Join 算法带来什么样的优化空间呢?

对于 Join 而言,运算的核心在于两表中 Joinkey 的匹配上,而对于其他列数据匹配上了就复制,匹配不上就丢弃。那么结合延迟物化的思想,是否可以等到匹配完成后再加载其他列数据,从而减小不必要的数据加载。

举个例子,对于如下 SQL:

SELECT emp.age, dept.name FROM emp, dept
WHERE emp.dept_id = dept.id

我们先抽出 emp 表的 dept_id 和 dept 表的 id 列数据,进行匹配,并输出匹配结果对应原表的位置信息,如下图所示:

www.zeeklog.com  - 列存数据库-kylin关键分析

其中等于号的左边为 dept_id 和 id 列的数据,等于号的右边为匹配结果对应原表的位置信息,比如第一行 1,2 代表 dept_id 列的第一个值 42 和 id 列的第 2 个值 42,Join 的结果。

然后根据输出的位置信息,就可以从原始数据中抽取 age,name 列的数据得到 Join 最后的结果。当然该算法能够产生明显优化效果的前提是 Join 的结果相较于原始数据比较小,这样才能够有效避免加载过多数据。另外由于上图输出结果的第二列是无序的,如果回表查必然造成大量随机 IO,为了解决这个问题,Jive Join[8]采用了对其进行排序之后再查询,即将随机 IO 转化为顺序 IO 的方法进行优化。

04

总结

综上,我们从大数据存储格式的变迁;存取方式中 Early Materialization 和 Late Materialization 的权衡取舍;执行框架向优化 CPU 的方向迈进;关系算子结合存储进行优化等几个方面对列存数据库进行了讲解。

实际上,列存数据库不只是存储格式的问题,底层存储的变化往往牵一发而动全身,如何适应性的修改计算引擎、存取方式等来达到更高更快的性能,并适应不同的 workload 或者硬件发展的趋势,都是列存数据库要关心的问题。

www.zeeklog.com  - 列存数据库-kylin关键分析