ClickHouse学习小记--MergeTree原理_index_granularity

MergeTree原理解析

表引擎是ClickHouse设计实现中的一大特色。可以说，是表引擎决定了一张数据表最终的“性格”，比如数据表拥有何种特性、数据以何种形式被存储以及如何被加载。ClickHouse拥有非常庞大的表引擎体系，其共拥有合并树、外部存储、内存、文件、接口和其他6大类20多种表引擎。
在生产环境的绝大部分场景中，都会使用合并树（MergeTree）表引擎及其家族系列（*MergeTree）的表引擎。

• 只有合并树系列的表引擎才支持主键索引、数据分区、数据副本和数据采样等特性
• 只有此系列的表引擎支持ALTER相关操作

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

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

一、MergeTree的创建方式与存储结构

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

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, 省略...] 
1
2
3
4
5
6
7
8
9
10

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)
1
2
3

抽样表达式需要配合SAMPLE子查询使用，这项功能对于选取抽样数据十分有用。

（5）SETTINGS：index_granularity [选填]
index_granularity对于MergeTree而言是一项非常重要的参数，它表示索引的粒度，默认值为8192。也就是说，MergeTree的索引在默认情况下，每间隔8192行数据才生成一条索引，其具体声明方式如下所示：

省略... ) ENGINE = MergeTree()
省略... SETTINGS index_granularity = 8192;
1
2

8192是一个神奇的数字，在ClickHouse中大量数值参数都有它的影子，可以被其整除（例如最小压缩块大小
min_compress_block_size:65536）。通常情况下并不需要修改此参数，但理解它的工作原理有助于我们更好地使用MergeTree。

（6）SETTINGS：index_granularity_bytes [选填]
在19.11版本之前，ClickHouse只支持固定大小的索引间隔，由index_granularity控制，默认为8192。在新版本中，它增加了自适应间隔大小的特性，即根据每一批次写入数据的体量大小，动态划分间隔大小。而数据的体
量大小，正是由index_granularity_bytes参数控制的，默认为10M(10×1024×1024)，设置为0表示不启动自适应功能。

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

（8）SETTINGS：merge_with_ttl_timeout [选填]
从19.6版本开始，MergeTree提供了数据TTL的功能。

（9）SETTINGS：storage_policy [选填]
从19.15版本开始，MergeTree提供了多路径的存储策略。

2、MergeTree的存储结构

MergeTree表引擎中的数据是拥有物理存储的，数据会按照分区目录的形式保存到磁盘之上，其完整的存储结构如图6-2所示。

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

（1）分区目录：partition
余下各类数据文件（primary.idx、 [Column].mrk、[Column].bin等）都是以分区目录的形式被组织存放的，属于相同分区的数据，最终会被合并到同一个分区目录，而不同分区的数据，永远不会被合并在一起。

（2）校验文件：checksums.txt
使用二进制格式存储。它保存了余下各类文件(primary.idx、count.txt等)的size大小及size的哈希值，用于
快速校验文件的完整性和正确性。

（3）列信息文件：columns.txt
使用明文格式存储。用于保存此数据分区下的列字段信息，例如：
$ cat columns.txt columns format version: 1 4 columns: ‘ID’ String ‘URL’ String ‘Code’ String ‘EventTime’ Date

（4）计数文件：count.txt
使用明文格式存储。用于记录当前数据分区目录下数据的总行数，例如：
$ cat count.txt 8 （5）primary.idx：一级索引文件，使用二进制格式存储。
用于存放稀疏索引，一张MergeTree表只能声明一次一级索引（通过ORDER BY或者PRIMARY KEY）。借助稀疏索引，在数据查询的时能够排除主键条件范围之外的数据文件，从而有效减少数据扫描范围，加速查询速度。

（6）数据文件：[Column].bin
使用压缩格式存储，默认为LZ4压缩格式，用于存储某一列的数据。由于MergeTree采用列式存储，所以每一个列字段都拥有独立的.bin数据文件，并以列字段名称命名（例如CounterID.bin、EventDate.bin等）。

（7）列字段标记文件：[Column].mrk
使用二进制格式存储。标记文件中保存了.bin文件中数据的偏移量信息。标记文件与稀疏索引对
齐，又与.bin文件一一对应，所以MergeTree通过标记文件建立了primary.idx稀疏索引与.bin数据文件之间的映射关系。即首先通过稀疏索引（primary.idx）找到对应数据的偏移量信息（.mrk），再通过偏移量直接从.bin文件中读取数据。由于.mrk标记文件与.bin文件一一对应，所以MergeTree中的每个列字段都会拥有与其对应的.mrk标记文件（例如CounterID.mrk、EventDate.mrk等）。

（8）[Column].mrk2
如果使用了自适应大小的索引间隔，则标记文件会以.mrk2命名。它的工作原理和作用与.mrk标记文件相同。

（9）partition.dat与minmax_[Column].idx
如果使用了分区键，例如PARTITION BY EventTime，则会额外生成partition.dat与minmax索引文件，它们均使用二进制格式存储。partition.dat用于保存当前分区下分区表达式最终生成的值；而minmax索引用于记录当前分区下分区字段对应原始数据的最小和最大值。例如EventTime字段对应的原始数据为2019-05-01、2019-05-05，分区表达式为PARTITION BY toYYYYMM(EventTime)。partition.dat中保存的值将是2019-05，而minmax索引中保存的值将会是2019-05-012019-05-05。

在这些分区索引的作用下，进行数据查询时能够快速跳过不必要的数据分区目录，从而减少最终需要扫描的数据范围。

（10）skp_idx_[Column].idx与skp_idx_[Column].mrk
如果在建表语句中声明了二级索引，则会额外生成相应的二级索引与标记文件，它们同样也使用二进制存储。二级索引在ClickHouse中又称跳数索引，目前拥有minmax、set、ngrambf_v1和tokenbf_v1四种类型。这些索引的
最终目标与一级稀疏索引相同，都是为了进一步减少所需扫描的数据范围，以加速整个查询过程。

二、数据分区

通过先前的介绍已经知晓在MergeTree中，数据是以分区目录的形式进行组织的，每个分区独立分开存储。借助这种形式，在对MergeTree进行数据查询时，可以有效跳过无用的数据文件，只使用最小的分区目录子集。这里有一点需要明确，在ClickHouse中，数据分区（partition）和数据分片（shard）是完全不同的概念。数据分区是针对本地数据而言的，是对数据的一种纵向切分。MergeTree并不能依靠分区的特性，将一张表的数据分布到多个ClickHouse服务节点。而横向切分是数据分片（shard）的能力。

1、 数据的分区规则

MergeTree数据分区的规则由分区ID决定，而具体到每个数据分区所对应的ID，则是由分区键的取值决定的。分区键支持使用任何一个或一组字段表达式声明，其业务语义可以是年、月、日或者组织单位等任何一种规则。针对取值数据类型的不同，分区ID的生成逻辑目前拥有四种规则：

（1）不指定分区键
如果不使用分区键，即不使用PARTITION BY声明任何分区表达式，则分区ID默认取名为all，所有的数据都会被写入这个all分区。

（2）使用整型
如果分区键取值属于整型（兼容UInt64，包括有符号整型和无符号整型），且无法转换为日期类型YYYYMMDD格式，则直接按照该整型的字符形式输出，作为分区ID的取值。

（3）使用日期类型
如果分区键取值属于日期类型，或者是能够转换为YYYYMMDD格式的整型，则使用按照YYYYMMDD进行格式化后的字符形式输出，并作为分区ID的取值。

（4）使用其他类型
如果分区键取值既不属于整型，也不属于日期类型，例如String、Float等，则通过128位Hash算法取其Hash值作为分区ID的取值。数据在写入时，会对照分区ID落入相应的数据分区，下表列举了分区ID在不同规则下的一些示例。

如果通过元组的方式使用多个分区字段，则分区ID依旧是根据上述规则生成的，只是多个ID之间通过“-”符号依次拼接。例如按照上述表格中的例子，使用两个字段分区：

PARTITION BY (length(Code),EventTime)
1

则最终的分区ID会是下面的模样：

2-20190501 
2-20190611
1
2

2、分区目录的命名规则

如果进入数据表所在的磁盘目录后，会发现MergeTree分区目录的完整物理名称并不是只有ID而已，在ID之后还跟着一串奇怪的数字，例如201905_1_1_0。那么这些数字又代表着什么呢？

众所周知，对于MergeTree而言，它最核心的特点是其分区目录的合并动作。但是我们可曾想过，从分区目录的命名中便能够解读出它的合并逻辑，一个完整分区目录的命名公式如下所示：

PartitionID_MinBlockNum_MaxBlockNum_Level
1

如果对照着示例数据，那么数据与公式的对照关系会如同下图所示。

上图中，201905表示分区目录的ID；1_1分别表示最小的数据块编号与最大的数据块编号；而最后的_0则表示目前合并的层级。接下来开始分别解释它们的含义：

（1）PartitionID：分区ID。

（2）MinBlockNum和MaxBlockNum
顾名思义，最小数据块编号与最大数据块编号。ClickHouse在这里的命名似乎有些歧义，很容易让
人与稍后会介绍到的数据压缩块混淆。但是本质上它们毫无关系，这里的BlockNum是一个整型的自增长编号。如果将其设为n的话，那么计数n在单张MergeTree数据表内全局累加，n从1开始，每当新创建一个分区目录时，计数n就会累积加1。对于一个新的分区目录而言，MinBlockNum与MaxBlockNum取值一样，同等于n，例201905_1_1_0、201906_2_2_0以此类推。但是也有例外，当分区目录发生合并时，对于新产生的合并目录MinBlockNum与MaxBlockNum有着另外的取值规则。

（3）Level
合并的层级，可以理解为某个分区被合并过的次数，或者这个分区的年龄。数值越高表示年龄越大。Level计数与BlockNum有所不同，它并不是全局累加的。对于每一个新创建的分区目录而言，其初始值均为0。之后，以分区为单位，如果相同分区发生合并动作，则在相应分区内计数累积加1。

3、分区目录的合并过程

MergeTree的分区目录和传统意义上其他数据库有所不同。首先，MergeTree的分区目录并不是在数据表被创建之后就存在的，而是在数据写入过程中被创建的。也就是说如果一张数据表没有任何数据，那么也不会有任何分区目录存在。其次，它的分区目录在建立之后也并不是一成不变的。在其他某些数据库的设计中，追加数据后目录自身不会发生变化，只是在相同分区目录中追加新的数据文件。而MergeTree完全不同，伴随着每一批数据的写入（一次INSERT语句），MergeTree都会生成一批新的分区目录。即便不同批次写入的数据属于相同分区，也会生成不同的分区目录。对于同一个分区而言，也会存在多个分区目录的情况。在之后的某个时刻（写入后的10～15分钟，也可以手动执行optimize查询语句），ClickHouse会通过后台任务再将属于相同分区的多个目录合并成一个新的目录。已经存在的旧分区目录并不会立即被删除，而是在之后的某个时刻通过后台任
务被删除（默认8分钟）。

属于同一个分区的多个目录，在合并之后会生成一个全新的目录，目录中的索引和数据文件也会相应地进行合并。新目录名称的合并方式遵循以下规则，

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

合并目录名称的变化过程如图6-4所示：

下面是一张完整的示例图，描述MergeTree分区目录从创建、合并到删除的整个过程，如图6-5所示：

分区目录在发生合并之后，旧的分区目录并没有被立即删除，而是会存留一段时间。但是旧的分区目录已不再是激活状态（active=0），所以在数据查询时，它们会被自动过滤掉。

三、一级索引

MergeTree的主键使用PRIMARY KEY定义，待主键定义之后，MergeTree会依据index_granularity间隔（默认8192行），为数据表生成一级索引并保存至primary.idx文件内，索引数据按照PRIMARY KEY排序。相比使用PRIMARY KEY定义，更为常见的简化形式是通过ORDER BY指代主键。在此种情形下，PRIMARY KEY与ORDER BY定义相同，所以索引（primary.idx）和数据（.bin）会按照完全相同的规则排序。

3.1、稀疏索引

primary.idx文件内的一级索引采用稀疏索引实现。既然提到了稀疏索引，那也有稠密索引！稀疏索引和稠密索引的区别如图6-6所示。

在稠密索引中每一行索引标记都会对应到一行具体的数据记录。而在稀疏索引中，每一行索引标记对应的是一段数据，而不是一行。用一个形象的例子来说明：如果把MergeTree比作一本书，那么稀疏索引就好比是这本书的一级章节目录。一级章节目录不会具体对应到每个字的位置，只会记录每个章节的起始页码。

稀疏索引仅需使用少量的索引标记就能够记录大量数据的区间位置信息，且数据量越大优势越为明显。以默认的索引粒度（8192）为例，MergeTree只需要12208行索引标记就能为1亿行数据记录提供索引。由于稀疏索引占用空间小，所以primary.idx内的索引数据常驻内存，取用速度自然极快。

3.2 索引粒度

index_granularity这个参数，它表示索引的粒度。虽然在新版本中，ClickHouse提供了自适应粒度大小的特性，但是为了便于理解，仍然会使用固定的索引粒度（默认8192）进行讲解。索引粒度对MergeTree而言是一个非常重要的概念，索引粒度就如同标尺一般，会丈量整个数据的长度，并依照刻度对数据进行标注，最终将数据标记成多个间隔的小段，如图6-7所示：

数据以index_granularity的粒度（默认8192）被标记成多个小的区间，其中每个区间最多8192行数据。MergeTree使用MarkRange表示一个具体的区间，并通过start和end表示其具体的范围。index_granularity的命名虽然取了索引二字，但它不单只作用于一级索引（.idx），同时也会影响数据标记（.mrk）和数据文件（.bin）。因为仅有一级索引自身是无法完成查询工作的，它需要借助数据标记才能定位数据，所以一级索引和数据标记的间隔粒度相同（同为index_granularity行），彼此对齐。而数据文件也会依照index_granularity的间隔粒度生成压缩数据块。