腾讯阿里头条翻牌子 | ClickHouse中MergeTree的存储结构和查询加速
共 8724字，需浏览 18分钟
·
2021-03-04 00:08
点击上方蓝色字体，选择“设为星标”
回复”资源“获取更多资源
引言
MergeTree存储
MergeTree思想
MergeTree存储结构
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 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列其关的存储文件)，从功能上分主要有三个类：
Granule是数据按行划分时用到的逻辑概念。关于多少行是一个Granule这个问题，在老版本中这是用参数index_granularity设定的一个常量，也就是每隔确定行就是一个Granule。在当前版本中有另一个参数index_granularity_bytes会影响Granule的行数，它的意义是让每个Granule中所有列的sum size尽量不要超过设定值。老版本中的定长Granule设定主要的问题是MergeTree中的数据是按Granule粒度进行索引的，这种粗糙的索引粒度在分析超级大宽表的场景中，从存储读取的data size会膨胀得非常厉害，需要用户非常谨慎得设定参数。
Block是列存文件中的压缩单元。每个列存文件的Block都会包含若干个Granule，具体多少个Granule是由参数min_compress_block_size控制，每次列的Block中写完一个Granule的数据时，它会检查当前Block Size有没有达到设定值，如果达到则会把当前Block进行压缩然后写磁盘。
从以上两点可以看出MergeTree的Block既不是定data size也不是定行数的，Granule也不是一个定长的逻辑概念。所以我们需要额外信息快速找到某一个Granule。这就是Mark标识文件的作用，它记录了每个Granule的行数，以及它所在的Block在列存压缩文件中的偏移，同时还有Granule在解压后的Block中的偏移位置。
MergeTree查询
索引检索
/// 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;
数据Sampling
数据扫描
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之间进行并行数据扫描，对于单查询可以达到非常高吞吐的数据读取。
并行扫描：传统的计算引擎在数据扫描部分的并发度大多和存储文件数绑定在一起，所以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头尾的一部分行。
结语
