ClickHouse内核分析MergeTree的存储结构和查询加速

注：以下分析基于开源 v19.15.2.2-stable 版本进行

引言

ClickHouse 是最近比较火的一款开源列式存储分析型数据库，它最核心的特点就是极致存储压缩率和查询性能，本人最近正在学习 ClickHouse 这款产品中。从我个人的视角来看存储是决定一款数据库核心竞争力、适用场景的关键所在，所以接下来我会陆续推出一系列文章来分析 ClickHouse 中最重要的 MergeTree 存储内核。本文主旨在于介绍 MergeTree 的存储格式，并且彻底剖析 MergeTree 存储的极致检索性能。

MergeTree 存储

MergeTree 思想

提到 MergeTree 这个词，可能大家都会联想到 LSM-Tree 这个数据结构，我们常用它来解决随机写磁盘的性能问题，MergeTree 的核心思想和 LSM-Tree 相同。MergeTree 存储结构需要对用户写入的数据做排序然后进行有序存储，数据有序存储带来两大核心优势：

• 列存文件在按块做压缩时，排序键中的列值是连续或者重复的，使得列存块的数据压缩可以获得极致的压缩比。

• 存储有序性本身就是一种可以加速查询的索引结构，根据排序键中列的等值条件或者 range 条件我们可以快速找到目标行所在的近似位置区间(下文会展开详细介绍)，而且这种索引结构是不会产生额外存储开销的。

大家可以从 ClickHouse 的官方文档上找到一系列的 MergeTree 表引擎，包括基础的 MergeTree，拥有数据去重能力的 ReplacingMergeTree、CollapsingMergeTree、VersionedCollapsingMergeTree，拥有数据聚合能力的 SummingMergeTree、AggregatingMergeTree 等。但这些拥有“特殊能力”的 MergeTree 表引擎在存储上和基础的 MergeTree 其实没有任何差异，它们都是在数据 Merge 的过程中加入了“额外的合并逻辑”，这部分会在后续介绍 MergeTree 异步 Merge 机制的文章中详细展开介绍。

MergeTree 存储结构

为了方便大家理解表的存储结构，下面列举了某个 POC 用户的测试表 DDL，我们将从这个表入手来分析 MergeTree 存储的内核设计。从 DDL 的 PARTITION BY 申明中我们可以看出用户按每个区服每小时粒度创建了数据分区，而每个数据分区内部的数据又是按照 (action_id, scene_id, time_ts, level, uid) 作为排序键进行有序存储。

CREATE TABLE user_action_log (`time` DateTime DEFAULT CAST('1970-01-01 08:00:00', 'DateTime') COMMENT '日志时间',
  `action_id` UInt16 DEFAULT CAST(0, 'UInt16') COMMENT '日志行为类型 id',
  `action_name` String DEFAULT ''COMMENT' 日志行为类型名 ',
  `region_name` String DEFAULT ''COMMENT' 区服名称 ',
  `uid` UInt64 DEFAULT CAST(0, 'UInt64') COMMENT '用户 id',
  `level` UInt32 DEFAULT CAST(0, 'UInt32') COMMENT '当前等级',
  `trans_no` String DEFAULT ''COMMENT' 事务流水号 ',
  `ext_head` String DEFAULT ''COMMENT' 扩展日志 head',
  `avatar_id` UInt32 DEFAULT CAST(0, 'UInt32') COMMENT '角色 id',
  `scene_id` UInt32 DEFAULT CAST(0, 'UInt32') COMMENT '场景 id',
  `time_ts` UInt64 DEFAULT CAST(0, 'UInt64') COMMENT '秒单位时间戳',
  index avatar_id_minmax (avatar_id) type minmax granularity 3
) ENGINE = MergeTree()
PARTITION BY (toYYYYMMDD(time), toHour(time), region_name)
ORDER BY (action_id, scene_id, time_ts, level, uid)
PRIMARY KEY (action_id, scene_id, time_ts, level);

该表的 MergeTree 存储结构逻辑示意图如下：

MergeTree 表的存储结构中，每个数据分区相互独立，逻辑上没有关联。单个数据分区内部存在着多个 MergeTree Data Part。这些 Data Part 一旦生成就是 Immutable 的状态，Data Part 的生成和销毁主要与写入和异步 Merge 有关。MergeTree 表的写入链路是一个极端的 batch load 过程，Data Part 不支持单条的 append insert。每次 batch insert 都会生成一个新的 MergeTree Data Part。如果用户单次 insert 一条记录，那就会为那一条记录生成一个独立的 Data Part，这必然是无法接受的。一般我们使用 MergeTree 表引擎的时候，需要在客户端做聚合进行 batch 写入或者在 MergeTree 表的基础上创建 Distributed 表来代理 MergeTree 表的写入和查询，Distributed 表默认会缓存用户的写入数据，超过一定时间或者数据量再异步转发给 MergeTree 表。MergeTree 存储引擎对数据实时可见要求非常高的场景是不太友好的。

上图展示了单个 MergeTree Data Part 里最核心的一部分磁盘文件(只画了 action_id 和 avatar_id 列其关的存储文件)，从功能上分主要有三个类：

1 数据文件：action_id.bin、avatar_id.bin 等都是单个列按块压缩后的列存文件。ClickHouse 采用了非常极端的列存模式，这里展开一些细节，单个列数据可能会对应多个列存文件，例如申明一个 Nullable 字段时会多一个 nullable 标识的列存文件，申明一个 Array 字段时会多一个 array size 的列存文件, 采用字典压缩时字典 Key 也会单独变成一个列存文件。有一点小 Tips：当用户不需要 Null 值特殊标识时，最好不要去申明 Nullable，这是 ClickHouse 的极简化设计思路。

2 Mark 标识文件：action_id.mrk2、avatar_id.mrk2 等都是列存文件中的 Mark 标记，Mark 标记和 MergeTree 列存中的两个重要概念相关：Granule 和 Block。

• 1. Granule 是数据按行划分时用到的逻辑概念。关于多少行是一个 Granule 这个问题，在老版本中这是用参数 index_granularity 设定的一个常量，也就是每隔确定行就是一个 Granule。在当前版本中有另一个参数 index_granularity_bytes 会影响 Granule 的行数，它的意义是让每个 Granule 中所有列的 sum size 尽量不要超过设定值。老版本中的定长 Granule 设定主要的问题是 MergeTree 中的数据是按 Granule 粒度进行索引的，这种粗糙的索引粒度在分析超级大宽表的场景中，从存储读取的 data size 会膨胀得非常厉害，需要用户非常谨慎得设定参数。
• 1. Block 是列存文件中的压缩单元。每个列存文件的 Block 都会包含若干个 Granule，具体多少个 Granule 是由参数 min_compress_block_size 控制，每次列的 Block 中写完一个 Granule 的数据时，它会检查当前 Block Size 有没有达到设定值，如果达到则会把当前 Block 进行压缩然后写磁盘。
• 1. 从以上两点可以看出 MergeTree 的 Block 既不是定 data size 也不是定行数的，Granule 也不是一个定长的逻辑概念。所以我们需要额外信息快速找到某一个 Granule。这就是 Mark 标识文件的作用，它记录了每个 Granule 的行数，以及它所在的 Block 在列存压缩文件中的偏移，同时还有 Granule 在解压后的 Block 中的偏移位置。

3 主键索引：primary.idx 是表的主键索引。ClickHouse 对主键索引的定义和传统数据库的定义稍有不同，它的主键索引没用主键去重的含义，但仍然有快速查找主键行的能力。ClickHouse 的主键索引存储的是每一个 Granule 中起始行的主键值，而 MergeTree 存储中的数据是按照主键严格排序的。所以当查询给定主键条件时，我们可以根据主键索引确定数据可能存在的 Granule Range，再结合上面介绍的 Mark 标识，我们可以进一步确定数据在列存文件中的位置区间。ClickHoue 的主键索引是一种在索引构建成本和索引效率上相对平衡的粗糙索引。MergeTree 的主键序列默认是和 Order By 序列保存一致的，但是用户可以把主键序列定义成 Order By 序列的部分前缀。

4 分区键索引：minmax_time.idx、minmax_region_name.idx 是表的分区键索引。MergeTree 存储会把统计每个 Data Part 中分区键的最大值和最小值，当用户查询中包含分区键条件时，就可以直接排除掉不相关的 Data Part，这是一种 OLAP 场景下常用的分区裁剪技术。

5Skipping 索引：skp_idx_avatar_id_minmax.idx 是用户在 avatar_id 列上定义的 MinMax 索引。Merge Tree 中 的 Skipping Index 是一类局部聚合的粗糙索引。用户在定义 skipping index 的时候需要设定 granularity 参数，这里的 granularity 参数指定的是在多少个 Granule 的数据上做聚合生成索引信息。用户还需要设定索引对应的聚合函数，常用的有 minmax、set、bloom_filter、ngrambf_v1 等，聚合函数会统计连续若干个 Granule 中的列值生成索引信息。Skipping 索引的思想和主键索引是类似的，因为数据是按主键排序的，主键索引统计的其实就是每个 Granule 粒度的主键序列 MinMax 值，而 Skipping 索引提供的聚合函数种类更加丰富，是主键索引的一种补充能力。另外这两种索引都是需要用户在理解索引原理的基础上贴合自己的业务场景来进行设计的。

MergeTree 查询

这一章主要会结合 ClickHouse 的源码为大家分析 MergeTree 表引擎上的数据查询过程，我大致把这个过程分为两块：索引检索和数据扫描。索引检索部分对每个 MergeTree Data Part 是串行执行，但 Data Part 之间的检索没有任何关联。而在数据扫描部分中最底层的列存扫描是多所有 Data Part 并行执行，各 Data Part 的列存扫描之间也没有任何关联。

索引检索

MergeTree 存储在收到一个 select 查询时会先抽取出查询中的分区键和主键条件的 KeyCondition，KeyCondition 类上实现了以下三个方法，用于判断过滤条件可能满足的 Mark Range。上一章讲过 MergeTree Data Part 中的列存数据是以 Granule 为粒度被 Mark 标识数组索引起来的，而 Mark Range 就表示 Mark 标识数组里满足查询条件的下标区间。

/// Whether the condition is feasible in the key range.
    /// left_key and right_key must contain all fields in the sort_descr in the appropriate order.
    /// data_types - the types of the key columns.
    bool mayBeTrueInRange(size_t used_key_size, const Field * left_key, const Field * right_key, const DataTypes & data_types) const;
    /// Whether the condition is feasible in the direct product of single column ranges specified by `parallelogram`.
    bool mayBeTrueInParallelogram(const std::vector<Range> & parallelogram, const DataTypes & data_types) const;
    /// Is the condition valid in a semi-infinite (not limited to the right) key range.
    /// left_key must contain all the fields in the sort_descr in the appropriate order.
    bool mayBeTrueAfter(size_t used_key_size, const Field * left_key, const DataTypes & data_types) const;

索引检索的过程中首先会用分区键 KeyCondition 裁剪掉不相关的数据分区，然后用主键索引挑选出粗糙的 Mark Range，最后再用 Skipping Index 过滤主键索引产生的 Mark Range。用主键索引挑选出粗糙的 Mark Range 的算法是一个不断分裂 Mark Range 的过程，返回结果是一个 Mark Range 的集合。起始的 Mark Range 是覆盖整个 MergeTree Data Part 区间的，每次分裂都会把上次分裂后的 Mark Range 取出来按一定粒度步长分裂成更细粒度的 Mark Range，然后排除掉分裂结果中一定不满足条件的 Mark Range，最后 Mark Range 到一定粒度时停止分裂。这是一个简单高效的粗糙过滤算法。

使用 Skipping Index 过滤主键索引返回的 Mark Range 之前，需要构造出每个 Skipping Index 的 IndexCondition，不同的 Skipping Index 聚合函数有不同的 IndexCondition 实现，但判断 Mark Range 是否满足条件的接口和 KeyCondition 是类似的。

数据 Sampling

经过上一小节的索引过滤之后，我们已经得到了需要扫描的 Mark Range 集合，接下来就应该是数据扫描部分了。这一小节插入简单讲一下 MergeTree 里的数据 Sampling 是如何实现的。它并不是在数据扫描过程中实现的，而是在索引检索的过程中就已经完成，这种做法是为了极致的 sample 效率。用户在建表的时候可以指定主键中的某个列或者表达式作为 Sampling 键，ClickHouse 在这里用了简单粗暴的做法：Sampling 键的值必须是数值类型的，并且系统假定它的值是随机均匀分布的一个状态。如果 Sampling 键的值类型是 Uint32，当我们设定 sample 比率是 0.1 的时候，索引检索过程中会把 sample 转换成一个 filter 条件：Sampling 键的值 < Uint32::max * 0.1。用户在使用 Sampling 功能时必须清楚这个细节，不然容易出现采样偏差。一般我们推荐 Sampling 键是列值加一个 Hash 函数进行随机打散。

数据扫描

MergeTree 的数据扫描部分提供了三种不同的模式：

• Final 模式：该模式对 CollapsingMergeTree、SummingMergeTree 等表引擎提供一个最终 Merge 后的数据视图。前文已经提到过 MergeTree 基础上的高级 MergeTree 表引擎都是对 MergeTree Data Part 采用了特定的 Merge 逻辑。它带来的问题是由于 MergeTree Data Part 是异步 Merge 的过程，在没有最终 Merge 成一个 Data Part 的情况下，用户无法看到最终的数据结果。所以 ClickHouse 在查询是提供了一个 final 模式，它会在各个 Data Part 的多条 BlockInputStream 基础上套上一些高级的 Merge Stream，例如 DistinctSortedBlockInputStream、SummingSortedBlockInputStream 等，这部分逻辑和异步 Merge 时的逻辑保持一致，这样用户就可以提前看到“最终”的数据结果了。
• Sorted 模式：sort 模式可以认为是一种 order by 下推存储的查询加速优化手段。因为每个 MergeTree Data Part 内部的数据是有序的，所以当用户查询中包括排序键 order by 条件时只需要在各个 Data Part 的 BlockInputStream 上套一个做数据有序归并的 InputStream 就可以实现全局有序的能力。
• Normal 模式：这是基础 MergeTree 表最常用的数据扫描模式，多个 Data Part 之间进行并行数据扫描，对于单查询可以达到非常高吞吐的数据读取。

接下来展开介绍下 Normal 模式中几个关键的性能优化点：

• 并行扫描：传统的计算引擎在数据扫描部分的并发度大多和存储文件数绑定在一起，所以 MergeTree Data Part 并行扫描是一个基础能力。但是 MergeTree 的存储结构要求数据不断 mege，最终合并成一个 Data Part，这样对索引和数据压缩才是最高效的。所以 ClickHouse 在 MergeTree Data Part 并行的基础上还增加了 Mark Range 并行。用户可以任意设定数据扫描过程中的并行度，每个扫描线程分配到的是 Mark Range In Data Part 粒度的任务，同时多个扫描线程之间还共享了 Mark Range Task Pool，这样可以避免在存储扫描中的长尾问题。
• 数据 Cache：MergeTree 的查询链路中涉及到的数据有不同级别的缓存设计。主键索引和分区键索引在 load Data Part 的过程中被加载到内存，Mark 文件和列存文件有对应的 MarkCache 和 UncompressedCache，MarkCache 直接缓存了 Mark 文件中的 binary 内容，而 UncompressedCache 中缓存的是解压后的 Block 数据。
• SIMD 反序列化：部分列类型的反序列化过程中采用了手写的 sse 指令加速，在数据命中 UncompressedCache 的情况下会有一些效果。
• PreWhere 过滤：ClickHouse 的语法支持了额外的 PreWhere 过滤条件，它会先于 Where 条件进行判断。当用户在 sql 的 filter 条件中加上 PreWhere 过滤条件时，存储扫描会分两阶段进行，先读取 PreWhere 条件中依赖的列值，然后计算每一行是否符合条件。相当于在 Mark Range 的基础上进一步缩小扫描范围，PreWhere 列扫描计算过后，ClickHouse 会调整每个 Mark 对应的 Granule 中具体要扫描的行数，相当于可以丢弃 Granule 头尾的一部分行。

结语

随着阅读 ClickHouse 源码深入了解它的内核实现，我认为 ClickHouse 目前还不是一个特别完美的分析型数据库。但它仍然有许多极致的性能优化设计，这些设计都是源于 Yandex 公司真实的分析场景，并且确实可以解决海量数据下的一些业务问题。我相信在一部分适合 ClickHouse 的业务场景中，它就是可以给用户带来最极致性能体验的数据库。

后续会陆续推出更多的分析文章，有兴趣的同学可以多多交流和 follow，先为后面的文章取个名字：

MergeTree 的 Merge 和 Mutation 机制
MergeTree 写入链路全解析
MergeTree 的 Table 管理设计：Alter、TTL 和分层存储