《大规模分布式计算深入解析》7.1 Hash aggregate 与分组

Hash 聚合逐行更新分组键到累加器的表,表大小由分组数决定:10 万组乘 32 字节是 3.2MB,10 组只有 320B 可驻留 L1;200MB 表在 64MB 内存下切 4 个溢出分区。map 端预聚合把 100 万行压到 10 万组,shuffle 数据降 90%。

7.1 Hash aggregate 与分组

聚合把多行压成每组一行。最常见的实现是 hash 聚合:维护一张「分组键 → 累加器」的哈希表,每来一行就按键找到累加器、更新状态,最后把表里每个条目输出成一行。它的成本和分组数直接挂钩,而不是和输入行数直接挂钩——这是它和排序聚合最根本的区别。

本节沿一条判断链走:现象是同一个聚合查询在不同数据上快慢差几十倍,机制是聚合表大小由分组基数决定,账本是 3.2MB 表、4 个溢出分区与 90% 的 shuffle 削减,判据是分组数落在哪个量级。

逐行更新的聚合表

阶段动作成本
构建/更新每行算分组键、查表、更新累加器每行一次哈希与随机访存
溢出表超出内存时按分区落盘额外 IO
输出遍历表,每组输出一行正比于分组数

输入行数只影响更新次数,分组数才决定表的大小。这两个量可以完全脱钩:100 万行聚合成 10 组,表只有 320B;10 万行如果每行一个键,表反而更大。判断 hash 聚合的瓶颈,先看基数,再看行数。

分组数决定表大小:10 万组 × 32 字节 = 3.2MB

lab 用例 55 给出最基本的口径:聚合表内存等于分组数乘以每组字节数。

// 用例 55:聚合表内存
long bytes = Operator.hashAggTableBytes(100_000L, 32);
// 100,000 × 32 = 3,200,000 字节 = 3.2MB
量取值说明
分组数100,000不同分组键的数量
每组字节32键、累加器与指针
聚合表内存3,200,000 字节用例 55,即 3.2MB

3.2MB 是一个会被缓存接住的尺寸:它放不进最小的 L1,但对 L2 或 L3 来说不算大。这意味着 10 万组的聚合,更新时的大部分查表可能命中缓存,随机访存的代价被压低。分组数再往上走一个数量级,这个优势就没了。

分组极少:10 组 = 320B,驻留 L1

反过来,如果分组数很小,聚合表会小到几乎不占空间。lab 用例 56:

聚合表 = 10 × 32 字节 = 320 字节
分组数聚合表内存缓存层级更新成本
10320B(用例 56)可驻留 L1几乎全是缓存命中
1,00032,000B(公式推导)可驻留 L1/L2命中率高
100,0003,200,000B(用例 55)超出 L1,进 L2/L3部分随机访存
1,000,00032,000,000B(公式推导)超出多数缓存随机访存主导

分组数少时,聚合几乎是无成本的:320B 的表完全在 L1 里,每行的更新只是一次极快的缓存读写。这也解释了一个常见现象——GROUP BY 一个低基数列(比如状态、类型)常常比高基数列快一个数量级,即使扫描的行数完全相同。

分组多到放不下:200MB 切成 4 个溢出分区

当分组数大到表放不进内存,hash 聚合必须溢出。lab 用例 57 的场景是 200MB 聚合表、64MB 内存:

分区数 = ceil(200MB ÷ 64MB)
       = ceil(3.125)
       = 4 个分区
量取值说明
聚合表200MB全量分组状态
内存上限64MB单分区可用内存
整除结果3.125公式推导
溢出分区4用例 57,向上取整

溢出分区的切法是按分组键的哈希做,保证同一个分组只落在一个分区里,这样每个分区可以独立聚合、独立输出,不需要跨分区合并。代价是多了一轮写盘与读盘;4 个分区意味着聚合表被完整地写出去又读回来一次。

map 端预聚合:100 万行压到 10 万组,shuffle 降 90%

分布式聚合最有效的一刀不在 reduce 端,而在 map 端先做一次局部聚合。lab 用例 58 的口径是 100 万行输入、预聚合后剩 10 万组:

shuffle 削减比例 = 1 - 部分聚合行数 ÷ 输入行数
                 = 1 - 100,000 ÷ 1,000,000
                 = 1 - 0.1
                 = 90%
方案shuffle 行数相对数据量说明
不预聚合1,000,000100%原始行全部过网络
map 端预聚合100,000(用例 58)10%每组只发一条中间结果

90% 的削减同时作用于网络、磁盘和 reduce 端的内存:少传 90% 的行,就少 90% 的反序列化、少 90% 的聚合表压力。如果每行按 32 字节估算,shuffle 数据从 32MB 降到 3.2MB(公式推导),这对 200MB 就要溢出的 reduce 端是决定性的。

基数估计与分区选择

溢出分区数取决于「聚合表会有多大」,而聚合表大小取决于分组数——分组数事先往往不知道。引擎只能靠统计信息估算基数:

估算情况后果
低估分组数分区不足,运行中被迫二次溢出
高估分组数分区过多,小文件与调度开销上升
估算准确一次分区到位,无二次溢出

基数估计错了,溢出策略就会错。低估是最危险的方向:以为 64MB 够用,实际表到了 200MB,运行到一半才被迫切 4 个分区,前面的工作要重做。稳妥的做法是按偏大的基数预留,或直接采用可动态增加分区的实现。

判据:分组数落在哪个量级

分组数量级聚合表策略
十级320B(用例 56)单机内存聚合,无需关心
十万级3.2MB(用例 55)单机内存聚合,注意缓存
百万级32MB(公式推导)可能接近内存上限,评估溢出
千万级以上数百 MB必须分区溢出 + map 端预聚合

判据的主轴是「分组数 × 每组字节」与可用内存的比较。前者远小于内存,hash 聚合就是最优解;前者接近或超过内存,就必须提前规划溢出分区,并在 map 端尽量预聚合,把进入 shuffle 的行数压下来。

累加器的状态设计

「每组 32 字节」是一个常见估算,真实占用取决于聚合函数需要保存多少状态:

聚合函数需要的状态每组字节
count一个计数最小
sum一个数值小
avg和加计数稍大
count distinct去重集合或草图显著变大

去重类聚合会把表撑大一个量级:它不能只存一个数值,而要存见过的值(或近似的草图)。10 万组普通 sum 是 3.2MB,同样分组数的 count distinct 可能是几十 MB。这就是为什么估算聚合表大小时,必须先看聚合函数,而不是只看分组数。

两阶段聚合的执行计划

分布式 hash 聚合几乎都拆成两段:map 端先做局部聚合,shuffle 按分组键重分布,reduce 端再合并同键的部分结果。

阶段输入输出
map 局部聚合原始行每个键的部分结果
shuffle部分结果按分组键分区
reduce 合并同键的多个部分结果每组一行最终结果

用例 58 的 90% 削减发生在前两段之间:map 端把 100 万行压成 10 万条部分结果,shuffle 只需要搬这 10 万条。reduce 端的合并成本也随之下降,因为到达的中间结果少了 90%。

值得注意的是,map 端预聚合要求聚合函数可合并——sum、count、min、max 都满足,avg 只要同时传和与计数也能合并。不可合并的聚合(比如中位数)只能把原始行全部送到 reduce 端。

倾斜分组的处理

分组键分布不均时,某个键可能占据大部分行,对应的 reduce 分区成为长尾:

现象原因对策
单分区远慢于其他热点键热点键拆成两阶段聚合
分区大小不均哈希偏斜加盐打散热点键
少数键巨大天然高基数集中单独处理或限制输出

加盐的本质是把一个热键拆成多个子键:先按「键 + 随机后缀」做局部聚合,再把子键的结果按原键合并。代价是多一轮 shuffle,收益是把一个巨大的分区摊平成多个小分区。是否值得,取决于热点键占总行数的比例——占比越高,收益越大。

输出阶段

聚合的输出规模由分组数决定,而不是输入行数:

输入行数分组数输出行数
1,000,000100,000100,000(用例 58 口径)
1,000,0001010
10,000,000100,000100,000(公式推导)

输入从 100 万涨到 1000 万,只要分组数不变,输出仍是 10 万行。这也是聚合能压缩数据的原因:它把「行数」这个维度消掉了。反过来说,高基数聚合的输出本身就很大,下游如果还要排序或写文件,成本会重新出现。

三个常见误解

误解一:聚合只要分组不多,内存永远够用。 真相:表大小是分组数乘每组字节,10 万组 3.2MB 尚可,但分组到千万级就是几百 MB,200MB 的表在 64MB 内存下要切 4 个分区。

误解二:map 端预聚合只是提前算一点,对 shuffle 影响不大。 真相:100 万行预聚合到 10 万组后 shuffle 数据降 90%,网络、磁盘与 reduce 端内存都按同一比例节省。

误解三:分组数少所以聚合一定快,不用管实现。 真相:分组少时表小到能驻留 L1(10 组 320B),但每行仍要哈希与探测;分组多时瓶颈转为随机访存与溢出。

一句话总结本节

Hash 聚合的成本由分组基数而非输入行数决定:10 万组、每组 32 字节是 3.2MB 表,10 组只有 320B 可驻留 L1;200MB 的表在 64MB 内存下要切成 4 个溢出分区,而 map 端预聚合把 100 万行压到 10 万组,让 shuffle 数据降 90%。判断策略先算「分组数 × 每组字节」,再决定是否需要分区与预聚合。

分组聚合和外存边界

部分聚合仅适用于支持分解的聚合函数。若状态溢写,最终阶段需按键合并对应状态。

flowchart TD
    A[输入向量与分组键] --> B[更新分区内聚合状态]
    B --> C{状态超预算}
    C -->|是| D[(写出可合并的分区状态)]
    C -->|否| E[保留内存状态]
    D --> F[逐分区读回及合并]
    E --> F
    F --> G[最终化聚合]

上游实现参照

DuckDB 外存 Hash 聚合设计

本节 lab

下载卷五 Java 8 实验 · 实验运行与版本说明

在 bd-engine-lab 中验证 hash 聚合的表大小、溢出与预聚合账本:

  • 源码:src/operator/Operator.java 与 src/operator/OperatorSuite.java。
  • 运行:cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。
  • 断言:用例 55 验证「10 万分组 × 32 字节 = 3.2MB 聚合表」;用例 56 验证「10 个分组时聚合表 320B」;用例 57 验证「200MB 表、64MB 内存切 4 个溢出分区」;用例 58 验证「100 万行预聚合到 10 万组,shuffle 降 90%」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:同一聚合查询快慢差异巨大 → 拆出「分组数决定表大小」这条机制 → 算出 3.2MB 表、4 个溢出分区与 90% 的 shuffle 削减 → 按分组数量级决定是否分区溢出并做 map 端预聚合。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图