《大规模分布式计算深入解析》1.3 Push 模型与 Morsel 驱动并行

Push 由源端发起,morsel 把输入切块分给 worker。800 万行按 1 万行一块得 800 个 morsel,8 个 worker、每块 20ms 处理 2000ms;细化到 1000 行后为 8000 个,调度 400ms、占比 20%,块大小是均衡与开销的取舍。

1.3 Push 模型与 Morsel 驱动并行

1.2 的向量化解决的是「一次处理多少行」,但没有回答「谁来驱动这条流水线、多个 worker 怎么分活」。Push 模型与 morsel 驱动回答的正是后者:数据从源端主动推向下游,输入被切成固定大小的小块,每个小块作为一个调度单位交给一个 worker,从头到尾走完整条算子链。

这一节算清两笔账:morsel 切多大,调度开销占多少。切得粗,调度便宜但负载容易不均;切得细,均衡变好但调度成本线性上涨。20% 这个数字就是这条曲线的第一个警示点。

Pull 与 Push:谁发起控制流

火山模型和向量化模型都是 Pull:上层调用 next(),下层才产出数据。Push 反过来,由数据源发起,把一批数据推给下游算子,算子处理完再推给下一个,直到输出端。

维度Pull 模型Push 模型
控制流发起方上层算子数据源
数据流向被上层拉取主动推向下游
算子接口next() 返回数据push(batch) 接收数据
并行切入点上层切分源端切 morsel
短路能力天然支持 LIMIT需要中断信号

Push 的关键优势是控制流与数据流同向:源端知道有多少数据、能切多少块,调度器可以把块分给 worker,每个 worker 独立跑完整条链。Pull 模型也能并行,但并行点通常在算子之间插入 Exchange,控制流仍由上层发起。

Morsel:把输入切成可调度的小块

morsel 是 morsel 驱动并行的基本单位:一段连续输入,大小固定,通常在一万行量级。调度器维护一个 morsel 队列,worker 空闲时取一个,执行完整条流水线,完成后取下一个。

输入 8,000,000 行
morsel 大小 10,000 行
morsel 数 = 8,000,000 / 10,000 = 800 个
属性取值作用
morsel 大小10,000 行调度粒度
morsel 数800可分配的任务数
每块处理方式单 worker 跑完整条链避免算子间同步
队列全局或每 worker 本地动态负载均衡

一个 morsel 只由一个 worker 处理,块内不切分。这让每条流水线在块内保持局部性:数据留在 worker 的缓存里,算子之间不需要跨线程传递中间结果。块与块之间才是并行的边界。

800 个 morsel:用例 7 的账

用例 7 只做除法,确认切块数量:

morsel 数 = 行数 / morsel 大小
          = 8,000,000 / 10,000
          = 800 个
量取值来源
输入行数8,000,000统一场景
morsel 大小10,000 行模型参数
morsel 数800用例 7

800 这个数字本身不重要,重要的是它和 worker 数的比例。800 个块分给 8 个 worker,平均每个 worker 处理 100 块;块数远多于 worker 数,才有动态调整的空间。

8 个 worker:2000ms

假设每个 morsel 的处理时间是 20ms,8 个 worker 并行处理 800 个 morsel。用例 8 按「块数除以 worker 数、向上取整」计算:

每个 worker 的块数 = ceil(800 / 8) = 100
并行处理时间     = 100 × 20ms = 2000ms
量取值
morsel 数800
worker 数8
每块处理时间20ms
每 worker 块数100
并行处理时间2000ms

2000ms 是理想均分的结果:800 能被 8 整除,每人都拿 100 块,没有尾块等待。真实场景里块的处理时间不会完全一致,但只要块数足够多,调度器可以在快 worker 完成后再塞新块,尾部的偏差被摊平。

细化到 1000 行:8000 个 morsel

把 morsel 从 1 万行减到 1000 行,块数变成 8000 个。每块数据少了 10 倍,处理时间也按比例降到 2ms。用例 9 同时给出调度开销与占比:

morsel 数    = 8,000,000 / 1,000 = 8,000 个
调度开销     = 8,000 × 50µs = 400,000µs = 400ms
并行处理时间 = ceil(8,000 / 8) × 2ms = 1,000 × 2ms = 2000ms
调度占比     = 400ms / 2000ms = 20%
量1 万行 morsel1000 行 morsel
morsel 数8008,000
每块处理时间20ms2ms
并行处理时间2000ms2000ms
调度开销40ms(推算)400ms(用例 9)
调度占处理时间2%(推算)20%(用例 9)

处理时间没有变,变的是调度开销。块缩小 10 倍,每块的处理时间也缩小 10 倍,8 个 worker 的总处理时间仍然是 2000ms;但块数涨了 10 倍,按每块 50µs 的调度成本,调度开销从 40ms 涨到 400ms,占比从 2% 涨到 20%。

调度与均衡的取舍曲线

继续把 morsel 减半到 500 行,块数变成 16000 个,调度开销翻倍到 800ms,处理时间仍然是 2000ms:

morsel 行数morsel 数调度开销处理时间调度占比
10,000800(用例 7)40ms(推算)2000ms(用例 8)2%(推算)
1,0008,000(用例 9)400ms(用例 9)2000ms(用例 9)20%(用例 9)
50016,000(推算)800ms(推算)2000ms(推算)40%(推算)

这条曲线说明 morsel 不能无限细化:处理时间有下限,调度开销却随块数线性上涨。当调度占比达到 20%,已经有五分之一的并行时间花在「分活」上;再细一倍就是 40%,调度的收益被自己吃掉。

反过来,morsel 太大也有问题:块数接近 worker 数时,一个慢块会拖住一个 worker,其他 worker 早早空闲。调度开销低了,但尾部延迟高了。

为什么 morsel 要远多于 worker

morsel 数 : worker 数均衡能力调度开销适用
1 : 1无,慢块直接决定总时间最低块耗时完全一致
10 : 1有限,尾部偏差约一块低较均匀的数据
100 : 1好,快 worker 可继续取块中常见默认
1000 : 1很好,但调度占比上升高强倾斜数据

800 个 morsel 对 8 个 worker 是 100 : 1,这是用例 8 能算出理想 2000ms 的原因:块足够多,调度器总能把空闲 worker 填满。如果只有 8 个 morsel,每个 worker 一块,任何一块慢 50%,总时间就慢 50%,没有补救空间。

Push 模型的实现代价

Push 不是「把 Pull 反过来」这么简单,它改变了短路、错误传播与内存管理的方式:

问题Pull 的做法Push 的做法
LIMIT 短路上层不再调用 next()向下游发中断信号
背压自然形成,上层不取就不产需要队列或阻塞协议
错误传播异常沿调用栈返回沿推送链向上报告
中间结果由上层持有由推送方管理生命周期

短路是 Push 最不自然的地方:Pull 模型里 LIMIT 10 只要停止调用,数据就不再产生;Push 模型里数据已经在路上,必须让下游能拒绝或让源端收到停止信号,否则会多算很多行。实现上通常用异常、标志位或批次边界检查来中断。

什么时候该用 morsel 驱动

场景建议原因
十万到百万行Push + morsel并行收益开始显现,调度占比可控
数据倾斜明显减小 morsel块多才能动态均衡
极短查询行式或单线程调度开销高于并行收益
超大扫描向量化 + morsel批处理降调用,morsel 提供并行
强依赖顺序单线程并行会破坏语义

morsel 驱动的价值在「中等规模、需要并行、负载不完全均匀」这一段。再小的查询不值得调度,再大的扫描则要先靠向量化把单核效率做上去,否则并行只是把同样的低效复制到更多核。

三个常见误解

误解一:Push 模型本身就是并行模型。 真相:Push 描述的是控制流方向,单线程也能 Push;真正的并行单位是 morsel,由调度器把块分给 worker。

误解二:morsel 越小,负载越均衡,所以总越快。 真相:块从 1 万行减到 1000 行,处理时间仍是 2000ms,调度开销却从 40ms 涨到 400ms,占比达到 20%,再细只会更差。

误解三:morsel 数等于 worker 数最省调度。 真相:800 个块对 8 个 worker 才有 100 : 1 的动态均衡空间;块数等于 worker 数时,一个慢块就直接决定总时间。

一句话总结本节

Push 模型由源端发起控制流,morsel 驱动把 800 万行按 1 万行一块切成 800 个 morsel,8 个 worker、每块 20ms 时处理时间为 2000ms;块细化到 1000 行后变成 8000 个,处理时间仍是 2000ms,但 8000 × 50µs = 400ms 的调度开销占到 20%。块大小是在负载均衡与调度开销之间取舍,块数要远多于 worker 数。

控制面、Morsel 与 Worker

同一 Pipeline 内,Worker 按数据块处理 Scan、Filter 和 Project。阻塞算子或 Exchange 需要新的执行边界。

flowchart LR
    P[查询调度器] --> Q[就绪 Pipeline 队列]
    Q --> W1[Worker 1]
    Q --> W2[Worker 2]
    T[(输入列或文件范围)] --> M[Morsel 列表及领取进度]
    M --> W1
    M --> W2
    W1 --> B[本地向量缓冲]
    W2 --> C[本地向量缓冲]
    B --> E[下游算子或阻塞边界]
    C --> E
    E -. LIMIT 或取消 .-> P

本节 lab

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

在 bd-engine-lab 中验证 morsel 切分与调度占比:

  • 源码: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。
  • 断言:用例 7 验证「800 万行、每块 1 万行,得到 800 个 morsel」;用例 8 验证「800 个 morsel、8 个 worker、每块 20ms,并行处理 2000ms」;用例 9 验证「morsel 细化到 1000 行后为 8000 个,调度 400ms、处理 2000ms,调度占比 20%」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:看到并行执行需要分活 → 把输入切成固定大小的 morsel → 800 个块分给 8 个 worker 得 2000ms → 块细化到 1000 行后调度涨到 400ms、占比 20% → 块大小按均衡与开销取舍,块数保持远多于 worker。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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