ClickHouse源码阅读计划(一) - Everything About MergeTree
问题导读：1、MergeTree是什么?用来解决什么问题?
2、MergeTree有哪些文件?
3、MergeTree的这些文件分别包含了什么?交互关系是?
4、MergeTree如何利用这些索引来进行读取加速?
本文基于社区版本21.4分析
研究一个数据库系统,不妨从存储引擎这个基石开始谈起,基本上每一次Query的执行都离不开把数据从磁盘中读取出来或者是写入的过程.只有了解了存储引擎中数据如何布局,然后才能更好地了解其读写机制.参考bohuTang介绍MergeTree的文章,我们将要解决以下问题:
1.MergeTree是什么?用来解决什么问题?
2.MergeTree有哪些文件?
3.MergeTree的这些文件分别包含了什么?交互关系是?
4.MergeTree有什么类型的索引?
5.MergeTree如何利用这些索引来进行读取加速?
[*] From LSM-Tree to MergeTree
其实MergeTree和LSM-Tree思想很像,我们不妨想下LSM Tree核心思想就是在数据落盘的时候把数据进行MergeSort排成有序SST文件,然后后台不断Merge成更大的SST文件(Merge策略有Level/Size-Tired两种).而LSM-Tree通过攒批把原本通过随机IO落盘的数据写入内存中,然后最后通过顺序IO flush到磁盘上,写入效率是远比随机IO要高得多的.
而MergeTree一开始设计的时候是没有WAL和MemTable机制的,正如官方文档所言
MergeTree is not an LSM tree because it doesn’t contain “memtable” and “log”: inserted data is written directly to the filesystem. This makes it suitable only to INSERT data in batches, not by individual row and not very frequently – about once per second is ok, but a thousand times a second is not. We did it this way for simplicity’s sake, and because we are already inserting data in batches in our applications.
不过从20.6开始已经默认采用了WAL机制了(MergeTreeWriteAheadLog.h),而WAL是LSM tree用来避免MemTable在机器宕机的时候数据丢失的,换句话说其实现在的Clickhouse也有MemTable的概念,只不过换了个名字叫In-Memory dataparts罢了.所以其实MergeTree发展过程中越来越像LSM-Tree.之后会在代码阅读部分仔细介绍写入的细节.
然后我们不妨思考,为什么存储数据要把数据有序排序呢?会给存储带来什么好处?参考资料就从存储效率和查询效率说明了2点:
1.列存文件按照block进行压缩存储,相邻数据往往相同或者按照一定顺序排列.而且根据信息论,数据越相似,信息熵越少,压缩所占的时空间都会减少.这也使得很多压缩算法的使用更为高效,压缩算法同样是阅读源码的一个细节,日后会详细介绍.
2.相邻有序的数据也有利于索引的查找加速.例如通过等值条件或者range条件能够快速定位所查数据在存储文件中的区间.
[*] MergeTree的文件组织
我们用docker搭个单节点,建一张表看看情况:
sudo docker run -d --name some-clickhouse-server --ulimit nofile=262144:262144 yandex/clickhouse-server
sudo docker run -it --rm --link some-clickhouse-server:clickhouse-server yandex/clickhouse-client --host clickhouse-server
CREATE TABLE default.test
(
`a` Int32,
`b` Int32,
`c` Int32,
INDEX idx_c c TYPE minmax GRANULARITY 1
)
ENGINE = MergeTree
PARTITION BY a
ORDER BY b
SETTINGS index_granularity = 3
insert into default.test(a,b,c) values(10,10,10);
insert into default.test(a,b,c) values(5,1,1),(5,2,2);
insert into default.test(a,b,c) values(3,10,4),(3,9,5),(3,1,2);
insert into default.test(a,b,c) values(20,20,20);
我们在data这个表的目录下可以看到有以下几个文件夹:
如10_1_1_0其实就是一个datapart,每个datapart本质上对应磁盘上的一个目录，而且一旦datapart落盘后就是不可变的了,里面的文件不能再修改.
而细心的读者可能会发现,我们进行了四次插入操作,而恰好生成了四个datapart.也就是说每一次插入数据都会生成一个新的datapart. 但笔者发现如果一次插入操作插入了若干条分区键不同的数据,如插入了4条分区键不同的数值,会同时生成4个datapart.因此更准确的理解为每一次插入数据至少生成一个新的datapart,生成的数量取决于插入数据的分区键的数量.
Clickhouse官方推荐1s1次写入,那如果是1s1000次写入那可就万万不行了,因为频繁小批量的写入会短时间内迅速创建很多的datapart目录,迅速耗尽文件系统的inode数目.而后台的merge线程又来不及把小的datapart合并成大的datapart(默认一次compaction的间隔大概为10-15min),而且如果对lsm-tree比较熟悉的朋友也许也会知道后台频繁的merge线程其实会造成比较严重的性能抖动(主要是磁盘IO的cost).
那datapart目录这四个数字又分别表示什么含义呢? 以10_1_1_0为例
[*]10表示分区key的值,本表使用a列作为分区键,日常生产会使用日期函数来作为分区键
[*]1表示存储这个datapart的数据的block的最小值
[*]1表示存储这个datapart的数据的block的最大值
[*]0表示MergeTree的深度,大约可以理解为datapart进行mutation的次数
这里引出ClickHouse两个重要概念:
[*] datapart
每个datapart存储着压缩后的数据文件，元数据文件和各种索引文件，校验和文件等。datapart其实在磁盘上有两种存储方式:一种是MergeTreeDataPartCompact,另一种是MergeTreeDataPartWide.所有写入的数据先写入到内存中的MergeTreeDataPartInMemory中，你可以理解为ClickHouse的MemTable，当In Memory DataPart积攒到一定大小就会flush到磁盘生成compact或者wide形式的datapart。
Compact方式
所有的列数据单独存储在一个文件data.bin中,所有索引文件也存储在一个data.mrk3文件中.这种compact存储方式用于存储大小不足10M的小datapart. 可用于优化频繁的小批量写操作，并且只有开启了自适应性granularity功能的MergeTree Table才支持Compact方式的存储.而随着数据增加，最终在mutation之后还是会以Wide方式来存储datapart.
Wide方式
每一个列都会有单独的mrk3文件和若干个.bin文件来分别存储其元数据和压缩后的数据文件. 当未压缩的数据的大小或者行数分别超过`min_bytes_for_wide_part` 或者`min_rows_for_wide_part`就会采用Wide方式来存储.
[*] partition
ck会通过建表时指定的分区键(PARTITION BY expr)将写入的数据划分到不同的partition中,partition可以理解为逻辑分区,datapart理解为物理分区,若干个分区键相同的datapart组成一个相同的partition.
而且MergeTree的Merge操作只发生在拥有相同分区键的datapart中,因此官方文档建议不要将分区的粒度不要太细,避免生成过多的partition文件,在读写查询的时候要对大量的文件进行读写,在进程中维护大量的文件描述符,影响性能.
接下来我们看一下每个datapart的具体文件组织：
[*].bin 列存文件,数据以列式组织并且以block为单位压缩后存储在该文件中,并且数据会按照主键进行排列. 很明显这里的datapart是以compact形式存储的，所有列数据都只存储在一个.bin文件上.
[*].mrk 元数据文件，若是非自适应性的Graunle会生成.mrk文件，若是Wide形式的datapart会生成.mrk2文件，若是Compact形式的datapart则会生成.mrk3文件。我们需要搞懂两个问题：这个文件存储着什么东西？以及Ck如何通过该文件进行数据快速定位？为了搞懂这两个问题，首先我们又要弄清楚两个CK重要的概念:
Granule
我们知道数据以列存形式组织，那么即使是读取一行数据也要把整个.bin文件加载到内存，那么这样是很消耗IO的，那CK是如何在存储引擎来解决IO读放大问题呢？
ClickHouse引入了颗粒度这个概念。每个data part都会被逻辑划分为若干个Granules，Granule作为CK在内存中进行数据扫描的单位。写入数据会根据index_granularity或者index_granularity_bytes 参数来积攒成一个Granule，默认是8192行一个Granule ，当若干个Granule在内存的buffer中又积攒到一定量（min_compress_block_size 默认64KB）的时候就会触发数据压缩和落盘操作而生成一个Block。每个Granule会对应.mrk文件中的一个mrk。
Block
Block作为CK进行磁盘IO的基本单位和文件压缩/解压缩的基本单位。每一个Block都有若干个Granules。在CK的代码内我们也可以看到许多以Block为单位的字节流接口，说明数据在读写字节流中都是以Block为单位进行传输的。block的大小范围取决于max_compress_block_size和min_compress_block_size,每个block的文件头都会保存该block压缩前后大小，用于数据校验。
这里顺便介绍一下header:在CompressionInfo.h头文件中我们可以看到其内存布局
/** The compressed block format is as follows:
*
* The first 16 bytes are the checksum from all other bytes of the block. Now only CityHash128 is used.
* In the future, you can provide other checksums, although it will not be possible to make them different in size.
*
* The next byte specifies the compression algorithm. Then everything depends on the algorithm.
*
* 0x82 - LZ4 or LZ4HC (they have the same format).
* Next 4 bytes - the size of the compressed data, taking into account the header; 4 bytes is the size of the uncompressed data.
*
* NOTE: Why is 0x82?
* Originally only QuickLZ was used. Then LZ4 was added.
* The high bit is set to distinguish from QuickLZ, and the second bit is set for compatibility,
*for the functions qlz_size_compressed, qlz_size_decompressed to work.
* Although now such compatibility is no longer relevant.
*
* 0x90 - ZSTD
*
* All sizes are little endian.
*/
16bytes用于存储校验和
1byte用于标记采用的压缩算法
两个4byte用来存储压缩前后大小
到这里我们就能回答我们刚才提出的两个问题：
1.mrk文件存储着若干个mrk,每个mrk对应一个Granule,分记录着Granule所在的block在压缩文件.bin的偏移量，Granule在block压缩后的偏移量，还记录着每一个Graunle的行数，分别占8个bytes，即一个mark占24个bytes。
2.有了.mrk文件，CK即使是读取一行数据，也不需要把整个.bin文件加载到内存，只需要通过.mrk文件快速定位所查询数据所在的Granule，首先根据该Granule所在的block在.bin文件中的偏移量把block找出来，然后解压，解压之后有根据.mrk中记录的该Granule在解压后的block的偏移量把该Granule找出来。然后就在这个Granule中对我们所要查找的数据进行读取和校验。
一句话总结：.mrk文件存储着mark到granule的映射
那新的问题来了，我们怎么知道我们要查的数据对应.mrk文件的哪个mark？接下来就介绍几个索引文件，看看稀疏索引是如何在CK中加速数据查询的。
[*] primary.idx
存储着该datapart的主键索引，但注意的是ClickHouse的主键索引并没有主键去重的功能能。它记录的是每一个Granule第一行的主键值（通常是最小值），而我们知道block内的列存数据是严格按照建表的时候指定的主键排序的，因此主键索引的目录项同样也是顺序排列的，每个目录项都对应一个mark。所以其实primary.idx所占大小通常很小，可以常驻内存加快查询效率。总的来看，主键索引是一种稀疏索引，可以快速通过二分查找法找到所要读取数据所在的Granule区间，进而间接减少了读取磁盘文件的IO，提高查询性能。
假如你所要查找数据primary key=5,可以通过二分查找内存中的primary.idx,快速定位数据所在的Granule区间,就不需要对列存文件进行全局扫描了.
一句话总结：primary.idx文件存储着查询数据到mark的映射
而结合.mrk文件，我们就完成了从查询数据到数据所在的block所在的映射,通过稀疏索引迅速过滤所需要读取的block,并以mark作为读取数据和granule的媒介,快速定位数据所在的granule.
[*] minmax_{colume}.idx
存储着整个分区键的min/max,用于分区裁剪,直接过滤掉不符合条件的data part,一定程度上舒缓了LSM-Tree的Range Query的读放大问题.
[*] skp_idx_{colume}.idx (skipping index)
INDEX index_name expr TYPE type(...) GRANULARITY granularity_value
其中granularity参数用于指定有多少个Graunle聚合生成索引信息
skipping index与primary index功能相似,同样作为稀疏索引,用于加快找出寻找数据所在的Block和Granule.一共有以下种类:
[*] minmax
以index granularity为单位，存储指定表达式计算后的min、max值；在等值和范围查询中能够帮助快速跳过不满足要求的块，减少IO。
下图表示为Index granularity=1时的布局，每个minmax目录项分别记录一个颗粒的min max值，可用于query快速定位数据是否存在于哪个block中,同样可以舒缓range query的读放大问题.
[*] set(max_rows)
目录项存储着若干个granule聚合,去重后的集合,适用于重复度较高的数据，可用于等值查询快速判断是否命中该值。
[*] bloom_filter()
为某列数据设置Bloom_filter,用于快速确定查询值是否存在于若干granule聚合后的颗粒中，用于equals,like,in等查询的优化
<div>ngrambf_v1(n, size_of_bloom_filter_in_bytes, number_of_hash_functions, random_seed)
</div><div>tokenbf_v1(size_of_bloom_filter_in_bytes, number_of_hash_functions, random_seed) </div>
这两个索引用于字符串equals,like,in的优化,同样利用bloom_filter来对字符进行快速判断是否存在。
最后简要介绍datapart其他文件:
[*] partition.dat
分区表达式的值
[*] columns.txt
每个列的字段
[*] count.txt
当前分区下数据的总行数
[*] checksums.txt
目录下每个文件的size以及哈希值，用于attach等操作时候校验
[*] default_compression_codec.txt
记录保存block采取的压缩算法
到这里，我们就能回答文章开头的几个问题了。我们介绍了MergeTree的文件组织后，接下来又介绍一下MergeTree的几个变种以及从代码角度介绍一下Mutation等行为的细节.
作者：DamonChiu
来源：https://zhuanlan.zhihu.com/p/366735514
最新经典文章，欢迎关注公众号http://www.aboutyun.com/data/attachment/forum/201903/18/215536lzpn7n3u7m7u90vm.jpg
感谢分享
页:
[1]