Clickhouse 中 MergeTree 引擎的数据存储结构
暂时忽略复杂的高可用、水平扩展架构,从数据结构的角度,看 Clickhouse 是如何实现 OLAP 的

Clickhouse 是个使用列式存储方案的 OLAP 数据库。

row-oriented scanning

column-oriented scanning

OLAP(OnLine Analytical Processing) 的特点,包括:

  • 适用于数据分析:适合做统计、聚合等分析性质的查询,区别于适合做增删改查的 OLTP 数据库
  • 适合在线处理:可以短时间(数秒内)得到结果,区别于离线分析(如至少需要数分钟才能得到结果的 hive)

而列式存储的优势,则在于这样的场景:

我的一张表有很多列(几百上千列)属性,但每次检索,只关心其中的一小部分(十几二十个)。这时使用列式存储,则可以忽略不相关的列,减少 I/O 和内存的开销。

数据存储结构

storage-diagram

  1. 一张表由多个分区 (partitions) 构成,数据按照 PARTITION BY 指定的键,保存在不同的分区。

  2. 每个分区由多个数据分片 (data parts) 构成。

    每次插入数据都会产生一个新的 data part, 后台再对这些分片进行合并(即 merge )。

    这里和 HBase, level db, rocks db 不同的是,这里没有内存表 (memory table), 每次插入都会产生新分片。所以 clickhouse 绝对不能一行一行的插入数据,要像 kafka 那样一批一批写入。

  3. 每个数据分片内的数据按主键排序。

  4. 数据默认使用列式存储 (wide 格式),但也可以行式存储 (compact 格式).

    可以用 min_bytes_for_wide_part, min_rows_for_wide_part 来控制是否使用行式存储。每行数据比较小的表,可以用行式存储。

    不指定这两个选项时,默认使用 wide 格式。

  5. 每个数据分片由多个颗粒 (granules) 构成。颗粒是 clickhouse 读取数据的最小单位。

    这是 clickhouse 的关键数据结构

    Granule 的大小由表设置 index_granularity, index_granularity_bytes 控制。即:

    • 一个 granule 中包含的数据行数,不会超过 index_granulartiy 的配置
    • 一个 granule 的大小,除去 granule 中的最后一行数据后,大小不超过 index_granularty_bytes 的配置。最后一行数据的大小可以溢出

    一个 granule 的头部会标记这个 granule 内第一行数据的主键的值。随后的数据就不再会带有主键的值。此外,clickhouse 会按这个主键值为 granules 建立索引。

    Granules 是个很独特的设计。

    作为列式存储的系统,每列的数据是分开保存的。(属于废话了)

    在之前的系统里,列式存储大概有两种方式。一个是 Hive 的方案,只存数据,没有排序和索引。读取的时候只能做全列扫描。另一个是 HBase 的方案,按主键排好序并建立索引。

    HBase 的这种索引模式和列式存储配合起来时存在一个很大的问题:既然每列是分开存储的,那么每列的索引也就是分开的,那么主键的值就会在每列上都被重复保存,占用大量空间。为了规避这个问题,HBase 并不是每列数据都分开保存,而是按 column family 分开保存,并且 column family 的数量不能太多。

    Clickhouse 的 granules 设计,相当于是以上两种方式的折中。即:

    1. 对数据按主键排序
    2. 不对每行数据建索引,只对 granules 建索引。

    这样避免了主键占用大量空间,又使得检索的时候不需要做全表扫描(可以先根据索引定位到 granules, 然后在 granules 内部做遍历扫描)。

    同时,这样的设计也使得 granules 内的数据更加紧凑,有利于数据压缩。

Secondary Index

以上的数据结构只能满足主键检索的需要。非主键的检索,还需要其它数据结构来支撑。

Clickhouse 的 secondary index 和传统数据库的 B 树索引完全不同,它被成为 data skipping index, 用于在检索中快速跳过不相关的 granules, 作用和 HBase 的 bloom filter 比较类似。

Bloom filter 确实也是 clickhouse 支持的一种 data skipping index 类型。不过 clickhouse 还支持更多的类型,包括:

  • minmax: 保存 granules 中数据的最大最小值区间
  • set(max_rows): 保存去重后数据的值
  • ngramebf_v1: 对字符串做 ngram 后再保存到 bloom filter 中,适合字符串 LIKE 搜索
  • tokenbf_v1: 对字符串做 tokenization 后再保存到 bloom filter 中
  • bloomfilter: 保存数据到 bloom filter 中

granularity_value 参数控制 data skipping index 的粒度,最小粒度为 1 个 granules. 增大粒度可以节省索引空间,减小粒度可以提高索引的有效性。

这种设计下,索引的有效性会收到数据分布和排序键的影响。一个极端的例子,排序键是 (年, 月, 日). 数据如:

1970	01	01	foo
1970	01	02	foo
...
1970	01	31	foo
1970	02	01	foo
...

这时如果建立索引 (日), 那么由于每个 granules 都包含了从 1 到 31 的所有值,这个索引会完全不起作用。


最后修改于 2021-10-05