原文: https://www.arroyo.dev/blog/how-arroyo-beats-flink-at-sliding-windows

在 Arroyo 我们正在构建先进的流处理引擎, 以便为每个人提供实时数据. 如今, 默认的流处理工具是 Apache Filnk. 但是在 Splunk 和 Lyft 构建以 Flink 为基础的流式平台, 我们在早期发现, Flink的局限性使得不适合作为构建可靠, 高效平台的基础.

从头开始开发一个新的, 基于 Rust 的流引擎是一项艰巨的任务. 但它使我们有机会大大改善流处理的用户体验. UX 的一部分使我们的用户能够在不深入了解引擎性能特征的情况下编写他们想要的任何查询.

这需要出色的基准性能, 而且看似合理的查询也不会使性能骤降. 在这篇文章中, 我将讨论一个示例, 说明我们的架构如何解决一类在 Flink 中表现出病态进行为的查询模式.

什么是滑动窗口

一个滑动窗口(或者称为跳跃窗口) 是一个在流处理中常见的结构, 在 Flink, Cloud Dataflow, KSql, and Spark Streaming 都出现过. 它由两个时间段进行定义: 窗口的”宽度” 和 两个窗口开始的时间 “距离”, 通常来说, 滑动的距离要小于窗口的长度, 滑动窗口可以提供窗口时间内(宽度决定)的数据视图, 并以某种频率进行更新(滑动距离决定)

在 Flink 中, 如果你减小滑动周期, 吞吐量将会急剧下降. 但是 Arroyo 能够在较小的滑动周期中保持几乎恒定的吞吐量, 并且能够不断的增加窗口.

Arroyo 是怎么处理短周期的滑动呢

我们的滑动窗口算法被设计成即使在窗口宽度远大于滑动周期的情况下也能有效工作。这是通过将每个键的数据存储在一个结构中来完成的，该结构允许随着时间的推移进行增量修改。例如，如果要计算在一个滑动窗口中具有给定 auction_id 的出价数量，SQL 语句可能像这样:

SELECT auction_id,
    hop(interval '2 seconds', interval '2 minutes') as window,
    count(*) as bids
  FROM bids
  GROUP BY 1,2

Arroyo 使用一个叫做 WindowState 的数据类型来高效计算连续的滑动窗口. 在收到一条记录时，window_state.add_event_to_bin(bin_time) 被调用并记录相关的值到 bin 中, 当到了新窗口提交(emit)时 window_state.tick(next_bin) 会更新状态并返回当前窗口的计数.

struct WindowState {
    width: Duration,
    prior_window_count: i64,
    bin_counts: BTreeMap<SystemTime, i64>,
}

impl WindowState {
    fn add_event_to_bucket(&mut self, bin_start: SystemTime) {
        self.bin_counts
            .entry(bin_start)
            .and_modify(|prior_value| {
                prior_value.add(1);
            })
            .or_insert(1);
    }
    
    fn tick(&mut self, next_bin: SystemTime) -> i64 {
        let leaving_bin = next_bin - self.width;
        self.prior_window_count -= self.bin_counts
        	.remove(&leaving_bin).unwrap_or_default();
        self.prior_window_count += self.bin_counts
            .get(&next_bin)
            .map(|val| *val)
            .unwrap_or_default();
        self.prior_window_count
    }
}

这种算法在滑动周期较小时也非常高效. 尤其是只需付出非空数据桶的内存增加代价(当时间推进时，一些旧的数据桶会被移除，一些新的数据桶会被添加，从而保持滑动窗口的更新, 单位时间内创建的和销毁的对象增多).如果你的查询正在做额外的处理, 比如返回窗口内的前N个值，那么结构化的操作者重新使用前一个窗口的数据就会变得更加具有挑战性。

Flink 是怎么对滑动窗口进行处理的

Flink 的滑动窗口实现与其他 Flink Windows 实现一样. 它将计算一条记录所属的所有窗口, 并在每个窗口进行聚合. 让我们用上面的例子(width=5, slide=2)进行举例.t=4的事件属于 window1,window2和window3. Flink 将加载现有窗口(w1 和 w2)的当前计数,并进行增加. 使用 1 对新窗口 w3 进行初始化,然后将其全部写回堆栈.

这对窗口的数量较少时还不错, 但是随着窗口滑动间隔的减小, 每条记录所属的窗口数变多了.对于每个事件, 都有(窗口宽度/滑动距离)个窗口需要更新. 对于 1小时/5秒 来说, 一个事件将会隶属于720个窗口,意味着有720次更新! 一旦宽度超过滑动距离的 10 倍, 这种低效将会显现, 从而使计算成本增加.

为什么 Flink 没有进行修复

自2016年以来，Flink社区就知道滑动窗口可以做得更有效率。关于更高效的滑动窗口的详细建议可以在 FLINK-7001 以及链接的 论文 和设计文档中找到。Arroyo 的算法利用类似的见解和构造来实现不受小滑动或大窗口影响的性能。尽管如此，还是没有取得任何进展。这其中有几个原因：

过于通用的窗口 API

Flink的Java APIs允许用户指定窗口的细粒度行为，包括触发器、驱逐者和聚合器。它还将每个未来的窗口实体化，并为其安排一个触发器。这对大多数窗口化策略来说是没有问题的，因为它们往往每个事件只有一个窗口。然而，这意味着它没有利用滑动窗口的特殊语义。

针对开发者API的SQL

Flink SQL是针对程序员在Java中创建Flink管道时使用的相同公共API实现的。然而，Java开发人员可以直接访问Flink的底层基元，以精确控制其管道的性能和行为。因此，内部架构成为公共API的一部分，使得根本的改变几乎不可能。有了Arroyo，公共接口是简单的SQL，使我们可以自由地进行快速的改变，以提高性能而不影响用户。

开源的惯性

随着大型开源项目的成熟，它们也倾向于强化其初始实现和用户群。 任何重大的 API 更改或性能下降都将面临难以置信的高门槛。 多年来，Flink 也一直缺乏强大的企业赞助商，这使得对架构的大幅改变难以置信地难以执行。

SQL-First实时处理

我学会了如何编码编写和优化Hadoop Map-Reduce作业，并且多年来一直在教授给每个新工程师的教程。然而，随着时间的推移，对工程师进行这种困难的技术培训的意义越来越小。数据框架和基于SQL的查询引擎现在在数据处理中占主导地位。它们将广泛采用的声明式API与强大的后端配对。Arroyo提供了一个专门为实时SQL优化的执行系统，用户只需担心业务逻辑，而我们则确保其效率最大化。