《大规模分布式计算深入解析》1.1 火山模型:迭代器与逐行开销

火山模型把每个算子做成迭代器,每输出一行都要穿过整条 next() 调用链。本节用 800 万行 3 算子算出 2400 万次调用,按每次虚调用 15ns 得 360ms 调度开销,再加每行一次分支预测失败的 40ms,说明成本主要在调度而非计算;lab 用三用例断言。

1.1 火山模型:迭代器与逐行开销

几乎每一个现代执行引擎的第一版都长这样:Scan 读一行,Filter 判断一行,Project 算一行。三个算子串成一条链,最上层反复调用 next(),数据就像火山喷发一样一行一行往上冒。这套结构叫火山模型(Volcano iterator model),它的优点是把算子组合得极其灵活,缺点是每一行都要为这种灵活付一次固定的调度税。

本节只算一笔账:800 万行、3 个算子、逐行执行,调度成本到底是多少。把数字算清楚,才能理解后面两节为什么要做批处理和 Push 模型。

一次 next() 如何穿过三个算子

火山模型把每个算子抽象成迭代器,对外只暴露三个方法:open()、next()、close()。上层调用 next() 要一行数据,算子向它的子算子要一行,子算子再向更下层要,直到数据源。

算子next() 做的事每次调用返回
Scan从文件或内存读下一行1 行原始数据
Filter向子算子要行,判断谓词1 行通过或继续要
Project向子算子要行,计算表达式1 行投影结果

关键在最后一行:每输出一行,next() 调用链就要从根走到叶一次。链上有几个算子,一行数据就要被传递几次;如果 Filter 过滤掉一行,这次调用链白跑一趟,下一行再来一遍。

2400 万次调用是怎么算出来的

lab 的统一场景是 800 万行输入、scan → filter → project 三个算子。用例 1 只做一件事:把「每行每算子一次 next()」乘起来。

总调用次数 = 行数 × 算子数
           = 8,000,000 × 3
           = 24,000,000 次
量取值来源
输入行数8,000,000统一场景
算子数3scan、filter、project
每行调用次数3每个算子一次 next()
总调用次数24,000,000用例 1

这不是 2400 万次「有用的计算」,而是 2400 万次控制转移。真正的谓词判断和投影表达式只占其中一部分,其余都是把「该谁干活」这个消息从链的一端传到另一端。

虚调用 15ns:360ms 的调度税

迭代器在 Java 里通常是一个接口,next() 是接口方法。调用方持有的是接口引用,运行时才知道具体是哪个实现类,因此每次调用都要经过虚方法分派,编译器很难把它内联成一条直接跳转。

lab 用例 2 给每次虚调用估了 15ns,这个数字包含分派、栈帧建立与返回值传递的量级成本:

// 用例 1:每行每算子一次 next()
long calls = rows * ops;              // 8,000,000 × 3 = 24,000,000

// 用例 2:按每次 15ns 计算总开销
long costNs = calls * 15L;            // 24,000,000 × 15 = 360,000,000ns
double costMs = costNs / 1_000_000.0; // 360ms
参数取值说明
总调用次数24,000,000用例 1
每次虚调用15ns模型参数
总调度开销360ms用例 2

360ms 是纯调度成本,还没有算任何业务逻辑。如果这条查询的真实计算只需要几十毫秒,那么大部分时间都花在「把行交给下一个算子」上。这也是为什么逐行模型在宽表扫描上会被批处理拉开一个数量级的差距。

分支预测失败:40ms 的隐藏成本

逐行执行还有第二笔账。Filter 的谓词通常依赖数据本身,比如 status = 'paid' 或 amount > 100。对 CPU 来说,这种分支的结果没有规律,分支预测器经常猜错,猜错一次要清空流水线,代价在纳秒量级。

lab 用例 3 的模型是每行发生 1 次分支预测失败、每次 5ns:

分支失败成本 = 行数 × 每次失败成本
             = 8,000,000 × 5ns
             = 40,000,000ns
             = 40ms
成本项计算结果
逐行分支失败8,000,000 × 5ns40ms
每行固定工作读行、判断、写回未计入本节账本

40ms 单独看不算大,但它和 360ms 是叠加关系,而且它不会随着算子变少而消失:只要还是一行一行判断,分支就还是一行一次。向量化和 SIMD 之所以有效,一部分原因正是把「每行一次判断」变成「一批一次判断」或「一条指令判断多个值」。

逐行执行的三笔账

把火山模型的成本拆开,可以列成一张固定的账本:

成本项触发频率本节数值能否靠换硬件消除
虚调用分派每行每算子360ms部分,CPU 更快只线性下降
分支预测失败每行40ms很难,取决于数据分布
真实计算每行未计入取决于表达式复杂度

三笔账里有两笔是结构性的:它们不随数据内容变化,只随「行数 × 算子数」增长。这意味着优化方向不是把表达式写得更聪明,而是减少每行要穿过的调度次数。这正是 1.2 向量化要解决的问题。

为什么逐行模型曾经是正确的选择

火山模型诞生于磁盘时代,当时的瓶颈是 I/O,不是 CPU。逐行迭代器有几个很难替代的优点:

优点具体表现代价
组合灵活任意算子可串联、可嵌套每行多次虚调用
内存占用低一次只保留一行无法批量向量化
流水线自然上层要一行,下层才产一行分支不可预测
支持短路LIMIT 取够就停无

低内存与短路是火山模型的杀手锏。SELECT * FROM t LIMIT 10 在 10 亿行表上只需要读 10 行,火山模型天然做到;批处理模型如果一次拉 1024 行,就会多读一千多行。所以即使向量化大行其道,点查、短结果、强短路场景仍然保留行式执行路径。

什么时候该离开火山模型

判断是否该换执行模型,看的不是「火山模型是否先进」,而是三个量:行数、算子数、选择率。

场景火山模型表现建议
点查、LIMIT 很小只读少量行,启动成本低保留行式
小表关联行数少,调度占比低保留行式
大表全扫描调用次数随行数线性膨胀转向批处理
多算子长链每行穿过的算子多转向批处理或融合
高选择率过滤大量行被丢弃,仍付满调用成本批处理 + 向量化谓词

判据可以写得很直接:当 行数 × 算子数 达到千万级,虚调用与分支成本就会进入几百毫秒的量级,此时逐行执行不再是「实现简单」的小代价,而是主要的性能瓶颈。

一行 50ns:把总量摊到单行

把 360ms 与 40ms 加起来,再除以 800 万行,可以得到一行数据的固定调度成本:

每行固定成本 = (360ms + 40ms) / 8,000,000
             = 400,000,000ns / 8,000,000
             = 50ns/行
其中:3 次虚调用 × 15ns = 45ns,分支失败 5ns
行数固定调度成本(按 50ns/行推算)说明
1,000,00050ms公式推导,未计真实计算
4,000,000200ms公式推导
8,000,000400ms用例 2 与用例 3 之和

50ns/行是一个很好用的心算单位。看到一条查询要扫几千万行,先用行数乘以 50ns 估一下调度底噪,再判断瓶颈是不是在执行框架上。如果真实耗时远大于这个数,才轮到算子和表达式优化。

选择率改变不了扫描侧的调用次数

一个容易被忽略的事实:Filter 丢弃的行同样要付 scan.next() 与 filter.next() 的成本,只有 project.next() 会随选择率下降。设输入 800 万行,三种选择率下的调用账本如下:

总调用 = scan 8,000,000 + filter 8,000,000 + project (8,000,000 × 选择率)
选择率scan 调用filter 调用project 调用总调用调度成本(推算)
100%8,000,0008,000,0008,000,00024,000,000360ms(用例 2)
50%8,000,0008,000,0004,000,00020,000,000300ms
10%8,000,0008,000,000800,00016,800,000252ms

选择率从 100% 降到 10%,调度成本只从 360ms 降到 252ms。原因很直接:扫描和过滤必须逐行触碰输入,省不掉;能省的只有通过过滤之后的那部分投影。把谓词写得更严可以少算表达式,却救不了逐行控制流本身。

三个常见误解

误解一:火山模型慢,是因为它的计算逻辑写得不好。 真相:计算逻辑通常只占一小部分,800 万行场景里 2400 万次虚调用本身就是 360ms,优化表达式写法救不了调度结构。

误解二:next() 只是一次普通函数调用,开销可以忽略。 真相:接口方法要走虚分派、难以内联,按每次 15ns 计,2400 万次就是 360ms,量级足以吞掉整条查询的预算。

误解三:既然向量化更快,任何查询都该换掉火山模型。 真相:点查、短结果和 LIMIT 场景依赖火山模型的低启动成本与短路能力,盲目批处理反而会多读数据、多付批启动开销。

一句话总结本节

火山模型把算子做成迭代器,800 万行、3 个算子时每行要穿过 3 次 next(),共 2400 万次调用;按每次虚调用 15ns 计算是 360ms 调度开销,再叠加每行一次分支预测失败的 40ms,逐行执行的主要成本在调度而不在计算。它的低内存与短路能力仍适合点查和小结果,但大扫描与长算子链必须转向批处理。

上游实现参照

Volcano 模型原论文

本节 lab

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

在 bd-engine-lab 中验证火山模型的调用账本:

  • 源码:src/exec/Exec.java 与 src/exec/ExecSuite.java。
  • 运行:cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。
  • 断言:用例 1 验证「800 万行 × 3 个算子 = 2400 万次 next() 调用」;用例 2 验证「2400 万次 × 15ns = 360ms 调度开销」;用例 3 验证「800 万行 × 每行 1 次分支失败 × 5ns = 40ms」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:看到大扫描变慢 → 拆出每行每算子一次 next() 的控制流 → 算出 2400 万次调用、360ms 虚调用税与 40ms 分支成本 → 行数乘算子数达到千万级时改用批处理,点查与短结果保留行式。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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