ClickHouse列式存储引擎：MergeTree系列与向量化执行深度解析-育师

ClickHouse列式存储引擎：MergeTree系列与向量化执行深度解析

一、引言

ClickHouse是Yandex开源的列式分析型数据库，单表查询可达每秒数十亿行。其核心优势来自三大技术支柱：列式存储+压缩（IO减少10-100x）、MergeTree引擎族（稀疏索引+后台Merge）、向量化执行（SIMD + JIT编译）。

本文将深入这三者的源码级实现：从列存编码格式到MergeTree合并算法，再到LLVM JIT向量化表达式执行。

二、列式存储格式

2.1 列存物理布局

-- 行存 (MySQL/PostgreSQL): -- [id,name,age,id,name,age,id,name,age...] → 一行所有列连续存储 -- 查询SELECT age: 需要读取所有列! -- 列存 (ClickHouse): -- id.bin: [1, 2, 3, 4, ...] -- name.bin: ["Alice", "Bob", ...] -- age.bin: [25, 30, 22, ...] -- 查询SELECT age: 只读age.bin → IO降低N倍 -- ClickHouse MergeTree目录结构: -- /var/lib/clickhouse/data/db/table/ -- ├── 20240101_0_100_0/ ← part目录 -- │ ├── id.bin ← 列数据 -- │ ├── id.mrk2 ← 标记文件(稀疏索引→数据位置) -- │ ├── name.bin -- │ ├── name.mrk2 -- │ ├── primary.idx ← 主键索引(稀疏) -- │ ├── checksums.txt -- │ └── columns.txt -- └── 20240101_101_200_1/ ← 合并后的part

2.2 编码压缩算法

// ClickHouse压缩管线: 列数据 → 编码 → 通用压缩// 1. Delta编码 (时间序列专用)// 原始: [100, 101, 103, 106, 110]// Delta: [100, 1, 2, 3, 4] ← 更小的值，更好的压缩率// 2. DoubleDelta编码 (均匀变化序列)// Delta: [100, 1, 2, 3, 4]// DDelta: [100, 1, 1, 1, 1] ← 更极端的压缩// 3. Gorilla编码 (浮点数时间序列, Facebook开源)// 浮点数的IEEE754位表示: 前后异或 → 前面连续0越多压缩越好uint64_txor_val=current_bits^prev_bits;intleading_zeros=__builtin_clzll(xor_val);inttrailing_zeros=__builtin_ctzll(xor_val);// 4. 字典编码 (低基数列)// 原始: ["CN","CN","US","CN","JP","US"]// 字典: ["CN"→0, "US"→1, "JP"→2]// 编码: [0, 0, 1, 0, 2, 1] ← 用整数替代字符串// 压缩后: Run-Length Encoding → [CN×2, US×1, CN×1, JP×1, US×1]// 5. LZ4/ZSTD通用压缩 (默认LZ4)// ClickHouse压缩块大小: 64KB-1MB// 查询时按需解压(只解压查询列+Granule级别)

2.3 稀疏索引(Granule)

-- MergeTree稀疏索引核心概念:-- 1) 数据按主键排序-- 2) 每8192行(=index_granularity)取一个标记(mark)-- 3) 查询时: 二分主键索引→定位granule→顺序扫描granule内数据CREATETABLEhits(CounterID UInt32,EventDateDate,UserID UInt64,...)ENGINE=MergeTree()PARTITIONBYtoYYYYMM(EventDate)ORDERBY(CounterID,EventDate)-- ★ 主键=排序键SETTINGS index_granularity=8192;-- 默认8192行一个granule-- 查询: SELECT * FROM hits WHERE CounterID = 123 AND EventDate = '2024-01-01'-- 执行过程:-- 1) 分区裁剪: 只扫描202401分区-- 2) 主键索引: 二分找到(CounterID=123, EventDate='2024-01-01')对应的granule-- 3) 读取mark文件: 定位该granule在.bin文件中的偏移-- 4) 解压该granule并扫描8192行-- 5) 只读取涉及列(CounterID, EventDate, UserID...)

三、MergeTree引擎族

3.1 MergeTree核心Merge算法

// ClickHouse后台Merge: 多个小part → 一个大part// 触发条件: active_parts > parts_to_delay_insert(默认150)// Merge算法: 多路归并排序std::vectorMergeTreeDataMerger::mergeParts(conststd::vector&parts){// 1. 打开所有输入part的列流std::vector>input_streams;for(constauto&part:parts){for(constauto&col:columns_to_merge){input_streams.push_back(part->reader->readColumn(col.name));}}// 2. 多路归并(Priority Queue)// 使用heap维护各part当前行在主键上的顺序usingHeapElement=std::pair;// (行数据, part索引)autocmp=[&](constHeapElement&a,constHeapElement&b){returncompareRows(a.first,b.first,sort_key)>0;// min-heap};std::priority_queue,decltype(cmp)>heap(cmp);// 初始化: 每个part的首行入堆for(size_t i=0;i<input_streams.size();++i){Row row=input_streams[i]->read();heap.push({row,i});}// 3. 归并写入autooutput_writer=new_part->writer();while(!heap.empty()){auto[row,part_idx]=heap.top();heap.pop();output_writer->write(row);// 从同一part读下一行if(autonext_row=input_streams[part_idx]->read()){heap.push({next_row,part_idx});}}// 4. 文件原子替换output_writer->finalize();// 新part的min_block=min(所有输入part的min_block)// 新part的max_block=max(所有输入part的max_block)// 命名: minBlock_maxBlock_level}

3.2 ReplacingMergeTree

-- 去重合并: 相同主键保留最新版本CREATETABLEuser_events(user_id UInt64,event_timeDateTime,event_type String)ENGINE=ReplacingMergeTree(event_time)-- ★ ver列决定保留哪行ORDERBYuser_id;-- 合并时: 同user_id的行 → 保留event_time最大的-- 注意: 去重仅在Merge时发生(异步!) → 查询可能看到重复-- 解决方案: SELECT ... FINAL → 强制去重(性能差)

3.3 SummingMergeTree

// 预聚合: Merge时同主键的行→数值列自动SUM// 业务场景: 广告投放 → 按广告主ID+日期聚合同一广告的曝光/点击// Merge逻辑(简化):voidSummingMergeTree::mergeData(constBlock&left,constBlock&right,Block&result){// 1. 主键相同 → 数值列累加if(left.getPrimaryKey()==right.getPrimaryKey()){result=left;for(constauto&col:numeric_columns){result[col]=left[col]+right[col];}}else{// 2. 主键不同 → 直接输出result=left;}}

3.4 AggregatingMergeTree

-- 支持任意聚合函数(不仅SUM):CREATEMATERIALIZEDVIEWhourly_statsENGINE=AggregatingMergeTree()ORDERBY(hour,ad_id)ASSELECTtoStartOfHour(event_time)ashour,ad_id,sumState(impressions)asimpressions,-- ★ 中间状态avgState(ctr)asctr,-- 不存储原始值uniqState(user_id)asunique_usersFROMraw_eventsGROUPBYhour,ad_id;-- 查询时使用Merge后缀:SELECThour,ad_id,sumMerge(impressions),-- 合并中间状态avgMerge(ctr)FROMhourly_statsGROUPBYhour,ad_id;

四、向量化执行引擎

4.1 列式处理 vs 行式处理

// 行式处理 (MySQL/PG): Volcano迭代器模型// for each row:// for each operator:// process(row) // 每次只处理一行 → CPU分支预测失败 + 虚函数开销// 列式处理 (ClickHouse): 向量化// for each block(8192 rows):// for each operator:// process(column[]) // 一次处理一列 → SIMD友好 + 无虚函数// 示例: SELECT a + b * 2 FROM t WHERE a > 10// 行式:for(inti=0;i<n;i++){if(a[i]>10)result[i]=a[i]+b[i]*2;}// 列式向量化:// Step 1: 过滤 → 生成selection maskautomask=compareGreaterThan(a_column,10);// SIMD: _mm256_cmpgt_epi32// Step 2: 按mask计算autob_mul=multiplyScalar(b_column,2);// SIMD: _mm256_mullo_epi32autoadd_result=add(a_column,b_mul);// SIMD: _mm256_add_epi32// Step 3: 按mask筛选结果autoresult=filter(add_result,mask);

4.2 JIT编译表达式

// ClickHouse使用LLVM JIT将表达式编译为机器码// 传统解释执行: 每个操作都是虚函数调用// JIT: 编译为一条紧致的内联函数// SQL: SELECT (a + b) * c / (d - e)//// 解释执行(慢):// result = divide(// multiply(add(a, b), c),// subtract(d, e)// ); // 4次虚函数调用 + 中间结果物化//// JIT编译后(快):// for (size_t i = 0; i < size; i++)// result[i] = (a[i] + b[i]) * c[i] / (d[i] - e[i]);// // 单循环、无函数调用、缓存友好// JIT编译配置:// SET compile_expressions = 1; -- 启用JIT// SET min_count_to_compile_expression = 3; -- 相同表达式出现3次才编译// JIT vs 向量化 选择:// • 表达式简单(1-3 ops) → 向量化已经够快// • 表达式复杂(5+ ops) → JIT编译收益大(消除中间物化)// • 常量折叠 → 两者都做，JIT可把const_expr编译为立即数

4.3 SIMD实战

#include// AVX2// ClickHouse中字符串大小写转换的SIMD实现:voidlowerUTF8_avx2(constuint8_t*src,uint8_t*dst,size_t size){const__m256i A=_mm256_set1_epi8('A');const__m256i Z=_mm256_set1_epi8('Z');const__m256i diff=_mm256_set1_epi8('a'-'A');// 32size_t i=0;for(;i+32<=size;i+=32){// 加载32字节__m256i data=_mm256_loadu_si256((__m256i*)(src+i));// 判断 'A' <= c <= 'Z'__m256i ge_A=_mm256_cmpgt_epi8(data,_mm256_sub_epi8(A,_mm256_set1_epi8(1)));__m256i le_Z=_mm256_cmpgt_epi8(_mm256_add_epi8(Z,_mm256_set1_epi8(1)),data);__m256i mask=_mm256_and_si256(ge_A,le_Z);// 大写字母 + 32__m256i lower=_mm256_add_epi8(data,_mm256_and_si256(mask,diff));_mm256_storeu_si256((__m256i*)(dst+i),lower);}// 剩余字节标量处理for(;i<size;i++){dst[i]=(src[i]>='A'&&src[i]<='Z')?src[i]+32:src[i];}}// SIMD加速比: 8-12x (32字节并行 vs 1字节)

五、分布式查询

-- ClickHouse分布式表: 逻辑表 → 分片查询 → 结果合并CREATETABLEevents_distASevents_localENGINE=Distributed(cluster_4shards_2replicas,-- 集群名default,-- 数据库events_local,-- 本地表rand()-- 分片键);-- 分布式查询流程:-- SELECT count(), avg(price) FROM events_dist WHERE date = '2024-01-01'---- 1) 查询被发送到4个分片 → 每个分片执行本地查询-- Shard1: (count=1000, sum=50000, count_price=1000)-- Shard2: (count=1200, sum=60000, count_price=1200)-- ...-- 2) 中间结果回传到发起节点-- 3) 发起节点合并: total_count=sum(count), avg=sum(sum)/sum(count)-- → 聚合函数必须是可分布式合并的! (sum/count/min/max ✅, median ❌)