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/ ← 合并后的part2.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_valcurrent_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,...)ENGINEMergeTree()PARTITIONBYtoYYYYMM(EventDate)ORDERBY(CounterID,EventDate)-- ★ 主键排序键SETTINGS index_granularity8192;-- 默认8192行一个granule-- 查询: SELECT * FROM hits WHERE CounterID 123 AND EventDate 2024-01-01-- 执行过程:-- 1) 分区裁剪: 只扫描202401分区-- 2) 主键索引: 二分找到(CounterID123, EventDate2024-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::vectorparts){// 1. 打开所有输入part的列流std::vectorinput_streams;for(constautopart:parts){for(constautocol:columns_to_merge){input_streams.push_back(part-reader-readColumn(col.name));}}// 2. 多路归并(Priority Queue)// 使用heap维护各part当前行在主键上的顺序usingHeapElementstd::pair;// (行数据, part索引)autocmp[](constHeapElementa,constHeapElementb){returncompareRows(a.first,b.first,sort_key)0;// min-heap};std::priority_queue,decltype(cmp)heap(cmp);// 初始化: 每个part的首行入堆for(size_t i0;iinput_streams.size();i){Row rowinput_streams[i]-read();heap.push({row,i});}// 3. 归并写入autooutput_writernew_part-writer();while(!heap.empty()){auto[row,part_idx]heap.top();heap.pop();output_writer-write(row);// 从同一part读下一行if(autonext_rowinput_streams[part_idx]-read()){heap.push({next_row,part_idx});}}// 4. 文件原子替换output_writer-finalize();// 新part的min_blockmin(所有输入part的min_block)// 新part的max_blockmax(所有输入part的max_block)// 命名: minBlock_maxBlock_level}3.2 ReplacingMergeTree-- 去重合并: 相同主键保留最新版本CREATETABLEuser_events(user_id UInt64,event_timeDateTime,event_type String)ENGINEReplacingMergeTree(event_time)-- ★ ver列决定保留哪行ORDERBYuser_id;-- 合并时: 同user_id的行 → 保留event_time最大的-- 注意: 去重仅在Merge时发生(异步!) → 查询可能看到重复-- 解决方案: SELECT ... FINAL → 强制去重(性能差)3.3 SummingMergeTree// 预聚合: Merge时同主键的行→数值列自动SUM// 业务场景: 广告投放 → 按广告主ID日期聚合同一广告的曝光/点击// Merge逻辑(简化):voidSummingMergeTree::mergeData(constBlockleft,constBlockright,Blockresult){// 1. 主键相同 → 数值列累加if(left.getPrimaryKey()right.getPrimaryKey()){resultleft;for(constautocol:numeric_columns){result[col]left[col]right[col];}}else{// 2. 主键不同 → 直接输出resultleft;}}3.4 AggregatingMergeTree-- 支持任意聚合函数(不仅SUM):CREATEMATERIALIZEDVIEWhourly_statsENGINEAggregatingMergeTree()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(inti0;in;i){if(a[i]10)result[i]a[i]b[i]*2;}// 列式向量化:// Step 1: 过滤 → 生成selection maskautomaskcompareGreaterThan(a_column,10);// SIMD: _mm256_cmpgt_epi32// Step 2: 按mask计算autob_mulmultiplyScalar(b_column,2);// SIMD: _mm256_mullo_epi32autoadd_resultadd(a_column,b_mul);// SIMD: _mm256_add_epi32// Step 3: 按mask筛选结果autoresultfilter(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 i0;for(;i32size;i32){// 加载32字节__m256i data_mm256_loadu_si256((__m256i*)(srci));// 判断 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*)(dsti),lower);}// 剩余字节标量处理for(;isize;i){dst[i](src[i]Asrc[i]Z)?src[i]32:src[i];}}// SIMD加速比: 8-12x (32字节并行 vs 1字节)五、分布式查询-- ClickHouse分布式表: 逻辑表 → 分片查询 → 结果合并CREATETABLEevents_distASevents_localENGINEDistributed(cluster_4shards_2replicas,-- 集群名default,-- 数据库events_local,-- 本地表rand()-- 分片键);-- 分布式查询流程:-- SELECT count(), avg(price) FROM events_dist WHERE date 2024-01-01---- 1) 查询被发送到4个分片 → 每个分片执行本地查询-- Shard1: (count1000, sum50000, count_price1000)-- Shard2: (count1200, sum60000, count_price1200)-- ...-- 2) 中间结果回传到发起节点-- 3) 发起节点合并: total_countsum(count), avgsum(sum)/sum(count)-- → 聚合函数必须是可分布式合并的! (sum/count/min/max ✅, median ❌)六、性能基准操作ClickHousePostgreSQL倍数COUNT(*) (10亿行)0.003s120s40000xSUMGROUP BY (10GB)0.8s45s56x点查(索引命中)0.02s0.005s0.25x ⚠️INSERT (1000行)0.01s0.3s30x⚡结论ClickHouse是OLAP王者但OLTP场景不如行存。七、总结ClickHouse高性能三板斧列存编码→ IO减少100xMergeTree稀疏索引→ 无需B树维护向量化JIT→ CPU利用率80%注意事项不适合频繁UPDATE/DELETEJOIN能力弱于MPP数据库。