Categories
数据库

KYLIN、DRUID、CLICKHOUSE核心技术对比

KYLIN、DRUID、CLICKHOUSE是目前主流的OLAP引擎,本文尝试从数据模型和索引结构两个角度,分析这几个引擎的核心技术,并做简单对比。在阅读本文之前希望能对KYLIN、DRUID、CLICKHOUSE有所理解。

1. KYLIN数据模型

Kylin的数据模型本质上是将二维表(Hive表)转换为Cube,然后将Cube存储到HBase表中,也就是两次转换。详细信息可以参我的另一篇文章《Kylin数据模型》

第一次转换,其实就是传统数据库的Cube化,Cube由CuboId组成,下图每个节点都被称为一个CuboId,CuboId表示固定列的数据数据集合,比如“ AB” 两个维度组成的CuboId的数据集合等价于以下SQL的数据集合:

select A, B, sum(M), sum(N) from table group by A, B
image

第二次转换,是将Cube中的数据存储到HBase中,转换的时候CuboId和维度信息序列化到rowkey,度量列组成列簇。在转换的时候数据进行了预聚合。下图展示了Cube数据在HBase中的存储方式。

image

2. KYLIN索引结构

因为Kylin将数据存储到HBase中,所以kylin的数据索引就是HBase的索引。HBase的索引是简化版本的B+树,相比于B+树,HFile没有对数据文件的更新操作。

HFile的索引是按照rowkey排序的聚簇索引,索引树一般为二层或者三层,索引节点比MySQL的B+树大,默认是64KB。数据查找的时候通过树形结构定位到节点,节点内部数据是按照rowkey有序的,可以通过二分查找快速定位到目标。

image

KYLIN小结:适用于聚合查询场景;因为数据预聚合,Kylin可以说是最快的查询引擎(group-by查询这样的复杂查询,可能只需要扫描1条数据);kylin查询效率取决于是否命中CuboId,查询波动较大;HBase索引有点类似MySQL中的联合索引,维度在rowkey中的排序和查询维度组合对查询效率影响巨大; 所以Kylin建表需要业务专家参与。

4. DRUID数据模型

Druid数据模型比较简单,它将数据进行预聚合,只不过预聚合的方式与Kylin不同,kylin是Cube化,Druid的预聚合方式是将所有维度进行Group-by,可以参考下图:

image

5. DRUID索引结构

Druid索引结构可以参考我的另一篇文章《Druid存储结构》,它使用自定义的数据结构,整体上它是一种列式存储结构,每个列独立一个逻辑文件(实际上是一个物理文件,在物理文件内部标记了每个列的start和offset)。对于维度列设计了索引,它的索引以Bitmap为核心。下图为“city”列的索引结构:

image

首先将该列所有的唯一值排序,并生成一个字典,然后对于每个唯一值生成一个Bitmap,Bitmap的长度为数据集的总行数,每个bit代表对应的行的数据是否是该值。Bitmap的下标位置和行号是一一对应的,所以可以定位到度量列,Bitmap可以说是反向索引。同时数据结构中保留了字典编码后的所有列值,其为正向的索引。

那么查询如何使用索引呢?以以下查询为例:

select site, sum(pv) from xx where date=2020-01-01 and city='bj' group by site
  1. city列中二分查找dictionary并找到’bj’对应的bitmap
  2. 遍历city列,对于每一个字典值对应的bitmap与‘bj’的bitmap做与操作
  3. 每个相与后的bitmap即为city=’bj’查询条件下的site的一个group的pv的索引
  4. 通过索引在pv列中查找到相应的行,并做agg
  5. 后续计算

DRUID小结:Druid适用于聚合查询场景但是不适合有超高基维度的场景;存储全维度group-by后的数据,相当于只存储了KYLIN Cube的Base-CuboID;每个维度都有创建索引,所以每个查询都很快,并且没有类似KYLIN的巨大的查询效率波动。

7. CLICKHOUSE索引结构(只讨论MergeTree引擎)

因为Clickhouse数据模型就是普通二维表,这里不做介绍,只讨论索引结构。整体上Clickhouse的索引也是列式索引结构,每个列一个文件。Clickhouse索引的大致思路是:首先选取部分列作为索引列,整个数据文件的数据按照索引列有序,这点类似MySQL的联合索引;其次将排序后的数据每隔8194行选取出一行,记录其索引值和序号,注意这里的序号不是行号,序号是从零开始并递增的,Clickhouse中序号被称作Mark’s number;然后对于每个列(索引列和非索引列),记录Mark’s number与对应行的数据的offset。

下图中以一个二维表(date, city, action)为例介绍了整个索引结构,其中(date,city)是索引列。

image

那么查询如何使用索引呢?以以下查询为例:

select count(distinct action) where date=toDate(2020-01-01) and city=’bj’
  1. 二分查找primary.idx并找到对应的mark’s number集合(即数据block集合)
  2. 在上一步骤中的 block中,在date和city列中查找对应的值的行号集合,并做交集,确认行号集合
  3. 将行号转换为mark’s number 和 offset in block(注意这里的offset以行为单位而不是byte)
  4. 在action列中,根据mark’s number和.mark文件确认数据block在bin文件中的offset,然后根据offset in block定位到具体的列值。
  5. 后续计算

该实例中包含了对于列的正反两个方向的查找过程。反向:查找date=toDate(2020-01-01) and city=’bj’数据的行号;正向:根据行号查找action列的值。对于反向查找,只有在查找条件匹配最左前缀的时候,才能剪枝掉大量数据,其它时候并不高效。

Clickhouse小结:MergeTree Family作为主要引擎系列,其中包含适合明细数据的场景和适合聚合数据的场景;Clickhouse的索引有点类似MySQL的联合索引,当查询前缀元组能命中的时候效率最高,可是一旦不能命中,几乎会扫描整个表,效率波动巨大;所以建表需要业务专家,这一点跟kylin类似。

小结

  • KYLIN、DRUID只适合聚合场景,CLICKHOUSE适合明细和聚合场景
  • 聚合场景,查询效率排序:KYLIN > DRUID > CLICKHOUSE
  • KYLIN、CLICKHOUSE建表都需要业务专家参与
  • KYLIN、CLICKHOUSE查询效率都可能产生巨大差异
  • CLICKHOUSE在向量化方面做得的最好,DRUID少量算子支持向量化、KYLIN目前还不支持向量化计算。

版权声明:文章为作者辛勤劳动的成果,转载请注明作者与出处。

11 replies on “KYLIN、DRUID、CLICKHOUSE核心技术对比”

My wife and i were very thankful when Peter managed to round up his survey while using the precious recommendations he received when using the weblog. It is now and again perplexing to simply possibly be releasing tips and hints which usually the others might have been trying to sell. We really take into account we now have you to thank for this. These illustrations you made, the straightforward website navigation, the relationships your site make it possible to promote – it is mostly terrific, and it is making our son in addition to us recognize that this theme is satisfying, which is certainly very vital. Thanks for the whole thing!

I happen to be writing to make you understand what a terrific experience our princess undergone visiting yuor web blog. She picked up such a lot of things, with the inclusion of what it is like to possess an incredible teaching style to make the others without hassle thoroughly grasp specified tricky topics. You undoubtedly surpassed visitors’ expected results. Thanks for showing those valuable, trustworthy, revealing not to mention unique tips on your topic to Sandra.

I intended to create you one little note just to give thanks as before for the extraordinary ideas you’ve discussed at this time. It has been certainly incredibly generous of people like you to allow extensively all that a lot of folks could possibly have distributed as an e-book in order to make some cash for their own end, especially considering the fact that you could have done it if you considered necessary. The good tips also acted as the easy way to be sure that most people have a similar dream just like mine to find out a lot more in respect of this condition. I’m certain there are lots of more enjoyable moments ahead for individuals that find out your blog.

hydraruzxpnew4af, конечно же, обеспечивает анонимность в сети, но тем не менее, этой защиты недостаточно и работать с проектом с обычного браузера нельзя. При открытии сайта через привычный для вас браузер провайдер отследит все проекты, на которые вы заходили, и столь подозрительная активность может заинтересовать правоохранительные органы. Потому нужно задуматься о дополнительной безопасности.

Howdy veгy cool web sіte!! Man .. Excelⅼent ..
Amazіng .. Ι’ll bookmark youг website and take the feeds
alsο? I am sаtisfied to fіnd a lot ߋf helpful info right here in the submit, ᴡe need work out more techniques on this regard,
thank you for ѕһaring. . . . . .

my site … sony xperia

Thanks foг your personal marvelous posting! I truly enjoyed rеading it, you may be a great
author. I will remember to bⲟоkmaгk your blog and will often come bаck later on. I want to encourage you to continue yoᥙr great writing, have a nice evening!

Here is my web blog: xperia

Leave a Reply

Your email address will not be published. Required fields are marked *