ClickHouse学习笔记五 MergeTree 原理解析

表引擎是 ClickHouse 设计实现中的一大特色。可以说，是表引擎决定了一张数据表最终的”性格”，比如数据表拥有何种特性、数据以何种形式被存储以及如何被加载。ClickHouse 拥有非常庞大的表引擎体系，其共拥有合并树、外部存储、内存、文件、接口和其他 6 大类 20 多种表引擎。而在这众多的表引擎中，又属合并树（MergeTree）表引擎及其家族系列（*MergeTree）最为强大，在生产环境的绝大部分场景中，都会使用此系列的表引擎。因为只有合并树系列的表引擎才支持主键索引、数据分区、数据副本和数据采样这些特性，同时也只有此系列的表引擎支持 ALTER 相关操作。

合并树家族自身也拥有多种表引擎的变种。其中 MergeTree 作为家族中最基础的表引擎，提供了主键索引、数据分区、数据副本和数据采样等基本能力，而家族中其他的表引擎则在 MergeTree 的基础之上各有所长。例如 ReplacingMergeTree 表引擎具有删除重复数据的特性，而 SummingMergeTree 表引擎则会按照排序键自动聚合数据。如果给合并树系列的表引擎加上 Replicated 前缀，又会得到一组支持数据副本的表引擎，例如 ReplicatedMergeTree、ReplicatedReplacingMergeTree、ReplicatedSummingMergeTree 等。

虽然合并树的变种很多，但 MergeTree 表引擎才是根基。作为合并树家族系列中最基础的表引擎，MergeTree 具备了该系列其他表引擎共有的基本特征，所以吃透了 MergeTree 表引擎的原理，就能够掌握该系列引擎的精髓。以下针对 MergeTree 的一些基本原理进行解读。

1.1 MergeTree 的创建方式与存储结构

MergeTree 在写入一批数据时，数据总会以数据片段的形式写入磁盘，且数据片段不可修改。为了避免片段过多，ClickHouse 会通过后台线程，定期合并这些数据片段，属于相同分区的数据片段会被合成一个新的片段。这种数据片段往复合并的特点，也正是合并树名称的由来。

1.1.1 MergeTree 的创建方式

创建 MergeTree 数据表的方法，与我们之前介绍的定义数据表的方法大致相同，但需要将 ENGINE 参数声明为 MergeTree()，其完整的语法如下所示：

CREATE TABLE [IF NOT EXISTS] [db_name.]table_name (
    name1 [type] [DEFAULT|MATERIALIZED|ALIAS expr],
    name2 [type] [DEFAULT|MATERIALIZED|ALIAS expr],
    ...
) ENGINE = MergeTree()
[PARTITION BY expr]
[ORDER BY expr]
[PRIMARY KEY expr]
[SAMPLE BY expr]
[SETTINGS name=value, ...]

MergeTree 表引擎除了常规参数之外，还拥有一些独有的配置选项。接下来会着重介绍其中几个重要的参数。

（1）PARTITION BY [选填]： 分区键，用于指定表数据以何种标准进行分区。分区键既可以是单个列字段，也可以通过元组的形式使用多个列字段，同时它也支持使用列表达式。如果不声明分区键，则 ClickHouse 会生成一个名为 all 的分区。合理使用数据分区，可以有效减少查询时数据文件的扫描范围。

（2）ORDER BY [必填]： 排序键，用于指定在一个数据片段内，数据以何种标准排序。默认情况下主键（PRIMARY KEY）与排序键相同。排序键既可以是单个列字段，例如ORDER BY CounterID，也可以通过元组的形式使用多个列字段，例如ORDER BY（CounterID,EventDate）。当使用多个列字段排序时，以ORDER BY（CounterID,EventDate）为例，在单个数据片段内，数据首先会以CounterID排序，相同CounterID的数据再按EventDate排序。

（3）PRIMARY KEY [选填]： 默认情况下，主键与排序键(ORDER BY)相同，所以通常直接使用ORDER BY代为指定主键，无须刻意通过PRIMARY KEY声明。所以在一般情况下，在单个数据片段内，数据与一级索引以相同的规则升序排列。与其他数据库不同，MergeTree主键允许存在重复数据（ReplacingMergeTree可以去重）。

（4）SAMPLE BY [选填]： 抽样表达式，用于声明数据以何种标准进行采样。如果使用了此配置项，那么在主键的配置中也需要声明同样的表达式，例如：

) ENGINE = MergeTree()
ORDER BY (CounterID, EventDate, intHash32(UserID)
SAMPLE BY intHash32(UserID)

（5）SETTINGS：index_granularity [选填]： 索引粒度，默认值为 8192。MergeTree 的索引在默认情况下，每间隔 8192 行数据才生成一条索引。

（6）SETTINGS：index_granularity_bytes [选填]： 自适应间隔大小，默认为 10M，设置为 0 表示不启动自适应功能。

（7）SETTINGS：enable_mixed_granularity_parts [选填]： 是否开启自适应索引间隔，默认开启。

（8）SETTINGS：merge_with_ttl_timeout [选填]： TTL 合并超时时间。

（9）SETTINGS：storage_policy [选填]： 多路径存储策略。

1.1.2 MergeTree 的存储结构

MergeTree 表引擎中的数据是拥有物理存储的，数据会按照分区目录的形式保存到磁盘之上。

图 1-2 MergeTree 在磁盘上的物理存储结构

从图中可以看出，一张数据表的完整物理结构分为 3 个层级，依次是数据表目录、分区目录及各分区下具体的数据文件。

（1）partition： 分区目录，属于相同分区的数据最终会被合并到同一个分区目录。

（2）checksums.txt： 校验文件，二进制格式存储，保存了各类文件的 size 及哈希值。

（3）columns.txt： 列信息文件，明文格式存储，例如：

columns format version: 1
4 columns:
'ID' String
'URL' String
'Code' String
'EventTime' Date

（4）count.txt： 计数文件，记录当前分区目录下数据的总行数。

（5）primary.idx： 一级索引文件，二进制格式，用于存放稀疏索引。

（6）[Column].bin： 数据文件，压缩格式存储，默认为 LZ4，每一列一个 .bin 文件。

（7）[Column].mrk： 列字段标记文件，保存了 .bin 文件中数据的偏移量信息。

（8）[Column].mrk2： 自适应索引间隔时使用，与 .mrk 原理相同。

（9）partition.dat 与 minmax_[Column].idx： 分区索引文件，用于快速跳过不必要的数据分区目录。

（10）skp_idx[Column].idx 与 skp_idx[Column].mrk： 二级索引文件。

1.2 数据分区

在 ClickHouse 中，数据分区（partition）和数据分片（shard）是完全不同的概念。数据分区是针对本地数据而言的纵向切分；而横向切分是数据分片（shard）的能力。

1.2.1 数据的分区规则

分区 ID 的生成逻辑目前拥有四种规则：

 ID 在不同规则下的示例

如果通过元组的方式使用多个分区字段，多个 ID 之间通过 - 符号依次拼接，例如：

PARTITION BY (length(Code), EventTime) -- 最终分区 ID: 2-20190501, 2-20190611

1.2.2 分区目录的命名规则

一个完整分区目录的命名公式如下所示：

例如 201905_1_1_0，其中：

• PartitionID：201905分区 ID
• MinBlockNum 和 MaxBlockNum：1最小/1最大数据块编号，全局自增
• Level：0合并的层级，初始值为 0，每次合并加 1

1.2.3 分区目录的合并过程

MergeTree 的分区目录在数据写入过程中被创建，每次 INSERT 都会生成新的分区目录。后台任务会将相同分区的多个目录合并。

合并规则：

• MinBlockNum：取同一分区内所有目录中最小的值
• MaxBlockNum：取同一分区内所有目录中最大的值
• Level：取同一分区内最大 Level 值加 1

旧的分区目录合并后不会被立即删除，而是存留一段时间，状态变为非激活（active=0），查询时自动过滤。

1.3 一级索引

MergeTree 会依据 index_granularity 间隔（默认 8192 行），为数据表生成一级索引并保存至 primary.idx 文件内。

1.3.1 稀疏索引

primary.idx 采用稀疏索引实现。与稠密索引（每行数据都有一条索引记录）不同，稀疏索引每隔一定行数才生成一条索引记录。

以默认索引粒度 8192 为例，MergeTree 只需要 12208 行索引标记就能为 1 亿行数据提供索引。

1.3.2 索引粒度

index_granularity 将数据划分为多个小的区间，每个区间最多 8192 行数据。MergeTree 使用 MarkRange 表示一个具体的区间，并通过 start 和 end 表示其范围。

1.3.3 索引数据的生成规则

由于是稀疏索引，所以MergeTree需要间隔index_granularity行数据才会生成一条索引记录，其索引值会依据声明的主键字段获取。所示是对照测试表hits_v1中的真实数据具象化后的效果。hits_v1使用年月分区（PARTITION BY toYYYYMM(EventDate)），所以2014年3月份的数据最终会被划分到同一个分区目录内。如果使用CounterID作为主键（ORDER BY CounterID），则每间隔8192行数据就会取一次CounterID的值作为索引值，索引数据最终会被写入primary.idx文件进行保存。

例如第0(8192×0)行CounterID取值57，第8192(8192×1)行CounterID取值1635，而第16384(8192×2)行CounterID取值3266，最终索引数据将会是5716353266。从图中也能够看出，MergeTree对于稀疏索引的存储是非常紧凑的，索引值前后相连，按照主键字段顺序紧密地排列在一起。不仅此处，ClickHouse中很多数据结构都被设计得非常紧凑，比如其使用位读取替代专门的标志位或状态码，可以不浪费哪怕一个字节的空间。以小见大，这也是ClickHouse为何性能如此出众的深层原因之一。

如果使用多个主键，例如ORDER BY(CounterID,EventDate)，则每间隔8192行可以同时取CounterID与EventDate两列的值作为索引值，具体如图所示。

1.3.4 索引的查询过程

索引查询是两个数值区间的交集判断。

首先，我们需要了解什么是MarkRange。MarkRange在ClickHouse中是用于定义标记区间的对象。通过先前的介绍已知，MergeTree按照index_granularity的间隔粒度，将一段完整的数据划分成了多个小的间隔数据段，一个具体的数据段即是一个MarkRange。MarkRange与索引编号对应，使用start和end两个属性表示其区间范围。通过与start及end对应的索引编号的取值，即能够得到它所对应的数值区间。而数值区间表示了此MarkRange包含的数据范围。

下面用一份示例数据来进一步说明。假如现在有一份测试数据，共192行记录。其中，主键ID为String类型，ID的取值从A000开始，后面依次为A001、A002……直至A192为止。MergeTree的索引粒度index_granularity=3，根据索引的生成规则，MergeTree会将此数据片段划分成192/3=64个小的MarkRange，两个相邻MarkRange相距的步长为1。其中，所有MarkRange（整个数据片段）的最大数值区间为[A000,+inf)。在引出了数值区间的概念之后，对于索引的查询过程就很好解释了。索引查询其实就是两个数值区间的交集判断。其中，一个区间是由基于主键的查询条件转换而来的条件区间；而另一个区间是刚才所讲述的与MarkRange对应的数值区间。

分为 3 个步骤：

（1）生成查询条件区间：

WHERE ID = 'A003'  →  ['A003', 'A003']
WHERE ID > 'A000'  →  ('A000', +inf)
WHERE ID < 'A188'  →  (-inf, 'A188')
WHERE ID LIKE 'A006%' → ['A006', 'A007')

（2）递归交集判断：

• 无交集 → 剪枝跳过
• 有交集且步长 > 8 → 拆分为 8 个子区间继续递归
• 有交集且不可再分 → 记录 MarkRange 并返回

（3）合并 MarkRange 区间： 将最终匹配的 MarkRange 合并

总结：MergeTree通过递归的形式持续向下拆分区间，最终将MarkRange定位到最细的粒度，以帮助在后续读取数据的时候，能够最小化扫描数据的范围。当查询条件WHERE ID=’A003’的时候，最终只需要读取[A000,A003]和[A003,A006]两个区间的数据,它们对应MarkRange(start:0,end:2)范围，而其他无用的区间都被裁剪掉了。因为MarkRange转换的数值区间是闭区间，所以会额外匹配到临近的一个区间。

1.4 二级索引

二级索引又称跳数索引，由数据的聚合信息构建而成。

与一级索引一样，如果在建表语句中声明了跳数索引，则会额外生成相应的索引与标记文件（skp_idx[Column].idx与skp_idx[Column].mrk)。

1.4.1 granularity 与 index_granularity 的关系

不同的跳数索引之间，除了它们自身独有的参数之外，还都共同拥有granularity参数。初次接触时，很容易将granularity与index_granularity的概念弄混淆。对于跳数索引而言，index_granularity定义了数据的粒度，而granularity定义了聚合信息汇总的粒度。换言之，granularity定义了一行跳数索引能够跳过多少个index_granularity区间的数据。要解释清楚granularity的作用，就要从跳数索引的数据生成规则说起，其规则大致是这样的：首先，按照index_granularity粒度间隔将数据划分成n段，总共有[0,n-1]个区间（n=total_rows/index_granularity，向上取整）。接着，根据索引定义时声明的表达式，从0区间开始，依次按index_granularity粒度从数据中获取聚合信息，每次向前移动1步(n+1)，聚合信息逐步累加。最后，当移动granularity次区间时，则汇总并生成一行跳数索引数据。以minmax索引为例，它的聚合信息是在一个index_granularity区间内数据的最小和最大极值。以下图为例，假设index_granularity=8192且granularity=3，则数据会按照index_granularity划分为n等份，MergeTree从第0段分区开始，依次获取聚合信息。当获取到第3个分区时（granularity=3），则汇总并会生成第一行minmax索引（前3段minmax极值汇总后取值为[1,9]）

• index_granularity 定义数据的粒度
• granularity 定义一行跳数索引能跳过多少个 index_granularity 区间

1.4.2 跳数索引的类型

CREATE TABLE skip_test (
    ID String,
    URL String,
    Code String,
    EventTime Date,
    INDEX a ID TYPE minmax GRANULARITY 5,
    INDEX b (length(ID) * 8) TYPE set(2) GRANULARITY 5,
    INDEX c (ID, Code) TYPE ngrambf_v1(3, 256, 2, 0) GRANULARITY 5,
    INDEX d ID TYPE tokenbf_v1(256, 2, 0) GRANULARITY 5
) ENGINE = MergeTree()

1.5 数据存储

1.5.1 各列独立存储

每个列字段拥有一个对应的 .bin 数据文件。数据经过压缩（默认 LZ4），按 ORDER BY 排序，以压缩数据块形式组织。

1.5.2 压缩数据块

压缩数据块由头信息（9 字节）和压缩数据两部分组成：

每个压缩数据块大小严格控制在 64KB～1MB：

• 单个批次 < 64KB：继续累积直到 ≥ 64KB
• 64KB ≤ 单个批次 ≤ 1MB：直接生成一个压缩块
• 单个批次 > 1MB：按 1MB 截断生成多个压缩块

1.6 数据标记

如果把MergeTree比作一本书，primary.idx一级索引好比这本书的一级章节目录，.bin文件中的数据好比这本书中的文字，那么数据标记(.mrk)会为一级章节目录和具体的文字之间建立关联。对于数据标记而言，它记录了两点重要信息：其一，是一级章节对应的页码信息；其二，是一段文字在某一页中的起始位置信息。这样一来，通过数据标记就能够很快地从一本书中立即翻到关注内容所在的那一页，并知道从第几行开始阅读。

1.6.1 数据标记的生成规则

• 与索引区间对齐，按 index_granularity 粒度
• 每个 .bin 文件对应一个 .mrk 文件
• 一行标记 = 压缩文件偏移量 + 解压后数据偏移量（元组形式）
• 使用 LRU 缓存策略

1.6.2 数据标记的工作方式

JavaEnable字段的数据类型为UInt8，所以每行数值占用1字节。而hits_v1数据表的index_granularity粒度为8192，所以一个索引片段的数据大小恰好是8192B。按照6.5.2节介绍的压缩数据块的生成规则，如果单个批次数据小于64KB，则继续获取下一批数据，直至累积到size>=64KB时，生成下一个压缩数据块。因此在JavaEnable的标记文件中，每8行标记数据对应1个压缩数据块（1B*8192=8192B,64KB=65536B,65536/8192=8）。所以，从下图所示中能够看到，其左侧的标记数据中，8行数据的压缩文件偏移量都是相同的，因为这8行标记都指向了同一个压缩数据块。而在这8行的标记数据中，它们的解压缩数据块中的偏移量，则依次按照8192B（每行数据1B，每一个批次8192行数据）累加，当累加达到65536(64KB)时则置0。因为根据规则，此时会生成下一个压缩数据块。

理解了上述标记数据之后，接下来就开始介绍MergeTree具体是如何定位压缩数据块并读取数据的。

（1）读取压缩数据块： 在查询某一列数据时，MergeTree无须一次性加载整个.bin文件，而是可以根据需要，只加载特定的压缩数据块。而这项特性需要借助标记文件中所保存的压缩文件中的偏移量。在下图所示的标记数据中，上下相邻的两个压缩文件中的起始偏移量，构成了与获取当前标记对应的压缩数据块的偏移量区间。由当前标记数据开始，向下寻找，直到找到不同的压缩文件偏移量为止。此时得到的一组偏移量区间即是压缩数据块在.bin文件中的偏移量。例如在下图所示中，读取右侧.bin文件中[0，12016]字节数据，就能获取第0个压缩数据块。细心的可能会发现，在.mrk文件中，第0个压缩数据块的截止偏移量是12016。而在.bin数据文件中，第0个压缩数据块的压缩大小是12000。为什么两个数值不同呢？其实原因很简单，12000只是数据压缩后的字节数，并没有包含头信息部分。而一个完整的压缩数据块是由头信息加上压缩数据组成的，它的头信息固定由9个字节组成，压缩后大小为8个字节。所以，12016=8+12000+8，其定位方法如下图右上角所示。压缩数据块被整个加载到内存之后，会进行解压，在这之后就进入具体数据的读取环节了。

（2）读取数据： 在读取解压后的数据时，MergeTree并不需要一次性扫描整段解压数据，它可以根据需要，以index_granularity的粒度加载特定的一小段。为了实现这项特性，需要借助标记文件中保存的解压数据块中的偏移量。同样的，在下图所示的标记数据中，上下相邻两个解压缩数据块中的起始偏移量，构成了与获取当前标记对应的数据的偏移量区间。通过这个区间，能够在它的压缩块被解压之后，依照偏移量按需读取数据。例如在下图所示中，通过[0，8192]能够读取压缩数据块0中的

1.7 协同总结

1.7.1 写入过程

写入数据 → 生成分区目录 → 按 index_granularity 生成primary.idx（一级索引）+ 二级索引 + .mrk 标记 + .bin 压缩数据

1.7.2 查询过程

分区索引 → 一级索引 → 二级索引 → 数据标记 → 最小化扫描范围

1.7.3 数据标记与压缩数据块的对应关系

由于压缩数据块的划分，与一个间隔（index_granularity）内的数据大小相关，每个压缩数据块的体积都被严格控制在64KB～1MB。而一个间隔（index_granularity）的数据，又只会产生一行数据标记。那么根据一个间隔内数据的实际字节大小，数据标记和压缩数据块之间会产生三种不同的对应关系。