《大规模分布式计算深入解析》7.3 窗口算子与增量计算

窗口算子对每行算一个区间聚合。朴素滑窗 100 万行乘窗口 10 是 1000 万次,增量滑窗只处理进出各一次共 200 万次,省 80%;1000 个窗口分区、Top10 约 3322 次比较;单分区 1024MB 超出 64MB 内存必须溢写。

7.3 窗口算子与增量计算

窗口函数对每一行算一个「以它为中心或结尾的区间」的聚合。它最容易写出的实现是朴素滑窗:每行都把窗口里的元素重新扫一遍、重新算一遍。这个写法结果正确,但在大表上会把成本放大一个窗口长度那么多倍。增量滑窗换一个思路——窗口每前进一格,只处理进来的一行和出去的一行。

本节沿一条判断链走:现象是窗口查询比同规模的普通聚合慢一个数量级,机制是从「每行重算窗口」变成「只处理进出」,账本是 1000 万次对 200 万次、1000 个分区与 3322 次比较,判据是聚合是否可以增量、以及单分区能否放进内存。

朴素滑窗:行数 × 窗口长度

朴素实现的计算量与行数和窗口长度都成正比。lab 用例 62 的场景是 100 万行、窗口 10:

// 用例 62:朴素滑窗的聚合操作数
long ops = Operator.naiveSlideOps(1_000_000L, 10);
// 1,000,000 × 10 = 10,000,000 次
量取值说明
行数1,000,000窗口输入
窗口长度10每行覆盖的行数
聚合操作数10,000,000用例 62

1000 万次不是终点,而是窗口长度为 10 时的值。窗口一长,乘数直接变大:窗口 100 就是 1 亿次。朴素滑窗的成本对窗口长度线性敏感,而真实业务里的移动平均窗口动辄几十上百。

增量滑窗:进出各一次

滑动窗口前进一格,窗口内的元素只发生了两个变化:最前面出去一个、最后面进来一个。增量算法只对这两个元素做操作:

窗口 [i, i+w-1] → [i+1, i+w]
出去:第 i 行        → 从累加器减去
进来:第 i+w 行      → 向累加器加上

lab 用例 63 的口径是每行进出各一次:

增量操作数 = 行数 × 2 = 1,000,000 × 2 = 2,000,000 次
实现聚合操作数相对成本节省
朴素滑窗10,000,000(用例 62)100%—
增量滑窗2,000,000(用例 63)20%80%(用例 63)

80% 的节省来自把「乘以窗口长度」变成了「乘以 2」。这个比例在窗口更长时会更夸张:窗口 10 时省 80%,窗口 100 时朴素是 1 亿次、增量仍是 200 万次,节省超过 98%(公式推导)。

增量成立的条件

增量不是万能的,它依赖聚合函数可逆。把「加进来」能撤销成「减出去」,才能边滑动边更新:

聚合函数可增量说明
sum、count可以直接加减
avg可以维护 sum 与 count,相除得到
min、max需辅助结构用单调队列维护窗口内最值
median、分位数通常不可以无法用一个减法撤销

不可逆的聚合只能退回朴素实现或近似算法。中位数就是典型:从窗口里移除一个值,无法在常数时间内更新中位数。这也是很多引擎对 median 窗口函数性能明显更差的原因——不是实现不好,而是数学上无法增量。

分区:1000 个窗口分区

窗口计算天然可以按分区并行:不同分区之间没有数据依赖,可以独立计算。lab 用例 64 按每 1000 行一个分区切分 100 万行:

分区数 = ceil(行数 ÷ 每分区行数)
       = ceil(1,000,000 ÷ 1000)
       = 1000 个分区
量取值说明
总行数1,000,000窗口输入
每分区行数1000分区粒度
分区数1000用例 64

分区粒度同时是并行度与内存的旋钮。分区越多,并行度越高、单分区越小、越容易放进内存;分区越少,单分区越大、并行度越低,但分区边界上的窗口处理更简单(跨分区窗口需要额外合并逻辑)。

TopN:堆的复杂度

窗口里常见的另一种计算是 TopN。如果先全排序再取前 k 个,成本是 n log2 n;用大小为 k 的堆则只需 n log2 k。lab 用例 65 算的是 1000 行取 Top10:

// 用例 65:每分区 TopN 的比较次数
double ops = Operator.topNOps(1000L, 10);
// 1000 × log2(10)
// = 1000 × 3.3219
// = 3321.9 次
klog2(k)比较次数(1000 行)说明
103.32193321.9(用例 65)堆只需维持 10 个元素
52.32192321.9(公式推导)k 更小,比较更少
1006.64396643.9(公式推导)k 接近 n,优势缩小

log2(k) 是关键:k 从 10 涨到 100,比较次数只从约 3322 涨到约 6644,远慢于 k 的增长。这也是 TopN 用堆而不用全排序的原因——它把「排序全部」换成「维护 k 个候选」。

单分区溢出:1024MB 对 64MB

窗口算子也会溢出,触发条件不是总数据量,而是单个分区的大小。lab 用例 66 的场景是单分区 1024MB、可用内存 64MB:

单分区 1024MB > 内存 64MB → 必须溢出
单分区大小内存是否需要溢出后果
64MB 以内64MB否全内存计算
等于 64MB64MB临界几乎无余量
1024MB64MB是(用例 66)必须切分或落盘

分区不能切得太粗。总数据量也许只有 1GB,但如果按一个分区处理,单分区就是 1GB,在 64MB 内存下必然溢出;同样 1GB 按 1000 行一个分区切,每个分区都很小,可以全内存跑完。分区的意义不只是并行,更是把「总内存需求」拆成「单分区内存需求」。

判据:窗口算子怎么选实现

条件结论
聚合可逆(sum、count、avg)用增量滑窗,省约 80%
聚合不可逆(median)朴素滑窗或近似算法
分区可独立按行数切分区并行
单分区超过内存细分区或落盘溢出
窗口内 TopN用大小为 k 的堆,不是全排序

判据的主轴有两条:聚合函数能不能增量,决定了成本是「行数 × 窗口」还是「行数 × 2」;单分区能不能放进内存,决定了要不要继续细分。两条都满足时,窗口计算可以做到近似线性;任何一条不满足,成本就会回到朴素或溢出路径上。

窗口帧的三种形态

「窗口」不只指前后各若干行的滑动窗口,至少还有两种常见帧:

帧类型边界增量方式
滑动窗口当前行前后固定行数进一个、出一个
累积窗口从分区起点到当前行只进不出,累加器单调增长
会话窗口按事件间隙切分依赖水位线与间隙判断

累积窗口比滑动窗口更简单:它只加不减,不需要处理「出去」的那一行,因此对聚合函数没有可逆性要求。滑动窗口则必须能撤销,这也是上一节「可增量条件」那张家表的由来。

乱序与水位线

上面的增量推导都假设数据按顺序到达、窗口一旦滑过就不再回头。事件时间乱序会打破这个假设:

到达情况处理方式对增量算法的影响
基本有序到界即触发无影响
少量乱序等水位线推进后再触发延迟输出,状态多留一会
严重乱序允许延迟或丢弃迟到数据需要回撤或重算

「出去的行不会再回来」是增量算法的隐含前提。如果一行迟到、本应落进已经算完的窗口,累加器就得回撤——而回撤要求聚合可逆。对不可逆聚合,工程上通常选择允许一定延迟(等水位线)或直接丢弃迟到数据,而不是付出重算整个窗口的代价。

多窗口函数共享一次扫描

同一条查询里常有多个窗口函数,比如同时算移动平均、移动求和和排名。如果每个函数各自扫描一遍分区,读放大会随函数个数线性增长:

做法分区扫描次数说明
每个函数单独算函数个数次重复读同一批行
共享分区扫描一次各函数维护自己的状态

共享扫描把「窗口数 × 分区大小」的读放大压回一次:扫描到某一行时,同时更新所有窗口函数的状态。代价是状态更多——每个函数都要保留自己的累加器或堆。这与前面「增量滑窗」的取舍一致:用更多状态换更少的重复计算。

三个常见误解

误解一:窗口函数每行都要重算整个窗口,省不了。 真相:滑动窗口前进一格只进一个、出一个,增量算法 200 万次就够,比朴素 1000 万次省 80%。

误解二:窗口分区只是并行度问题,与内存无关。 真相:分区大小决定单分区内存,1024MB 的单分区在 64MB 内存下必须溢写,分区太粗会直接打爆内存。

误解三:TopN 必须全排序后取前 k 个。 真相:维护大小为 k 的堆只需约 n log2 k 次比较,1000 行取 Top10 约 3322 次,远小于全排序。

一句话总结本节

窗口算子的成本取决于算法与分区:朴素滑窗要 100 万行乘窗口 10 共 1000 万次聚合,增量滑窗只处理进出各一次共 200 万次,省 80%;100 万行按 1000 行切出 1000 个分区,Top10 用堆约 3322 次比较。增量依赖聚合可逆,单分区 1024MB 超出 64MB 内存时必须细分或溢写,所以分区粒度也是内存决策。

本节 lab

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

在 bd-engine-lab 中验证窗口算子的增量账本、分区与 TopN:

  • 源码: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。
  • 断言:用例 62 验证「100 万行、窗口 10 的朴素滑窗 1000 万次聚合」;用例 63 验证「增量滑窗 200 万次,节省 80%」;用例 64 验证「100 万行按 1000 行切分得到 1000 个分区」;用例 65 验证「1000 行 Top10 约 3322 次比较」;用例 66 验证「单分区 1024MB 超出 64MB 内存必须溢出」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:窗口查询比普通聚合慢一个数量级 → 拆出「每行重算窗口」这条机制 → 算出 1000 万次对 200 万次、1000 个分区与 3322 次比较 → 聚合可逆就用增量、单分区超内存就细分或溢写。

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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