【列存引擎内核】Merge 与 Mutation

Insert 只 追加 Part；后台 merge 把多个小 Part 归并为更大 Part——列存的「心脏手术」，类比 LSM Compaction。Mutation 则异步重写 Part 实现 UPDATE/DELETE，堆积会拖垮集群。

一、为何需要 Merge

flowchart LR
  P1[Part 小] --> M[Merge]
  P2[Part 小] --> M
  M --> P3[Part 大]

二、Merge 触发与 selector

MergeTreeBackgroundExecutor 调度任务；selector 根据 Part 大小、level、分区挑选可 merge 组合（SimpleMergeSelector 等）。

Settings：max_bytes_to_merge_at_max_space_in_pool、merge_max_block_size、number_of_free_entries_in_pool_to_execute_merge。

观察（本机）：

SELECT * FROM system.merges;
SELECT database, table, sum(1) FROM system.parts WHERE active GROUP BY database, table;

不伪造 system.merges 行。

三、Merge 做什么

对同分区、排序键兼容的 Part 多路归并（与 LSM 归并相似）：

• 输出新 Part，旧 Part Outdated
• 重新压缩、可应用新 CODEC
• Replacing/Summing 等引擎在归并时应用语义

源码：MergeTreeDataMergerMutator.cpp。

四、ReplacingMergeTree

CREATE TABLE r (
  id UInt64,
  v String,
  ver UInt64
) ENGINE = ReplacingMergeTree(ver)
ORDER BY id;

Merge 同 id 保留 ver 最大行。查询可能见重复，除非 FINAL（有性能成本）。

五、CollapsingMergeTree

Sign Int8：+1 插入，-1 撤销；merge 折叠。适合变更流。

六、Mutation

ALTER TABLE UPDATE v = ... WHERE ... → 队列 → 读旧 Part 写新 Part。

危害：

• 与 merge 争线程
• 磁盘写放大
• system.mutations 堆积

生产尽量避免大范围 mutation；用 Replacing 或重建表替代。

stateDiagram-v2
  [*] --> Queued: ALTER UPDATE
  Queued --> Executing: background
  Executing --> Done: 新 Part 替换
  Executing --> Failed: 磁盘/超时

七、TTL

TTL 规则在 merge 时删除/移动过期 granule，依赖 merge 运行。

八、学术谱系：RS Merge · LSM Compaction · Mutation

争论：用 merge 消化变更（类 LSM / RS）vs 原地更新（行存）。列存选前者换 scan；代价是 parts 过多、mutation 堆积（第 15 篇）。

8.1 工程间隙

8.2 开放问题

1. Mutation 是否应默认禁止于大表？ 可检验：同等更新用 Collapsing/Replacing ingest vs ALTER UPDATE 的 parts 与合并时长。
2. Merge 与查询的 CPU/IO 隔离——多租户下仍是生产痛点；论文实验少覆盖。

九、小结

Merge = 归并 Part、控制读放大、实现引擎语义；Mutation = 重写 Part、应慎用。

上一篇：查询读取路径

下一篇：索引与跳数索引

参考资料

核心论文

1. Stonebraker et al., C-Store, VLDB 2005（RS 归并直觉；A 级）。
2. O’Neil et al., The Log-Structured Merge-Tree, Acta Informatica 1996（compaction 对照；A 级）。

规范 / 源码 / 文档

3. ClickHouse Documentation, ReplacingMergeTree、CollapsingMergeTree、Mutations（A 级）。
4. ClickHouse Source, MergeTreeDataMergerMutator.cpp、MergeTreeBackgroundExecutor.cpp（A 级）。
5. LSM 系列, Compaction。

Merge selector

SimpleMergeSelector / TTLMergeSelector 等根据 Part 大小、年龄、分区挑选 merge 任务；目标减少 Part 数且控制写放大。

ReplacingMergeTree

replace 版本列默认 is_deleted 或显式 version；merge 同排序键保留 version 最大。查询仍可能见重复行，除非 FINAL 或应用层去重。

CollapsingMergeTree

Sign 列 +1/-1 表示插入与撤销；merge 折叠成 net 行。适合变更流而非物理 DELETE。

Mutation 路径

ALTER TABLE UPDATE/DELETE → MutationCommands 队列 → 后台读 Part 重写新 Part → 原子替换。堆积时 system.mutations 可见；与 merge 争用 BackgroundSchedulePool。