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 次
| k | log2(k) | 比较次数(1000 行) | 说明 |
|---|---|---|---|
| 10 | 3.3219 | 3321.9(用例 65) | 堆只需维持 10 个元素 |
| 5 | 2.3219 | 2321.9(公式推导) | k 更小,比较更少 |
| 100 | 6.6439 | 6643.9(公式推导) | k 接近 n,优势缩小 |
log2(k) 是关键:k 从 10 涨到 100,比较次数只从约 3322 涨到约 6644,远慢于 k 的增长。这也是 TopN 用堆而不用全排序的原因——它把「排序全部」换成「维护 k 个候选」。
单分区溢出:1024MB 对 64MB
窗口算子也会溢出,触发条件不是总数据量,而是单个分区的大小。lab 用例 66 的场景是单分区 1024MB、可用内存 64MB:
单分区 1024MB > 内存 64MB → 必须溢出
| 单分区大小 | 内存 | 是否需要溢出 | 后果 |
|---|---|---|---|
| 64MB 以内 | 64MB | 否 | 全内存计算 |
| 等于 64MB | 64MB | 临界 | 几乎无余量 |
| 1024MB | 64MB | 是(用例 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
在 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 次比较 → 聚合可逆就用增量、单分区超内存就细分或溢写。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。