企业官网建设流程全解析

并行加速 ClickHouse 中固定哈希表的聚合合并

大概半年前，我被一个 GROUP BY 查询折磨到怀疑人生。32 个线程已经在并行扫描数据，局部聚合也执行完了，可整条 SQL 还是卡在“合并结果”这一环。从 Profile 上看，Aggregator 的 merge 阶段吃掉了超过一半的时间。你可能会问：局部聚合都算完了，合并不就是把几份结果加起来吗，能有多慢？如果你也这么想，说明你还没遇到过 FixedHashTable 在并行聚合合并场景下的真实瓶颈。

这个问题的本质，不是“合并”这个操作本身复杂度有多高，而是 ClickHouse 的聚合流水线在并行执行时，局部聚合和结果合并之间的衔接方式，决定了哈希表的并行度能利用到什么程度。这篇内容就围绕“怎么把固定哈希表的聚合合并从串行或伪并行，变成真正吃满多核的并行”展开。我会从原理、实现路线、实测数据和踩坑经历几个方面聊透，适合正在做 ClickHouse 二次开发、或对高性能聚合引擎感兴趣的开发者阅读。

1. 从一个慢查询说起：聚合合并怎么成了瓶颈

1.1 聚合流水线里最容易被忽略的时间黑洞

先还原我当时的场景。一张宽表，大概 40 亿行，按某个高基数的用户字段做 GROUP BY，同时附带十几个聚合函数。查询执行计划很常规：并行读取数据块，每个线程维护自己的局部哈希表做 partial aggregation，最后把众多局部结果合并进一个全局状态。因为分组键基数很高，局部聚合不会把数据压得特别小，每个线程手里的哈希表都有几十万到几百万个 entry。

问题出现在最后一步。早期版本里，多个局部哈希表往全局哈希表合并时，实际采用的是串行合并，每次只取一个输入表，把它里面的键值对逐个往全局表里插。32 个局部表合并下来，总耗时比所有局部聚合加起来还要长。perf 的数据很难看：大部分时间花在 cache-miss 和随机内存访问上，CPU 的有效利用率非常低。

所以说，聚合合并并不是“几份结果加起来”这么简单。它本质上是在做大量的哈希探测、状态合并和内存搬移。只要键的分布是随机的，合并过程对 cache 就极度不友好。一个表里的第 100 万个 key，在全局表里的目标位置可能分布在整个内存空间的任意角落。

1.2 FixedHashTable 在这条链里的具体位置

ClickHouse 的聚合会针对不同键类型选择哈希表实现。对于数值型定长键，常用的是 FixedHashTable——连续内存数组、开放寻址法、key 直接哈希定位。它可以是局部聚合的容器，也可以是全局聚合的容器。于是合并就变成了“N 个 FixedHashTable 向 1 个 FixedHashTable 灌注数据”。

我把它单独拎出来说，是因为很多人误以为瓶颈只在“插入”上。实际上，合并还包含聚合状态（AggregateState）的合并。比如 sum 状态的合并是数值相加，但 uniq 状态是 HyperLogLog 的合并，avg 中间态要同时合并 count 和 sum。这些状态合并不是无脑 memcpy，而是一个个调用聚合函数的 merge 方法，开销不小。

2. FixedHashTable 的结构与合并本质：为什么不能像插元素一样简单处理

2.1 FixedHashTable 为什么叫“固定”

FixedHashTable 的“固定”不是说容量不可变，而是指它的 cell 布局在设计上是固定的：每个 cell 放着 key 和对应的聚合状态，哈希表通过开放寻址法解决冲突，查找时从哈希位置开始线性探测，遇到空 cell 就停。

正因为 cell 是紧密排列的，它的内存局部性比链表式哈希表好得多。单个哈希表内部遍历时，cache 命中率很高。但一旦涉及多表合并，这个优势就没了——你在源表里连续遍历 cell，目标表的位置却是跳跃的，cache 友好性直接崩掉。这是合并不好优化的根本原因之一。

在 ClickHouse 的源码里，FixedHashTable 往往还会配合 Arena 来管理聚合状态的内存。所以在合并时，不光要把 key 插进新表，还要把状态从源表的 Arena 拷贝或合并到目标表的 Arena。这里的指针跳转进一步加剧了随机访问。

2.2 合并的本质：不只是搬运 key，还要搬运中间状态

假设我们有两个局部哈希表 A 和 B，要把 B 合并进 A。最朴素的做法是：遍历 B 的每个非空 cell，拿 key 到 A 里查找；如果 A 里没有就插入一个新 cell，把 B 的聚合中间态整体搬过来；如果 A 里已有，就执行两个中间态的 merge，合并成一个新的中间态。

对于 sum / count 这类函数，状态就一个数值，merge 非常快。对于 uniq / quantile 这类状态，merge 的成本较高，因为要合并底层数据结构。对于 agg state 里还有复杂子结构的，还要注意所有权和生命周期问题，避免 double free 或内存泄漏。

这带来一个重要的启示：合并的耗时跟聚合函数类型强相关。同样是 1 亿个 key，只做 sum 和做 10 个复杂聚合函数，耗时能差出数倍。我们做并行优化时，不能只看 key 的搬运，还要把状态 merge 的成本分摊到并行线程里。

2.3 串行合并的两个隐藏代价

第一个是缓存失效。串行合并且时，目标哈希表会在一次合并中被反复写入热点区域。这个区域的 cache line 会在多核间迁移。如果另一个 CPU 核也同时尝试写同一个 cache line，就会造成伪共享（false sharing），明明大家写的是不同 key，却互相拖慢。

第二个是锁竞争。如果选择让多个线程同时往一个全局哈希表里插，就必须加锁。哈希表插入的临界区其实很短，但键值对数量很大时，锁获取释放的开销会被无限放大。尤其是采用自旋锁时，高并发下 CPU 空转非常严重。串行合并虽然避开了锁问题，却又回到了单核利用率低的老路。

3. 并行合并的三条路线：分片、预分区和层级合并且

要真正提升合并性能，核心思路只有一条：尽可能让每个线程只碰自己那一份内存，线程之间零共享。围绕这个思路，业界和 ClickHouse 内部也有几种不同实现路线。

3.1 路线一：分片哈希表 + 细粒度锁

这条路线很好理解：把一个大的哈希表水平拆成 N 个分片，每个分片是一个独立的 FixedHashTable，每个分片对应一把独立的锁。合并 B 的时候，先按 key 哈希值决定落到哪个分片，然后只锁那个分片。

优点是实现简单，能立刻把单线程合并变成多线程。缺点是：如果 key 分布不够均匀，某些分片会成为热点；锁的开销虽然比全局锁小，但仍然存在。实测中我发现，在 48 核机器上，分片数超过 64 之后，锁竞争下降的收益会被内存带宽瓶颈抵消，加速比不再线性增长。

3.2 路线二：按哈希高位预分区，相当于两级哈希

这是我认为最值得采用的一条路线，ClickHouse 自己也用了类似思路（TwoLevelHashTable）。维护一个两级结构：先看 key 哈希值的高 8 位或高 N 位，决定它落到哪一个区（shard），区内再用 FixedHashTable 存储。合并时，每个线程固定负责一个或多个区，互不干扰，完全无锁。

这条路线的优点非常突出：

• 合并且天然并行，线程之间没有共享写；
• 分区数可以很大（如 256 个），充裕的任务粒度有利于负载均衡；
• 哈希冲突被限制在单个分区内，哈希表的总容量可以按分区独立管理。

缺点是要处理偏斜：如果某个分区的 key 特别多，负责该分区的线程会成为长尾。通常做法是动态调整分区到线程的任务分配，而不是静态绑定。

3.3 路线三：层级合并，把合并过程做成树

第三种路线是把合并过程组织成一棵合并树：底层是每个线程的局部哈希表，两两合并成中间表，再进一步向上合并，最后得到一个全局表。这种方案的好处是每一层的并行度都很高，任何时刻都有多组线程在独立完成合并任务，特别适合跨 NUMA 节点的场景。

缺点是会引入较多中间表，内存占用和构建开销不小。而且如果并行度不高，树形合并的收益反而不如直接平铺分区。它更适合 CPU 核心数非常多、局部表数量非常多的情况。

3.4 三条线路的取舍对比

我的建议是：如果你的目标是嵌入现有引擎，优先选择高位预分区。它把“并行”从锁竞争中彻底解放出来，长时间运行的系统里收益最稳定。树形合并且在特定规模下更快，但调参成本高，一般项目扛不住。

4. 实现细节决定成败：预分配、批量搬移与缓存友好

分了区、去了锁，不代表合并就快了。真正的差距往往藏在实现细节里。哪怕同样走“高位预分区”路线，预分配与否、搬移方式是逐个循环还是批量处理，性能可以差出好几倍。

4.1 合并前预分配，让 resize 一次都不发生

哈希表在插入过程中如果负载因子超过阈值，会触发 resize，也就是重新分配一块更大的内存，把已有元素全部重新哈希一遍。这个操作对单个哈希表来说是 O(n)，如果合并过程中反复触发，代价极高。

解决办法是合并前做一个预估：遍历所有源表的已使用 cell 数，求和，再加上一定余量，一次性为目标表分配足够的内存。这样整个合并过程中不会发生任何一次 resize。

需要注意：预估的准确性会影响内存开销。如果估少了，后期还是得 resize；估多了，浪费内存，但换来稳定性能。我一般按源表已使用 cell 总数的 1.2 倍预估。ClickHouse 官方插件里也把类似逻辑做成“预分配预取器”，目的就是这个。

4.2 批量搬移 cell，而不是逐个插入

很多人在写合并代码时，习惯写成：

for (auto it = source.begin(); it != source.end(); ++it) { target.insert(it->key, it->state); }

这个慢在两个方面：一是每次 insert 都要做一次完整的哈希探测，二是循环体内分支太多，CPU 分支预测器很难优化。

优化的方向是“区间处理”。观察到 FixedHashTable 的 cell 数组是连续的，可以一次扫描一大段：

• 如果整段都是空 cell，直接跳过；
• 如果段里有非空 cell，就把这些 key 打包后批量探测目标表。

配合 SIMD 风格的掩码判断，可以一次性找出连续空 cell 的位置，减少逐 cell 判空的开销。在源表缓存友好的遍历中，这种批量处理能让 CPU 流水线明显更顺畅。

4.3 内存布局与伪共享

多线程合并时，不同线程负责不同分区，但如果两个分区在一个 cache line 里，两者交替写内存时依然会产生激烈的 cache line 竞争。解决办法很土但有效：分区内存按 64 或 128 字节对齐，每个分区之间加 padding，确保一个 cache line 只属于一个分区。

实测过，这个被很多人忽略的细节，在 32 线程以上时能带来 15% 到 20% 的提升。毕竟 cache line 是内存一致性协议的最小粒度，宁可多浪费一点内存，也别让两个线程踩在同一个 cache line 上。

4.4 一个简化版合并循环

我把去掉错误处理和细节的合并核心逻辑简化成伪代码，方便你理解一个兼顾预分配、批量搬移和预取的合并循环长什么样：

void parallelMerge(HashTable* src, HashTable* dst, size_t threadId, size_t threadCount) { // 每个线程只处理属于自己的一组分区 for (size_t shard = threadId; shard < kShards; shard += threadCount) { auto* shard = dst->getShard(shard); shard->reserveForMerge(estimateSize(shard, src)); // 按块扫描源表，提升 prefetch 命中率 for (size_t offset = 0; offset < src->cells.size(); offset += kBatchSize) { __builtin_prefetch(src->cells.data() + offset + kPrefetchDistance); for (size_t i = offset; i < min(offset + kBatchSize, src->cells.size()); ++i) { if (src->cells[i].isEmpty()) continue; auto* place = shard->findOrInsert(src->cells[i].key); place->state.merge(src->cells[i].state); } } } }

这里有两个重点：一是用 hardware prefetch 提前把目标 cache line 拉进 L1/L2；二是把 source 的扫描分成 batch，让源表遍历本身就保持顺序访问。这样源表读取是线性的，目标表探测虽然有随机性，但 prefetch 能抵消一部分延迟。

5. 实测对比与 profile 解读

所有优化到底有没有用，最终要看数据。我把三种路线都放到同一台测试机上验证过一遍，结果很能说明问题。

5.1 测试环境与数据构造

测试机是某内部性能集群上的 48 物理核实例，内存 512 GB，禁用超线程，使用 jemalloc 作为内存分配器。数据是模拟生成的点击流事件表，40 亿行，分组键是一个 uint64 类型的高基数 ID，几乎每个 key 都只出现一两次。这正好让局部哈希表的规模和全局哈希表的规模都非常大，KPI 足够明显。

5.2 三个方案的实测结果

高位预分区方案相对串行合并有接近 6 倍的加速，而且合并阶段在整条 SQL 里的占比从 68% 降到了 32%。整条查询的耗时从接近 70 秒降到 26 秒左右。这个结果基本符合预期：哈希表合并的主瓶颈不在 CPU 算力，而在于内存延迟和并行粒度。

5.3 从 profile 事件里看到的真相

我用 perf 和 ClickHouse 自带的 profile events 统计了几个关键指标，分布很有意思：

• 串行合并时，cache-miss 率高得惊人，几乎每次访问目标表都是 miss；
• 细粒度锁方案虽然 cache-miss 有所降低，但锁相关的开销依然不低；
• 高位预分区方案里，cache-miss 降到了可接受范围，而且每个线程的 IPC（每周期指令数）明显上升。

还有个现象值得提：合并且线程数从 8 提升到 24 时，加速比接近线性；但从 24 提升到 48 时，提升幅度明显变小。这说明当任务粒度已经足够多的时候，进一步增加线程是在跟内存控制器和总线带宽较劲，而不是在提升计算并行度。

6. 进阶优化与踩坑记录

6.1 线程数不是越多越好，内存带宽会先到天花板

我在参数调优时犯过一个错误：以为 48 核机器就该把合并线程拉满到 48。实际上，哈希表合并非常吃内存带宽。每个 key 的插入都要访问一段随机的内存区域，当并发线程太多时，所有线程都在等内存控制器响应，CPU 反而利用率下降。

结合实测，我建议按“分区数 = 物理核数的一半到三分之二”来初始设置，然后把分区总数设得比线程数多几倍（例如线程 16，分区 256），让每个线程动态领取分区任务，而不是提前绑定死。这样既保证任务粒度足够细，又避免线程数过多挤爆内存带宽。

6.2 分配器选择：jemalloc 不一定总是好

很多人迷信 jemalloc，但我在这个场景下做过对比：在小规模数据合并时，默认分配器在预分配良好时并不比 jemalloc 差；但在大规模并发合并下，jemalloc 的 arena 机制能明显减少线程间的堆竞争，总体优势大约有 10%。

不过要注意：如果分区预分配做得不好，导致大量小内存块频繁分配释放，jemalloc 的缓存再大也白搭。所以分配器是辅助，预分配才是核心。先把预分配和批量搬移做好，再考虑换分配器。

6.3 哈希种子与偏斜防御

有一个隐蔽的坑是恶意或偶然的哈希偏斜。如果数据生成时有规律，比如所有 ID 的低 16 位都是 0，那么按哈希值高位分区就会让某个 shard 极端膨胀，拖垮整个合并。

解决办法有两个方向：一是引入随机哈希种子，让哈希值在不同运行中随机化，防止固定规律的数据导致固定热点；二是监控分区耗时，当某个分区明显偏大时，把该分区的任务进一步拆细，或者把它的哈希重新映射到更细的子分区。ClickHouse 的 TwoLevelHashTable 在 resize 时也会做类似的分裂操作，思路是一样的。

6.4 与现有执行参数的配合

如果你是直接在 ClickHouse 里调参而不是改源码，也有空间。注意观察group_by_two_level_threshold和group_by_two_level_threshold_bytes这两个参数。它们决定聚合在什么规模下切换到两级哈希表（也就是 256 分区的 TwoLevelHashTable），切换之后合并阶段的并行度会明显提升。

我在测试中把阈值调低后，中等数据量查询的耗时立刻下降了一截。不过阈值也不是越低越好：数据量很小的时候，两级哈希表的管理开销反而比单级 FixedHashTable 大，会出现负优化。建议根据线上查询的常见数据量单独标定，不要全局一刀切。

还有一点，开启max_threads时不要拍脑袋填一个很大的值。我的经验值是先按物理核数来，然后看合并阶段是否已经把占比压到 30% 以下，如果压不下去，说明瓶颈已经挪到别处了，再堆线程毫无意义。

如果你问我这个优化里最重要的心得是什么，那就是：合并且从来不是一个单纯的数据结构问题，而是一个内存系统问题。把 cache line、内存带宽、预取行为和线程粒度放在一起考虑，才能把固定哈希表的并行合并真正做好。这个思路不止适用于 ClickHouse，任何面对大哈希表合并的系统，都可以从中得到启发。