Vgbhfive's Blog

ClickHouse-MergeTree原理

Posted on Edited on

引入

表引擎是 ClickHouse 设计实现的一大特色，也可以说是表引擎成就了一张表的最终面貌。

创建方式

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

创建 MergeTree 数据表的方式与之前的方式一样，但需要将 ENGINE 声明为 MergeTree()。另外 MergeTree() 表引擎除了常规的配置参数之外，还有独有的配置选项。

1
2
3
4
5
6
7
8
9
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]
[SETTING name=value, ...]

  1. PARTITION BY expr 分区键，用于指定表数据以何种标准进行分区。其中分区键既可以是单个列字段，也可以是通过元组的形式使用多个列字段，同时它也支持使用列表达式，如果不声明分区键则 ClickHouse 会自动生成一个名为 all 的分区。

  2. ORDER BY expr 排序键，用于指定在一个数据片段内，数据以何种方式标准排序。默认情况下主键与排序键相同。

  3. PRIMARY KEY expr 主键，声明后会依靠主键生成一级索引，用于加速表查询。默认情况下，主键与排序键相同，所以通常使用 ORDER BY 代为指定主键。

  4. SAMPLE BY 抽样表达式，用于声明数据以何种标准进行采样。

  5. SETTINGS key=value 设置表引擎参数。

    • index_granulatrity 表示索引粒度，默认值为 8192。
    • index_granulatrity_bytes 表示索引间隔大小，即控制每一批次写入数据的题量大小，默认为 10M，当设置为 0 时表示不启动自适应功能。
    • enabled_mixed_granulatrity_parts 表示是否开启自适应索引间隔的功能，默认开启。
    • merge_with_ttl_timeout 数据 TTL 的功能。
    • storage_policy 多路径存储策略。

存储结构

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

  1. partition 分区目录，余下的各类数据文件都是以分区目录的形式被组织存储的，属于相同分区的数据最终都会被合并到同一个分区目录，而不同分区的数据永远不会被合并。

  2. checksums.txt 校验文件，使用二进制格式存储。它保存了余下各类文件的 size 大小和 size 的哈希值，用于快速校验文件的完整性和正确性。

  3. columns.txt 列信息文件，使用明文格式存储。用于保存此数据分区下的列字段信息。

  4. count.txt 计数文件，使用明文格式存储。用于记录当前数据分区目录下数据的总行数。

  5. primary.txt 一级索引文件，使用二进制格式存储。用于存放稀疏索引，一张 MergeTree 表只能声明一次一级索引。通过一级索引可以在查询数据时排除主键条件范围之外的数据文件，从而有效减少数据扫描范围，加速查询速度。

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

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

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

  9. partition.dat 和 minmax_[Column].idx 若使用了分区键，则会生成 partition.dat 和 minmax 索引文件，均使用二进制格式存储。其中 partition.dat 用于保存当前分区下分区表达式最终生成的值；而 minmax 索引用于记录当前分区下分区字段对应原始数据的最小和最大值。

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

数据分区

在 ClickHouse 中数据分区（partition）和数据分区（shard）是完全不同的概念。数据分区是针对本地数据而言的，是对数据的一种纵向切分，MergeTree 并不能依靠数据分区的特性，将一张表的数据分布到多个 ClickHouse 节点中。而数据分片则是对数据进行横向切分。

分区规则

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

  • 不指定分区键，如果不使用分区键，即不使用 PARTITION BY 声明任何分区表达式，则分区 ID 默认取名为 all，所有的数据都会被写入到这个 all 分区。
  • 使用整数，如果分区键取值属于整形，且无法转换为日期类型，则直接按照该整形的字符串形式输出，作为分区 ID 的取值。
  • 使用日期类型，如果分区键取值属于日期类型，或者能转换为日期类型，则可以按照 YYYYMMDD 格式化后的字符串形式输出，作为分区 ID 的取值。
  • 使用其他类型，如果分区键既不属于整形，也不属于日期类型，则通过 128 位 Hash 算法取其 Hash 值作为分区 ID 的取值。

如果通过元组的形式使用多个分区字段，则分区 ID 依旧是按照上述规则生成，只是多个 ID 之间通过 - 符号依次连接。

分区目录的命名规则

完整分区目录的命名公式所示：PartitionID_MinBlockNum_MaxBlockNum_Level。

  • partitionID 分区 ID。
  • MinBlockNum 和 MaxBlockNum 顾名思义最小数据块编号和最大数据块编号。
  • Level 合并的层级，可以理解为某个分区被合并的次数，或者为这个分区的年龄。

分区目录的合并过程

MergeTree 的分区目录在某种意义上与其他数据库是不同的。
首先，MergeTree 的分区目录并不是在数据表被创建之后就存在的，而是在数据被写入过程中被 创建。即没有数据时分区目录是不存在的。
其次，分区目录在建立之后并不是一成不变的，在其他的数据库中，追加数据后目录自身并不会变化，只是在相同目录下添加数据文件。而 MeregTree 完全不同，在每一批数据写入后都会生成一批新的目录（即便是不同批次属于相同的数据，都会生成不同的分区目录）。而在这之后的某个时刻 ClickHouse 会通过后台任务将属于相同分区的多个目录进行合并成一个新的目录，已经存在的旧分区目录不会被立即删除，而是在这之后的某个时刻通过后台任务被删除。

属于同一个分区的多个目录在合并之后会生成一个新的目录，目录中的索引和数据文件都会被合并。新的目录名称的合并方式遵循以下规则，其中：

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

neo4j-3-2.jpg

分区目录在合并之后，旧分区目录并没有被删除，但旧分区目录的状态却不是激活状态，因此在查询数据时，会被自动过滤。

一级索引

MergeTree 的主键使用 PRIMARY KEY 定义，待主键定义之后 MergeTree 会依据 index_granularity 间隔为数据表生成一级索引并保存至 primary.idx 文件内，索引数据按照 PRIMARY KEY 排序。

稀疏索引

primary.idx 文件内的一级索引采用稀疏索引实现。
neo4j-3-3.jpg

简单来说，在稠密索引中每一行索引标记都会对应一行具体的数据记录，而在稀疏索引中每一行索引标记的是每一段数据，而不是一行。

稀疏索引的优势显而易见，仅需要使用少量的索引标记就能够记录大量数据的区间信息，且数据越大优势越明显。

索引粒度

索引粒度对于 MergeTree 是一个非常重要的 Point，所以很有必要着重说明一下。索引粒度就犹如标尺一样会丈量整个数据的长度，并依照刻度对数据进行标注，最终将数据标记成多个间隔的小段。

数据以 index_granularity 粒度被标记成多个小区间，其中每个区间之间最多间隔 index_granularity 行数据。MergeTree 使用 MarkRange 表示一个具体的区间，并通过 start 和 end 表示具体的范围。
index_granularity 的命名中包含索引，但并不仅作用于一级索引，同时也会影响数据标记 .mrk 和数据文件 .bin，因为仅借助一级索引是无法完成查询的，需要借助数据标记才能定位具体数据。

索引数据的生成规则

由于是稀疏索引所以 MergeTree 需要间隔 index_granularity 行数据才会生成一条索引记录，其索引值会依据声明的主键字段获取。
neo4j-3-4.jpg

A00A8192A16384 在 MergeTree 对于稀疏索引的存储是非常紧凑的，索引值前后相连，按照主键字段顺序紧密的列在一起。

索引的查询过程

前面说过了 MarkRange 是用于在 ClickHouse 中用于定义标记区间的对象。MergeTree 按照 index_granularity 的间隔粒度，将一段完整的数据划分为多个小的间隔数据，一个具体的数据段即一个 MarkRange，与索引编号一一对应，使用 start 和 end 两个属性表示其区间范围，通过 start 和 end 对应的索引编号的取值即能够得到对应的数值区间，而数值区间即此 MarkRange 包含的数据范围。

neo4j-3-5.jpg
索引查询其本质就是两个数值区间的交集判断，其中一个区间是由基于主键的查询条件转换而来的条件区间，而另一个区间则是 MarkRange 对应的数值区间。具体可以分为三个步骤：

  • 生成查询条件区间。将查询条件转换为条件区间，即便是单个值的查询条件也会被转换为区间的形式。
  • 递归交集判断。以递归的形式依次对 MarkRange 的数值区间与条件区间做交集判断。
    假设从最大的区间 [+A000, +inf) 开始：
    • 如果不存在交集，则直接通过剪枝算法优化此段 MarkRange。
    • 如果存在交集，且 MarkRange 步长大于 8 * (end - start) ，则将此区间进一步拆分为八个子区间（由 merge_tree_coarse_index_granularity 指定，默认值为 8），并重复此规则继续做递归交集判断。
    • 如果存在交集，且 MarkRange 不可再分解（步长小于 8），则记录 MarkRange 并返回。
  • 合并 MarkRange 区间。将最终匹配的 MarkRange 聚在一起，合并他们的范围。

neo4j-3-6-1.jpg

二级索引

除了一级索引以外 MergeTree 同样支持二级索引。二级索引又称被为跳数索引，由数据的聚合信息构建而成，根据索引类型的不同，其聚合信息的内容也不同。当然跳数索引的目的也与一级索引一样都是为了帮助查询时减少数据扫描的范围。
跳数索引在默认情况下是关闭的，需要设置 allow_experimental_data_skipping_indices 才能使用：SET allow_experimental_data_skipping_indices = 1。
该参数在新版本中已经被取消。

另外跳数索引需要在 CREATE 语句内定义，支持使用元组和表达式的形式声明，其完整的定义语法如下所示：

1
INDEX index_name expr TYPE index_type(...) GRANULARITY granularity

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

granularity 与 index_granularity 的关系

不同的跳数索引之间除了拥有自身的参数之外，还拥有一个共同的参数就是 granularity。
对于跳数索引而言 index_granularity 定义数据的粒度，而 granularity 定义聚合信息汇总的粒度，即 granularity 定义一行跳数索引能够跳过多少个 index_granularity 区间的数据。

要解释 granularity 的作用，还要从跳数索引的数据生成规则说起，首先按照 index_granularity 粒度间隔将数据划分为 n 段，总共有 [0, n-1] 个区间，接着根据索引定义时声明的表达式，从 0 区间开始，依次按 index_granularity 粒度从数据中获取聚合信息，每次向前移动一步，聚合信息逐步累加，最后当移动 granularity 次区间时，则汇总并生成一行跳数索引数据。
neo4j-3-7.png

跳数索引的类型

MergeTree 支持四种跳数索引，分别是 minmax、 set、 ngrambf_v1 和 tokenbf_v1。

  • minmax：记录了一段数据内的最小和最大值，其索引的作用类似分区目录的 minmax 索引，能够快速跳过无用的数据区间。 
    1
    INDEX a ID TYPE minmax GRANULARITY 5
  • set：直接记录了声明字段或表达式的取值（唯一值，无重复），其完整形式为 set(max_rows)，其中 max_rows 是一个阈值，表示在一个 index_granularity 内，索引最多记录的数据行数。 
    1
    INDEX b (length(ID) * 8) TYPE set(256) GRANULARITY 5
  • ngrambf_v1：记录的是数据短语的布隆表过滤器，只支持 String 和 FixedString 数据类型，ngrambf_v1 只能够提升 in、 notIn、 like、 equals 和 notEquals 查询的性能，其完整形式为 ngrambf_v1(n, size_of_bloom_filter_in_bytes, number_of_hash_functions, random_seed)。 
    1
    INDEX c (ID, Code) TYPE ngrambf_v1(3, 256, 2, 0) GRANULARITY 5
  • tokenbf_v1：是 ngrambf_v1 的变种，同样是一种布隆过滤器索引，tokenbf_v1 除了短语 token 的处理方法外，其他与 ngrambf_v1 是完全一样的，tokenbf_v1 会自动按照非字符的、数字的字符串分割 token。 
    1
    INDEX d ID TYPE tokenbf_v1(256, 2, 0) GRANULARITY 5

一张表支持声明多个跳数索引。

数据存储

前面短暂提过在 MergeTree 中数据是按照列存储的，那么具体的存储细节、MergeTree 如何工作接下来就会说明。

各列独立存储

在 MergeTree 中，数据按列存储，而具体到每个列字段，数据也是独立存储的，每个列字段都有对应的 .bin 数据文件，承载着数据的物理存储。数据文件以分区目录的形式被存储，所以 .bin 数据文件只会保存当前分区片段内的这一部分数据。
按列独立存储的优势：

  • 更好地进行数据压缩（相同类型地数据放在一起，对压缩更友好）。
  • 最小化数据扫描的范围。

MergeTree 并不是一股脑地将数据写入 .bin 数据文件，首先数据是经过压缩的，目前支持 LZ4、 ZSTD、 Multiple 和 Delta 几种算法，默认使用 LZ4 算法；其次数据会按照 ORDER BY 的声明排序；最后数据以压缩数据块的形式被组织写入 .bin 数据文件。

压缩数据块

一个压缩数据块由头信息和压缩数据两部分组成，头信息固定使用 9 位字节组成，具体由 1 个 UInt8 （1 字节）整形和 2 个 UInt32 （4 字节）整形组成，分别代表使用的用压缩算法类型、压缩后的数据大小和压缩前的数据大小。

.bin 压缩文件是由多个压缩数据块组成的，而每个压缩数据块的头信息则基于 CompressionMethod_CompressedSize_UncompressedSize 公式生成的。
每个压缩数据块的体积按照其压缩前的数据字节大小被阉割控制在 64KB ~ 1MB，其上下限分别由 min_compress_block_size （默认 65536）和 max_compress_block_size （默认 1048576）参数指定。而一个压缩数据块的大小则是由 index_granularity 内数据的实际大小相关。

MergeTree 在数据具体的写入过程中，会依照索引粒度（默认 8192），按批次获取数据并进行处理。如果把一批数据的未压缩大小设为 size，则整个写入过程遵循以下规则：

  • 单个批次数据 size < 64KB：如果单个批次数据小于 64KB，则继续获取下一批次数据直到大于 64KB，然后生成一个数据压缩块。
  • 单个批次数据 64KB <= size <= 1MB：如果单个批次数据大小刚好在 64KB 和 1MB 之间，则可以直接生成下一个数据压缩块。
  • 单个批次数据 size > 1MB：如果单个批次数据大于 1MB，则会截断 1MB 大小数据并生成一个压缩数据块，剩余数据继续依据上述规则执行。
    neo4j-3-8.png

在 .bin 文件中引入压缩数据块的目的有以下两个：

  • 虽然数据被压缩后能够有效减少数据大小，降低存储空间并加属数据传输效率，但数据的压缩和解压动作，其本身也会带来额外的性能损耗。所以需要控制被压缩数据的大小，以求在性能损耗和压缩率之间寻求平衡。
  • 在具体读取某一列数据时，首先需要将压缩数据加载到内存并解压，这样才能后续处理。通过压缩数据块，可以在步读取整个 .bin 文件的情况下将读取粒度降低到压缩数据块级别，从而缩小数据读取的范围。

数据标记

如果把 MergeTree 比作一本书，那么 primary.idx 一级索引就是这本书的目录，.bin 文件就是书中的内容，而 .mrk 文件则是一级章节目录和具体内容之间的关联。
主要记录以下两点重要信息：

  • 一级章节对应的页码信息。
  • 一段文字内容在某一页中的起始位置信息。

数据标记的生成规则

数据标记作为衔接一级索引与数据之间的桥梁，类似于书签，且书中的每一个章节都有自己的书签。
neo4j-3-9.png

在上述中可以发现数据标记的首个特征即数据标记和索引区间是对齐的，均按照 index_granularity 的粒度间隔，如此一来只需简单通过索引区间的下标编号即可找到对应的数据标记。
为了能够与数据衔接，数据标记文件也与 .bin 文件一一对应，即每一个列字段 [Column].bin 文件都有一个与之对应的 [Column].mrk 数据标记文件，用于记录数据在 .bin 文件中的偏移量信息。
一行标记数据使用一个元组表示，元组内包含两个整形数值的偏移量信息，他们分别表示在此段数据区间内，在对应的 .bin 压缩文件中压缩数据块的起始偏移量；以及将该数据压缩块解压后，其未压缩数据的起始偏移量。

每一行标记数据都表示一个片段的数据在 .bin 压缩文件中的位置信息。标记数据与一级索引数据不同，并不能常驻内存，而是使用 LRU 缓存策略加快其取用速度。

数据标记的工作方式

MergeTree 在读取数据时必须通过标记数据的位置信息才能找到所需要的数据，整个查找过程大致可以分为读取压缩数据块和读取数据两个步骤。

  • 读取压缩数据块，在查询某一列数据时，MergeTree 无需一次性加载全部 .bin 文件，而是可以根据需要，只加载特定的压缩数据块。
  • 读取数据，在读取解压后的数据时，MergeTree 并不需要一次性扫描全部解压数据，而是可以根据需要以 index_granularity 的粒度加载特定的一小段，而为了实现这一特性需要借助标记文件中保存的解压数据块中的偏移量。

协同总结

在说明上述的特性后，下面按照写入过程、查询过程以及数据标记和压缩数据块的三种对应关系的角度来说一说。

写入过程

数据写入的第一步就是生成分区目录，伴随着每一批数据的写入，都会生成一个新的分区目录。而在后续的某一时刻，属于相同分区的目录会按照规则继续合并。接下来会按照 index_granularity 索引粒度，会分别生成 primary.idx 一级索引、列字段 .mrk 数据标记和 .bin 数据压缩文件。
其中索引与标记都是一一对应的，而标记与数据压缩块则是根据区间数据的大小会生成多对一、一对一、一对多三种关系。

查询过程

数据查询的本质就是一个不断缩小数据范围的过程，在理想的情况下，MergeTree 借助分区索引、一级索引、二级索引，将数据扫描到最小，然后借助数据标记，将需要解压与计算的数据范围缩至最小。
当然最坏的情况就是查询语句没有匹配到任何的索引，那么在后续的数据扫描中，会扫描所有的分区目录，以及目录内索引段的最大区间，当然在此虽然不能减少数据扫描范围，不过以及可以借助数据标记，同时以多线程的方式同时读取多个压缩块以提升性能。

数据标记与压缩数据块之间对应关系

由于数据压缩块的划分与一个间隔 index_granularity 内的数据大小有关，每个数据压缩块的体积被限制在 64KB~1MB 之间，同时一个间隔内的数据又只会产生一行数据标记，那么根据一个间隔内的数据的实际字节大小，数据标记和压缩数据块之间产生了不同的三种关系。

  • 多对一，即多个数据标记对应一个数据压缩块。当一个间隔内的数据未压缩大小小于 64KB，则会出现这种情况。
  • 一对一，即一个数据标记对应一个数据压缩块。当一个间隔内的数据未压缩大小刚好大于等于 64KB 且小于 1MB，则会出现这种情况。
  • 一对多，即一个数据标记对应多个数据压缩块。当一个间隔内的数据未压缩大小直接大于 1MB，则会出现这种情况。

引用

个人备注

此博客内容均为作者学习所做笔记，侵删！
若转作其他用途，请注明来源！