双栈滑动窗口聚合：流式计算的经典算法

什么是双栈滑动窗口聚合

双栈滑动窗口聚合（Two-Stack Sliding-Window Aggregation）是一种用于流式计算的高效算法，它用两个栈来维护一个滑动窗口，从而在 O(1) 均摊时间内完成元素插入和过期删除，并实时查询窗口内的聚合值。

这个思路在 Hacker News 上引发讨论（原帖），核心价值在于：它把「滑动窗口」这个看似需要反复扫描的结构，转化为两个方向互补的栈——一个负责「进入」，一个负责「离开」，查询时只需合并两者的聚合结果。

为什么滑动窗口需要特殊算法

滑动窗口的朴素实现

最直接的滑动窗口做法是维护一个队列，每次新元素进来就加入队尾，窗口超限就弹出队头，查询时遍历整个窗口计算聚合。这种做法在窗口大小为 k 时，每次查询的复杂度是 O(k)，高频查询场景下开销明显。

单调队列能解决一部分问题

对「求窗口最大值/最小值」这类问题，单调队列可以把查询降到 O(1) 均摊。但单调队列依赖比较运算的单调性，对求和、计数、平均值等聚合，它并不直接适用——因为这些操作不满足「弹出较小元素不影响结果」的性质。

双栈聚合的巧妙之处在于，它覆盖的是任意满足结合律的聚合操作（求和、计数、最值、甚至更复杂的合并），而不只是单调队列能处理的那类。

摊还分析（Amortized Analysis） 是这里的关键分析工具。它不关注单次操作的最坏耗时，而是考察「一串操作平均下来」的代价。经典例子是动态数组扩容：单次插入可能触发 O(n) 的搬移，但连续 n 次插入的总代价仍是 O(n)，故均摊每次为 O(1)。同样地，双栈聚合里 back 搬到 front 的单次操作是 O(n)，但因为每个元素在有生之年只会被搬运一次（从 back 弹出、再压入 front，之后就一直待在 front 直到过期），任意一段连续操作序列的总代价都与元素个数成正比，均摊下来每次插入/删除/查询都是 O(1)。理解摊还，就不会被「某次操作特别慢」这个表象误导——只要调用方不要求严格的单次最坏响应时间，摊还 O(1) 在工程上完全等价于 O(1)。

双栈结构的核心机制

两个栈的分工

把滑动窗口拆成前后两段：

• back 栈：新元素从顶部压入，负责「进入窗口」。
• front 栈：元素按先进先出顺序从这里弹出，负责「离开窗口」。

每个栈都额外维护一个「聚合值数组」：栈中每个位置都记录从栈底到该位置的聚合结果。这样任何一个栈的聚合值都能在 O(1) 读出。

何时把 back 搬到 front

当需要弹出队头元素、而 front 栈为空时，就把 back 栈的所有元素依次弹出并压入 front 栈。这个操作会反转元素的顺序，让最早进入的元素回到 front 栈顶，从而可以正确弹出。

单次搬运是 O(n)，但每个元素一生只被搬运一次，所以均摊复杂度仍是 O(1)。这是典型的「摊还分析」应用场景。

查询时如何合并

窗口的聚合值 = front 栈的聚合值 ⊕ back 栈的聚合值，其中 ⊕ 是聚合操作的合并运算。因为两个栈各自已经维护了从栈底到当前的有效聚合，查询只需一次合并，复杂度 O(1)。

适用场景与工程价值

实时监控与指标系统

在监控系统中，经常需要「最近 N 秒的请求数」「最近 N 秒的 P99 延迟」这类滚动指标。双栈聚合让这些指标可以在数据到达时增量更新，而不是每次都重扫窗口。

与其它方案的对比

方案	查询复杂度	支持的聚合
朴素队列	O(k)	任意
单调队列	O(1) 均摊	仅最值
双栈聚合	O(1) 均摊	任意结合律聚合

对需要「任意聚合 + 高频查询」的场景，双栈是目前很优雅的折中。如果聚合操作可逆（比如求和），也可以用「加进来、减出去」的方式，但一旦涉及不可逆聚合（最值、中位数近似），双栈就更稳妥。

t-digest 与 GK 摘要 是两类常用的小内存近似分位数算法。t-digest 通过「按分位位置动态调整簇的粗细」来保证尾部分位数（如 P99）精度更高，适合监控延迟这类关注极值的场景；GK 摘要（Greenwald-Khanna）则用带误差界的计数器给出确定性的分位数近似保证。相较之下，双栈滑动窗口聚合处理的是「最近 N 个元素」这种结构性过期问题，它保证的是精确结果，但不解决「在一个超大窗口里省内存地估分位数」这件事。二者常配合使用：双栈负责维护固定窗口的精确求和与计数，分位数这类不可结合的指标则交给 t-digest 之类的近似结构单独处理。

实现上的几个细节

聚合的可结合性是前提

双栈依赖聚合操作满足结合律：合并顺序不影响结果。求和、计数、最值、集合的并集都满足，但平均值本身不满足——需要改成「和维护 + 计数维护」两个可结合的量分别处理，查询时再做除法。

结合律（Associativity） 指运算满足 (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)，即合并的「分组方式」不影响最终结果。这一点之所以是双栈的前提，是因为窗口聚合实际上是把 front 栈和 back 栈各自的聚合值再做一次合并，而两个栈内部的聚合又是在不同时机分别累积的，如果结合律不成立，累积顺序一变结果就会漂移。求和、计数、最大值、最小值、按位或、集合的并集都满足结合律；而平均值、中位数、方差 这类则不满足——它们的正确写法是把问题拆成若干可结合分量（例如平均值拆为和与计数、方差拆为和、平方和、计数），在查询时才做最后的除法或开方。像 t-digest、GK 摘要这样的近似流式结构 之所以复杂，正是因为它们要在不满足简单结合律的统计量上尽量维持可控误差。

空栈与边界处理

front 为空时查询、窗口尚未填满时查询，都是容易出错的边界。工程实现中通常给空栈一个单位元（identity），使「空栈聚合」也能参与合并而不破坏结果。

何时该换个思路

双栈聚合假设窗口是「一刀切」的定长或按时间的过期策略。如果窗口边界更复杂（比如加权窗口、多级窗口），或者聚合本身要求精确的中位数、分位数，双栈就不再是最优解，需要转向更专门的流式算法（如 t-digest、GK 摘要等近似结构）。

小结

双栈滑动窗口聚合用一个简单的数据结构技巧，把滑窗查询从 O(k) 降到均摊 O(1)，同时保持对广泛聚合操作的支持。它的价值不在于新颖，而在于可靠、可预测、易于实现——这也是为什么它在流式处理库和实时指标系统里长期占有一席之地。对做后端或数据基础设施的工程师而言，理解这套机制，能在设计指标系统时快速判断该用哪种窗口结构。